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

Abstract

Consider the following class of learning schemes: $$\hat{\mathbf{\beta }}:=\arg \underset{\mathbf{\beta }}{\min }\sum _{j=1}^n\ell ({\mathbf{x}}_j^{\top }\mathbf{\beta };y_j)+\lambda R(\mathbf{\beta }),(1)$$ where ${\mathbf{x}}_i\in {\mathbb{R}}^p$ and $y_i\in \mathbb{R}$ denote the $i^{\text{th}}$ feature and response variable respectively. Let $\ell$ and $R$ be the loss function and regularizer, $\mathbf{\beta }$ denote the unknown weights, and $\lambda$ be a regularization parameter. Finding the optimal choice of $\lambda$ is a challenging problem in high-dimensional regimes where both $n$ and $p$ are large. We propose two frameworks to obtain a computationally efficient approximation ALO 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 (1). We prove the equivalence of the two approaches under smoothness conditions. This equivalence enables us to justify the accuracy of both methods under such conditions. We use our approaches to obtain a risk estimate for several standard problems, including generalized LASSO, nuclear norm regularization, and support vector machines. We empirically demonstrate the effectiveness of our results for non-differentiable cases.

arXiv commentThe paper is published on ICML 2018

References in corpus (6)

• Scikit-learn: Machine Learning in Python
• Message Passing Algorithms for Compressed Sensing
• On the "degrees of freedom" of the lasso
• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
• A scalable estimate of the extra-sample prediction error via approximate leave-one-out

Cited by in corpus (10)

• Asymptotics of Cross-Validation
• On the interplay between noise and curvature and its effect on optimization and generalization
• Extrapolated cross-validation for randomized ensembles
• Approximate Cross-Validation for Structured Models
• Automatic Hyperparameter Tuning in Sparse Matrix Factorization
• Approximate Cross-validated Mean Estimates for Bayesian Hierarchical Regression Models
• A Mean-Field Theory for Kernel Alignment with Random Features in Generative and Discriminative Models
• A Distributionally Robust Optimization Method for Adversarial Multiple Kernel Learning
• Accelerating Cross-Validation in Multinomial Logistic Regression with ${\ell }_1$-Regularization
• Approximate Cross-validation: Guarantees for Model Assessment and Selection