# Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 13 Feb 2024.

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

- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso](https://mlsanity.com/paper/1707.08692/) (2017)
- [Consistent Risk Estimation in Moderately High-Dimensional Linear Regression](https://mlsanity.com/paper/1902.01753/) (2019)
- [Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing](https://mlsanity.com/paper/1907.07502/) (2019)
- [On Optimal Generalizability in Parametric Learning](https://mlsanity.com/paper/1711.05323/) (2017)
- [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)
- [Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression](https://mlsanity.com/paper/2107.09194/) (2021)
- [Does SLOPE outperform bridge regression?](https://mlsanity.com/paper/1909.09345/) (2019)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [Consistent Parameter Estimation for LASSO and Approximate Message Passing](https://mlsanity.com/paper/1511.01017/) (2015)
- [Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers (extended version)](https://mlsanity.com/paper/2310.17629/) (2023)
- [Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration](https://mlsanity.com/paper/1902.10375/) (2019)

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

- [Certified Data Removal Under High-dimensional Settings](https://mlsanity.com/paper/2505.07640/) (2025)
- [Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach](https://mlsanity.com/paper/2510.13094/) (2025)
- [Simultaneous analysis of approximate leave-one-out cross-validation and mean-field inference](https://mlsanity.com/paper/2501.02624/) (2025)
- [Evaluation and Optimization of Leave-one-out Cross-validation for the Lasso](https://mlsanity.com/paper/2508.14368/) (2025)
- [Accelerating Conformal Prediction via Approximate Leave-One-Out](https://mlsanity.com/paper/2606.31915/) (2026)

## Abstract (arXiv)

Despite a large and significant body of recent work focused on estimating the out-of-sample risk of regularized models in the high dimensional regime, a theoretical understanding of this problem for non-differentiable penalties such as generalized LASSO and nuclear norm is missing. In this paper we resolve this challenge. We study this problem in the proportional high dimensional regime where both the sample size n and number of features p are large, and n/p and the signal-to-noise ratio (per observation) remain finite. We provide finite sample upper bounds on the expected squared error of leave-one-out cross-validation (LO) in estimating the out-of-sample risk. The theoretical framework presented here provides a solid foundation for elucidating empirical findings that show the accuracy of LO.