# Toward Better Generalization Bounds with Locally Elastic Stability

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

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

- [Learning Dynamics of LLM Finetuning](https://mlsanity.com/paper/2407.10490/) (2024)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (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)
- [On the Generalization Mystery in Deep Learning](https://mlsanity.com/paper/2203.10036/) (2022)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Explaining Generalization Power of a DNN Using Interactive Concepts](https://mlsanity.com/paper/2302.13091/) (2023)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)
- [Last-Layer Fairness Fine-tuning is Simple and Effective for Neural Networks](https://mlsanity.com/paper/2304.03935/) (2023)
- [Black-box tests for algorithmic stability](https://mlsanity.com/paper/2111.15546/) (2021)
- [The Debate on RLVR Reasoning Capability Boundary: Shrinkage, Expansion, or Both? A Two-Stage Dynamic View](https://mlsanity.com/paper/2510.04028/) (2025)
- [Disparity Between Batches as a Signal for Early Stopping](https://mlsanity.com/paper/2107.06665/) (2021)
- [Reinforcement Learning with Stepwise Fairness Constraints](https://mlsanity.com/paper/2211.03994/) (2022)
- [Imitating Deep Learning Dynamics via Locally Elastic Stochastic Differential Equations](https://mlsanity.com/paper/2110.05960/) (2021)
- [Envisioning Future Deep Learning Theories: Some Basic Concepts and Characteristics](https://mlsanity.com/paper/2112.09741/) (2021)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [Beyond Reward Margin: Rethinking and Resolving Likelihood Displacement in Diffusion Models via Video Generation](https://mlsanity.com/paper/2511.19049/) (2025)
- [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)
- [Class-wise Generalization Error: an Information-Theoretic Analysis](https://mlsanity.com/paper/2401.02904/) (2024)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Revisiting Generalization Power of a DNN in Terms of Symbolic Interactions](https://mlsanity.com/paper/2502.10162/) (2025)
- [Practical Assessment of Generalization Performance Robustness for Deep Networks via Contrastive Examples](https://mlsanity.com/paper/2106.10653/) (2021)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning](https://mlsanity.com/paper/2302.09967/) (2023)

## Abstract (arXiv)

Algorithmic stability is a key characteristic to ensure the generalization ability of a learning algorithm. Among different notions of stability, uniform stability is arguably the most popular one, which yields exponential generalization bounds. However, uniform stability only considers the worst-case loss change (or so-called sensitivity) by removing a single data point, which is distribution-independent and therefore undesirable. There are many cases that the worst-case sensitivity of the loss is much larger than the average sensitivity taken over the single data point that is removed, especially in some advanced models such as random feature models or neural networks. Many previous works try to mitigate the distribution independent issue by proposing weaker notions of stability, however, they either only yield polynomial bounds or the bounds derived do not vanish as sample size goes to infinity. Given that, we propose locally elastic stability as a weaker and distribution-dependent stability notion, which still yields exponential generalization bounds. We further demonstrate that locally elastic stability implies tighter generalization bounds than those derived based on uniform stability in many situations by revisiting the examples of bounded support vector machines, regularized least square regressions, and stochastic gradient descent.