Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions

Published in INFORMS Data Mining and Decision Analysis Workshop, 2019

Recommended citation: Wenda Zhou, Shuaiwen Wang, Peng Xu, Haiho Lu, Arian Maleki, Vahab Mirrokni. "Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions." 2019 INFORMS Workshop on Data Mining and Decision Analytics. Oct 2019.

[Download] [R Package]

(Runner-up of the Best Paper Competition, Theoretical Track)

Abstract

Consider the class of learning schemes which is composed of a sum of losses over every data point and a regularizer that imposes special structures on the model parameter and controls the model complexity. A tuning parameter, typically adjusting the amount of regularization, is necessary for this framework to work well. Finding the optimal tuning is a challenging problem in high-dimensional regimes where both the sample size and the dimension of the parameter space are large. We propose two frameworks to obtain a computationally efficient approximation of the leave-one-out cross validation (LOOCV) risk for nonsmooth losses and regularizers. Our two frameworks are based on the primal and dual formulations of the aforementioned learning scheme. We then prove the equivalence of the two approaches under smoothness conditions. This equivalence enables us to justify the accuracy of both methods under such conditions. Finally we apply our approaches to several standard problems, including generalized LASSO and support vector machines, and empirically demonstrate the effectiveness of our results.