mlsanityData to 14 Oct 2026

Online Classification with Predictions

arXiv 2405.14066 ↗First posted 22 May 2024cs.LG cs.DS stat.MLcited by 5

Not on the map. Why?

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.

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

19 of 41 references.

References · 19

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 153
  4. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  5. 2020Online metric algorithms with untrusted predictionscited by 75
  6. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  7. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  8. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 52
  9. 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
  10. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  11. 2022Learning Augmented Binary Search Treescited by 31
  12. 2021Learning-Augmented k-means Clusteringcited by 26
7 more
  1. 2023Multiclass Online Learning and Uniform Convergencecited by 19
  2. 2021Online Facility Location with Predictionscited by 14
  3. 2023A Trichotomy for Transductive Online Learningcited by 14
  4. 2021Uniform Bounds for Scheduling with Job Size Estimatescited by 12
  5. 2023Online Learning in Dynamically Changing Environmentscited by 8
  6. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  7. 2024The Complexity of Sequential Prediction in Dynamical Systemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Online Learning in the Random Order Modelcited by 2
  2. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  3. 2026The Secretary Problem with a Stochastic Precursorcited by 0
  4. 2026Adversarial Online Classification with a Previewcited by 0
  5. 2026Augmented Hypothesis Testing with Persona-Based LLM Simulationscited by 0