Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)
Not on the map. Why?
Abstract (arXiv)
Prior work (Klochkov & Zhivotovskiy, 2021) establishes at most Oleft(log (n)/nright) excess risk bounds via algorithmic stability for strongly-convex learners with high probability. We show that under the similar common assumptions -- - Polyak-Lojasiewicz condition, smoothness, and Lipschitz continous for losses -- - rates of Oleft(log2(n)/n2right) are at most achievable. To our knowledge, our analysis also provides the tightest high-probability bounds for gradient-based generalization gaps in nonconvex settings.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 29 of its 59 references that are in the map. First posted on arXiv 13 Oct 2024.
Builds on
29 of 59 references.
References · 29
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
- 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
- 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
- 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
17 more
- 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
- 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
- 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
- 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 42
- 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
- 2017Algorithmic stability and hypothesis complexitycited by 39
- 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
- 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
- 2019Hypothesis Set Stability and Generalizationcited by 23
- 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
- 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
- 2018Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimizationcited by 14
- 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
- 2020Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theorycited by 13
- 2018Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditionscited by 9
- 2020Characterization of Excess Risk for Locally Strongly Convex Population Riskcited by 5
- 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
Built on by
Citing papers per year: 2026: 2.
2 papers.