Technical Summary: Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

Problem Formulation

This paper addresses a class of bilevel optimization problems where both the upper-level and lower-level problems exhibit minimax structures. The general formulation is defined as:
$$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$$
where $(y_1, y_2)$ represents a saddle-point of the lower-level function $\tilde{f}$. The authors assume specific structural properties: $f$ and $\tilde{f}$ can be decomposed into smooth components and proper closed convex functions, with specific convexity/concavity properties regarding their respective variables (e.g., $\tilde{f}$ is convex in $y_1$ and concave in $y_2$).

A significant subset of this work focuses on bilevel problems where the lower-level is a convex minimization problem with convex nonlinear inequality constraints:
$$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$$
Under Slater's condition, this constrained problem is reformulated as a special case of the general minimax bilevel framework via Lagrangian duality.

Existing literature largely focuses on bilevel optimization where the lower-level is a single-objective minimization (often strongly convex). Methods relying on hypergradients or implicit differentiation often fail when the lower-level is merely convex, non-convex, or possesses a minimax structure. This work aims to fill the gap by developing first-order methods for the minimax lower-level setting without requiring strong convexity.

Methodology

The proposed approach utilizes a value-function penalty reformulation. The constrained bilevel problem is transformed into an unconstrained (or simpler constrained) minimax problem by introducing a penalty parameter $\rho$.

Deterministic Setting

1. Penalty Reformulation: The original problem is reformulated into a single-level minimax problem:
   $$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$$
   where $P_\rho$ incorporates the objective function and the penalty term $\rho(p(x_1, y_1) - d(x_1, y_2))$, representing the duality gap of the lower-level problem.
2. Algorithm: The authors propose an inexact proximal point method. The outer loop updates the primal-dual variables by solving a sequence of strongly-convex-strongly-concave (SCSC) subproblems.
3. Subproblem Solver: Each subproblem is solved using an optimal first-order method (specifically, a variant of the method by Lu and Mei [52] or Kovalev and Gasnikov [37]), denoted as OptFOM.
4. Complexity: The method finds an $\epsilon$-KKT point with an oracle complexity of $\tilde{O}(\epsilon^{-4})$.

Stochastic Setting

When only stochastic gradient oracles are available for the smooth components:

1. Algorithm: The deterministic proximal point method is adapted to use a Stochastic Accelerated Primal-Dual (SAPD) method (specifically SAPD+ by Zhang et al. [75]) to solve the inner subproblems.
2. Convergence: The method finds a "nearly" $\epsilon$-KKT point (where the solution is within $\epsilon$ distance of an exact $\epsilon$-KKT point) with a stochastic oracle complexity of $\tilde{O}(\epsilon^{-9})$.

Application to Constrained Lower-Level Problems

For the specific case of bilevel optimization with a constrained convex lower-level (Problem 4), the authors show that under Slater's condition, the Lagrange multipliers are bounded within a box $[0, B]^l$. This allows the constrained problem to be reformulated as the general minimax bilevel problem (Problem 1) by introducing the dual variables as explicit optimization variables with box constraints. This reformulation avoids the need for an inner penalty parameter, leading to improved complexity bounds compared to prior work.

Key Contributions

1. First Complexity Results for Bilevel Minimax: The paper establishes the first complexity bounds for deterministic and stochastic first-order methods for bilevel optimization where the lower-level is a minimax problem.
   • Deterministic complexity: $\tilde{O}(\epsilon^{-4})$.
   • Stochastic complexity: $\tilde{O}(\epsilon^{-9})$.
2. Improved Bounds for Constrained Bilevel Problems: By reformulating bilevel problems with convex constrained lower-levels as instances of the proposed minimax framework, the authors achieve a complexity of $\tilde{O}(\epsilon^{-4})$. This improves upon existing results for merely convex lower-levels ($\tilde{O}(\epsilon^{-7})$ in [53]) and strongly convex lower-levels ($\tilde{O}(\epsilon^{-6})$ in [51]). The improvement stems from avoiding the use of a second penalty parameter for the inner constraints, which previously led to higher smoothness parameters.
3. Empirical Validation:
   • Synthetic Data: On constrained linear bilevel problems, the proposed method demonstrates competitive convergence speeds against existing penalty-based methods (FOP and SMO), particularly when the Lipschitz constant is tuned.
   • Real-World Application: The method is applied to hyperparameter tuning for Distributionally Robust Optimization (DRO) in deep learning. On the CelebA and Waterbirds datasets, the proposed stochastic bilevel approach outperforms standard DRO methods in terms of worst-group accuracy while maintaining comparable average accuracy.

Results and Significance

The paper claims that the proposed penalty-based framework provides a unified approach to handling bilevel problems with minimax structures, a setting previously unexplored in the literature regarding first-order complexity.

• Theoretical Significance: The work bridges the gap between bilevel optimization and minimax optimization, providing rigorous convergence guarantees without relying on strong convexity assumptions for the lower-level problem. The reduction of complexity from $\tilde{O}(\epsilon^{-7})$ to $\tilde{O}(\epsilon^{-4})$ for constrained lower-levels is presented as a significant theoretical advancement.
• Practical Significance: The application to DRO demonstrates the utility of the method in machine learning scenarios involving distribution shifts and group fairness. The results on the CelebA and Waterbirds datasets show that the method can effectively handle the "worst-group" optimization challenge, achieving higher worst-group accuracy than baseline DRO methods.

The authors acknowledge limitations, including the requirement for compact feasible domains, the use of a lifted space for KKT definitions, and the high complexity of the stochastic case ($\tilde{O}(\epsilon^{-9})$), noting that variance reduction techniques could be a direction for future work.