Enhancing Hypergradients Estimation: A Study of Preconditioning and
  Reparameterization
Zhenzhang Ye Gabriel Peyré Daniel Cremers Pierre Ablin
Bilevel optimization aims to optimize an outer objective function that
depends on the solution to an inner optimization problem. It is routinely used
in Machine Learning, notably for hyperparameter tuning. The conventional method
to compute the so-called hypergradient of the outer problem is to use the
Implicit Function Theorem (IFT). As a function of the error of the inner
problem resolution, we study the error of the IFT method. We analyze two
strategies to reduce this error: preconditioning the IFT formula and
reparameterizing the inner problem. We give a detailed account of the impact of
these two modifications on the error, highlighting the role played by
higher-order derivatives of the functionals at stake. Our theoretical findings
explain when super efficiency, namely reaching an error on the hypergradient
that depends quadratically on the error on the inner problem, is achievable and
compare the two approaches when this is impossible. Numerical evaluations on
hyperparameter tuning for regression problems substantiate our theoretical
findings.