Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
29 of 74 references.
References · 29
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
- 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 215
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2020Few-Shot Learning via Learning the Representation, Provablycited by 214
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
- 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
- 2019Sharper bounds for uniformly stable algorithmscited by 93
- 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
- 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
- 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
- 2013Loss minimization and parameter estimation with heavy tailscited by 50
- 2014Learning without Concentrationcited by 50
17 more
- 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
- 2017Algorithmic stability and hypothesis complexitycited by 39
- 2014Empirical risk minimization for heavy-tailed lossescited by 37
- 2021Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Taskscited by 36
- 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
- 2013Concentration in unbounded metric spaces and algorithmic stabilitycited by 22
- 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
- 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
- 2021On Data Efficiency of Meta-learningcited by 16
- 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
- 2016Stability revisited: new generalisation bounds for the Leave-one-Outcited by 10
- 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8
- 2023Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopescited by 8
- 2021Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stabilitycited by 7
- 2019An Exponential Efron-Stein Inequality for Lq Stable Learning Rulescited by 6
- 2020Algorithmic Stability and Generalization of an Unsupervised Feature Selection Algorithmcited by 6
- 2025Estimation of High-dimensional Nonlinear Vector Autoregressive Modelscited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.
- 2026The Sharp Tail of Uniform Stabilitycited by 0
- 2026The Sharp Tail of Uniform Stability25 Aug 2026