mlsanityData to 14 Oct 2026

Online-to-PAC Conversions: Generalization Bounds via Regret Analysis

arXiv 2305.19674 ↗First posted 31 May 2023stat.ML cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We present a new framework for deriving bounds on the generalization bound of statistical learning algorithms from the perspective of online learning. Specifically, we construct an online learning game called the "generalization game", where an online learner is trying to compete with a fixed statistical learning algorithm in predicting the sequence of generalization gaps on a training set of i.i.d. data points. We establish a connection between the online and statistical learning setting by showing that the existence of an online learning algorithm with bounded regret in this game implies a bound on the generalization error of the statistical learning algorithm, up to a martingale concentration term that is independent of the complexity of the statistical learning method. This technique allows us to recover several standard generalization bounds including a range of PAC-Bayesian and information-theoretic guarantees, as well as generalizations thereof.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 34 of its 88 references that are in the map. First posted on arXiv 31 May 2023.

Builds on

34 of 88 references.

References · 34

  1. 2017Exploring Generalization in Deep Learningcited by 600
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  4. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  6. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  7. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  8. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
  9. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  10. 2020Estimating means of bounded random variables by bettingcited by 169
  11. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  12. 2016Coin Betting and Parameter-Free Online Learningcited by 133
22 more
  1. 2014A Second-order Bound with Excess Lossescited by 95
  2. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  3. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  4. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 49
  5. 2015Fast rates in statistical and online learningcited by 47
  6. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 46
  7. 2013A PAC-Bayesian Tutorial with A Dropout Boundcited by 43
  8. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  9. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  10. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 43
  11. 2019PAC-Bayes Un-Expected Bernstein Inequalitycited by 36
  12. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  13. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  14. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 30
  15. 2015On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalitiescited by 27
  16. 2022Generalization Bounds via Convex Analysiscited by 27
  17. 2020A Limitation of the PAC-Bayes Frameworkcited by 25
  18. 2015Adaptive Online Learningcited by 23
  19. 2020Non-exponentially weighted aggregation: regret bounds for unbounded loss functionscited by 18
  20. 2018Online Learning: Sufficient Statistics and the Burkholder Methodcited by 14
  21. 2018An Optimal Transport View on Generalizationcited by 5
  22. 2017ZigZag: A new approach to adaptive online learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 7; 2025: 2; 2026: 2.

14 papers.

Sort:

  1. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  2. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  3. 2025Confidence Sequences for Generalized Linear Models via Regret Analysiscited by 10
  4. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 9
  5. 2023Comparing Comparators in Generalization Boundscited by 5
  6. 2024Better-than-KL PAC-Bayes Boundscited by 4
  7. 2024Generalization and Robustness of the Tilted Empirical Riskcited by 4
  8. 2024Generalization Bounds via Conditional f-Informationcited by 4
  9. 2023Local Risk Bounds for Statistical Aggregationcited by 3
  10. 2024Online-to-PAC generalization bounds under graph-mixing dependenciescited by 2
  11. 2024Preparing for Black Swans: The Antifragility Imperative for Machine Learningcited by 1
  12. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
2 more
  1. 2026Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Lossescited by 1
  2. 2025Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spacescited by 0