Timezone: »

 
Poster
Algorithms with Prediction Portfolios
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii

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

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.

Keywords: Load Balancing · algorithms with predictions · minimum cost matching · learnability · multiple predictions · completion time scheduling
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Michael Dinitz (Johns Hopkins University)
Sungjin Im (University of California, Merced)
Thomas Lavastida (University of Texas at Dallas)
Benjamin Moseley (Carnegie Mellon University)
Sergei Vassilvitskii (Google)

More from the Same Authors