  Many recent advances in machine learning are driven by a challenging
trifecta: large data size $N$; high dimensions; and expensive algorithms. In
this setting, cross-validation (CV) serves as an important tool for model
assessment. Recent advances in approximate cross validation (ACV) provide
accurate approximations to CV with only a single model fit, avoiding
traditional CV's requirement for repeated runs of expensive algorithms.
Unfortunately, these ACV methods can lose both speed and accuracy in high
dimensions -- unless sparsity structure is present in the data. Fortunately,
there is an alternative type of simplifying structure that is present in most
data: approximate low rank (ALR). Guided by this observation, we develop a new
algorithm for ACV that is fast and accurate in the presence of ALR data. Our
first key insight is that the Hessian matrix -- whose inverse forms the
computational bottleneck of existing ACV methods -- is ALR. We show that,
despite our use of the \emph{inverse} Hessian, a low-rank approximation using
the largest (rather than the smallest) matrix eigenvalues enables fast,
reliable ACV. Our second key insight is that, in the presence of ALR data,
error in existing ACV methods roughly grows with the (approximate, low) rank
rather than with the (full, high) dimension. These insights allow us to prove
theoretical guarantees on the quality of our proposed algorithm -- along with
fast-to-compute upper bounds on its error. We demonstrate the speed and
accuracy of our method, as well as the usefulness of our bounds, on a range of
real and simulated data sets.
