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

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