Implicit differentiation of Lasso-type models for hyperparameter optimization

Abstract

Setting regularization parameters for Lasso-type estimators is notoriously difficult, though crucial in practice. The most popular hyperparameter optimization approach is grid-search using held-out validation data. Grid-search however requires to choose a predefined grid for each parameter, which scales exponentially in the number of parameters. Another approach is to cast hyperparameter optimization as a bi-level optimization problem, one can solve by gradient descent. The key challenge for these methods is the estimation of the gradient with respect to the hyperparameters. Computing this gradient via forward or backward automatic differentiation is possible yet usually suffers from high memory consumption. Alternatively implicit differentiation typically involves solving a linear system which can be prohibitive and numerically unstable in high dimension. In addition, implicit differentiation usually assumes smooth loss functions, which is not the case for Lasso-type problems. This work introduces an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems. Our approach scales to high-dimensional data by leveraging the sparsity of the solutions. Experiments demonstrate that the proposed method outperforms a large number of standard methods to optimize the error on held-out data, or the Stein Unbiased Risk Estimator (SURE).

References in corpus (12)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Nearly unbiased variable selection under minimax concave penalty
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• On the "degrees of freedom" of the lasso
• Task-Driven Dictionary Learning
• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Differentiable Convex Optimization Layers
• Maximal Sparsity with Deep Networks?
• A Regularized Framework for Sparse and Structured Neural Attention
• Optimizing Millions of Hyperparameters by Implicit Differentiation
• Critical Hyper-Parameters: No Random, No Cry
• Dual Extrapolation for Sparse Generalized Linear Models

Cited by in corpus (10)

• Efficient and Modular Implicit Differentiation
• Nonsmooth Implicit Differentiation for Machine Learning and Optimization
• Model identification and local linear convergence of coordinate descent
• Anderson acceleration of coordinate descent
• One-step differentiation of iterative algorithms
• Muddling Labels for Regularization, a novel approach to generalization
• Learning to solve TV regularized problems with unrolled algorithms
• Cost-Efficient Online Hyperparameter Optimization
• On the complexity of nonsmooth automatic differentiation
• Optimizing generalization on the train set: a novel gradient-based framework to train parameters and hyperparameters simultaneously