Mixing predictions for online metric algorithms

Conference item

A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of ℓ predictors, we obtain a competitive ratio of 𝑂(ℓ2), and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a (1+𝜖)-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the 𝑘-server problem.

Authors: Antoniadis, A; Coester, C; Eliáš, M; Polak, A; Simon, B

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Journal of Machine Learning Research
• Host title: Proceedings of the 40th International Conference on Machine Learning
• Pages: 969-983
• Series: PMLR
• Series number: 202
• Publication date: 2023-07-03
• Acceptance date: 2023-04-24
• Event title: 40th International Conference on Machine Learning (ICML 2023)
• Event location: Honolulu, Hawaii, USA
• Event website: https://icml.cc/
• Event start date: 2023-07-23
• Event end date: 2023-07-29
• ISSN: 2640-3498
• Language: English
• Keywords: FFR