# Learning-Augmented Algorithms with Explicit Predictors

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 12 Mar 2024.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Generalization in portfolio-based algorithm selection](https://mlsanity.com/paper/2012.13315/) (2020)
- [Online Paging with a Vanishing Regret](https://mlsanity.com/paper/2011.09439/) (2020)
- [On the Configuration-LP of the Restricted Assignment Problem](https://mlsanity.com/paper/1611.01934/) (2016)

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

- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Online Algorithms with Unreliable Guidance](https://mlsanity.com/paper/2602.20706/) (2026)
- [Resilient Byzantine Agreement with Predictions](https://mlsanity.com/paper/2605.19452/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Learning Augmented Exact Exponential Algorithms](https://mlsanity.com/paper/2606.18807/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper we focus on online problems; prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box (to get the predictions it was trained for). In contrast, in this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor to learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we focus on a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems we consider, we introduce new algorithms that take advantage of explicit learning algorithms which we carefully design towards optimizing the overall performance. We demonstrate the potential of our approach by deriving performance bounds which improve over those established in previous work.