Optimal Cross-Validation for Sparse Linear Regression
This work addresses a computational bottleneck for practitioners using sparse regression, though it is incremental as it builds on existing methods.
The paper tackles the computational burden of cross-validation in sparse linear regression by deriving tractable relaxations that reduce the number of mixed-integer optimization problems by 50-80%, and shows that exact cross-validation can be competitive with existing software like glmnet and L0Learn on real-world datasets.
Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To choose hyperparameters that control the sparsity level and amount of regularization, practitioners commonly use k-fold cross-validation. However, cross-validation substantially increases the computational cost of sparse regression as it requires solving many mixed-integer optimization problems (MIOs) for each hyperparameter combination. To address this computational burden, we derive computationally tractable relaxations of the k-fold cross-validation loss, facilitating hyperparameter selection while solving $50$--$80\%$ fewer MIOs in practice. Our computational results demonstrate, across eleven real-world UCI datasets, that exact MIO-based cross-validation can be competitive with mature software packages such as glmnet and L0Learn -particularly when the sample-to-feature ratio is small.