# Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 19 Jul 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Approximate Cross-validation: Guarantees for Model Assessment and Selection](https://mlsanity.com/paper/2003.00617/) (2020)
- [A scalable estimate of the extra-sample prediction error via approximate leave-one-out](https://mlsanity.com/paper/1801.10243/) (2018)

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

- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Bayes beats Cross Validation: Efficient and Accurate Ridge Regression via Expectation Maximization](https://mlsanity.com/paper/2310.18860/) (2023)
- [OLR-WA: Online Weighted Average Linear Regression in Multivariate Data Streams](https://mlsanity.com/paper/2512.14892/) (2025)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [Prevalidated ridge regression is a highly-efficient drop-in replacement for logistic regression for high-dimensional data](https://mlsanity.com/paper/2401.15610/) (2024)
- [SOAK: Same/Other/All K-fold cross-validation for estimating similarity of patterns in data subsets](https://mlsanity.com/paper/2410.08643/) (2024)
- [Stability Regularized Cross-Validation](https://mlsanity.com/paper/2505.06927/) (2025)
- [OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging](https://mlsanity.com/paper/2512.12779/) (2025)
- [Prediction-Only Distillation in Linear and Logistic Regression](https://mlsanity.com/paper/2607.15450/) (2026)

## Abstract (arXiv)

Models like LASSO and ridge regression are extensively used in practice due to their interpretability, ease of use, and strong theoretical guarantees. Cross-validation (CV) is widely used for hyperparameter tuning in these models, but do practical optimization methods minimize the true out-of-sample loss? A recent line of research promises to show that the optimum of the CV loss matches the optimum of the out-of-sample loss (possibly after simple corrections). It remains to show how tractable it is to minimize the CV loss. In the present paper, we show that, in the case of ridge regression, the CV loss may fail to be quasiconvex and thus may have multiple local optima. We can guarantee that the CV loss is quasiconvex in at least one case: when the spectrum of the covariate matrix is nearly flat and the noise in the observed responses is not too high. More generally, we show that quasiconvexity status is independent of many properties of the observed data (response norm, covariate-matrix right singular vectors and singular-value scaling) and has a complex dependence on the few that remain. We empirically confirm our theory using simulated experiments.