# Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 56 references that are in the map.
- First posted on arXiv 22 Jan 2021.

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

- [DARTS: Deceiving Autonomous Cars with Toxic Signs](https://mlsanity.com/paper/1802.06430/) (2018)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [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)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions](https://mlsanity.com/paper/1805.12051/) (2018)
- [Bloom Filters in Adversarial Environments](https://mlsanity.com/paper/1412.8356/) (2014)
- [The Everlasting Database: Statistical Validity at a Fair Price](https://mlsanity.com/paper/1803.04307/) (2018)

## Built on by (most cited first, 30 of 39)

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [The unstable formula theorem revisited via algorithms](https://mlsanity.com/paper/2212.05050/) (2022)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)
- [The Dimension of Self-Directed Learning](https://mlsanity.com/paper/2402.13400/) (2024)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood](https://mlsanity.com/paper/2410.03849/) (2024)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)

## Abstract (arXiv)

Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone's dimension, thus resolving the main open question from Ben-David, P'al, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).