mlsanityData to 14 Oct 2026

The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms

arXiv 2411.12030 ↗First posted 18 Nov 2024cs.LG cs.IT math.ITcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, the method of gaps, a technique for deriving closed-form expressions in terms of information measures for the generalization error of supervised learning algorithms, is introduced. This method relies on the notion of gaps, which characterize the variation of the expected empirical risk (when either the model or dataset is kept fixed) with respect to changes in the probability measure on the varying parameter. This distinction results in two classes of gaps: algorithm-driven gaps (fixed dataset) and data-driven gaps (fixed model). The method relies on two central observations: (i) the generalization error is the expectation of an algorithm-driven gap or a data-driven gap. In the first case, the expectation is with respect to a measure on the datasets; in the second case, it is with respect to a measure on the models. (ii) Both algorithm-driven gaps and data-driven gaps exhibit closed-form expressions in terms of relative entropies. In particular, algorithm-driven gaps involve a Gibbs probability measure on the set of models, which represents a supervised Gibbs algorithm. Alternatively, data-driven gaps involve a worst-case data-generating (WCDG) probability measure on the set of data points, which is also a Gibbs probability measure. Interestingly, such Gibbs measures, which are exogenous to the analysis of generalization, place the supervised Gibbs algorithm and the WCDG probability measure as natural references for the analysis of supervised learning algorithms. New exact expressions and all existing exact expressions for the generalization error of supervised learning algorithms can be obtained with the proposed method. Such new expressions are intended as structural and conceptual characterizations, not computational shortcuts. Finally, these expressions unveil strong connections among generalization, hypothesis testing, information measures, and Pythagorean identities.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 32 of its 77 references that are in the map. First posted on arXiv 18 Nov 2024.

Builds on

32 of 77 references.

References · 32

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  4. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  6. 2021Deep learning: a statistical viewpointcited by 240
  7. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  8. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
  9. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  10. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  11. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  12. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
20 more
  1. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  2. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  3. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 61
  4. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  5. 2020PAC-Bayes unleashed: generalisation bounds with unbounded lossescited by 43
  6. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  7. 2020Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithmscited by 19
  8. 2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
  9. 2019Still no free lunches: the price to pay for tighter PAC-Bayes boundscited by 14
  10. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 12
  11. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  12. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  13. 2024An Information-Theoretic Approach to Generalization Theorycited by 9
  14. 2022f-divergences and their applications in lossy compression and bounding generalization errorcited by 7
  15. 2023Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measurecited by 7
  16. 2024Equivalence of the Empirical Risk Minimization to Regularization on the Family of f-Divergencescited by 6
  17. 2024Asymmetry of the Relative Entropy in the Regularization of Empirical Risk Minimizationcited by 6
  18. 2020Upper Bounds on the Generalization Error of Private Algorithms for Discrete Datacited by 5
  19. 2023Analysis of the Relative Entropy Asymmetry in the Regularization of Empirical Risk Minimizationcited by 5
  20. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025Proofs for Folklore Theorems on the Radon-Nikodym Derivativecited by 4
  2. 2025Variations on the Expectation due to Changes in the Probability Measurecited by 3
  3. 2025Information Science Principles of Machine Learning: A Causal Chain Meta-Framework Based on Formalized Information Mappingcited by 2
  4. 2025Koopman-Based Generalization of Deep Reinforcement Learning With Application to Wireless Communicationscited by 1
  5. 2026Equivalence Between Nested Gibbs Measures and Log-Linear Combinations of Gibbs Measurescited by 0