Online Algorithms with Learned Predictions

Abstract

<p>Optimization under uncertainty is a classic theme in the fields of algorithm design and machine learning. The traditional design of online algorithms have however proved to be insufficient for practical instances, since it only tries to optimize for the worst-case (but possibly highly unlikely) future scenarios. The availability of data and the advent of powerful machine learning paradigms has led to a promising approach of leveraging predictions about the future to aid in making decisions under uncertainty. This motivates us to explore whether algorithm design can go beyond the worst-case, i.e is it possible to design efficient algorithms that perform well for the typical instances, while retaining a suitable robustness guarantee for the worst-case instance? This entails our vision of combining the power of Machine Learning and Algorithm design to get the best of both worlds. This can be categorized into two inter-dependent parts : (1) How to design the prediction pipeline to generate forecasts about the future unknowns and (2) Given such predictions, how to re-design the decision-making algorithm to best leverage them. In this thesis, we investigate both of these questions, and summarise the key contributions as follows:</p><p>Rent or Buy Problem: We investigate the rent-or-buy problem and design a simple online algorithm that leverages predictions from classification black-box model whose performance is directly dependent on the prediction error of the classification task. We then demonstrate that by incorporating the optimization benchmarks in prediction model leads to significantly better performance, while maintaining a worst-case adversarial result.</p><p>Online Search: We define a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We then model the task of making predictions as a regression problem and show nearly tight bounds on the sample complexity of this regression problem.</p><p>Online Algorithms with Multiple Predictions: We study the setting of online covering problems that are supplemented with multiple predictions. We give algorithmic techniques that obtain a solution that is competitive against the performance of the best predictor. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, andonline facility location in the multiple predictions setting. </p>