mlsanityData to 14 Oct 2026

Amortized Implicit Differentiation for Stochastic Bilevel Optimization

arXiv 2111.14580 ↗First posted 29 Nov 2021math.OC cs.LGcited by 63

Not on the map. Why?

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.

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

30 of 49 references.

References · 30

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2015Automatic differentiation in machine learning: a surveycited by 855
  3. 2019Meta-Learning with Implicit Gradientscited by 525
  4. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  5. 2018Meta-learning with differentiable closed-form solverscited by 397
  6. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  7. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 304
  8. 2018Approximation Methods for Bilevel Programmingcited by 236
  9. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  10. 2016Hyperparameter optimization with approximate gradientcited by 233
  11. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  12. 2021Efficient and Modular Implicit Differentiationcited by 203
18 more
  1. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
  2. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  3. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  4. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 153
  5. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 112
  6. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  7. 2018Reviving and Improving Recurrent Back-Propagationcited by 69
  8. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  9. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  10. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  11. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  12. 2018Subgradient methods for sharp weakly convex functionscited by 33
  13. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 32
  14. 2020Super-efficiency of automatic differentiation for functions defined as a minimumcited by 24
  15. 2020Convergence Properties of Stochastic Hypergradientscited by 19
  16. 2019Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noisecited by 9
  17. 2020A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encodingcited by 4
  18. 2019Estimate Sequences for Variance-Reduced Stochastic Composite Optimizationcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 14; 2024: 19; 2025: 10; 2026: 14.

63 papers.

Sort:

By area:

  1. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  2. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  3. 2022Tutorial on amortized optimizationcited by 83
  4. 2023An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learningcited by 41
  5. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  6. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  7. 2023Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexitycited by 26
  8. 2024Implicit Diffusion: Efficient Optimization through Stochastic Samplingcited by 24
  9. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  10. 2024Functional Bilevel Optimization for Machine Learningcited by 20
  11. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  12. 2022Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-startcited by 17
38 more
  1. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
  2. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  3. 2024Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategycited by 16
  4. 2024Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomycited by 16
  5. 2024Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysiscited by 15
  6. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  7. 2023Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiationcited by 13
  8. 2023Adaptive Training Distributions with Scalable Online Bilevel Optimizationcited by 11
  9. 2024Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexitycited by 10
  10. 2024Dynamic Gradient Alignment for Online Data Mixingcited by 10
  11. 2024A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothnesscited by 7
  12. 2025Differentiable Generalized Sliced Wasserstein Planscited by 7
  13. 2023A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Conditioncited by 5
  14. 2024Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysiscited by 5
  15. 2024LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspacecited by 4
  16. 2025A First-order Generative Bilevel Optimization Framework for Diffusion Modelscited by 4
  17. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  18. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 3
  19. 2022A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programmingcited by 2
  20. 2023Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimizationcited by 2
  21. 2024Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Ratescited by 2
  22. 2025qNBO: quasi-Newton Meets Bilevel Optimizationcited by 2
  23. 2025Learning Theory for Kernel Bilevel Optimizationcited by 2
  24. 2025Multi-Objective Bilevel Learningcited by 2
  25. 2025Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generationcited by 2
  26. 2026Non-Stationary Functional Bilevel Optimizationcited by 2
  27. 2026SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimizationcited by 2
  28. 2023Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learningcited by 1
  29. 2024Functionally Constrained Algorithm Solves Convex Simple Bilevel Problemscited by 1
  30. 2024Fully First-Order Methods for Decentralized Bilevel Optimizationcited by 1
  31. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  32. 2024Exploring the Generalization Capabilities of AID-based Bi-level Optimizationcited by 1
  33. 2024Learning Set Functions with Implicit Differentiationcited by 1
  34. 2026Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementationcited by 1
  35. 2026Efficient Bilevel Optimization with KFAC-Based Hypergradientscited by 1
  36. 2026A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimizationcited by 1
  37. 2023Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimizationcited by 0
  38. 2023A Challenge in Reweighting Data with Bilevel Optimizationcited by 0

50 most cited of 63 All 63 (JSON)