# Efficient Cross-Validation for Sparse Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 26 Jun 2023.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [Difference of convex algorithms for bilevel programs with applications in hyperparameter selection](https://mlsanity.com/paper/2102.09006/) (2021)
- [Rank-one Convexification for Sparse Regression](https://mlsanity.com/paper/1901.10334/) (2019)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression](https://mlsanity.com/paper/2107.09194/) (2021)
- [A Scalable Algorithm For Sparse Portfolio Selection](https://mlsanity.com/paper/1811.00138/) (2018)
- [A Gradient-based Bilevel Optimization Approach for Tuning Hyperparameters in Machine Learning](https://mlsanity.com/paper/2007.11022/) (2020)
- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [A Linear-Time Algorithm for Trust Region Problems](https://mlsanity.com/paper/1401.6757/) (2014)

## Abstract (arXiv)

Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To choose hyperparameters that control the sparsity level and amount of regularization, practitioners commonly use k-fold cross-validation. However, cross-validation substantially increases the computational cost of sparse regression as it requires solving many mixed-integer optimization problems (MIOs) for each hyperparameter combination. To address this computational burden, we derive computationally tractable relaxations of the k-fold cross-validation loss, facilitating hyperparameter selection while solving 50--80% fewer MIOs in practice. Our computational results demonstrate, across eleven real-world UCI datasets, that exact MIO-based cross-validation can be competitive with mature software packages such as glmnet and L0Learn.