Carl Burch

Machine learning in metrical task systems and other on-line problems Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum
Graduated: May 2000

Abstract:

We establish and explore a new connection between two general on-line scenarios deriving from two historically disjoint communities. Though the problems are inherently similar, the techniques and questions developed for these two scenarios are very different. From competitive analysis comes the problem of metrical task systems, where the algorithm is to decide in which state to process each of several sequential tasks, where each task specifies the processing cost in each state, and the algorithm must pay according to a metric to move between states. And from machine learning comes the problem of predicting from expert advice -- that is, of choosing one of several experts for each query in a sequence without doing much worse than the best expert overall.

The dissertation includes four results touching on this connection. We begin with the first metrical task system algorithm that can guarantee for every task sequence that the ratio of its expected cost to the cheapest way to process the sequence is only polylogarithmic in the number of states. Then we see how we can use expert-advice results to combine on-line algorithms on-line if there is a fixed cost for changing between the on-line algorithms. The third result establishes new expert-advice algorithms deriving from metrical task system research; in addition to establishing theoretical bounds, we compare the algorithms empirically on a process migration scenario. Finally, we investigate a modified version of paging, where we want to do well against an adversary who is allowed to ignore a paging request cheaply.

Thesis Committee:
Avrim Blum (Chair)
Allan Borodin
Bruce Maggs
Daniel Sleator

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Competitive ratio, metrical task systems, machine learning theory, on-line algorithms