Customizing ML Predictions for Online Algorithms

Keerti Anand, Rong Ge, Debmalya Panigrahi
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:303-313, 2020.

Abstract

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-anand20a, title = {Customizing {ML} Predictions for Online Algorithms}, author = {Anand, Keerti and Ge, Rong and Panigrahi, Debmalya}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {303--313}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/anand20a/anand20a.pdf}, url = {https://proceedings.mlr.press/v119/anand20a.html}, abstract = {A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.} }
Endnote
%0 Conference Paper %T Customizing ML Predictions for Online Algorithms %A Keerti Anand %A Rong Ge %A Debmalya Panigrahi %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-anand20a %I PMLR %P 303--313 %U https://proceedings.mlr.press/v119/anand20a.html %V 119 %X A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.
APA
Anand, K., Ge, R. & Panigrahi, D.. (2020). Customizing ML Predictions for Online Algorithms. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:303-313 Available from https://proceedings.mlr.press/v119/anand20a.html.

Related Material