A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints

Summary

This works addresses a bilevel problem where the lower-level has constraints that couple both the upper- and lower-level variables. The proposed method leverages a penalty approach and Lagrangian duality theory that transform the original bilevel problem into a single-level minimization problem where the x and y variables are decoupled. A first-order algorithm is developed which relies on the solution of two min-max subproblems and a rigorous convergence theory is developed. The effectiveness of the proposed method is validated on two real-world applications: infrastructure planning in transportation networks and support vector machine model training.

Strengths

* This works deals with a challenging bilevel problem, as not only the lower-level is constrained, but in fact these constraints couple both the upper- and lower-level variables. * The proposed algorithm is first-order, even though the problem is a challenging one due to the presence of coupled constraints in the lower-level. In contrast, methods relying on implicit gradients, regardless if the problem is constrained or not, usually require access to second-order information. * Evaluation of the BLOCC algorithm on both toy examples and real-world applications (SVM model training and Transportation network design).

Weaknesses

* Lemmas 2 and 3, which derive some key properties of the inner min-max problems, assume that the Lagrangian multipliers are bounded for every $x \in X$. This is not a common assumption in literature and thus I am not sure why it is seen as mild. The authors cite Theorem 1.6 from [30] as a justification, however it is not immediately clear how the bounded property follows from that theorem. In fact, Theorem 1.6 is written for a more general (abstract) setting. As this is an important point, I think the authors should explain this in more detail. They might even include the theorem (or perhaps a different version of the theorem, tailored to the specific setting of this problem) in the Appendix and provide a clearer explanation. * Requires the solution of two min-max subproblems where the solution of each subproblem requires a double-loop algorithm. As a result, the proposed BLOCC method is a triple loop algorithm. On the contrary, most hypergradient methods rely only on the solution of a minimization problem (the lower problem). * The convergence result requires additional assumptions (assumption 5) beyond the ones concerning the objectives ($f,g$) and the constraints ($g_{c}$) of the original bilevel problem. It is unclear how restrictive assumption 5 is, as it is not expressed directly over $f,g,g_c$, but rather over some dual function. On the other hand, at least from the perspective of the dual function, the assumption is mild as the dual function is already concave.

Questions

* Can you elaborate on Assumption 3? What do you mean by saying that $g^{c}$ satisfies the LICQ in $y$? Does this mean that for a given x the LICQ holds: a) for every $y \in Y(x)$ or b) for every KKT point $y^{*}(x)$ of the lower-level problem? * Do the Assumptions 1-5 and the conditions within the theorems hold in the bilevel problems of the experiments (SVM model training and Transportation network design)? * Typos * In equation (7): the + symbol is misplaced * In the proof of Lemma 10 in page 17: in the formula of $\nabla u_{h}(x)$ we should have $\nabla h^{c}$ instead of $h^{c}$

Rating

5

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

No negative societal impact.

Summary

This paper proposes an algorithm named BLOCC for solving a particular class of bilevel optimization problems where so-called coupled constraints are present. Coupled constraints are constraints w.r.t. the upper and lower level variables which are applied in addition to simple constraints like bound/ball constraints which are easy to solve for. Bilevel problems with coupled constraints have not been addressed in prior works in this literature, which rely on solving the inner problem and using the implicit function theorem (IFT) to pass gradients through the inner problem. BLOCC is particular suited for extremely large-scale optimization problems where other existing approaches which use IFT are intractable to solve due to the size of the KKT systems of the inner problems. Notably, BLOCC avoids solving the inner problem directly, instead replacing the inner problem with a simpler problem which only involves the simple constraints (and can be solved with a fast projection instead of requiring an iterative method). The coupled constraint is moved to the objective function of the outer problem, which is also modified as a result to be a saddle point problem. A custom first-order min-max solver is proposed to solve the outer problem and is an additional contribution of the paper. The convergence properties of the algorithm is established, along with equivalence of the penalty reformulation to the original bilevel problem and BLOCC is evaluated on some interesting bilevel optimization problems against related methods. Particularly appealing are the extremely large-scale transportation network design experiments.

Strengths

The proposed method handles a broader range of bilevel problems compared to prior works in this literature, i.e., large-scale problems with coupled constraints in the inner problem. The characteristics of the algorithm itself (projection free, first-order only) are appealing. Furthermore, a reasonably detailed convergence analysis for all components of the algorithm are provided. The technical writing overall is of a reasonably high quality. Finally, the large-scale experiments for the network planning setting help demonstrate that BLOCC is useful to solve large-scale problems in practice which are currently unattainable by methods which use implicit function theorem.

Weaknesses

The main weakness in the paper in my mind is the statement of contribution, it was not immediately obvious why BLOCC is necessary on the first read-through. Only after reading the experimental section did I realize the importance of the algorithm design for large-scale problems. As a more concrete suggestion, I think contextualising this work in the broader bi-level optimization literature would be beneficial. For instance, the value function reformulation (see [1] for example) is another way to solve an arguably broader class of optimization problems. However, I can see why directly solving the resultant single level problem may be computationally intractable for very large-scale problems using standard solvers, which motivates BLOCC. I would suggest referencing that literature better and emphasizing why the algorithmic properties of BLOCC enable application to large-scale bi-level problems earlier in the paper. I also think more analysis around the comparison methods LV-HBA and GAM for the large-scale problem in 4.3 is required. For instance, line 330-331 states that for GAM a Hessian must be inverted (presumably as part of using the IFT and differentiating through the inner problem). However, the actual linear system of equations may be solved using something more scalable such as conjugate gradient, which may permit the IFT methods to perform reasonably on this task. Some discussion or a direct comparison would greatly improve the experimental section in the paper. Finally, a more detailed description of GAM and LV-HBA would be helpful to better understand the differences to BLOCC. For instance, it is claimed that LV-HBA projection steps are expensive, however looking at their paper it seems that the projection is a fairly simple operation (Proj_Z defined in section 2.3 in their paper)? Adding this information will make the paper more self-contained. [1] Sinha et al. Bilevel Optimization based on Kriging Approximations of Lower Level Optimal Value Function. (2018 IEEE Congress on Evolutionary Computation)

Questions

How easy/robust is the tuning of the penalty parameters? Typically you just have a set of constraints for a problem. What is the significance of decoupling the inner problem into two sets of constraints, i.e., g^c and \mathcal{Y}(x)? This appears to be a quirk of this literature and not say something like [1]. [1] Sinha et al. Bilevel Optimization based on Kriging Approximations of Lower Level Optimal Value Function. (2018 IEEE Congress on Evolutionary Computation)

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

I believe there is a general lack of discussion of limitations in this paper. It would be nice to understand at the least which parameters are difficult to tune.

Summary

The paper proposed a fully first-order algorithm named BLOCC for the bilevel optimization problems with lower level coupled constraints. They provide convergence theory for the algorithm and demonstrate its effectiveness through numerical experiments in SVM-based model training and infrastructure planning in transportation networks.

Strengths

This paper designs a first-order algorithm for bilevel programming problems with coupling constraints in the lower level, and it does not require joint projection operations. The effectiveness of the algorithm is validated through extensive experiments. The writing is clear and well-structured.

Weaknesses

1. This paper relies on some restrictive assumptions compared to other works, such as the strong convexity of both lower level objective $g$ and constraint $g^c$ with respect to $y$ (Assumption 2) and the Linear Independence Constraint Qualification (LICQ) condition in lower level (Assumption 4). These assumptions reduce the challenge of the bilevel problem considered. It is unclear whether the application problems tested in the numerical experiments satisfy these assumptions. The authors should clearly state in the introduction that their work depends on the strong convexity of the lower level problem. 2. The proposed algorithm requires solving two minimax problems at each iteration, which can be computationally expensive for practical applications. 3. The theoretical results do not clearly state how to choose the step size \eta. 4. The experiments in the paper lack details on the chosen hyperparameters of the algorithm. 5. I have checked the code provided in the Supplementary Material. For the SVM problem, the implementation does not match the proposed algorithm; the minimax problems at each iteration are solved by different solvers than those stated in the paper.

Questions

1. There are some typos in the paper. For example, in line 165, it should be \mathbb{R}^{d_x}_{+}, in line 125, there is an extra “and”. 2. How did the authors choose the iteration number T for the two inner minimax solvers in the experiments?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Relies on the strong convexity of the lower level problem.

Summary

This paper presents an algorithm to solve bilevel optimization problems with coupled constraints using a primal-dual-assisted penalty reformulation. The study establishes rigorous convergence theory and demonstrates the algorithm's effectiveness through real-world applications, including SVM model training and transportation network planning.

Strengths

Strength: - The paper is well-written with clear introduction of the problem, assumptions and technical presentation for their methodology. - The primal-dual-assisted penalty reformulation and the main optimization algorithm effectively addresses the challenges of this class of problems. - Comprehensive theoretical analysis are provided to show the theoretical convergency. - Application examples including SVM and transportation network design, are provided to demonstrate the effectiveness of the proposed algorithm.

Weaknesses

Weakness: - It would be great if more discussion on the computational complexity and scalability of the proposed method can be provided. - In the experiments part, the compared baselines are very limited.

Questions

How can the proposed algorithm be seamlessly integrated with other solvers?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Reviewer's Comment

I would like to thank the authors for their detailed response. It seems like one of the major issues I raised was a misunderstanding due to an incorrect reference within the text. The new result seems more reasonable. I am raising my score to 5.

Response to authors

Thank you for your response to my questions. I think the rebuttal suitably addresses my concerns around robustness to hyperparameter tuning and the time complexity of the comparison methods. Again, I think more discussion around the large-scale nature of the setting in the introduction (a few extra sentences, say) would have helped me appreciate the paper more on the first read-through, but this is a minor comment and does not detract from the overall contribution. I will raise my score to reflect the rebuttal.