Concentration inequalities for leave-one-out cross validation

2022/11/04 by Avelin, Benny, Viitasaari, Lauri
#60F15 #62G05 #62R07 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2211.02478

Abstract

In this article we prove that estimator stability is enough to show that leave-one-out cross validation is a sound procedure, by providing concentration bounds 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.

Related

• Concentration inequalities of the cross-validation estimator for Empirical Risk Minimiser
• Concentration inequalities of the cross-validation estimate for stable predictors
• Estimating Subagging by cross-validation
• Simultaneous analysis of approximate leave-one-out cross-validation and mean-field inference
• Efficient Concentration with Gaussian Approximation