Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the nonconvex inner problem bilevel optimization, proposed algorithm for such a problem, and theoretically show the asyptotically convergence. 
strengths_and_weaknesses: The paper provides the comprehensive study of the problem and the result is complete.
questions: How to understand the UL in (BGS)? We also have the variable of $y$ and the minimization is only taken in $x$.

In Definition 1, 1.Criticality, is it $\partial_y g(x, \phi(x, y)) = 0$? Moreover, is self-consistency needed?
 
limitations: The paper lack numerical verifications, and I am doubt about the setting of selection map, my inituition is that it is a mapping from $\mathcal{X}$ to $\mathcal{Y}$.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies bilevel optimization. The authors show that existing algorithms is subject to approximation errors. The authors introduce a simple correction to these algorithms for removing the errors.
strengths_and_weaknesses: Strength: A good background survey of bilevel optimization. The writing is reasonable.

Weakness: 1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the "Unrolled Optimization Scheme"
2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?
3. Any concrete example to show the other algorithms issue would be much better.
4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.
questions: 1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the "Unrolled Optimization Scheme"
2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?
3. Any concrete example to show the other algorithms issue would be much better.
4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.
limitations: 1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the "Unrolled Optimization Scheme"
2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?
3. Any concrete example to show the other algorithms issue would be much better.
4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper analyses bilevel optimization problems with a non-convex lower level problem through the concept of a selection map that chooses a particular solution to the lower problem. They use this notion to define a new selection map based on gradient flows and analyze the resulting games and the differentiability of the selection using a new set of tools in Morse theory. They finally use the analysis to propose an algorithm for differentiating through the inner problem even when the unrolled optimization of the inner problem is solved for a finite number of steps.
strengths_and_weaknesses: **Strengths**
1. The paper is well written and was comprehensible even for a practitioner like me without much prior knowledge about the specific theoretical tools used to analyze such problems. It also provided a nice overview of the existing approaches which I really appreciated.
2. As a practitioner, I think the primary contribution of the paper was showing that the rough equivalent of the implicit function theorem is actually the theoretically sound approach to take even in the case where the inner problem is non-convex (which is what we used to do even otherwise, but it’s very useful to actually have a theoretical justification for it ;) ) under reasonable assumption. To my knowledge this is the first paper showing this. 
**Weaknesses**
1. Although, I realize that it’s probably unreasonable of me to expect experiments from a theory paper, I would have appreciated some experiments showing the practical impact of applying the gradient correction on some toy problems. 


questions: I think my comments under the weaknesses section are addressable and would appreciate the authors making amends along those directions.

**Minor Comments**
Minor Typo : line 266 : knew -> known


limitations: Yes
review_title: null

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: Bilevel optimization problems present an ambiguous model when the lower-level problem has multiple solutions. Typical ways to deal with this ambiguity are to consider either the so-called "optimistic" or "pessimistic" versions of the problem. In contrast, this paper proposes the use of a selection map to resolve the ambiguity. Under certain conditions, the authors show the selection map is differentiable which they claim makes the model amenable to numerical computation.
strengths_and_weaknesses: The strengths of the paper are related to the technical rigor of the work. The results look reasonable and as would be expected under the specified conditions, though I did not check the proofs. The weaknesses of the paper are that the notation is unclear and, more significantly, that the relevance of the selection map model is questionable. 

The authors present the pessimistic-BG problem using non-standard notation of separately presenting an upper-level and a lower-level problem. The typical notation is to write a single optimization problem where the lower-level problem is included as a constraint in the upper-level problem. The authors' notation is understandable to readers with familiarity with bilevel optimization, but their notation would be unclear to readers not familiar with bilevel optimization.

However, the notation that the authors use to present the selection map within the BGS problem is unclear. As currently written, the authors' notation is unclear, and the resulting model does not resolve the ambiguity that they seek to resolve. The authors' notation does resolve the ambiguity if an additional assumption, which is not explicitly stated in the paper, is made -- specifically that the $y$ variable within the selection map is a kind of "initial condition" or "state variable".

Regardless of the above issue about the meaning of how the selection map is used, there is questionable relevance of this model of using a selection map to resolve ambiguity in bilevel optimization problems with lower levels that have non-unique solutions. The reason this model is questionable is that depending on how this selection map is chosen the results of the model can be completely different, and so the selection map approach does not really resolve any ambiguity in which lower-level solution is used in the upper-level problem. The authors present no evidence that this would be a meaningful model. Even if the authors provide evidence that the model is meaningful, it is questionable that this represents an important or major contribution. Based on my understanding of the authors' unclear notation, their idea of using a selection map is equivalent to merely defining a different (parametric) objective function for the upper-level problem. As such, the authors' problem is equivalent to an optimistic bilevel optimization problem with a different (parametric) objective function. The technical results are also arguably: not surprising, not particularly difficult to derive or prove, and not interesting.
questions: What do the authors mean by their notation for the BGS problem? Should the $y$ variable in the selection map in the upper-level problem be interpreted as a kind of "initial condition" or "state variable"?
limitations: Not applicable
review_title: null

Meta-review: metareview: This paper studies bilevel optimization problems and proposes techniques for disambiguating cases where the lower-level objective has multiple optimal solutions. The main points the reviewers raise in favor of acceptance are that:

1. The paper provides theoretical justification for techniques used to solve ambiguous bilevel optimization in practice, and this theory leads to algorithmic improvements. 
1. The paper is well written.
1. The topic and results are of interest to the NeurIPS community.

Reviewer oofy argues strongly for reject with the following main concerns:

1. The notation of the paper is confusing (and in particular, there are concerns about the use of the variable y when the bilevel games with selection (BGS)). Reviewer gXUJ also had some confusion about the BGS setup, and reviewer tW4t agreed that the use of y is inconsistent in the BGS setup.
1. Introducing a selection map doesn’t really resolve ambiguity in the optimization problem because choosing the selection map is essentially resolving the ambiguity by hand.

In the rebuttal, the authors argue that the theoretical analysis is still interesting and useful because many algorithms used to solve bilevel optimization problems in practice are implicitly making a choice of selection map, and the theoretical analysis of the paper allows us to understand what those techniques are really optimizing for. Reviewer tW4t also found the example selection maps provided in the paper to be compelling. I am convinced by the author rebuttal and reviewer tW4t that the selection map is useful.

As for the notational concerns in the introduction of BGS, I think the paper would benefit from added discussion on the role of y in the upper level. In particular, from the author responses and later sections of the paper, it appears that y plays the role of a warm-start or initialization for the agent optimizing in the lower level. This discussion should be included near to the introduction of BGS, since otherwise it is confusing why the selection map is not a function from X -> Y.


confidence: Less certain
Decision: Accept