Online Algorithms with Multiple Predictions

Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:582-598, 2022.

Abstract

This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-anand22a, title = {Online Algorithms with Multiple Predictions}, author = {Anand, Keerti and Ge, Rong and Kumar, Amit and Panigrahi, Debmalya}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {582--598}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/anand22a/anand22a.pdf}, url = {https://proceedings.mlr.press/v162/anand22a.html}, abstract = {This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.} }
Endnote
%0 Conference Paper %T Online Algorithms with Multiple Predictions %A Keerti Anand %A Rong Ge %A Amit Kumar %A Debmalya Panigrahi %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-anand22a %I PMLR %P 582--598 %U https://proceedings.mlr.press/v162/anand22a.html %V 162 %X This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.
APA
Anand, K., Ge, R., Kumar, A. & Panigrahi, D.. (2022). Online Algorithms with Multiple Predictions. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:582-598 Available from https://proceedings.mlr.press/v162/anand22a.html.

Related Material