Solving bilevel optimization via sequential minimax optimization
This addresses optimization challenges in machine learning and operations research by providing a more efficient algorithm for bilevel problems, though it is incremental as it builds on existing methods with specific improvements.
The paper tackles constrained bilevel optimization problems with nonsmooth convex lower-level and nonconvex upper-level parts by proposing a sequential minimax optimization method, achieving operation complexities of O(ε^{-7}logε^{-1}) and O(ε^{-6}logε^{-1}) for ε-KKT solutions, with the latter improving prior results by a factor of ε^{-1} and showing superior computational performance in preliminary tests.
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.