mlsanityData to 7 Oct 2026

Near Optimal Memory-Regret Tradeoff for Online Learning

arXiv 2303.01673 ↗First posted 3 Mar 2023cs.DS cs.AI cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

In the experts problem, on each of T days, an agent needs to follow the advice of one of n ``experts''. After each day, the loss associated with each expert's advice is revealed. A fundamental result in learning theory says that the agent can achieve vanishing regret, i.e. their cumulative loss is within o(T) of the cumulative loss of the best-in-hindsight expert. Can the agent perform well without sufficient space to remember all the experts? We extend a nascent line of research on this question in two directions: bullet We give a new algorithm against the oblivious adversary, improving over the memory-regret tradeoff obtained by [PZ23], and nearly matching the lower bound of [SWXZ22]. bullet We also consider an adaptive adversary who can observe past experts chosen by the agent. In this setting we give both a new algorithm and a novel lower bound, proving that roughly √n memory is both necessary and sufficient for obtaining o(T) regret.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 36 of its 67 references that are in the map. First posted on arXiv 3 Mar 2023.

Builds on

36 of 67 references.

References · 36

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  3. 2013Non-stationary Stochastic Optimizationcited by 173
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 102
  6. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  7. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  8. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  9. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 47
  10. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  11. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  12. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
24 more
  1. 2015The Computational Power of Optimization in Online Learningcited by 38
  2. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  3. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
  4. 2019Improved Path-length Regret Bounds for Banditscited by 22
  5. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  6. 2017Stochastic Multi-armed Bandits in Constant Spacecited by 21
  7. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  8. 2022Memory Bounds for the Experts Problemcited by 20
  9. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  10. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  11. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
  12. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
  13. 2022Memory Bounds for Continual Learningcited by 18
  14. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  15. 2022Online Prediction in Sub-linear Spacecited by 16
  16. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  17. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  18. 2019Private Learning Implies Online Learning: An Efficient Reductioncited by 10
  19. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 10
  20. 2020Towards a combinatorial characterization of bounded memory learningcited by 9
  21. 2021Memory-Sample Lower Bounds for Learning Parity with Noisecited by 8
  22. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  23. 2023Improved Space Bounds for Learning with Expertscited by 5
  24. 2019Polynomial Pass Lower Bounds for Graph Streaming Algorithmscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 3; 2026: 6.

15 papers.

Sort:

  1. 2023The sample complexity of multi-distribution learningcited by 12
  2. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  3. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  4. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  5. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  6. 2026TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Abilitycited by 3
  7. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 2
  8. 2026On Language Generation in the Limit with Bounded Memorycited by 2
  9. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  10. 2025Communication Bounds for the Distributed Experts Problemcited by 1
  11. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  12. 2026Lookahead identification in adversarial bandits: accuracy and memory boundscited by 0
3 more
  1. 2026Better Bounds for the Distributed Experts Problemcited by 0
  2. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0
  3. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0