Online Dynamic Algorithm Portfolios
Staff - Faculty of Informatics
Start date: 24 March 2010
End date: 25 March 2010
On Wednesday March 24th, 2010 at 14h00 in the “Red Building” (room A33), Mr. Matteo GAGLIOLO will defend his Ph.D. dissertation titled:
“Online Dynamic Algorithm Portfolios”
The dissertation committee is composed of:
- Prof. Dr. Jürgen Schmidhuber, IDSIA/Università della Svizzera italiana, Lugano, Switzerland (research advisor)
- Prof. Dr. Matthias Hauswirth, Università della Svizzera italiana, Lugano, Switzerland (internal member)
- Prof. Dr. Fernando Pedone, Università della Svizzera italiana, Lugano, Switzerland (internal member)
- Dr. Mauro Birattari, IRIDIA - Université Libre de Bruxelles, Bruxelles, Belgium (external member)
- Prof. Dr. Carla Gomes, Cornell University, Ithaca, USA (external member)
- Dr. Faustino Gomez, IDSIA, Manno, Switzerland (external member)
ABSTRACT:
This thesis presents a method for minimizing the computational effort of problem solving. Rather than looking at a particular algorithm, we consider the issue at a higher level, and propose techniques that, given a set of candidate algorithms, of unknown performance, learn to use these algorithms while solving a sequence of problem instances, with the aim of solving all instances in a minimum time.
Analogous meta-level approaches to problem solving have been adopted in many different fields, with different aims and different terminology. A widely accepted term to describe it is algorithm selection. Algorithm portfolios represent a more general framework, in which computation time is allocated to a set of algorithms running on one or more processors.
Automating algorithm selection is an old dream of the AI community, which has been brought closer to reality in the last decade.
Most available selection techniques are based on a model of algorithm performance, learned in a separate offline training sequence, which is often prohibitively expensive; and used to perform a static allocation of resources, with no feedback from the actual execution of the algorithms.
There is a trade-off between the performance of model-based selection, and the cost of learning the model. In this thesis, we solve this trade-off as a bandit problem.
We propose a fully dynamic and online algorithm portfolio selection technique, with no separate training phase: all candidate algorithms are run in parallel, while a model incrementally learns their runtime distributions.
A redundant set of time allocators uses the partially trained model to optimize machine time shares for the algorithms, in order to minimize runtime.
A bandit problem solver picks the allocator to use on each instance, gradually increasing the impact of the best time allocators as the model improves.
