Concentration inequalities for leave-one-out cross validation
Benny Avelin
Lauri Viitasaari
Oct 2026
Machine Learning
Data Science
Abstract
In this article we prove that estimator stability, together with a gradient-growth condition on the expected fitted loss, is enough to provide concentration bounds for leave-one-out cross-validation in a general framework. In particular, we provide concentration bounds beyond Lipschitz continuity assumptions on the loss or on the estimator. We obtain our results by relying on random variables with distribution satisfying the logarithmic Sobolev inequality, providing us a relatively rich class of distributions. We illustrate our method by considering several interesting examples, including linear regression, kernel density estimation, and stabilized/truncated estimators such as stabilized kernel regression.
