Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$
Bowei Zhu, Shaojie Li, Mingyang Yi, Yong Liu
Prior work 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 same common assumptions—strong convexity, 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.