# Amortized Implicit Differentiation for Stochastic Bilevel Optimization

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 49 references that are in the map.
- First posted on arXiv 29 Nov 2021.

## Builds on (most cited first, 30 of 30)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Reviving and Improving Recurrent Back-Propagation](https://mlsanity.com/paper/1803.06396/) (2018)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [Super-efficiency of automatic differentiation for functions defined as a minimum](https://mlsanity.com/paper/2002.03722/) (2020)
- [Convergence Properties of Stochastic Hypergradients](https://mlsanity.com/paper/2011.07122/) (2020)
- [Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise](https://mlsanity.com/paper/1901.08788/) (2019)
- [A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encoding](https://mlsanity.com/paper/2006.14859/) (2020)
- [Estimate Sequences for Variance-Reduced Stochastic Composite Optimization](https://mlsanity.com/paper/1905.02374/) (2019)

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

- [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)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [Implicit Diffusion: Efficient Optimization through Stochastic Sampling](https://mlsanity.com/paper/2402.05468/) (2024)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [Achieving Linear Speedup in Non-IID Federated Bilevel Learning](https://mlsanity.com/paper/2302.05412/) (2023)
- [Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start](https://mlsanity.com/paper/2202.03397/) (2022)
- [A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (2023)
- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)
- [Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy](https://mlsanity.com/paper/2405.09927/) (2024)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024)
- [SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning](https://mlsanity.com/paper/2305.19442/) (2023)
- [Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiation](https://mlsanity.com/paper/2302.04969/) (2023)
- [Adaptive Training Distributions with Scalable Online Bilevel Optimization](https://mlsanity.com/paper/2311.11973/) (2023)
- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [Dynamic Gradient Alignment for Online Data Mixing](https://mlsanity.com/paper/2410.02498/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [Differentiable Generalized Sliced Wasserstein Plans](https://mlsanity.com/paper/2505.22049/) (2025)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [A First-order Generative Bilevel Optimization Framework for Diffusion Models](https://mlsanity.com/paper/2502.08808/) (2025)
- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)

## Abstract (arXiv)

We study a class of algorithms for solving bilevel optimization problems in both stochastic and deterministic settings when the inner-level objective is strongly convex. Specifically, we consider algorithms based on inexact implicit differentiation and we exploit a warm-start strategy to amortize the estimation of the exact gradient. We then introduce a unified theoretical framework inspired by the study of singularly perturbed systems (Habets, 1974) to analyze such amortized algorithms. By using this framework, our analysis shows these algorithms to match the computational complexity of oracle methods that have access to an unbiased estimate of the gradient, thus outperforming many existing results for bilevel optimization. We illustrate these findings on synthetic experiments and demonstrate the efficiency of these algorithms on hyper-parameter optimization experiments involving several thousands of variables.