An a Priori Exponential Tail Bound for k-Folds Cross-Validation
We consider a priori generalization bounds developed in terms of cross-validation estimates and the stability of learners. In particular, we first derive an exponential Efron-Stein type tail inequality for the concentration of a general function of n independent random variables. Next, under some reasonable notion of stability, we use this exponential tail bound to analyze the concentration of the k-fold cross-validation (KFCV) estimate around the true risk of a hypothesis generated by a general learning rule. While the accumulated literature has often attributed this concentration to the bias and variance of the estimator, our bound attributes this concentration to the stability of the learning rule and the number of folds k. This insight raises valid concerns related to the practical use of KFCV and suggests research directions to obtain reliable empirical estimates of the actual risk.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsvalidSimilar Papers 제목 키워드 기반
Curvature-Dependant Global Convergence Rates for Optimization on Manifolds of Bounded Geometry
We give curvature-dependant convergence rates for the optimization of weakly convex functions defined on a manifold of 1-bounded geometry via Riemannian gradient descent and via the dynamic trivialization algorithm. In o…
Robust Estimation in metric spaces: Achieving Exponential Concentration with a Fréchet Median
There is growing interest in developing statistical estimators that achieve exponential concentration around a population target even when the data distribution has heavier than exponential tails. More recent activity ha…
Random projections of random manifolds
Interesting data often concentrate on low dimensional smooth manifolds inside a high dimensional ambient space. Random projections are a simple, powerful tool for dimensionality reduction of such data. Previous works hav…
Dimensionality ReductionA semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
We study stability of optimizers and convergence of Sinkhorn's algorithm in the framework of entropic optimal transport. We show entropic stability for optimal plans in terms of the Wasserstein distance between their mar…
$\left( β, \varpi \right)$-stability for cross-validation and the choice of the number of folds
In this paper, we introduce a new concept of stability for cross-validation, called the $\left( \beta, \varpi \right)$-stability, and use it as a new perspective to build the general theory for cross-validation. The $\le…
Model Selection