Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
- 3 November 2023
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 55 (4) , STOC21-154
Abstract
Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed subpopulation 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 [O. Ben-Eliezer and E. Yogev, The adversarial robustness of sampling, in Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2020, pp. 49–62] 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 [S. Ben-David, D. Pál, and S. Shalev-Shwartz, Agnostic online learning, in Proceedings of the 22nd Conference on Learning Theory (COLT), 2009], which was also posed by [A. Rakhlin, K. Sridharan, and A. Tewari, J. Mach. Learn. Res., 16 (2015), pp. 155–186].Keywords
Funding Information
- National Science Foundation (DMS-2154082)
- BSF (2018267)
- Israel Science Foundation (1225/20)
- BSF (2018385)
- Israel Science Foundation (950/15, 2686/20)
- Israel Science Foundation (2893/22)
This publication has 37 references indexed in Scilit:
- A General Class of Exponential Inequalities for Martingales and RatiosThe Annals of Probability, 1999
- Sharper Bounds for Gaussian and Empirical ProcessesThe Annals of Probability, 1994
- Discrepancy and approximations for bounded VC-dimensionCombinatorica, 1993
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985
- Central Limit Theorems for Empirical MeasuresThe Annals of Probability, 1978
- On Tail Probabilities for MartingalesThe Annals of Probability, 1975
- Sample Functions of the Gaussian ProcessThe Annals of Probability, 1973
- On the density of families of setsJournal of Combinatorial Theory, Series A, 1972
- An analog of the minimax theorem for vector payoffsPacific Journal of Mathematics, 1956