mlsanityData to 7 Oct 2026

Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity

arXiv 2302.03407 ↗First posted 7 Feb 2023math.OC cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

Gradient methods have become mainstream techniques for Bi-Level Optimization (BLO) in learning fields. The validity of existing works heavily rely on either a restrictive Lower-Level Strong Convexity (LLSC) condition or on solving a series of approximation subproblems with high accuracy or both. In this work, by averaging the upper and lower level objectives, we propose a single loop Bi-level Averaged Method of Multipliers (sl-BAMM) for BLO that is simple yet efficient for large-scale BLO and gets rid of the limited LLSC restriction. We further provide non-asymptotic convergence analysis of sl-BAMM towards KKT stationary points, and the comparative advantage of our analysis lies in the absence of strong gradient boundedness assumption, which is always required by others. Thus our theory safely captures a wider variety of applications in deep learning, especially where the upper-level objective is quadratic w.r.t. the lower-level variable. Experimental results demonstrate the superiority of our method.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 40 of its 62 references that are in the map. First posted on arXiv 7 Feb 2023.

Builds on

40 of 62 references.

References · 40

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  3. 2019Meta-Learning with Implicit Gradientscited by 523
  4. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  5. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  6. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  7. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  8. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  9. 2016Hyperparameter optimization with approximate gradientcited by 231
  10. 2018Approximation Methods for Bilevel Programmingcited by 231
  11. 2019Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluationcited by 230
  12. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
28 more
  1. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  2. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  3. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  4. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  5. 2019DARTS+: Improved Differentiable Architecture Search with Early Stoppingcited by 105
  6. 2019Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functionscited by 104
  7. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  8. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  9. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  10. 2019Meta-Learning of Neural Architectures for Few-Shot Learningcited by 73
  11. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  12. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  13. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  14. 2021Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyondcited by 62
  15. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  16. 2021A Value-Function-based Interior-point Method for Non-convex Bi-level Optimizationcited by 60
  17. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  18. 2016Connecting Generative Adversarial Networks and Actor-Critic Methodscited by 49
  19. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  20. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  21. 2019Penalty Method for Inversion-Free Deep Bilevel Optimizationcited by 33
  22. 2021A General Descent Aggregation Framework for Gradient-based Bi-level Optimizationcited by 28
  23. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  24. 2020Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guaranteecited by 27
  25. 2022Non-Convex Bilevel Games with Critical Point Selection Mapscited by 25
  26. 2021Value-Function-based Sequential Minimization for Bi-level Optimizationcited by 24
  27. 2020Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functionscited by 13
  28. 2022Optimization-Derived Learning with Essential Convergence Analysis of Training and Hyper-trainingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 8; 2025: 5; 2026: 6.

26 papers.

Sort:

By area:

  1. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  2. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  3. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  4. 2024Functional Bilevel Optimization for Machine Learningcited by 20
  5. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  6. 2024Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategycited by 15
  7. 2023On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Levelcited by 14
  8. 2024Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexitycited by 10
  9. 2024Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimizationcited by 10
  10. 2023A Single-Loop Algorithm for Decentralized Bilevel Optimizationcited by 7
  11. 2023A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Conditioncited by 5
  12. 2024LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspacecited by 4
14 more
  1. 2025A First-order Generative Bilevel Optimization Framework for Diffusion Modelscited by 4
  2. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  3. 2023Adaptive Mirror Descent Bilevel Optimizationcited by 2
  4. 2024Advancing Generalized Transfer Attack with Initialization Derived Bilevel Optimization and Dynamic Sequence Truncationcited by 2
  5. 2025Bi-Level Decision-Focused Causal Learning for Large-Scale Marketing Optimization: Bridging Observational and Experimental Datacited by 2
  6. 2025Multi-Objective Bilevel Learningcited by 2
  7. 2025Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generationcited by 2
  8. 2024Soft-Label Integration for Robust Toxicity Classificationcited by 1
  9. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1
  10. 2026A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimizationcited by 1
  11. 2026DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexitycited by 1
  12. 2026S3LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimizationcited by 0
  13. 2026Learning with Bilevel-Minimax Optimization for Efficient and Reliable Transfer Attackscited by 0
  14. 2026To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationaritycited by 0