# Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 50 references that are in the map.
- First posted on arXiv 22 Mar 2021.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [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)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Bounds](https://mlsanity.com/paper/1702.02030/) (2017)
- [Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate](https://mlsanity.com/paper/1901.09344/) (2019)
- [Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions](https://mlsanity.com/paper/1805.04577/) (2018)
- [Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors](https://mlsanity.com/paper/2009.09304/) (2020)
- [Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization](https://mlsanity.com/paper/1601.04011/) (2016)

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

- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Stable Conformal Prediction Sets](https://mlsanity.com/paper/2112.10224/) (2021)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loops](https://mlsanity.com/paper/2502.18865/) (2025)
- [Post-hoc Bias Scoring Is Optimal For Fair Classification](https://mlsanity.com/paper/2310.05725/) (2023)
- [Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2206.01274/) (2022)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignment](https://mlsanity.com/paper/2410.20727/) (2024)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [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)
- [Hypothesis Transfer Learning with Surrogate Classification Losses: Generalization Bounds through Algorithmic Stability](https://mlsanity.com/paper/2305.19694/) (2023)
- [Sharp error bounds for imbalanced classification: how many examples in the minority class?](https://mlsanity.com/paper/2310.14826/) (2023)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (2022)
- [Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithms](https://mlsanity.com/paper/2206.03834/) (2022)
- [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)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Are all models wrong? Fundamental limits in distribution-free empirical model falsification](https://mlsanity.com/paper/2502.06765/) (2025)
- [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)
- [Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming](https://mlsanity.com/paper/2401.00664/) (2024)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)
- [Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity](https://mlsanity.com/paper/2410.20649/) (2024)
- [Reweighting Improves Conditional Risk Bounds](https://mlsanity.com/paper/2501.02353/) (2025)

## Abstract (arXiv)

The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondr'ak, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a generally inevitable sampling error term of order Theta(1/√n). When applied to excess risk bounds, this leads to suboptimal results in several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term Theta(1/√n) can be avoided, and high probability excess risk bounds of order up to O(1/n) are possible via uniform stability. Using this result, we show a high probability excess risk bound with the rate O(log n/n) for strongly convex and Lipschitz losses valid for any empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (2009). We discuss how O(log n/n) high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.