Fast Partition-Based Cross-Validation With Centering and Scaling for XTX and XTY

We present algorithms that substantially accelerate partition-based cross-validation for machine learning models that require matrix products XTX and XTY. Our algorithms have applications in model selection for, for example, principal component analysis (PCA), principal component regression (PCR), ridge regression (RR), ordinary least squares (OLS), and partial least squares (PLS). Our algorithms support all combinations of column-wise centering and scaling of X and Y, and we demonstrate in our accompanying implementation that this adds only a manageable, practical constant over efficient variants without preprocessing. We prove the correctness of our algorithms under a fold-based partitioning scheme and show that the running time is independent of the number of folds; that is, they have the same time complexity as that of computing XTX and XTY and space complexity equivalent to storing X, Y, XTX, and XTY. Importantly, unlike alternatives found in the literature, we avoid data leakage due to preprocessing. We achieve these results by eliminating redundant computations in the overlap between training partitions. Concretely, we show how to manipulate XTX and XTY using only samples from the validation partition to obtain the preprocessed training partition-wise XTX and XTY. To our knowledge, we are the first to derive correct and efficient cross-validation algorithms for any of the 16 combinations of column-wise centering and scaling, for which we also prove only 12 give distinct matrix products.