# Generalization Error Bounds for Noisy, Iterative Algorithms

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

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jan 2018.

## Built on by (most cited first, 30 of 82)

- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review](https://mlsanity.com/paper/2304.09355/) (2023)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2109.14595/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [PAC-Bayes Information Bottleneck](https://mlsanity.com/paper/2109.14509/) (2021)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Models](https://mlsanity.com/paper/2407.08039/) (2024)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [RATT: Leveraging Unlabeled Data to Guarantee Generalization](https://mlsanity.com/paper/2105.00303/) (2021)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Information-Theoretic Analysis of Unsupervised Domain Adaptation](https://mlsanity.com/paper/2210.00706/) (2022)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning](https://mlsanity.com/paper/2110.00926/) (2021)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal States](https://mlsanity.com/paper/2211.10691/) (2022)
- [Information-Theoretic Generalization Bounds for Deep Neural Networks](https://mlsanity.com/paper/2404.03176/) (2024)
- [Generalisation under gradient descent via deterministic PAC-Bayes](https://mlsanity.com/paper/2209.02525/) (2022)
- [Generalization and Informativeness of Conformal Prediction](https://mlsanity.com/paper/2401.11810/) (2024)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning](https://mlsanity.com/paper/2202.02423/) (2022)
- [On Leave-One-Out Conditional Mutual Information For Generalization](https://mlsanity.com/paper/2207.00581/) (2022)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)

## Abstract (arXiv)

In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bound on the generalization error of empirical risk minimization based on the mutual information I(S;W) between the algorithm input S and the algorithm output W, when the loss function is sub-Gaussian. We leverage these results to derive generalization error bounds for a broad class of iterative algorithms that are characterized by bounded, noisy updates with Markovian structure. Our bounds are very general and are applicable to numerous settings of interest, including stochastic gradient Langevin dynamics (SGLD) and variants of the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm. Furthermore, our error bounds hold for any output function computed over the path of iterates, including the last iterate of the algorithm or the average of subsets of iterates, and also allow for non-uniform sampling of data in successive updates of the algorithm.