# Streaming Algorithms for Learning with Experts: Deterministic Versus Robust

arXiv: https://arxiv.org/abs/2303.01709 · HTML: https://mlsanity.com/paper/2303.01709/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [Tight Lower Bounds for Multiplicative Weights Algorithmic Families](https://mlsanity.com/paper/1607.02834/) (2016)
- [Adversarially Robust Submodular Maximization under Knapsack Constraints](https://mlsanity.com/paper/1905.02367/) (2019)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Adversarially Robust Streaming via Dense--Sparse Trade-offs](https://mlsanity.com/paper/2109.03785/) (2021)
- [Rounding Dynamic Matchings Against an Adaptive Adversary](https://mlsanity.com/paper/1911.05545/) (2019)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [A Simple Proof of a New Set Disjointness with Applications to Data Streams](https://mlsanity.com/paper/2105.11338/) (2021)
- [Adversarially Robust Coloring for Graph Streams](https://mlsanity.com/paper/2109.11130/) (2021)
- [The White-Box Adversarial Data Stream Model](https://mlsanity.com/paper/2204.09136/) (2022)
- [Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms](https://mlsanity.com/paper/2212.10641/) (2022)

## Built on by (most cited first, 3 of 3)

- [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)
- [Communication Bounds for the Distributed Experts Problem](https://mlsanity.com/paper/2501.03132/) (2025)

## 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.