mlsanityData to 7 Oct 2026

Streaming Algorithms for Learning with Experts: Deterministic Versus Robust

arXiv 2303.01709 ↗First posted 3 Mar 2023cs.DS cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of T days (or times), given a set of n experts who make predictions on each day (or time). The algorithm is given feedback on the outcomes of each day, including the cost of its prediction and the cost of the expert predictions, and the goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. Recent work by Srinivas, Woodruff, Xu, and Zhou (STOC 2022) introduced the study of the online learning with experts problem under memory constraints. However, often the predictions made by experts or algorithms at some time influence future outcomes, so that the input is adaptively chosen. Whereas deterministic algorithms would be robust to adaptive inputs, existing algorithms all crucially use randomization to sample a small number of experts. In this paper, we study deterministic and robust algorithms for the experts problem. We first show a space lower bound of widetildeOmegaleft(fracnMRTright) for any deterministic algorithm that achieves regret R when the best expert makes M mistakes. Our result shows that the natural deterministic algorithm, which iterates through pools of experts until each expert in the pool has erred, is optimal up to polylogarithmic factors. On the positive side, we give a randomized algorithm that is robust to adaptive inputs that uses widetildeOleft(fracnR√Tright) space for M=Oleft(fracR2 Tlog2 nright), thereby showing a smooth space-regret trade-off.

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

Builds on

28 of 60 references.

References · 28

  1. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  2. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  3. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  4. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  5. 2013Bandits with Switching Costs: T^{2/3} Regretcited by 38
  6. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  7. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  8. 2022Memory Bounds for the Experts Problemcited by 20
  9. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  10. 2019Bandits with Feedback Graphs and Switching Costscited by 17
  11. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  12. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
16 more
  1. 2022Online Prediction in Sub-linear Spacecited by 16
  2. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  3. 2020On Adaptive Distance Estimationcited by 10
  4. 2019Adversarially Robust Submodular Maximization under Knapsack Constraintscited by 9
  5. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  6. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  7. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  8. 2016Tight Lower Bounds for Multiplicative Weights Algorithmic Familiescited by 8
  9. 2021Adversarially Robust Streaming via Dense--Sparse Trade-offscited by 7
  10. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  11. 2019Rounding Dynamic Matchings Against an Adaptive Adversarycited by 6
  12. 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
  13. 2021A Simple Proof of a New Set Disjointness with Applications to Data Streamscited by 4
  14. 2021Adversarially Robust Coloring for Graph Streamscited by 3
  15. 2022The White-Box Adversarial Data Stream Modelcited by 3
  16. 2022Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithmscited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  2. 2024Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Banditscited by 4
  3. 2025Communication Bounds for the Distributed Experts Problemcited by 1