mlsanityData to 7 Oct 2026

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

arXiv 2103.12024 ↗First posted 22 Mar 2021cs.LG cs.DS math.OCcited by 42

Not on the map. Why?

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.

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

Builds on

24 of 50 references.

References · 24

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  6. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  7. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  8. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  9. 2019Sharper bounds for uniformly stable algorithmscited by 91
  10. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  11. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  12. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 52
12 more
  1. 2015Fast rates in statistical and online learningcited by 47
  2. 2017Algorithmic stability and hypothesis complexitycited by 39
  3. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  4. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  5. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 31
  6. 2019An improper estimator with optimal excess risk in misspecified density estimation and logistic regressioncited by 24
  7. 2021Distribution-Free Robust Linear Regressioncited by 19
  8. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  9. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  10. 2018Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditionscited by 9
  11. 2020Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictorscited by 9
  12. 2016Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimizationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 12; 2023: 9; 2024: 5; 2025: 6; 2026: 7.

42 papers.

Sort:

By area:

  1. 2022On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyondcited by 37
  2. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  3. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  4. 2021Stable Conformal Prediction Setscited by 19
  5. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  6. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 15
  7. 2023Post-hoc Bias Scoring Is Optimal For Fair Classificationcited by 14
  8. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  9. 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
  10. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
  11. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  12. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
30 more
  1. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  2. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  3. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  4. 2023Hypothesis Transfer Learning with Surrogate Classification Losses: Generalization Bounds through Algorithmic Stabilitycited by 4
  5. 2023Sharp error bounds for imbalanced classification: how many examples in the minority class?cited by 4
  6. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  7. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3
  8. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  9. 2023On the Stability and Generalization of Triplet Learningcited by 2
  10. 2023Exploring Local Norms in Exp-concave Statistical Learningcited by 2
  11. 2024Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)cited by 2
  12. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  13. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1
  14. 2024Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programmingcited by 1
  15. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  16. 2025Reweighting Improves Conditional Risk Boundscited by 1
  17. 2025Are all models wrong? Fundamental limits in distribution-free empirical model falsificationcited by 1
  18. 2026On the Intrinsic Dimensions of Data in Kernel Learningcited by 1
  19. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  20. 2026Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithmscited by 1
  21. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  22. 2021Learning Rates for Nonconvex Pairwise Learningcited by 0
  23. 2024Towards Sharper Risk Bounds for Minimax Problemscited by 0
  24. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0
  25. 2025Covariate-dependent Graphical Model Estimation via Neural Networks with Statistical Guaranteescited by 0
  26. 2025Non-Asymptotic Optimization and Generalization Bounds for Stochastic Gauss-Newton in Overparameterized Modelscited by 0
  27. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  28. 2026Unveiling High-Probability Generalization in Decentralized SGDcited by 0
  29. 2026Non-asymptotic estimates of the minimal risk in statistical learningcited by 0
  30. 2026The Sharp Tail of Uniform Stabilitycited by 0