Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$
This work provides sharper theoretical guarantees for generalization in machine learning, particularly for gradient-based methods, but is incremental as it builds on existing stability analysis.
The paper tackles the problem of improving excess risk bounds for strongly-convex learners under common assumptions like the Polyak-Lojasiewicz condition, achieving a rate of O(log^2(n)/n^2), which is tighter than prior O(log(n)/n) bounds.
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.