mlsanityData to 7 Oct 2026

Provably Faster Algorithms for Bilevel Optimization

arXiv 2106.04692 ↗First posted 8 Jun 2021cs.LG math.OC stat.MLcited by 106

Not on the map. Why?

Abstract (arXiv)

Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve bilevel optimization problems faster. However, those momentum-based algorithms do not achieve provably better computational complexity than widetilde O(ε-2) of the SGD-based algorithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the variance. We show that both algorithms achieve the complexity of widetilde O(ε-1.5), which outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.

Key facts. Cited by 106 papers in the map (data through 7 Oct 2026). Builds on 23 of its 41 references that are in the map. First posted on arXiv 8 Jun 2021.

Builds on

23 of 41 references.

References · 23

  1. 2019Meta-Learning with Implicit Gradientscited by 523
  2. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  3. 2018Meta-learning with differentiable closed-form solverscited by 395
  4. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  8. 2016Hyperparameter optimization with approximate gradientcited by 231
  9. 2018Approximation Methods for Bilevel Programmingcited by 231
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  11. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  12. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
11 more
  1. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 108
  2. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  3. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  4. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  5. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  6. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  7. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  8. 2018A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimizationcited by 33
  9. 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 31
  10. 2020Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learningcited by 28
  11. 2018SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithmscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 28; 2023: 27; 2024: 17; 2025: 16; 2026: 10.

106 papers.

Sort:

By area:

  1. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  2. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  3. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 97
  4. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  5. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  6. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  7. 2023First-order penalty methods for bilevel optimizationcited by 40
  8. 2023An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learningcited by 39
  9. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  10. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  11. 2024ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweightingcited by 35
  12. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
38 more
  1. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 33
  2. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  3. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  4. 2022On Implicit Bias in Overparameterized Bilevel Optimizationcited by 30
  5. 2025PR-Attack: Coordinated Prompt-RAG Attacks on Retrieval-Augmented Generation in Large Language Models via Bilevel Optimizationcited by 29
  6. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  7. 2022Betty: An Automatic Differentiation Library for Multilevel Optimizationcited by 27
  8. 2022Gradient-based Bi-level Optimization for Deep Learning: A Surveycited by 26
  9. 2024Implicit Diffusion: Efficient Optimization through Stochastic Samplingcited by 22
  10. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  11. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  12. 2022Local Stochastic Bilevel Optimization with Momentum-Based Variance Reductioncited by 20
  13. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  14. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  15. 2022Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-startcited by 17
  16. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  17. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
  18. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  19. 2024Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomycited by 16
  20. 2024Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysiscited by 15
  21. 2022On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Networkcited by 14
  22. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 14
  23. 2022Mitigating Gradient Bias in Multi-objective Learning: A Provably Convergent Stochastic Approachcited by 14
  24. 2023On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Levelcited by 14
  25. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  26. 2023Contextual Stochastic Bilevel Optimizationcited by 14
  27. 2023RedCore: Relative Advantage Aware Cross-modal Representation Learning for Missing Modalities with Imbalanced Missing Ratescited by 14
  28. 2022Is Bayesian Model-Agnostic Meta Learning Better than Model-Agnostic Meta Learning, Provably?cited by 13
  29. 2022Asynchronous Distributed Bilevel Optimizationcited by 13
  30. 2023Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiationcited by 13
  31. 2023Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problemcited by 13
  32. 2022A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minimacited by 12
  33. 2022Communication-Efficient Robust Federated Learning with Noisy Labelscited by 11
  34. 2021Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problemscited by 10
  35. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  36. 2024First-Order Methods for Linearly Constrained Bilevel Optimizationcited by 10
  37. 2024An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothnesscited by 9
  38. 2024Bayesian Experimental Design via Contrastive Diffusionscited by 9

50 most cited of 106 All 106 (JSON)