Solving bilevel optimization via sequential minimax optimization

• URL: http://arxiv.org/abs/2511.07398v1
• Date: Mon, 10 Nov 2025 18:51:05 GMT
• Title: Solving bilevel optimization via sequential minimax optimization
• Authors: Zhaosong Lu, Sanyou Mei,
• Abstract summary: We study a class of constrained bilevel optimization problems in which the part is a possibly non-smooth convex part.<n>We find that the SMO method improves the complexity of the lower-level objective functions.<n>Preliminary results compare to the recently developed first-order penalty performance.
• Score: 2.735801286587348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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^{-7}\log\varepsilon^{-1})$ and $O(\varepsilon^{-6}\log\varepsilon^{-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.

Related papers

• Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
  Bilevel optimization is widely applied in many machine learning tasks such as hyper learning, meta learning and reinforcement learning. We propose an efficient Hessian/BiO method with the optimal convergence $frac1TT) under some mild conditions. We conduct some some experiments on the bilevel game hyper-stationary numerical convergence.
  arXiv  Detail & Related papers  (2024-07-25T07:25:06Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem. We measure the performance of our method in terms of suboptimality and infeasibility errors.
  arXiv  Detail & Related papers  (2024-02-12T22:34:53Z)
• First-order penalty methods for bilevel optimization [1.2691047660244337]
  We show a class of $varepsilon$ complexity solution for unconstrained and constrained bilevel optimization problems. We also propose first-order penalty methods for finding an $epsilon$KKT solution of the unconstrained and constrained bilevel problems.
  arXiv  Detail & Related papers  (2023-01-04T17:29:04Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of emphconcave unconstrained problems.<n>Our method improves the existing line-search-based min-max optimization by shaving off an $O(loglog(1/eps)$ factor in the required number of Schur decompositions.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem [18.15207779559351]
  We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane. Our method achieves best-known assumption for the considered class of bilevel problems.
  arXiv  Detail & Related papers  (2022-06-17T16:12:47Z)
• Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient [0.0]
  We first consider unconstrained convex optimization with Lipschitz continuous gradient (LLCG) and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG methods are equipped with a verifiable termination criterion and enjoy an operation complexity of $cal O(varepsilon-1/2log varepsilon-1)$. Preliminary numerical results are presented to demonstrate the performance of our proposed methods.
  arXiv  Detail & Related papers  (2022-06-02T10:34:26Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  Bilevel optimization is one of the problems in machine learning. Recent developments in bilevel optimization converge on the first fundamental nonaptature multi-step analysis.
  arXiv  Detail & Related papers  (2022-02-08T07:10:06Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. We show that our results are more challenging than that of minimax applications.
  arXiv  Detail & Related papers  (2021-02-07T21:46:29Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.