# Generalization Bounds for Uniformly Stable Algorithms

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2018.

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Toward Understanding Generative Data Augmentation](https://mlsanity.com/paper/2305.17476/) (2023)
- [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)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Global Convergence of Three-layer Neural Networks in the Mean Field Regime](https://mlsanity.com/paper/2105.05228/) (2021)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [Generalisation under gradient descent via deterministic PAC-Bayes](https://mlsanity.com/paper/2209.02525/) (2022)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [Differentially Private Shapley Values for Data Evaluation](https://mlsanity.com/paper/2206.00511/) (2022)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)
- [Conformal Risk Control for Non-Monotonic Losses](https://mlsanity.com/paper/2602.20151/) (2026)
- [Stability and Risk Bounds of Iterative Hard Thresholding](https://mlsanity.com/paper/2203.09413/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Towards Understanding Generalization via Decomposing Excess Risk Dynamics](https://mlsanity.com/paper/2106.06153/) (2021)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [A Unified Framework for Generative Data Augmentation: A Comprehensive Survey](https://mlsanity.com/paper/2310.00277/) (2023)
- [Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression](https://mlsanity.com/paper/2202.06054/) (2022)
- [Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithms](https://mlsanity.com/paper/2206.03834/) (2022)
- [On Generalization for Generative Flow Networks](https://mlsanity.com/paper/2407.03105/) (2024)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [Towards Auto-Regressive Next-Token Prediction: In-Context Learning Emerges from Generalization](https://mlsanity.com/paper/2502.17024/) (2025)

## Abstract (arXiv)

Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in [0,1], the generalization error of a γ-uniformly stable learning algorithm on n samples is known to be within O((γ +1/n) √n log(1/δ)) of the empirical error with probability at least 1-δ. Unfortunately, this bound does not lead to meaningful generalization bounds in many common settings where γ ≥ 1/√n. At the same time the bound is known to be tight only when γ = O(1/n). We substantially improve generalization bounds for uniformly stable algorithms without making any additional assumptions. First, we show that the bound in this setting is O(√(γ + 1/n) log(1/δ)) with probability at least 1-δ. In addition, we prove a tight bound of O(γ2 + 1/n) on the second moment of the estimation error. The best previous bound on the second moment is O(γ + 1/n). Our proofs are based on new analysis techniques and our results imply substantially stronger generalization guarantees for several well-studied algorithms.