TY - UNPB
T1 - Mixing Predictions or Online Metric Algorithms
AU - Antoniadis, Antonios
AU - Coester, Christian
AU - Eliáš, Marek
AU - Polak, Adam
AU - Simon, Bertrand
PY - 2023/12/15
Y1 - 2023/12/15
N2 - 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 O(ℓ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 k-server problem.
AB - 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 O(ℓ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 k-server problem.
U2 - 10.48550/arXiv.2304.01781
DO - 10.48550/arXiv.2304.01781
M3 - Preprint
BT - Mixing Predictions or Online Metric Algorithms
PB - ArXiv.org
ER -