# A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima arXiv: https://arxiv.org/abs/2203.01123 ยท HTML: https://mlsanity.com/paper/2203.01123/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 37 references that are in the map. - First posted on arXiv 1 Mar 2022. ## Builds on (most cited first, 27 of 27) - [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018) - [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) - [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015) - [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) - [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018) - [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020) - [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020) - [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016) - [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) - [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019) - [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020) - [Reviving and Improving Recurrent Back-Propagation](https://mlsanity.com/paper/1803.06396/) (2018) - [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017) - [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020) - [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021) - [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021) - [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021) - [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019) - [Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee](https://mlsanity.com/paper/2009.00690/) (2020) - [A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization](https://mlsanity.com/paper/2104.09003/) (2021) ## Built on by (most cited first, 13 of 13) - [First-order penalty methods for bilevel optimization](https://mlsanity.com/paper/2301.01716/) (2023) - [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023) - [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024) - [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023) - [Sharpness-Aware Data Poisoning Attack](https://mlsanity.com/paper/2305.14851/) (2023) - [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024) - [Solving bilevel optimization via sequential minimax optimization](https://mlsanity.com/paper/2511.07398/) (2025) - [Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2511.19656/) (2025) - [Convex and Bilevel Optimization for Neuro-Symbolic Inference and Learning](https://mlsanity.com/paper/2401.09651/) (2024) - [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026) - [Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization](https://mlsanity.com/paper/2405.00914/) (2024) - [Sequential QCQP for Bilevel Optimization with Line Search](https://mlsanity.com/paper/2505.14647/) (2025) - [Fully First-Order Algorithms for Online Bilevel Optimization](https://mlsanity.com/paper/2602.11665/) (2026) ## Abstract (arXiv) Bilevel optimization has found extensive applications in modern machine learning problems such as hyperparameter optimization, neural architecture search, meta-learning, etc. While bilevel problems with a unique inner minimal point (e.g., where the inner function is strongly convex) are well understood, such a problem with multiple inner minimal points remains to be challenging and open. Existing algorithms designed for such a problem were applicable to restricted situations and do not come with a full guarantee of convergence. In this paper, we adopt a reformulation of bilevel optimization to constrained optimization, and solve the problem via a primal-dual bilevel optimization (PDBO) algorithm. PDBO not only addresses the multiple inner minima challenge, but also features fully first-order efficiency without involving second-order Hessian and Jacobian computations, as opposed to most existing gradient-based bilevel algorithms. We further characterize the convergence rate of PDBO, which serves as the first known non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima. Our experiments demonstrate desired performance of the proposed approach.