mlsanityData to 14 Oct 2026

Improved Space Bounds for Learning with Experts

arXiv 2303.01453 ↗First posted 2 Mar 2023cs.DS cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We give improved tradeoffs between space and regret for the online learning with expert advice problem over T days with n experts. Given a space budget of nδ for δ ∈ (0,1), we provide an algorithm achieving regret tildeO(n2 T1/(1+δ)), improving upon the regret bound tildeO(n2 T2/(2+δ)) in the recent work of [PZ23]. The improvement is particularly salient in the regime δ rightarrow 1 where the regret of our algorithm approaches tildeOn(√T), matching the T dependence in the standard online setting without space restrictions.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 16 of its 37 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

16 of 37 references.

References · 16

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  3. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  4. 2013Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimationcited by 24
  5. 2017Stochastic Multi-armed Bandits in Constant Spacecited by 22
  6. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  7. 2013Memory Limited, Streaming PCAcited by 21
  8. 2022Memory Bounds for the Experts Problemcited by 20
  9. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  10. 2020Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Banditscited by 18
  11. 2022Online Prediction in Sub-linear Spacecited by 16
  12. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
4 more
  1. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  2. 2019Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memorycited by 13
  3. 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8
  4. 2022Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 1; 2026: 1.

5 papers.

  1. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  2. 2023The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Banditscited by 5
  3. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  4. 2025Communication Bounds for the Distributed Experts Problemcited by 1
  5. 2026Better Bounds for the Distributed Experts Problemcited by 0