# Iterative Approximate Cross-Validation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 5 Mar 2023.

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

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions](https://mlsanity.com/paper/1807.02694/) (2018)
- [Approximate Cross-validation: Guarantees for Model Assessment and Selection](https://mlsanity.com/paper/2003.00617/) (2020)
- [On Optimal Generalizability in Parametric Learning](https://mlsanity.com/paper/1711.05323/) (2017)
- [Approximate Cross-Validation for Structured Models](https://mlsanity.com/paper/2006.12669/) (2020)

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

- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)
- [Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers (extended version)](https://mlsanity.com/paper/2310.17629/) (2023)
- [Distributional bias compromises leave-one-out cross-validation](https://mlsanity.com/paper/2406.01652/) (2024)
- [RandALO: Out-of-sample risk estimation in no time flat](https://mlsanity.com/paper/2409.09781/) (2024)
- [Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression](https://mlsanity.com/paper/2410.02629/) (2024)
- [A Ridge Too Far: Correcting Over-Shrinkage via Negative Regularization](https://mlsanity.com/paper/2508.17412/) (2025)

## Abstract (arXiv)

Cross-validation (CV) is one of the most popular tools for assessing and selecting predictive models. However, standard CV suffers from high computational cost when the number of folds is large. Recently, under the empirical risk minimization (ERM) framework, a line of works proposed efficient methods to approximate CV based on the solution of the ERM problem trained on the full dataset. However, in large-scale problems, it can be hard to obtain the exact solution of the ERM problem, either due to limited computational resources or due to early stopping as a way of preventing overfitting. In this paper, we propose a new paradigm to efficiently approximate CV when the ERM problem is solved via an iterative first-order algorithm, without running until convergence. Our new method extends existing guarantees for CV approximation to hold along the whole trajectory of the algorithm, including at convergence, thus generalizing existing CV approximation methods. Finally, we illustrate the accuracy and computational efficiency of our method through a range of empirical studies.