# Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure

arXiv: https://arxiv.org/abs/2312.12236 · HTML: https://mlsanity.com/paper/2312.12236/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 13 of 13)

- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [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)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2010.12664/) (2020)
- [Generalized Maximum Entropy for Supervised Classification](https://mlsanity.com/paper/2007.05447/) (2020)
- [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)
- [f-divergences and their applications in lossy compression and bounding generalization error](https://mlsanity.com/paper/2206.11042/) (2022)
- [A unified framework for information-theoretic generalization bounds](https://mlsanity.com/paper/2305.11042/) (2023)

## Built on by (most cited first, 7 of 7)

- [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)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Variations on the Expectation due to Changes in the Probability Measure](https://mlsanity.com/paper/2502.02887/) (2025)
- [Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2601.13191/) (2026)
- [Equivalence Between Nested Gibbs Measures and Log-Linear Combinations of Gibbs Measures](https://mlsanity.com/paper/2609.19988/) (2026)
- [Machine Unlearning for Gibbs Supervised Learning Algorithms](https://mlsanity.com/paper/2609.29409/) (2026)

## Abstract (arXiv)

In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms.