# Learning Algorithm Generalization Error Bounds via Auxiliary Distributions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 2 Oct 2022.

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

- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [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)
- [Generalized Jensen-Shannon Divergence Loss for Learning with Noisy Labels](https://mlsanity.com/paper/2105.04522/) (2021)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [Individually Conditional Individual Mutual Information Bound on Generalization Error](https://mlsanity.com/paper/2012.09922/) (2020)
- [Concentration Inequalities for Statistical Inference](https://mlsanity.com/paper/2011.02258/) (2020)
- [Information-theoretic analysis for transfer learning](https://mlsanity.com/paper/2005.08697/) (2020)
- [Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2010.12664/) (2020)
- [An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift](https://mlsanity.com/paper/2202.12123/) (2022)
- [Distribution-Dependent Analysis of Gibbs-ERM Principle](https://mlsanity.com/paper/1902.01846/) (2019)
- [Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm](https://mlsanity.com/paper/2111.01635/) (2021)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [Theoretical Guarantees of Transfer Learning](https://mlsanity.com/paper/1810.05986/) (2018)

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

- [Information-Theoretic Generalization Bounds for Deep Neural Networks](https://mlsanity.com/paper/2404.03176/) (2024)
- [How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?](https://mlsanity.com/paper/2210.08188/) (2022)
- [Subgroups Matter for Robust Bias Mitigation](https://mlsanity.com/paper/2505.21363/) (2025)
- [Bounds on the Excess Minimum Risk via Generalized Information Divergence Measures](https://mlsanity.com/paper/2505.24117/) (2025)
- [An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learning](https://mlsanity.com/paper/2510.23448/) (2025)
- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)

## Abstract (arXiv)

Generalization error bounds are essential for comprehending how well machine learning models work. In this work, we suggest a novel method, i.e., the Auxiliary Distribution Method, that leads to new upper bounds on expected generalization errors that are appropriate for supervised learning scenarios. We show that our general upper bounds can be specialized under some conditions to new bounds involving the α-Jensen-Shannon, α-R'enyi (0< α < 1) information between a random variable modeling the set of training samples and another random variable modeling the set of hypotheses. Our upper bounds based on α-Jensen-Shannon information are also finite. Additionally, we demonstrate how our auxiliary distribution method can be used to derive the upper bounds on excess risk of some learning algorithms in the supervised learning context blue and the generalization error under the distribution mismatch scenario in supervised learning algorithms, where the distribution mismatch is modeled as α-Jensen-Shannon or α-R'enyi divergence between the distribution of test and training data samples distributions. We also outline the conditions for which our proposed upper bounds might be tighter than other earlier upper bounds.