Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$

Bowei Zhu; Shaojie Li; Mingyang Yi; Yong Liu

NeurIPS 2025poster0 citations

Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$

Bowei Zhu, Shaojie Li, Mingyang Yi, Yong Liu

Abstract

Prior work (Klochkov \& Zhivotovskiy, 2021) establishes at most $O\left(\log (n)/n\right)$ 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 $O\left(\log^2(n)/n^2\right)$ are at most achievable. To our knowledge, our analysis also provides the tightest high-probability bounds for gradient-based generalization gaps in nonconvex settings.

algorithmic stabilitygeneralization boundsexcess risk boundsstochastic gradiet descent

BibTeX

@inproceedings{
zhu2025stability,
title={Stability and Sharper Risk Bounds with Convergence Rate \${\textbackslash}tilde\{O\}(1/n{\textasciicircum}2)\$},
author={Bowei Zhu and Shaojie Li and Mingyang Yi and Yong Liu},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=dCcWKeO4y4}
}