mlsanityData to 14 Oct 2026

Solving bilevel optimization via sequential minimax optimization

arXiv 2511.07398 ↗First posted 10 Nov 2025math.OC cs.LG cs.NAcited by 3

Not on the map. Why?

Abstract (arXiv)

In this paper we propose a sequential minimax optimization (SMO) method for solving a class of constrained bilevel optimization problems in which the lower-level part is a possibly nonsmooth convex optimization problem, while the upper-level part is a possibly nonconvex optimization problem. Specifically, SMO applies a first-order method to solve a sequence of minimax subproblems, which are obtained by employing a hybrid of modified augmented Lagrangian and penalty schemes on the bilevel optimization problems. Under suitable assumptions, we establish an operation complexity of O(varepsilon-7logvarepsilon-1) and O(varepsilon-6logvarepsilon-1), measured in terms of fundamental operations, for SMO in finding an varepsilon-KKT solution of the bilevel optimization problems with merely convex and strongly convex lower-level objective functions, respectively. The latter result improves the previous best-known operation complexity by a factor of varepsilon-1. Preliminary numerical results demonstrate significantly superior computational performance compared to the recently developed first-order penalty method.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 42 of its 81 references that are in the map. First posted on arXiv 10 Nov 2025.

Builds on

42 of 81 references.

References · 42

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2017Gradient Episodic Memory for Continual Learningcited by 1,898
  4. 2018DARTS: Differentiable Architecture Searchcited by 1,798
  5. 2019Meta-Learning with Implicit Gradientscited by 525
  6. 2018Meta-learning with differentiable closed-form solverscited by 397
  7. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
  8. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  9. 2016Hyperparameter optimization with approximate gradientcited by 233
  10. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  11. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  12. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 153
30 more
  1. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  2. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 129
  3. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  4. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  5. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  6. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
  7. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  8. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  9. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  10. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  11. 2023First-order penalty methods for bilevel optimizationcited by 41
  12. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 33
  13. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  14. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  15. 2021Bilevel methods for image reconstructioncited by 20
  16. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  17. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  18. 2021Difference of convex algorithms for bilevel programs with applications in hyperparameter selectioncited by 17
  19. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  20. 2022A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minimacited by 13
  21. 2024Overcoming Lower-Level Constraints in Bilevel Optimization: A Novel Approach with Regularized Gap Functionscited by 12
  22. 2022An Improved Unconstrained Approach for Bilevel Optimizationcited by 11
  23. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  24. 2018Iteration complexity of first-order augmented Lagrangian methods for convex conic programmingcited by 7
  25. 2020Optimality Conditions for Constrained Minimax Optimizationcited by 6
  26. 2019Constraint qualifications and optimality conditions in bilevel optimizationcited by 5
  27. 2023A novel approach for bilevel programs based on Wolfe dualitycited by 5
  28. 2022Optimality Conditions and Numerical Algorithms for A Class of Linearly Constrained Minimax Optimization Problemscited by 4
  29. 2023Effective Bilevel Optimization via Minimax Reformulationcited by 3
  30. 2021Combined approach with second-order optimality conditions for bilevel programming problemscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  2. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1
  3. 2026Learning the Robustness Mechanism with Bilevel Optimizationcited by 0