mlsanityData to 7 Oct 2026

Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

arXiv 2101.09054 ↗First posted 22 Jan 2021cs.LG cs.CR cs.DScited by 39

Not on the map. Why?

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

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

Builds on

10 of 56 references.

References · 10

  1. 2018DARTS: Deceiving Autonomous Cars with Toxic Signscited by 53
  2. 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
  3. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  4. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  5. 2019The Adversarial Robustness of Samplingcited by 18
  6. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
  7. 2020On Adaptive Distance Estimationcited by 10
  8. 2018Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositionscited by 8
  9. 2014Bloom Filters in Adversarial Environmentscited by 3
  10. 2018The Everlasting Database: Statistical Validity at a Fair Pricecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 5; 2023: 10; 2024: 3; 2025: 5; 2026: 5.

39 papers.

Sort:

  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  2. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  3. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  4. 2021Realizable Learning is All You Needcited by 25
  5. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  6. 2021Understanding the Eluder Dimensioncited by 19
  7. 2023Multiclass Online Learning and Uniform Convergencecited by 19
  8. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  9. 2023Optimal Prediction Using Expert Advice and Randomized Littlestone Dimensioncited by 18
  10. 2021Majorizing Measures, Sequential Complexities, and Online Learningcited by 17
  11. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  12. 2022Online Prediction in Sub-linear Spacecited by 16
27 more
  1. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  2. 2023A Trichotomy for Transductive Online Learningcited by 13
  3. 2021On the power of adaptivity in statistical adversariescited by 12
  4. 2023Multiclass Online Learnability under Bandit Feedbackcited by 12
  5. 2023Online Learning and Solving Infinite Games with an ERM Oraclecited by 11
  6. 2021Online Selective Classification with Limited Feedbackcited by 8
  7. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  8. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  9. 2022The unstable formula theorem revisited via algorithmscited by 4
  10. 2023Apple Tasting: Combinatorial Dimensions and Minimax Ratescited by 4
  11. 2024The Dimension of Self-Directed Learningcited by 4
  12. 2023Quantum Learning Theory Beyond Batch Binary Classificationcited by 3
  13. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  14. 2026Learning from Equivalence Queries, Revisitedcited by 2
  15. 2026An Optimal Agnostic PAC Algorithmcited by 2
  16. 2024Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihoodcited by 1
  17. 2025Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learningcited by 1
  18. 2025Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settingscited by 1
  19. 2021Agnostic Online Learning and Excellent Setscited by 0
  20. 2023Clustering large 3D volumes: A sampling-based approachcited by 0
  21. 2023Robust Streaming, Sampling, and a Perspective on Online Learningcited by 0
  22. 2024Fast White-Box Adversarial Streaming Without a Random Oraclecited by 0
  23. 2025Discriminative Feature Feedback with General Teacher Classescited by 0
  24. 2025Minimizing Human Intervention in Online Classificationcited by 0
  25. 2026Robust Online Learningcited by 0
  26. 2026Regret-Oracle Complexity Tradeoffs in Agnostic Online Learningcited by 0
  27. 2026Agnostic Smoothed Online Regression with Adversarial Responsescited by 0