Learning Predictions for Algorithms with Predictions
  A burgeoning paradigm in algorithm design is the field of algorithms with
predictions, in which algorithms are designed to take advantage of a
possibly-imperfect prediction of some aspect of the problem. While much work
has focused on using predictions to improve competitive ratios, running times,
or other performance measures, less effort has been devoted to the question of
how to obtain the predictions themselves, especially in the critical online
setting. We introduce a general design approach for algorithms that learn
predictors: (1) identify a functional dependence of the performance measure on
the prediction quality, and (2) apply techniques from online learning to learn
predictors against adversarial instances, tune robustness-consistency
trade-offs, and obtain new statistical guarantees. We demonstrate the
effectiveness of our approach at deriving learning algorithms by analyzing
methods for bipartite matching, page migration, ski-rental, and job scheduling.
In the first and last settings we improve upon existing learning-theoretic
results by deriving online results, obtaining better or more general
statistical guarantees, and utilizing a much simpler analysis, while in the
second and fourth we provide the first learning-theoretic guarantees.
