# Approximate Cross-Validation for Structured Models

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

## Key facts

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

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

- [Fair Infinitesimal Jackknife: Mitigating the Influence of Biased Training Data Points Without Refitting](https://mlsanity.com/paper/2212.06803/) (2022)
- [Uncertainty Quantification 360: A Holistic Toolkit for Quantifying and Communicating the Uncertainty of AI](https://mlsanity.com/paper/2106.01410/) (2021)
- [Toward a Taxonomy of Trust for Probabilistic Machine Learning](https://mlsanity.com/paper/2112.03270/) (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)
- [TimeInf: Time Series Data Contribution via Influence Functions](https://mlsanity.com/paper/2407.15247/) (2024)
- [SOAK: Same/Other/All K-fold cross-validation for estimating similarity of patterns in data subsets](https://mlsanity.com/paper/2410.08643/) (2024)
- [TimeLAVA: Learning-Agnostic Valuation for Time Series Data](https://mlsanity.com/paper/2606.18729/) (2026)

## Abstract (arXiv)

Many modern data analyses benefit from explicitly modeling dependence structure in data -- such as measurements across time or space, ordered words in a sentence, or genes in a genome. A gold standard evaluation technique is structured cross-validation (CV), which leaves out some data subset (such as data within a time interval or data in a geographic region) in each fold. But CV here can be prohibitively slow due to the need to re-run already-expensive learning algorithms many times. Previous work has shown approximate cross-validation (ACV) methods provide a fast and provably accurate alternative in the setting of empirical risk minimization. But this existing ACV work is restricted to simpler models by the assumptions that (i) data across CV folds are independent and (ii) an exact initial model fit is available. In structured data analyses, both these assumptions are often untrue. In the present work, we address (i) by extending ACV to CV schemes with dependence structure between the folds. To address (ii), we verify -- both theoretically and empirically -- that ACV quality deteriorates smoothly with noise in the initial fit. We demonstrate the accuracy and computational benefits of our proposed methods on a diverse set of real-world applications.