# Approximate Cross-validation: Guarantees for Model Assessment and Selection

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2020.

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

- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression](https://mlsanity.com/paper/2107.09194/) (2021)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)
- [Synthetic Data for Model Selection](https://mlsanity.com/paper/2105.00717/) (2021)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [Extrapolated cross-validation for randomized ensembles](https://mlsanity.com/paper/2302.13511/) (2023)
- [Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization](https://mlsanity.com/paper/2306.10081/) (2023)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)
- [Rescaled Influence Functions: Accurate Data Attribution in High Dimension](https://mlsanity.com/paper/2506.06656/) (2025)
- [The Approximate Fisher Influence Function: Faster Estimation of Data Influence in Statistical Models](https://mlsanity.com/paper/2407.08169/) (2024)
- [The Relative Instability of Model Comparison with Cross-validation](https://mlsanity.com/paper/2508.04409/) (2025)
- [On the Accuracy of Newton Step and Influence Function Data Attributions](https://mlsanity.com/paper/2512.12572/) (2025)
- [Inconsistency of cross-validation for structure learning in Gaussian graphical models](https://mlsanity.com/paper/2312.17047/) (2023)
- [The Regularization Parameter: Sparse Precision Matrix Estimation](https://mlsanity.com/paper/2607.07735/) (2026)

## Abstract (arXiv)

Cross-validation (CV) is a popular approach for assessing and selecting predictive models. However, when the number of folds is large, CV suffers from a need to repeatedly refit a learning procedure on a large number of training datasets. Recent work in empirical risk minimization (ERM) approximates the expensive refitting with a single Newton step warm-started from the full training set optimizer. While this can greatly reduce runtime, several open questions remain including whether these approximations lead to faithful model selection and whether they are suitable for non-smooth objectives. We address these questions with three main contributions: (i) we provide uniform non-asymptotic, deterministic model assessment guarantees for approximate CV; (ii) we show that (roughly) the same conditions also guarantee model selection performance comparable to CV; (iii) we provide a proximal Newton extension of the approximate CV framework for non-smooth prediction problems and develop improved assessment guarantees for problems such as l1-regularized ERM.