Stability revisited: new generalisation bounds for the Leave-one-Out

Abstract

The present paper provides a new generic strategy leading to non-asymptotic theoretical guarantees on the Leave-one-Out procedure applied to a broad class of learning algorithms. This strategy relies on two main ingredients: the new notion of $L^q$ stability, and the strong use of moment inequalities. $L^q$ stability extends the ongoing notion of hypothesis stability while remaining weaker than the uniform stability. It leads to new PAC exponential generalisation bounds for Leave-one-Out under mild assumptions. In the literature, such bounds are available only for uniform stable algorithms under boundedness for instance. Our generic strategy is applied to the Ridge regression algorithm as a first step.

arXiv comment12 pages

Cited by in corpus (7)

• Cross-validation: what does it estimate and how well does it do it?
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Cross-validation Confidence Intervals for Test Error
• A New Formula for Faster Computation of the K-Fold Cross-Validation and Good Regularisation Parameter Values in Ridge Regression
• PAC-Bayesian Bound for the Conditional Value at Risk
• An a Priori Exponential Tail Bound for k-Folds Cross-Validation
• Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability