Stability and Sharper Risk Bounds with Convergence Rate O(1/n²)

2024/10/13 by Bo-Wei Zhu, Zhu, Bowei, Shaojie Li +3
Decision Sciences · #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2410.09766

Abstract

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

Related

• Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)
• Optimistic Rates for Learning with a Smooth Loss
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
• Binary Excess Risk for Smooth Convex Surrogates