Approximate Cross-Validation in High Dimensions with Guarantees
This work addresses a computational bottleneck for machine learning practitioners needing accurate model assessment in high-dimensional data, offering a practical solution with theoretical guarantees.
The paper tackles the problem of efficiently approximating leave-one-out cross-validation (LOOCV) in high-dimensional settings, where existing methods fail due to computational and accuracy issues. It shows that one approximation method performs well under sparsity assumptions, with running time and error depending on the small support size rather than the full dimension.
Leave-one-out cross-validation (LOOCV) can be particularly accurate among cross-validation (CV) variants for machine learning assessment tasks -- e.g., assessing methods' error or variability. But it is expensive to re-fit a model $N$ times for a dataset of size $N$. Previous work has shown that approximations to LOOCV can be both fast and accurate -- when the unknown parameter is of small, fixed dimension. But these approximations incur a running time roughly cubic in dimension -- and we show that, besides computational issues, their accuracy dramatically deteriorates in high dimensions. Authors have suggested many potential and seemingly intuitive solutions, but these methods have not yet been systematically evaluated or compared. We find that all but one perform so poorly as to be unusable for approximating LOOCV. Crucially, though, we are able to show, both empirically and theoretically, that one approximation can perform well in high dimensions -- in cases where the high-dimensional parameter exhibits sparsity. Under interpretable assumptions, our theory demonstrates that the problem can be reduced to working within an empirically recovered (small) support. This procedure is straightforward to implement, and we prove that its running time and error depend on the (small) support size even when the full parameter dimension is large.