mlsanityData to 7 Oct 2026

Online Prediction in Sub-linear Space

arXiv 2207.07974 ↗First posted 16 Jul 2022cs.DS cs.LGcited by 16

Not on the map. Why?

Abstract (arXiv)

We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret o(T) algorithm to T1-α regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 37 of its 70 references that are in the map. First posted on arXiv 16 Jul 2022.

Builds on

37 of 70 references.

References · 37

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Introduction to Multi-Armed Banditscited by 475
  3. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  4. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  5. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  6. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  7. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  8. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  9. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  10. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  11. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  12. 2015The Computational Power of Optimization in Online Learningcited by 38
25 more
  1. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  2. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
  3. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  4. 2015Adaptive Online Learningcited by 23
  5. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  6. 2017Stochastic Multi-armed Bandits in Constant Spacecited by 21
  7. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  8. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  9. 2022Memory Bounds for the Experts Problemcited by 20
  10. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  11. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  12. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
  13. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
  14. 2022Memory Bounds for Continual Learningcited by 18
  15. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  16. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  17. 2019Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memorycited by 13
  18. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  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. 2019Estimating Entropy of Distributions in Constant Spacecited by 7
  23. 2019Rounding Dynamic Matchings Against an Adaptive Adversarycited by 6
  24. 2022The White-Box Adversarial Data Stream Modelcited by 3
  25. 2022Estimation of Entropy in Constant Space with Improved Sample Complexitycited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

16 papers.

Sort:

  1. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  2. 2023The sample complexity of multi-distribution learningcited by 12
  3. 2023Tight Regret Bounds for Single-pass Streaming Multi-armed Banditscited by 9
  4. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  5. 2023Improved Space Bounds for Learning with Expertscited by 5
  6. 2023The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Banditscited by 5
  7. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4
  8. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  9. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  10. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  11. 2024Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problemscited by 1
  12. 2025Communication Bounds for the Distributed Experts Problemcited by 1
4 more
  1. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  2. 2026Lookahead identification in adversarial bandits: accuracy and memory boundscited by 0
  3. 2026Better Bounds for the Distributed Experts Problemcited by 0
  4. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0