Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$
This work addresses a foundational issue in machine learning theory by improving risk bounds for optimization algorithms, with implications for stochastic convex optimization and empirical risk minimization, though it is incremental in refining existing stability-based approaches.
The paper tackles the problem of suboptimal high probability generalization bounds for uniformly stable algorithms, which typically include a sampling error term of order Θ(1/√n) that leads to suboptimal excess risk bounds in stochastic convex optimization. By leveraging the Bernstein condition, they avoid this term and achieve high probability excess risk bounds of order up to O(1/n), specifically demonstrating an O(log n/n) bound for any empirical risk minimization method with strongly convex and Lipschitz losses, resolving a long-standing question.
The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondrák, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a generally inevitable sampling error term of order $Θ(1/\sqrt{n})$. When applied to excess risk bounds, this leads to suboptimal results in several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term $Θ(1/\sqrt{n})$ can be avoided, and high probability excess risk bounds of order up to $O(1/n)$ are possible via uniform stability. Using this result, we show a high probability excess risk bound with the rate $O(\log n/n)$ for strongly convex and Lipschitz losses valid for \emph{any} empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (2009). We discuss how $O(\log n/n)$ high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.