# Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers (extended version)

arXiv: https://arxiv.org/abs/2310.17629 · HTML: https://mlsanity.com/paper/2310.17629/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 54 references that are in the map.
- First posted on arXiv 26 Oct 2023.

## Builds on (most cited first, 9 of 9)

- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [Cross-validation Confidence Intervals for Test Error](https://mlsanity.com/paper/2007.12671/) (2020)
- [Consistent Risk Estimation in Moderately High-Dimensional Linear Regression](https://mlsanity.com/paper/1902.01753/) (2019)
- [A Higher-Order Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1907.12116/) (2019)
- [Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions](https://mlsanity.com/paper/2003.01770/) (2020)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [Approximate Leave-One-Out for High-Dimensional Non-Differentiable Learning Problems](https://mlsanity.com/paper/1810.02716/) (2018)
- [Robustness in sparse linear models: relative efficiency based on robust approximate message passing](https://mlsanity.com/paper/1507.08726/) (2015)

## Built on by (most cited first, 3 of 3)

- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Fast Leave-One-Out Approximation from Fragment-Target Prevalence Vectors (molFTP) : From Dummy Masking to Key-LOO for Leakage-Free Feature Construction](https://mlsanity.com/paper/2510.06029/) (2025)
- [Accelerating Conformal Prediction via Approximate Leave-One-Out](https://mlsanity.com/paper/2606.31915/) (2026)

## Abstract (arXiv)

The out-of-sample error (OO) is the main quantity of interest in risk estimation and model selection. Leave-one-out cross validation (LO) offers a (nearly) distribution-free yet computationally demanding approach to estimate OO. Recent theoretical work showed that approximate leave-one-out cross validation (ALO) is a computationally efficient and statistically reliable estimate of LO (and OO) for generalized linear models with differentiable regularizers. For problems involving non-differentiable regularizers, despite significant empirical evidence, the theoretical understanding of ALO's error remains unknown. In this paper, we present a novel theory for a wide class of problems in the generalized linear model family with non-differentiable regularizers. We bound the error |ALO - LO| in terms of intuitive metrics such as the size of leave-i-out perturbations in active sets, sample size n, number of features p and regularization parameters. As a consequence, for the ℓ1-regularized problems, we show that |ALO - LO| goes to zero as p goes to infinity while n/p and SNR are fixed and bounded.