Timezone: »

 
Poster
Implicit differentiation of Lasso-type models for hyperparameter optimization
Quentin Bertrand · Quentin Klopfenstein · Mathieu Blondel · Samuel Vaiter · Alexandre Gramfort · Joseph Salmon

Tue Jul 14 01:00 PM -- 01:45 PM & Wed Jul 15 01:00 AM -- 01:45 AM (PDT) @
in Poster Session 7 »

Setting regularization parameters for Lasso-type estimators is notoriously difficult, though crucial for obtaining the best accuracy. The most popular hyperparameter optimization approach is grid-search on a held-out dataset. However, grid-search requires to choose a predefined grid of parameters and scales exponentially in the number of parameters. Another class of approaches casts hyperparameter optimization as a bi-level optimization problem, typically solved by gradient descent. The key challenge for these approaches is the estimation of the gradient w.r.t. the hyperparameters. Computing that gradient via forward or backward automatic differentiation usually suffers from high memory consumption, while implicit differentiation typically involves solving a linear system which can be prohibitive and numerically unstable. In addition, implicit differentiation usually assumes smooth loss functions, which is not the case of Lasso-type problems. This work introduces an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems. Our proposal scales to high-dimensional data by leveraging the sparsity of the solutions. Empirically, we demonstrate that the proposed method outperforms a large number of standard methods for hyperparameter optimization.

Keywords: Sparsity and Compressed Sensing · Optimization - General

Author Information

Quentin Bertrand (INRIA)
Quentin Klopfenstein (Université de Bourgogne Franche-Comté)
Mathieu Blondel (Google)
Samuel Vaiter (CNRS)
Alexandre Gramfort (Inria)
Joseph Salmon (Université de Montpellier)

More from the Same Authors