# Online Classification with Predictions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 22 May 2024.

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

- [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)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Uniform Bounds for Scheduling with Job Size Estimates](https://mlsanity.com/paper/2110.00633/) (2021)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)

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

- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Adversarial Online Classification with a Preview](https://mlsanity.com/paper/2608.29503/) (2026)
- [Augmented Hypothesis Testing with Persona-Based LLM Simulations](https://mlsanity.com/paper/2609.24629/) (2026)

## Abstract (arXiv)

We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.