Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)

2021/03/22 by Klochkov, Yegor, Zhivotovskiy, Nikita · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2103.12024

Abstract

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/√(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/√(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 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.

Cited by

• Non-Asymptotic Optimization and Generalization Bounds for Stochastic Gauss-Newton in Overparameterized Models

Related

• Stability and Sharper Risk Bounds with Convergence Rate O(1/n²)
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Optimistic Rates for Learning with a Smooth Loss
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n²)-type of Risk Bounds