# Algorithms with Prediction Portfolios

arXiv: https://arxiv.org/abs/2210.12438 · HTML: https://mlsanity.com/paper/2210.12438/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 22 Oct 2022.

## Builds on (most cited first, 23 of 23)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [(Learned) Frequency Estimation Algorithms under Zipfian Distribution](https://mlsanity.com/paper/1908.05198/) (2019)
- [Improved Price of Anarchy via Predictions](https://mlsanity.com/paper/2205.04252/) (2022)
- [Generalization in portfolio-based algorithm selection](https://mlsanity.com/paper/2012.13315/) (2020)

## Built on by (most cited first, 19 of 19)

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Contract Scheduling with Distributional and Multiple Advice](https://mlsanity.com/paper/2404.12485/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Online Covering with Multiple Experts](https://mlsanity.com/paper/2312.14564/) (2023)
- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Prediction-Augmented Trees for Reliable Statistical Inference](https://mlsanity.com/paper/2510.16937/) (2025)
- [Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization](https://mlsanity.com/paper/2511.19573/) (2025)
- [Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts](https://mlsanity.com/paper/2605.09382/) (2026)
- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

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 best predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is the 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.