Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a bilevel optimization method based on unrolled gradient-descent iterations of the lower-level (LL) problem, while providing a theoretical connection between the ideal bilevel optimization and the unrolled one when LL problem might not be convex. The main idea is two-fold: Regarding the initial point (i.e., z) of LL variable as another variable in the UL problem, and taking the pessimistic value from the unrolled iteration, i.e., max_k F(x, y_k(x, z) ). The theoretical derivation presents that the ideal bilevel problem (min phi(x)) is asymptotically equivalent to the unrolled version (min phi_K(x, z)). The resulting algorithm is very simple: (1) perform a few unrolled steps (with computational graph) for LL, (2) take the pessimistic estimate (y_k) from the steps, (3) and perform gradient descent for x and z for the UL problem based on the y_k(x, z). The paper also proposes a Nesterov version (for LL iterations). The proposed method shows state-of-the-art performance for a toy problem and two applications.
main_review: ++ Relevant contribution for an important problem: Bilevel optimization with nonconvex objectives is popularly used nowadays. Solving this with unrolled iterations has been frequently used in the literature, but without any apparent theoretical guarantees. Providing this is definitely relevant.

-- Discrepancy between the theory and the algorithm: The most crucial problem I think is that the theory and the algorithm are describing different things. The convergence guarantee to global optima is true only because the inf operators in all the theoretical derivation are in fact global optimizers. However, the optimizer for the UL problem used in the proposed algorithm is actually a local one (projected gradient descent). For example, let us suppose the following case: F(x,y) = x + 1/2 y + cos(y), S(x) = argmin_y 1/2 y + cos(y), -1 <= x <= 1, -2pi <= y <= 2pi, and all the variables are scalars. In this case, if we pick a wrong z (and hyperparameters), then Algorithm 1 will converge to a non-global optimum. Moreover, the derivation says nothing about the convergence to local optima. This suggests that the proposed method excelling in the experiments might be not because of the guarantees provided in the paper. This is somewhat misleading and can confuse readers. I suggest the authors address this limitation in the main paper.

[After rebuttal]
My main concern has been well addressed in the authors' response. Providing the local solution convergence will be definitely helpful for the completeness. I'm satisfied with the response and I stay with my original score.
limitations_and_societal_impact: Explaining the above limitation (the discrepancy) can be helpful for the completeness of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a gradient-based bilevel optimization algorithm called IAPTT-GM that does not require the non-convex inner-level assumption. Specifically, the authors propose two methods: (1) initialization auxiliary that guides the optimization dynamics and (2) pessimistic truncation operation to build theoretical convergence. The authors theoretically show convergence of IAPTT-GM that does not assume the non-convexity of the inner-level problem and empirically show that the proposed method has improved performance on few-shot classification and hyper cleaning compared to previous approaches.

main_review: 1. Originality
 * The task of solving bilevel optimization that does not require the lower-level singleton (LLS) assumption has been explored in previous works (e.g. [1]).
*  However, I am not aware of the pessimistic trajectory truncated method to solve this particular issue and I believe that the algorithms & theoretical analysis presented in the paper are interesting and novel. 

2. Quality
* The submission is technically sound. I checked the derivation and proofs and they look correct.
* The potential limitations of the proposed approach are not addressed in the paper. For example, what would be the computational & memory overhead compared to previous approaches?

3. Clarity: 
 * The manuscript is overall well written and easy to understand. However, the paper uses several abbreviations that are not properly defined (e.g. UL, LL, LLS, LLC). It would be much helpful to properly define these abbreviations. Having a table describing these abbreviations would be helpful.
* Moreover, it would be helpful to summarize all mathematical notation used in the paper. Some notations have quite different interpretations with a subscript which makes proofs hard to read.

4. Significance: 
 * Gradient-based bilevel optimization that does not require the lower-level singleton (LLS) assumption is a recently emerging topic in the literature and I believe that result is important. It is relevant to the Neurips community.

5. Additional Comments:
* I don't exactly understand line 150: "The pessimistic max operation always results in a favorable trajectory truncation smaller than K". What would be the reason behind this statement?

6. Minor Comments:
* For gradient-based methods, I feel like the argmin formulation in equation 2 is weird. Can the rational reaction set S(x) map a solution of the local minima? Shouldn't the version that incorporates local minima (e.g. [2]) be more correct?
* In line 122, relevant references on convergence theory of non-convex first-order optimization would be helpful.
* In line 136, the footnote should be inside the comma.
* Introducing variables like T, K would be helpful in describing algorithm 1.
* I feel like showing the baseline algorithm next to algorithm 1 would help readers to better understand contributions made in this paper.

[1] Liu, Risheng, et al. "A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton." International Conference on Machine Learning. PMLR, 2020.

[2] Fiez, Tanner, Benjamin Chasnov, and Lillian J. Ratliff. "Convergence of learning dynamics in stackelberg games." arXiv preprint arXiv:1906.01217 (2019).

------
Thank you for your clarifications. I acknowledge that I read and other reviewers' comments and authors' responses.

I agree that properly defining abbreviations and showing the baseline algorithm would further add clarity to the paper (as well as the new assumption suggested by the authors). Given that these modifications would be made in the manuscript, I will increase my score to 7 (from 6).
limitations_and_societal_impact: While the authors did not address the potential negative social impact of their work, I believe that it is not necessary for this submission.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a truncated unrolling type method for solving a bilevel optimization problem with non-convex lower-level problem and the convergence of the proposed method is also shown. Compared to the results in the existing literature, the convergence analysis in this work does not require any convexity assumptions on both upper level and lower-level objective functions. Efficiency of the proposed method is shown in the numerical experiments of artificial problems and real application problems.
main_review: This work proposes a truncated unrolling type method for solving a bilevel optimization problem with non-convex lower-level problem and the convergence of the proposed method is also shown. Compared to the results in the existing literature, the convergence analysis in this work does not require any convexity assumptions on both upper level and lower-level objective functions. Efficiency of the proposed method is shown in the numerical experiments of artificial problems and real application problems.

I noticed that two interesting ideas, namely, Initialization Auxiliary and Pessimistic Trajectory Truncation, are applied in the designing of the proposed method. Initialization Auxiliary is a well-used technique in meta-learning, but the Pessimistic Trajectory Truncation technique is quite new. Thanks to the Pessimistic Trajectory Truncation technique, the proposed method admits a convergence guarantee, meanwhile, the computation cost in the numerical implementation is reduced. I think that such Pessimistic Trajectory Truncation technique may bring something new to other bilevel optimization algorithm designs.

Cons:
1. The convergence result of the proposed method is based on the sequence x_K being global minimum of the approximated subproblems. Since the approximation is just with respect to function values, I understand that it is usually too ambitious to establish the stationary points convergence in such a general case (nonconvex LL) considered in this paper. However, since the subproblems are always nonconvex, this referee would like to ask is it possible to derive convergence analysis for the case where x_K are local minimum. 
2. I understand that the LL compact set constraint Y is imposed for theoretical convergence analysis. The authors should clarify that how to set and deal with this extra Y in numerical experiments. 
3. In section 3.2, the authors embed the Nesterov’s acceleration dynamics into their algorithm. It seems that the convergence analysis does not rely on any particular features of the Nesterov’s acceleration dynamics. This referee feels that this part can be generalized to other acceleration dynamics.
4. The LL subproblem is now set to be differentiable. This referee wonder if the general non-differentiable case can be considered to capture more real applications. 
5. In the numerical experiments, the authors conduct a comparison for the proposed methods with and without Pessimistic Trajectory Truncation on an artificial problem. Empirically, the Pessimistic Trajectory Truncation technique brings a great improvement. I was wondering whether such an improvement also exists for real application problems.

**Final Comment (Post Rebuttal)** 

I acknowledge that I read and other reviewers' comments and authors' responses. I would like to keep my score as most concerns of mine have been well addressed.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a first-order algorithm for solving bilevel optimization problems where the lower-level problem is non-convex. The proposed algorithm, named as IAPTT-GM, in my understanding, is roughly alternating projected gradient descent in the upper level and lower level variables, combined with two key ideas, namely initialization auxiliary and pessimistic trajectory truncation.

This paper provides theoretical analysis of IAPTT-GM, supported by sufficient numerical experiments, both on toy problems and real datasets. 

This paper is well motivated and well written. The theoretical part is clean and concise, while the numerical experiments are well conducted, together with texts to describe the main takeaways.

In general, I like this paper and want to see it published. However, I am a bit skeptical about the theory. I may downgrade my score if there are severe theoretical issues. See main review.
main_review: The biggest confusion for me is, Theorem 3.1 seems to be so strong that it violates NP-hardness results of generic non-convex problems.

The bilevel optimization problem considered in this paper, neither has a convex upper level problem, nor has a convex lower level problem. Therefore, to me the problem is obviously non-convex and NP-hard, not to mention about the extra difficulty imposed by the bilevel structure. In addition, the proposed algorithm is a first order algorithm.  However, Theorem 3.1 claims that the algorithm can find a "solution" to the upper level problem.  How can this be possible? I wonder what does the term "solution" mean in this context, does it mean a first-order stationary point, or does it mean the "globally optimal solution"?  Intuitively, the best thing one can hope for first order methods is convergence to a first-order stationary point. So this result is a bit too strong for me. Am I missing some strong assumptions of Theorem 3.1?  I'd like the authors to clarify this point. I will also read the reviews. from other reviewers to see if they have similar concerns.

The other major comment is, how efficient is the proposed IAPTT-GM algorithm, compared with other methods? From the description of Algorithm 1, it seems many inner and outer iterations are required. Could the authors, in the experimental section, comment more on the runtime and efficiency of IAPTT-GM when compared with other baselines?

Bilevel programming is an active area of research in the mathematical programming community. I also wonder if the authors could draw connections to literature in that field when presenting related works. In particular, the value function approach seems to be a preferred approach for solving such problems. For example, see [Ref1] and references therein (the authors of [Ref1] seem to have made great efforts along this vein).

[Ref1]: Ye, Jane J., Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. "Difference of convex algorithms for bilevel programs with applications in hyperparameter selection." arXiv preprint arXiv:2102.09006 (2021).
limitations_and_societal_impact: See main review.
review_title: null

Meta-review: The paper proposes a truncated unrolling type method for solving a bi-level optimization with non-convex lower-level. It contains two interesting ideas, namely, Initialization Auxiliary and Pessimistic Trajectory Truncation. The proposed method admits a convergence guarantee, meanwhile, the computation cost is reduced. The techniques and analytic framework are novel, and enhance the understanding of gradient-based bi-level optimization methods. In summary, this work will possibly inspire some new bi-level optimization algorithms and technical analysis.
Decision: Accept (Spotlight)