Customizing ML Predictions for Online Algorithms

Part of Proceedings of the International Conference on Machine Learning 1 pre-proceedings (ICML 2020)

Bibtex »Metadata »Paper »

Bibtek download is not availble in the pre-proceeding


Authors

Keerti Anand, Rong Ge, Debmalya Panigrahi

Abstract

<p>Traditionally, online algorithms optimize the worst-case competitive ratio between the algorithm and the optimal solution. To overcome the inherent pessimism of worst-case analysis, 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 directly in ML loss functions leads to significantly better performance. We support this finding both through theoretical bounds and numerical simulations, and posit that ``learning for optimization'' is a fertile area for future research.</p>