Part of Advances in Neural Information Processing Systems 35 (NeurIPS 2022) Main Conference Track
Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun
The 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 and facility location, with ϵ-accurate predictions.