Research map / Optimization / Nonconvex and smooth optimization

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

NeurIPS 2025 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that algorithmic stability in gradients yields high-probability excess risk bounds of order log^2(n)/n^2 for ERM, PGD and SGD under PL, smoothness and Lipschitz assumptions (with a low-noise condition F(w*)=O(1/n)).

Problem

Algorithmic stability-based high-probability excess risk bounds have been stuck at O(log n / n); the paper asks whether they can go below O(1/n) under PL, smoothness and Lipschitz assumptions.

Approach

Generalizes uniform stability to gradients of the loss, proves a sharper generalization bound for gradients that depends on the squared gradient norm at the learned model (rather than the maximal gradient norm M), and combines it with PL to bound excess risk at rate O(log^2 n / n^2).

Key results

• Establishes high-probability excess risk bounds of O(log^2(n)/n^2) for ERM, PGD and SGD under smoothness, PL and Lipschitz assumptions, with F(w*)=O(1/n).
• Gradient generalization bound improves the constant-level 1/sqrt(n) term from M to sqrt(E||grad f||^2 log(1/delta)), with no dependence on iteration count.
• SGD achieves O(log^2 n/n^2) with T ~ n^2 iterations and O(1/n) with T ~ n iterations under F(w*)=O(1) (per the paper's table and remarks).

Measured effects reported in the paper

Surprising findings

• The paper claims prior analyses that use smoothness and PL did not fully exploit these assumptions, and that their own sharper bound follows from a gradient-stability analysis.

Limitations

• Requires the low-noise assumption F(w*) < O(1/n) to attain the O(1/n^2) rate.
• Requires smoothness, PL condition on both empirical and population risk, and sample size n >= 32 gamma^2 log(6/delta)/mu^2.
• Results are purely theoretical with no empirical validation in the excerpt.

Experimental setup

Metrics: excess risk bound order

Baselines: Klochkov & Zhivotovskiy 2021 uniform convergence gradient bounds (Lei & Ying 2020 style)

Builds on: Klochkov & Zhivotovskiy 2021 (stability-based high-probability excess risk) uniform stability in gradients (Lei & Ying 2020) vector Bernstein inequality McDiarmid's inequality

Closest papers by meaning

• Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$ (NeurIPS 2021 · similarity 0.92)
• Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments (ICML 2026 · similarity 0.91)
• Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.91)
• Exponential Generalization Bounds with Near-Optimal Rates for $L_q$-Stable Algorithms (ICLR 2023 · similarity 0.90)
• Characterization of Excess Risk for Locally Strongly Convex Population Risk (NeurIPS 2022 · similarity 0.90)
• Data-Dependent Stability of Stochastic Gradient Descent (ICML 2018 · similarity 0.90)