# Memory Bounds for the Experts Problem arXiv: https://arxiv.org/abs/2204.09837 · HTML: https://mlsanity.com/paper/2204.09837/ ## Key facts - Cited by 20 papers in the map (data through 14 Oct 2026). - Builds on 20 of its 68 references that are in the map. - First posted on arXiv 21 Apr 2022. ## Builds on (most cited first, 20 of 20) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015) - [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015) - [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016) - [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020) - [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014) - [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013) - [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015) - [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017) - [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017) - [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018) - [Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits](https://mlsanity.com/paper/2004.04666/) (2020) - [Heavy hitters via cluster-preserving clustering](https://mlsanity.com/paper/1604.01357/) (2016) - [Tight Lower Bounds for Multiplicative Weights Algorithmic Families](https://mlsanity.com/paper/1607.02834/) (2016) - [Tight Bounds for Set Disjointness in the Message Passing Model](https://mlsanity.com/paper/1305.4696/) (2013) - [Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization](https://mlsanity.com/paper/1603.00570/) (2016) - [BPTree: an ℓ2 heavy hitters algorithm using constant memory](https://mlsanity.com/paper/1603.00759/) (2016) - [Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG](https://mlsanity.com/paper/2002.07235/) (2020) - [Beating CountSketch for Heavy Hitters in Insertion Streams](https://mlsanity.com/paper/1511.00661/) (2015) - [An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems](https://mlsanity.com/paper/1603.00213/) (2016) ## Built on by (most cited first, 20 of 20) - [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022) - [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022) - [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023) - [A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits](https://mlsanity.com/paper/2205.00984/) (2022) - [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023) - [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024) - [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023) - [The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2309.03145/) (2023) - [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023) - [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023) - [Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2405.19752/) (2024) - [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023) - [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023) - [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (2026) - [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024) - [Communication Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2501.03132/) (2025) - [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025) - [Lookahead identification in adversarial bandits: accuracy and memory bounds](https://mlsanity.com/paper/2603.00803/) (2026) - [Better Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2603.09168/) (2026) - [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026) ## Abstract (arXiv) Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of n "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm. However, every application, to our knowledge, relies on storing weights for every expert, and uses Omega(n) memory. There is little work on understanding the memory required to solve the online learning with expert advice problem, or run standard sequential prediction algorithms, in natural streaming models, which is especially important when the number of experts, as well as the number of days on which the experts make predictions, is large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a reduction to a custom-built problem using a novel masking technique, to show a smooth trade-off for regret versus memory. Our upper bounds show novel ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. We hope that these results and techniques will have broad applications in online learning, and can inspire algorithms based on standard sequential prediction techniques, like multiplicative weights, for a wide range of other problems in the memory-constrained setting.