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

arXiv: https://arxiv.org/abs/1608.06412 · HTML: https://mlsanity.com/paper/1608.06412/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2016.

## Built on by (most cited first, 10 of 10)

- [Cross-validation: what does it estimate and how well does it do it?](https://mlsanity.com/paper/2104.00673/) (2021)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Adaptive Instrument Design for Indirect Experiments](https://mlsanity.com/paper/2312.02438/) (2023)
- [Extrapolated cross-validation for randomized ensembles](https://mlsanity.com/paper/2302.13511/) (2023)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)
- [Concentration inequalities for leave-one-out cross validation](https://mlsanity.com/paper/2211.02478/) (2022)
- [The Limits of Assumption-free Tests for Algorithm Performance](https://mlsanity.com/paper/2402.07388/) (2024)
- [The Relative Instability of Model Comparison with Cross-validation](https://mlsanity.com/paper/2508.04409/) (2025)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [Rolling Conformal Prediction in Sequential Model Training](https://mlsanity.com/paper/2609.26951/) (2026)

## Abstract (arXiv)

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 Lq stability, and the strong use of moment inequalities. Lq 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.