TY - GEN
T1 - Augmenting Online Algorithms with ε-Accurate Predictions
AU - Gupta, Anupam
AU - Panigrahi, Debmalya
AU - Subercaseaux, Bernardo
AU - Sun, Kevin
N1 - Publisher Copyright:
© 2022 Neural information processing systems foundation. All rights reserved.
PY - 2022
Y1 - 2022
N2 - A growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are ε-accurate: namely, each prediction is correct with probability (at least) ε, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an O(log(1/ε))-competitive algorithm for caching, and a simple O(1/ε)-competitive algorithm for a large family of covering problems, including set cover, network design, and facility location, with ε-accurate predictions.
AB - A growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are ε-accurate: namely, each prediction is correct with probability (at least) ε, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an O(log(1/ε))-competitive algorithm for caching, and a simple O(1/ε)-competitive algorithm for a large family of covering problems, including set cover, network design, and facility location, with ε-accurate predictions.
UR - http://www.scopus.com/inward/record.url?scp=85163175651&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85163175651&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85163175651
T3 - Advances in Neural Information Processing Systems
BT - Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
A2 - Koyejo, S.
A2 - Mohamed, S.
A2 - Agarwal, A.
A2 - Belgrave, D.
A2 - Cho, K.
A2 - Oh, A.
PB - Neural information processing systems foundation
T2 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
Y2 - 28 November 2022 through 9 December 2022
ER -