# Algorithmic stability and hypothesis complexity

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2017.

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

- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [Estimating Instance-dependent Bayes-label Transition Matrix using a Deep Neural Network](https://mlsanity.com/paper/2105.13001/) (2021)
- [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)
- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (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)
- [Can DPO Learn Diverse Human Values? A Theoretical Scaling Law](https://mlsanity.com/paper/2408.03459/) (2024)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [On the Algorithmic Stability and Generalization of Adaptive Optimization Methods](https://mlsanity.com/paper/2211.03970/) (2022)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [A Unified Framework for Generative Data Augmentation: A Comprehensive Survey](https://mlsanity.com/paper/2310.00277/) (2023)
- [On Uncertainty Quantification for Near-Bayes Optimal Algorithms](https://mlsanity.com/paper/2403.19381/) (2024)
- [Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2604.04090/) (2026)
- [Towards Sharper Utility Bounds for Differentially Private Pairwise Learning](https://mlsanity.com/paper/2105.03033/) (2021)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [On the Stability and Generalization of Triplet Learning](https://mlsanity.com/paper/2302.09815/) (2023)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Super-model ecosystem: A domain-adaptation perspective](https://mlsanity.com/paper/2208.14092/) (2022)
- [On Stability and Generalization of Bilevel Optimization Problem](https://mlsanity.com/paper/2210.01063/) (2022)
- [Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning](https://mlsanity.com/paper/2302.09967/) (2023)
- [Generalization error bounds for iterative learning algorithms with bounded updates](https://mlsanity.com/paper/2309.05077/) (2023)
- [On Sensitivity of Learning with Limited Labelled Data to the Effects of Randomness: Impact of Interactions and Systematic Choices](https://mlsanity.com/paper/2402.12817/) (2024)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)

## Abstract (arXiv)

We introduce a notion of algorithmic stability of learning algorithms---that we term argument stability---that captures stability of the hypothesis output by the learning algorithm in the normed space of functions from which hypotheses are selected. The main result of the paper bounds the generalization error of any learning algorithm in terms of its argument stability. The bounds are based on martingale inequalities in the Banach space to which the hypotheses belong. We apply the general bounds to bound the performance of some learning algorithms based on empirical risk minimization and stochastic gradient descent.