Metrical Task Systems with Online Machine Learned Advice
This work addresses improving online algorithm performance in dynamic systems for theoretical computer science, but it is incremental as it applies an existing predictor-augmentation idea to a specific problem.
The paper tackles the Online Metrical Task System problem by augmenting online algorithms with machine-learned predictors, resulting in a competitive algorithm with a bound of Θ(min(√η₀, log n)) for uniform task systems, where η₀ is the predictor's error, and provides a lower bound of Θ(log η₀).
Machine learning algorithms are designed to make accurate predictions of the future based on existing data, while online algorithms seek to bound some performance measure (typically the competitive ratio) without knowledge of the future. Lykouris and Vassilvitskii demonstrated that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. In this work we apply this idea to the Online Metrical Task System problem, which was put forth by Borodin, Linial, and Saks as a general model for dynamic systems processing tasks in an online fashion. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(\log n)$ competitive. By giving an online algorithms access to a machine learned oracle with absolute predictive error bounded above by $η_0$, we construct a $Θ(\min(\sqrt{η_0}, \log n))$ competitive algorithm for the uniform case of the metrical task systems problem. We also give a $Θ(\log η_0)$ lower bound on the competitive ratio of any randomized algorithm.