UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On the Iteration Complexity of Hypergradient Computation

Grazzi, R; Franceschi, L; Pontil, M; Salzo, S; (2020) On the Iteration Complexity of Hypergradient Computation. In: Daumé III, H and Singh, A, (eds.) Proceedings of the 37th International Conference on Machine Learning. (pp. pp. 3706-3716). Proceedings of Machine Learning Research (PMLR): Virtual conference. Green open access

[thumbnail of grazzi20a.pdf]
Preview
Text
grazzi20a.pdf - Published version

Download (3MB) | Preview

Abstract

We study a general class of bilevel problems, consisting in the minimization of an upper-level objective which depends on the solution to a parametric fixed-point equation. Important instances arising in machine learning include hyperparameter optimization, meta-learning, and certain graph and recurrent neural networks. Typically the gradient of the upper-level objective (hypergradient) is hard or even impossible to compute exactly, which has raised the interest in approximation methods. We investigate some popular approaches to compute the hypergradient, based on reverse mode iterative differentiation and approximate implicit differentiation. Under the hypothesis that the fixed point equation is defined by a contraction mapping, we present a unified analysis which allows for the first time to quantitatively compare these methods, providing explicit bounds for their iteration complexity. This analysis suggests a hierarchy in terms of computational efficiency among the above methods, with approximate implicit differentiation based on conjugate gradient performing best. We present an extensive experimental comparison among the methods which confirm the theoretical findings.

Type: Proceedings paper
Title: On the Iteration Complexity of Hypergradient Computation
Event: 37th International Conference on Machine Learning
Open access status: An open access version is available from UCL Discovery
Publisher version: http://proceedings.mlr.press/v119/grazzi20a.html
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10128628
Downloads since deposit
6Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item