mlsanityData to 7 Oct 2026

Chained Generalisation Bounds

arXiv 2203.00977 ↗First posted 2 Mar 2022stat.ML cs.IT cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

This work discusses how to derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. By developing a general theoretical framework, we establish a duality between generalisation bounds based on the regularity of the loss function, and their chained counterparts, which can be obtained by lifting the regularity assumption from the loss onto its gradient. This allows us to re-derive the chaining mutual information bound from the literature, and to obtain novel chained information-theoretic generalisation bounds, based on the Wasserstein distance and other probability metrics. We show on some toy examples that the chained generalisation bound can be significantly tighter than its standard counterpart, particularly when the distribution of the hypotheses selected by the algorithm is very concentrated. Keywords: Generalisation bounds; Chaining; Information-theoretic bounds; Mutual information; Wasserstein distance; PAC-Bayes.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 20 of its 61 references that are in the map. First posted on arXiv 2 Mar 2022.

Builds on

20 of 61 references.

References · 20

  1. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  2. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  3. 2018To understand deep learning we need to understand kernel learningcited by 186
  4. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  5. 2015Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measurescited by 138
  6. 2019A Primer on PAC-Bayesian Learningcited by 130
  7. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  8. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  9. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  10. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  11. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  12. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
8 more
  1. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  2. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  3. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  4. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  5. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  6. 2019Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Netscited by 6
  7. 2013Sharp Inequalities for f-divergencescited by 3
  8. 2020A Toolbox for the Radial and Angular Marginalization of Bivariate Normal Distributionscited by 2

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 4; 2024: 2; 2025: 1.

10 papers.

  1. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  2. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  3. 2023Generalization Bounds with Data-dependent Fractal Dimensionscited by 15
  4. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  5. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  6. 2023A unified framework for information-theoretic generalization boundscited by 6
  7. 2022An Entropy-Based Model for Hierarchical Learningcited by 2
  8. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  9. 2025Beyond Real Data: Synthetic Data through the Lens of Regularizationcited by 2
  10. 2024Error Bounds of Supervised Classification from Information-Theoretic Perspectivecited by 0