# Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 74 references that are in the map.
- First posted on arXiv 5 Jun 2026.

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

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning](https://mlsanity.com/paper/1810.01075/) (2018)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks](https://mlsanity.com/paper/2102.03832/) (2021)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [Concentration in unbounded metric spaces and algorithmic stability](https://mlsanity.com/paper/1309.1007/) (2013)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [On Data Efficiency of Meta-learning](https://mlsanity.com/paper/2102.00127/) (2021)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Stability revisited: new generalisation bounds for the Leave-one-Out](https://mlsanity.com/paper/1608.06412/) (2016)
- [Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning](https://mlsanity.com/paper/1904.11316/) (2019)
- [Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes](https://mlsanity.com/paper/2301.06806/) (2023)
- [Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stability](https://mlsanity.com/paper/2109.11792/) (2021)
- [An Exponential Efron-Stein Inequality for Lq Stable Learning Rules](https://mlsanity.com/paper/1903.05457/) (2019)
- [Algorithmic Stability and Generalization of an Unsupervised Feature Selection Algorithm](https://mlsanity.com/paper/2010.09416/) (2020)
- [Estimation of High-dimensional Nonlinear Vector Autoregressive Models](https://mlsanity.com/paper/2511.18641/) (2025)

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

- [The Sharp Tail of Uniform Stability](https://mlsanity.com/paper/2608.24098/) (2026)

## Abstract (arXiv)

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite Lp moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under Lp constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that Lp stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.