Concentration inequalities for leave-one-out cross validation
Benny Avelin, Lauri Viitasaari
math.ST
Nov 4, 2022 · v4
cs.LG stat.ML
TL;DR
The main concentration results for leave-one-out cross-validation are formalized in Lean 4, with the formalization in a public GitHub repository.
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.
Problem
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.
Approach
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.
Results
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.