# On the Iteration Complexity of Hypergradient Computation

arXiv: https://arxiv.org/abs/2006.16218 · HTML: https://mlsanity.com/paper/2006.16218/

## Key facts

- Cited by 155 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 30 of 155)

- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Adversarial Unlearning of Backdoors via Implicit Hypergradient](https://mlsanity.com/paper/2110.03735/) (2021)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Advancing Model Pruning via Bi-level Optimization](https://mlsanity.com/paper/2210.04092/) (2022)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients](https://mlsanity.com/paper/2106.10784/) (2021)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [First-order penalty methods for bilevel optimization](https://mlsanity.com/paper/2301.01716/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweighting](https://mlsanity.com/paper/2406.19976/) (2024)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Stability and Generalization of Bilevel Programming in Hyperparameter Optimization](https://mlsanity.com/paper/2106.04188/) (2021)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [A General Descent Aggregation Framework for Gradient-based Bi-level Optimization](https://mlsanity.com/paper/2102.07976/) (2021)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)

## Abstract (arXiv)

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.