TY - CONF
T1 - Mixing Predictions for Online Metric Algorithms
AU - Antoniadis, Antonios
AU - Coester, Christian
AU - Eliáš, Marek
AU - Polak, Adam
AU - Simon, Bertrand
N1 - Conference code: 40
PY - 2023/7
Y1 - 2023/7
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 banditlike 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 banditlike 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.
KW - 2024 OA procedure
U2 - 10.5555/3618408.3618448
DO - 10.5555/3618408.3618448
M3 - Paper
SP - 969
EP - 983
T2 - 40th International Conference on Machine Learning, ICML 2023
Y2 - 23 July 2023 through 29 July 2023
ER -