Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 hyperparam-eter 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 w.r.t. the hyperpa-rameters. 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 Esti-mator (SURE).
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [51 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02532683
Contributor : Quentin Bertrand <>
Submitted on : Sunday, April 5, 2020 - 8:26:13 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:19 PM

File

icml.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02532683, version 1

Citation

Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gramfort, et al.. Implicit differentiation of Lasso-type models for hyperparameter optimization. 2020. ⟨hal-02532683⟩

Share

Metrics

Record views

78

Files downloads

25