Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Alain Celisse 1, 2 Benjamin Guedj 2, 1 
2 MODAL - MOdel for Data Analysis and Learning
LPP - Laboratoire Paul Painlevé - UMR 8524, Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille
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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Benjamin Guedj Connect in order to contact the contributor
Submitted on : Tuesday, August 23, 2016 - 10:02:40 AM
Last modification on : Thursday, March 24, 2022 - 3:13:00 AM
Long-term archiving on: : Thursday, November 24, 2016 - 12:40:17 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-01355365, version 1



Alain Celisse, Benjamin Guedj. Stability revisited: new generalisation bounds for the Leave-one-Out. 2016. ⟨hal-01355365⟩



Record views


Files downloads