A Regression Approach to Learning-Augmented Online Algorithms
The emerging field of learning-augmented online algorithms uses ML techniques
to predict future input parameters and thereby improve the performance of
online algorithms. Since these parameters are, in general, real-valued
functions, a natural approach is to use regression techniques to make these
predictions. We introduce this approach in this paper, and explore it in the
context of a general online search framework that captures classic problems
like (generalized) ski rental, bin packing, minimum makespan scheduling, etc.
We show nearly tight bounds on the sample complexity of this regression
problem, and extend our results to the agnostic setting. From a technical
standpoint, we show that the key is to incorporate online optimization
benchmarks in the design of the loss function for the regression problem,
thereby diverging from the use of off-the-shelf regression tools with standard
bounds on statistical error.