A scalable estimate of the extra-sample prediction error via approximate leave-one-out

Kamiar Rahnama Rad, Arian MalekiarXiv 2018 · DOI · arXiv

Abstract

In high-dimensional statistics, where the number of features ($p$) often approaches or exceeds the number of observations ($n$), standard out-of-sample risk estimation techniques like $K$-fold cross-validation (CV) suffer from significant bias. While leave-one-out (LO) cross-validation offers a lower-bias alternative, its computational cost is often prohibitive. This paper introduces Approximate Leave-One-Out (ALO), a computationally efficient closed-form approximation for a wide class of regularized estimators. ALO provides the accuracy of LO with minimal computational overhead, requiring only a single model fit. We provide theoretical guarantees for its consistency in high dimensions without requiring sparsity assumptions and demonstrate its performance across synthetic and real-world neuroscience datasets.

Introduction

Selecting the optimal regularization parameter ($\lambda$) is critical for the performance of models like LASSO, Ridge, and Elastic-net. The standard approach, $K$-fold cross-validation, involves splitting the data into $K$ folds, training on $K-1$, and testing on the remainder. However, in high-dimensional settings, this method is known to be heavily biased, typically overestimating the true out-of-sample error. Leave-one-out (LO) cross-validation minimizes this bias but requires $n$ separate optimization procedures, making it impractical for large-scale data.

The Bias of K-Fold Cross-Validation

The primary drawback of $K$-fold CV in high dimensions is that removing a significant portion of the data (a "fold") fundamentally alters the model's solution compared to the full-data fit. This leads to a systematic overestimation of the prediction error.

Out-of-sample error estimation comparing K-fold CV, LO, and true extra-sample error.

As shown in the figure above, 3-fold, 5-fold, and 10-fold CV curves sit significantly higher than the true extra-sample error. In contrast, LO tracks the true error almost perfectly, highlighting its value as a gold standard for risk estimation if the computational hurdles can be overcome.

The ALO Method: Accuracy at Scale

ALO bridges the gap between the accuracy of LO and the speed of a single model fit. The core innovation involves using a single Newton step starting from the full-data solution $\hat{\beta}$ to approximate the $i$-th leave-one-out solution $\hat{\beta}_{/i}$.

To make this process efficient, the authors leverage the Woodbury matrix identity, which allows them to compute all $n$ approximations using a single matrix inversion and subsequent matrix multiplications. For non-smooth regularizers like LASSO, the authors employ a smoothing technique, proving that the ALO formula eventually depends only on the "active set" (non-zero coefficients) of the original model fit.

Computational Efficiency

The computational advantage of ALO is most apparent as the number of predictors ($p$) increases. While LO scales linearly with $n$, ALO's overhead relative to a single model fit is marginal.

Computation time comparison between LO, ALO, and a single model fit (FIT) across different regression models.

In empirical tests across linear, logistic, and Poisson regressions, ALO consistently performs orders of magnitude faster than LO. For instance, in a high-dimensional neuroscience application involving grid cell recordings ($n=3133, p=10000$), calculating the true LO error took over 16 hours, while ALO provided a nearly identical estimate in just 7 seconds.

Theoretical Guarantees and Robustness

A key contribution of this work is the theoretical proof that the difference between LO and ALO goes to zero ($|LO - ALO| \rightarrow 0$) as $n$ and $p$ grow, even when $p > n$. Notably, these guarantees do not rely on sparsity assumptions, which are often required in high-dimensional theory but may not hold in real-world discovery settings. This makes ALO a robust tool for a wide variety of data-generating processes.

Conclusion

ALO offers a scalable, low-bias solution for out-of-sample risk estimation in high-dimensional settings. By providing a closed-form approximation that avoids the $n$-fold training requirement of LO, it enables researchers to perform rigorous model selection on complex datasets that were previously computationally inaccessible. Future work may further enhance ALO's scalability for "ultra-high" dimensions through randomized linear algebra techniques.

Summary updated

Abstract

The paper considers the problem of out-of-sample risk estimation under the high dimensional settings where standard techniques such as $K$-fold cross validation suffer from large biases. Motivated by the low bias of the leave-one-out cross validation (LO) method, we propose a computationally efficient closed-form approximate leave-one-out formula (ALO) for a large class of regularized estimators. Given the regularized estimate, calculating ALO requires minor computational overhead. With minor assumptions about the data generating process, we obtain a finite-sample upper bound for $|\text{LO} - \text{ALO}|$. Our theoretical analysis illustrates that $|\text{LO} - \text{ALO}| \rightarrow 0$ with overwhelming probability, when $n,p \rightarrow \infty$, where the dimension $p$ of the feature vectors may be comparable with or even greater than the number of observations, $n$. Despite the high-dimensionality of the problem, our theoretical results do not require any sparsity assumption on the vector of regression coefficients. Our extensive numerical experiments show that $|\text{LO} - \text{ALO}|$ decreases as $n,p$ increase, revealing the excellent finite sample performance of ALO. We further illustrate the usefulness of our proposed out-of-sample risk estimation method by an example of real recordings from spatially sensitive neurons (grid cells) in the medial entorhinal cortex of a rat.
BibTeX
@misc{rad2018scalable,
  author = {Kamiar Rahnama Rad and Arian Maleki},
  title = {{A scalable estimate of the extra-sample prediction error via approximate leave-one-out}},
  year = {2018},
  eprint = {1801.10243},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.10243},
}
Figure