# Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 93 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 30 of 33)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition](https://mlsanity.com/paper/2011.03321/) (2020)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [The Implicit Regularization of Stochastic Gradient Flow for Least Squares](https://mlsanity.com/paper/2003.07802/) (2020)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization](https://mlsanity.com/paper/1805.10939/) (2018)
- [Cross-validation Confidence Intervals for Test Error](https://mlsanity.com/paper/2007.12671/) (2020)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [Iterate averaging as regularization for stochastic gradient descent](https://mlsanity.com/paper/1802.08009/) (2018)
- [Ridge Regularization: an Essential Concept in Data Science](https://mlsanity.com/paper/2006.00371/) (2020)
- [Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions](https://mlsanity.com/paper/1807.02694/) (2018)
- [Cross-Validation with Confidence](https://mlsanity.com/paper/1703.07904/) (2017)
- [Approximate Cross-validation: Guarantees for Model Assessment and Selection](https://mlsanity.com/paper/2003.00617/) (2020)
- [Out-of-sample error estimate for robust M-estimators with convex penalty](https://mlsanity.com/paper/2008.11840/) (2020)
- [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)
- [Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation](https://mlsanity.com/paper/2304.13016/) (2023)
- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Stability revisited: new generalisation bounds for the Leave-one-Out](https://mlsanity.com/paper/1608.06412/) (2016)

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

- [A theoretical framework for overfitting in energy-based modeling](https://mlsanity.com/paper/2501.19158/) (2025)
- [Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression](https://mlsanity.com/paper/2410.02629/) (2024)
- [GRADSTOP: Early Stopping of Gradient Descent via Posterior Sampling](https://mlsanity.com/paper/2508.19028/) (2025)
- [Beyond Negative-Ridge Endpoints: Mixed-Sign Spectral Regularization via Negative-Shifted Gradient Descent](https://mlsanity.com/paper/2607.22474/) (2026)

## Abstract (arXiv)

We analyze the statistical properties of generalized cross-validation (GCV) and leave-one-out cross-validation (LOOCV) applied to early-stopped gradient descent (GD) in high-dimensional least squares regression. We prove that GCV is generically inconsistent as an estimator of the prediction risk of early-stopped GD, even for a well-specified linear model with isotropic features. In contrast, we show that LOOCV converges uniformly along the GD trajectory to the prediction risk. Our theory requires only mild assumptions on the data distribution and does not require the underlying regression function to be linear. Furthermore, by leveraging the individual LOOCV errors, we construct consistent estimators for the entire prediction error distribution along the GD trajectory and consistent estimators for a wide class of error functionals. This in particular enables the construction of pathwise prediction intervals based on GD iterates that have asymptotically correct nominal coverage conditional on the training data.