Out-of-sample risk estimation in no time flat

Oregon Convention Center 

Hyperparameter tuning is an essential part of statistical machine learning pipelines, and becomes more computationally challenging as datasets become large. Furthermore, the standard method of k-fold cross-validation is known to be inconsistent for high-dimensional problems. We propose instead an efficient implementation of approximate leave-one-out (ALO) risk estimation, providing consistent risk estimation in high-dimensions at a fraction of the cost of k-fold cross-validation. We leverage randomized numerical linear algebra and reduce the computational task to a handful of quasisemidefinite linear systems, equivalent to equality-constrained quadratic programs, for any convex non-smooth loss and linear-separable regularizer.

Risk estimation

Cross-validation

High dimensions

Convex optimization

Randomized methods 

Section on Statistical Learning and Data Science