Timezone: »

 
Poster
Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions
Anupam Gupta · Debmalya Panigrahi · Bernardo Subercaseaux · Kevin Sun

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #317
in Poster Session 6 »
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 $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, 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/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Anupam Gupta (Carnegie Mellon University)
Debmalya Panigrahi (Duke University)
Bernardo Subercaseaux (Carnegie Mellon University)
Kevin Sun (Duke University)

More from the Same Authors