← All papers
First page of Concentration inequalities for leave-one-out cross validation

Concentration inequalities for leave-one-out cross validation

Benny Avelin, Lauri Viitasaari

math.ST Nov 4, 2022 · v4 cs.LG stat.ML
The main concentration results for leave-one-out cross-validation are formalized in Lean 4, with the formalization in a public GitHub repository.
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.

The work seeks concentration bounds for the leave-one-out cross-validation estimate of generalization error. The goal is to cover settings beyond Lipschitz continuity assumptions on the loss or the estimator.

Data are assumed to follow distributions satisfying a logarithmic Sobolev inequality. The authors combine a delete-one estimator stability condition with a gradient-growth condition on the expected fitted loss, and split the LOO error into three terms. A conditioned version uses a Bobkov-Nayar-Tetali restricted-measure estimate. The main results are formalized in Lean 4.

Concentration bounds hold in a Lipschitz case, a general quadratic-gradient case, and a conditioned case. Applications include the empirical mean, linear regression, kernel density estimation and stabilized kernel regression, supported by numerical experiments showing approximately exponential decay in n.