Timezone: »

 
Poster
Learning Predictions for Algorithms with Predictions
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar · Sergei Vassilvitskii

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #324
in Poster Session 2 »

A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in which algorithms can 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, tune robustness-consistency trade-offs, and bound the sample complexity. We demonstrate the effectiveness of our approach by applying it to bipartite matching, ski-rental, page migration, and job scheduling. In several settings we improve upon multiple existing results while utilizing a much simpler analysis, while in the others we provide the first learning-theoretic guarantees.

Keywords: Online Learning · Combinatorial Optimization · Meta-Learning · learning-augmented algorithms · algorithms with predictions
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Misha Khodak (CMU)
Maria-Florina Balcan (Carnegie Mellon University)
Ameet Talwalkar (CMU)
Sergei Vassilvitskii (Google)

More from the Same Authors