Sharper bounds for uniformly stable algorithms

Abstract

Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and Wagner (1978). In a series of recent breakthrough papers by Feldman and Vondrak (2018, 2019), it was shown that the best known high probability upper bounds for uniformly stable learning algorithms due to Bousquet and Elisseef (2002) are sub-optimal in some natural regimes. To do so, they proved two generalization bounds that significantly outperform the simple generalization bound of Bousquet and Elisseef (2002). Feldman and Vondrak also asked if it is possible to provide sharper bounds and prove corresponding high probability lower bounds. This paper is devoted to these questions: firstly, inspired by the original arguments of Feldman and Vondrak (2019), we provide a short proof of the moment bound that implies the generalization bound stronger than both recent results (Feldman and Vondrak, 2018, 2019). Secondly, we prove general lower bounds, showing that our moment bound is sharp (up to a logarithmic factor) unless some additional properties of the corresponding random variables are used. Our main probabilistic result is a general concentration inequality for weakly correlated random variables, which may be of independent interest.

arXiv comment17 pages, minor improvements, to appear in COLT

References in corpus (7)

• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Generalization Bounds for Uniformly Stable Algorithms
• Hypothesis Set Stability and Generalization
• Proper Learning, Helly Number, and an Optimal SVM Bound
• Optimal learning via local entropies and sample compression

Cited by in corpus (8)

• On the cross-validation bias due to unsupervised pre-processing
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• PAC-Bayesian Bound for the Conditional Value at Risk
• Proper Learning, Helly Number, and an Optimal SVM Bound
• Revisiting RIP guarantees for sketching operators on mixture models
• Generalisation under gradient descent via deterministic PAC-Bayes
• A Tight Lower Bound for Uniformly Stable Algorithms