Neur2BiLO: Neural Bilevel Optimization

Summary

This paper proposes two approximate methods for solving constrained, mixed-integer, non-linear bilevel optimization problems. The core idea is to convert the bilevel problem into a single level problem by clever use of neural networks trained offline by solving single level optimization problems. The upper-level approach trains a NN to predict for a fixed leader decision, the leader objective function assuming the follower acts optimally. A single level optimization problem can then be solved by replacing the lower level problem with the NN. The other approach uses the value function reformulation for bilevel problems and aims to train a neural network to learn the optimal value of the lower level problem, given a leader decision. The performance/capability tradeoffs for each method across different classes of bilevel problems is thoroughly discussed, and some theoretical analysis is provided which depends on the approximation error of the true objective/value function. Importantly, the algorithm has a "post-processing" step where the approximate solutions from Neur2BiLO are refined to ensure feasibility of the original bilevel problem. Neur2BiLO is thoroughly evaluated on several challenging benchmark problems to highlight the generality and effectiveness compared to exact baselines and other learning-based methods.

Strengths

This is a very strong submission overall and was enjoyable to review. In particular, the writing is of extremely high quality given the technical nature of the paper. The methodology is clearly written, but importantly, the discussion of related works, experimental setup, limitations and analysis of results are presented very cleanly. Neur2BiLO is comprehensively evaluated against exact methods and other learning based methods, both experimentally and in the discussion. The approach is relatively straightforward but seems to integrate machine learning into existing algorithms and results for bilevel optimization a very elegant and principled way. In particular, the practicality of training the method and the effectiveness in practice as shown in the experiments is very appealing.

Weaknesses

This is a minor weakness but none of the problems evaluated have coupled constraints. It would be great if Assumption 1 i) were satisfied but the constraints were coupled. The theory around the approximation error to the true underlying functions is discussed in Sec. 3.1, which is nice, but it is unclear whether or not for these class of problems that the optimal value function of the follower's problem is actually smooth. I think this is important to at least have some discussion of this to caveat the bounds, since the approximation error in (8) may not be attainable.

Questions

- Lines 161-173: My understanding is that this is a sensible heuristic approach which refines the approximation to satisfy constraints 2b, 2c imposed in (1). Specifically, there is no guarantee that the solution is optimal, but it is probably a good solution which is feasible. Can you please confirm or correct my intuition please? It was not completely clear from reading the paper whether or not this is the case. - This relates to one of the weaknesses. Is it reasonable to assume in general that the value function of the lower level problem or the optimal objective function of the outer level function is smooth?

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

Limitations have been discussed.

Summary

The paper tackles the bi-level optimization problem (BiLo) in general. BiLO can be seen as the problem of a leader computing a strategy (x) to commit to, such that the leader’s objective is optimized subject to the follower’s best response (y) to the committed strategy. The paper provides two ML-based approaches, one is the upper-level approximation that learns to predict a mapping from x to the leader’s objective, and the other is the lower-level approximation that learns to predict the utility of the follower given x. Both approaches reformulate the BiLO into a single-level mathematical program. The paper also provides approximation analyses for the lower-level approximation. The error term is an additive function of ML regression errors and a gap of f values due to discontinuity. In experiments, both approaches are evalutated on 4 different BiLO problems and compared against B&C, heuristics and exact solvers.

Strengths

The paper presents two novel ML-based approaches to reduce the challenging problem of BiLO. The approaches are not complicated but new and interesting. Empirical results show that both methods are promising - they can find similar quality or better quality solutions than the baselines but with shorter runtime. The paper is also easy to read.

Weaknesses

Note that I have reviewed this paper in the past and I am frankly surprised that it was rejected. The authors have addressed most of my concerns last time. These are not major weaknesses but still should be pointed out: The effectiveness of this approach mainly depends on how closely ML can learn to approximate \Phi(x) or F(x,y*). In general, this looks like a very challenging task and it is the bottleneck of these approaches. In this case, it just happens that the regression task is easy for the four benchmarks. Furthermore, the theoretical approximation guarantees are not that surprising given that the prediction error is assumed to be bounded.

Questions

I don't have any questions.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The applicability of this approach seems to be largely dependent on the ML regression errors. The authors have discussed limitations of their work in the paper.

Summary

The paper develops a neural method to solve bi-level optimization problems. It begins with a motivating application and then proposes NEUR2BILO, which utilizes two layers of neural networks to approximate solutions for the upper and lower levels.

Strengths

I found the work conducted to be substantial, supported by several proofs of components. Additionally, the experiments evaluate performance across four scenarios: KIP, CNP, DRP, and DNDP, which adds further substance to the study.

Weaknesses

1. The paper is not very friendly to readers who are not engaged in this specialized area. The problem addressed has many challenging issues, such as bi-level, non-linear, and mixed-variable components. I wonder how the authors address each of these challenges, as it is not very clear in the current presentation. 2. The paper introduces two models, NN^u and NN^l, designed to generate solutions for the upper and lower levels, respectively. Then, I would expect that the combination of the two models will solve the entire bi-level problem. However, in the experiments, NN^u and NN^l are compared in parallel, which is confusing. 3. I am struggling to identify the major contribution of this study to the learning to optimize area. The paper's organization makes it difficult to grasp the main points clearly. 4. The major body of the paper is not self-contained, requiring frequent switching between the main text and the appendix to obtain necessary information.

Questions

See weaknesses.

Rating

4

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

See weaknesses.

Summary

The paper studied bilevel optimization problems with discrete decision variables. The proposed framework, Neur2BiLO, adopts a learning-based approach to solve such problems, which is based on a trained neural network to approximate the leader's or follower's value functions.

Strengths

The paper studied an important problem, and its overall structure is easy to follow. In recent years, research in bilevel optimization has become increasingly popular. However, most algorithms are dedicated to bilevel programs with continuous decision variables, like the continuous network design problem in transportation and the hyperparameter optimization problem in machine learning. Yet, bilevel optimization problems with discrete decision variables are equally important and have also found applications in various domains. Hence, the relevance and applicability of tackling such problems are well-justified.

Weaknesses

The proposed algorithm is very straightforward in its development and lacks established performance guarantees. This limitation typically necessitates robust numerical validation. Despite multiple experiments, the evidence provided does not convincingly demonstrate superiority over existing methods. First, the experiments on the discrete network design problem (DNDP) are conducted on the relatively small Sioux-Falls network. I recommend testing on larger networks, such as the Chicago-Sketch [1], to better assess scalability. [1] https://github.com/bstabler/TransportationNetworks Second, a significant application, neural architecture search (NAS), is missing from the study. NAS and DNDP share conceptual similarities: one designs neural networks, and the other transportation networks. Traditionally, NAS often employs continuous relaxation for efficient architecture search using gradient descent. However, given that the proposed algorithm directly manages discrete bilevel optimization, it opens the possibility of exploring NAS without needing such relaxations. [2] Liu, H., Simonyan, K., & Yang, Y. (2018, September). DARTS: Differentiable Architecture Search. In International Conference on Learning Representations.

Questions

1. Can the proposed algorithm be extended to continuous network design problems? If not, please explain the reasons. 2. Can the proposed algorithm be applied to neural architecture search? If not, please explain the reasons.

Rating

4

Confidence

5

Soundness

3

Presentation

3

Contribution

2

Limitations

Please find my comments about the limitations in other parts of the review.

Response to Authors' rebuttal

Thank you for your detailed response and for agreeing to address my concerns and limitations. I still think this is a very strong paper and would advocate for acceptance. Re my concern about smoothness: My question was motivated by the universal approximation theorem and the general ability for a neural network to approximate a function which may not be continuous (the value function in this case). It would be nice to have a little bit of discussion around the approximation error (empirical insights or general discussion like in your response will suffice) for the other more general problems where discontinuous value functions may arise. I appreciate that Theorem 3.1 is for a particular class of problems and does not require any assumption on the value function specifically.