mlsanityData to 7 Oct 2026

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

arXiv 2402.16793 ↗First posted 26 Feb 2024math.ST cs.LG stat.MLcited by 4

Not on the map. Why?

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.

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

Builds on

33 of 93 references.

References · 33

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  3. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  4. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  5. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 248
  6. 2021Deep learning: a statistical viewpointcited by 239
  7. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  8. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  9. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
  10. 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 87
  11. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 86
  12. 2020Understanding Double Descent Requires a Fine-Grained Bias-Variance Decompositioncited by 75
21 more
  1. 2018A Continuous-Time View of Early Stopping for Least Squarescited by 67
  2. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  3. 2020Asymptotics of Ridge (less) Regression under General Source Conditioncited by 61
  4. 2020The Implicit Regularization of Stochastic Gradient Flow for Least Squarescited by 58
  5. 2023Learning time-scales in two-layers neural networkscited by 57
  6. 2018Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularizationcited by 52
  7. 2020Cross-validation Confidence Intervals for Test Errorcited by 32
  8. 2017Early stopping for kernel boosting algorithms: A general analysis with localized complexitiescited by 27
  9. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
  10. 2020Ridge Regularization: an Essential Concept in Data Sciencecited by 19
  11. 2018Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensionscited by 15
  12. 2020Approximate Cross-validation: Guarantees for Model Assessment and Selectioncited by 14
  13. 2017Cross-Validation with Confidencecited by 13
  14. 2020Out-of-sample error estimate for robust M-estimators with convex penaltycited by 13
  15. 2020Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensionscited by 11
  16. 2023Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validationcited by 11
  17. 2023Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuningcited by 11
  18. 2016Stability revisited: new generalisation bounds for the Leave-one-Outcited by 10
  19. 2021Derivatives and residual distribution of regularized M-estimators with application to adaptive tuningcited by 7
  20. 2023Iterative Approximate Cross-Validationcited by 7
  21. 2022Concentration inequalities for leave-one-out cross validationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025A theoretical framework for overfitting in energy-based modelingcited by 5
  2. 2024Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regressioncited by 0
  3. 2025GRADSTOP: Early Stopping of Gradient Descent via Posterior Samplingcited by 0
  4. 2026Beyond Negative-Ridge Endpoints: Mixed-Sign Spectral Regularization via Negative-Shifted Gradient Descentcited by 0