# The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms arXiv: https://arxiv.org/abs/2411.12030 ยท HTML: https://mlsanity.com/paper/2411.12030/ ## 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 (most cited first, 30 of 32) - [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016) - [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018) - [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017) - [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018) - [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017) - [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021) - [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021) - [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019) - [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015) - [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015) - [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019) - [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015) - [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020) - [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018) - [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023) - [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019) - [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020) - [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021) - [Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2010.12664/) (2020) - [Fantastic Generalization Measures are Nowhere to be Found](https://mlsanity.com/paper/2309.13658/) (2023) - [Still no free lunches: the price to pay for tighter PAC-Bayes bounds](https://mlsanity.com/paper/1910.04460/) (2019) - [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023) - [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022) - [On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation](https://mlsanity.com/paper/2306.12380/) (2023) - [An Information-Theoretic Approach to Generalization Theory](https://mlsanity.com/paper/2408.13275/) (2024) - [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022) - [Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure](https://mlsanity.com/paper/2312.12236/) (2023) - [Equivalence of the Empirical Risk Minimization to Regularization on the Family of f-Divergences](https://mlsanity.com/paper/2402.00501/) (2024) - [Asymmetry of the Relative Entropy in the Regularization of Empirical Risk Minimization](https://mlsanity.com/paper/2410.02833/) (2024) - [Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data](https://mlsanity.com/paper/2005.05889/) (2020) ## Built on by (most cited first, 5 of 5) - [Proofs for Folklore Theorems on the Radon-Nikodym Derivative](https://mlsanity.com/paper/2501.18374/) (2025) - [Variations on the Expectation due to Changes in the Probability Measure](https://mlsanity.com/paper/2502.02887/) (2025) - [Information Science Principles of Machine Learning: A Causal Chain Meta-Framework Based on Formalized Information Mapping](https://mlsanity.com/paper/2505.13182/) (2025) - [Koopman-Based Generalization of Deep Reinforcement Learning With Application to Wireless Communications](https://mlsanity.com/paper/2503.02961/) (2025) - [Equivalence Between Nested Gibbs Measures and Log-Linear Combinations of Gibbs Measures](https://mlsanity.com/paper/2609.19988/) (2026) ## 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.