High-Dimensional Risk Estimation via Approximate Leave-One-Out

This direction is merged into another direction: computational cost of cross-validation. Its last version stays readable and citable here.

Version 1 of 123 papers30 conceptsfrozen 2026-10-04

In classical statistics, cross-validation (CV) is the "gold standard" for estimating how well a model will perform on unseen data. We split our data, train on a subset, and test on the remainder. However, as the number of features ($p$) approaches or exceeds the number of observations ($n$), this foundational tool begins to crack.

Recent research reveals that in high-dimensional regimes, standard cross-validation techniques become systematically biased and computationally prohibitive. To solve this, researchers have developed a suite of "Approximate Leave-One-Out" (ALO) methods that provide consistent risk estimates with the computational cost of a single model fit.

The High-Dimensional Bias of K-Fold CV

The core problem with standard $K$-fold cross-validation in high dimensions is sample-size bias. In a regime where the ratio $\gamma = p/n$ dictates model behavior, training on a fraction of the data (e.g., 80% in 5-fold CV) fundamentally changes the geometry of the problem.

As Arian Maleki, Kamiar Rahnama Rad, and Ji Xu demonstrate in Consistent Risk Estimation in High-Dimensional Linear Regression, reducing the training set by even 10% or 20% significantly alters the feature-to-observation ratio. This leads to a pessimistic bias: the CV error overestimates the true out-of-sample error because the model trained on the fold is "weaker" than the model trained on the full dataset.

This phenomenon is particularly acute for algorithms with implicit regularization, like early-stopped Gradient Descent. Pratik Patil and Ryan Tibshirani show in Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent that while Generalized Cross-Validation (GCV) can fail in these settings, Leave-One-Out Cross-Validation (LOOCV) remains robust because it uses $n-1$ samples—keeping the $p/n$ ratio almost identical to the full dataset.

The Computational Bottleneck

If LOOCV is the most accurate estimator, why don't we always use it? The answer is cost. For a dataset of size $n$, LOOCV requires retraining the model $n$ times. In high-dimensional settings where $p$ is large, even a single fit can be expensive; $n$ fits are often impossible.

Furthermore, traditional approximations like the Infinitesimal Jackknife or standard GCV lose accuracy as dimensionality grows. Tamara Broderick and William T. Stephenson note in Sparse Approximate Cross-Validation for High-Dimensional GLMs that these approximations degrade when the number of features is large relative to the number of observations, especially if the data isn't perfectly sparse.

The Solution: Approximate Leave-One-Out (ALO)

The breakthrough in this field is the realization that we can approximate the effect of removing one data point without actually retraining the model.

The intuition comes from Taylor expansions. If the loss function is smooth, the change in the model parameters when one observation is removed can be estimated using the Hessian of the loss function at the full-data solution. This "one-step" approximation allows us to estimate the LOOCV error using only the results of the initial model fit.

Key advancements in this area include:

  1. Handling Non-Differentiability: Many high-dimensional models, like the LASSO or SVMs, use non-differentiable penalties. Shuaiwen Wang and Arian Maleki extended ALO to these cases in Approximate Leave-One-Out for High-Dimensional Non-Differentiable Learning Problems, providing a way to tune hyperparameters like $\lambda$ almost instantaneously.
  2. Randomized Speedups: To avoid the $O(p^3)$ cost of inverting a Hessian, Parth Nobel and Emmanuel Candes introduced RandALO in RandALO: Out-of-sample risk estimation in no time flat. By using randomized linear algebra, they achieve LOOCV accuracy at a speed faster than even 5-fold CV.
  3. Theoretical Guarantees: Kamiar Rahnama Rad and colleagues proved in Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions that the error of these ALO estimators actually vanishes as $n$ and $p$ grow, confirming their reliability in the very regimes where traditional CV fails.

Beyond Simple Regression

This framework is now being extended to more complex scenarios. For instance, Mohsen Bayati and Andrea Montanari utilized Approximate Message Passing (AMP) theory to estimate LASSO risk in Estimating LASSO Risk and Noise Level. Meanwhile, Pratik Patil and Daniel LeJeune have shown that GCV can be made consistent for "sketched" ensembles, allowing researchers to estimate the risk of massive models using small, computationally cheap data sketches (Asymptotically Free Sketched Ridge Ensembles).

By shifting from "re-training on subsets" to "approximating the leave-one-out perturbation," this research direction provides a path toward reliable, scalable model evaluation in the high-dimensional era.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_high_dimensional_risk_estimation_via_app_83c4caca,
  title = {High-Dimensional Risk Estimation via Approximate Leave-One-Out},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-dimensional-risk-estimation-via-approximate-leave-one-out/rdr_83c4caca617e4db7ab1aa5a92a8a1b00},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_high_dimensional_risk_estimation_via_app_83c4caca_v1,
  title = {High-Dimensional Risk Estimation via Approximate Leave-One-Out},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-dimensional-risk-estimation-via-approximate-leave-one-out/rdr_83c4caca617e4db7ab1aa5a92a8a1b00/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}