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 bilevel optimization with unique inner solution, proposed the algorithm that utilizes the dynamic barrier gradient methods, theoretically captures the convergence rate of the proposed algorithm, and implemented plenty of numerical simulations to ensure the validity of the proposed algorithm.
strengths_and_weaknesses: The paper is convincing that it provides various numerical simulations that verifies the validity of the algorithm, and it also provides the convergence rate, not just asymptotic guarantee.
questions: Since we do not have the access to the second order information of $\nabla^2 g(v, \theta)$, do we implicitly approximately computed the inverse of Hessian?
limitations: It would be better if the authors provide more intuition on how the convergence rate is derived.
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 authors present a first-order smooth bilevel optimization algorithm that avoids implicit differentiation, instead using a value function to reduce the problem to a single level constrained optimization problem. The single level problem is solved by a so-called dynamic barrier gradient descent algorithm, which notably does not require the lower level problem to have a unique solution. Convergence guarantees are proven for the algorithm and numerical experiments are reported on several different examples, confirming the theoretical results and suggesting that the algorithm performs favorably in practice.
strengths_and_weaknesses: I found the paper to be generally well written and clear, save for a few small typos that otherwise don't affect the arguments, and I appreciated that the assumptions on the functions and problem settings were clearly stated, adding to the quality of the paper. 

While the idea of using a value function in bilevel optimization to reduce the problem to a single level optimization problem isn't original per se, the algorithm and analysis here seem original and significant to the best of my knowledge, particularly the convergence rate for the case where the lower level solution is not unique. The analysis given doesn't require necessarily the uniqueness of the minimizer for the lower level problem, which makes the algorithm more broadly applicable than many other bilevel optimization algorithms, adding to the significance of the paper.

There were a lot of different problems considered in the applications section and the results were fairly convincing, although I think that in the examples which admit a unique minimizer for the lower level problem it would be interesting to compare to AmIGO as well.
questions: In line 113, where it's explained that theta T is treated as constant despite depending on v, how is this justified? Even if you had a global minimizer theta star instead of the approximation, it would still depend on v, so it's unclear if this works.

In line 44, what is meant by powerful BO method?

In line 82 and line 107, if the lower level problem is nonconvex then what is meant by theta star?

In line 138, should it be CRCQ instead of CRCO?
limitations: I think the paper has done a good job explaining the limitations of its contributions, which are primarily theoretical analyses, by clearly stating the assumptions needed to apply the theorems.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a fast bi-level optimization (BO) algorithm, that only involves the calculation of the first-order gradient. The proposed method is built on the value-function approach, and integrated the dynamic barrier gradient descent algorithm into the new BO algorithm, which helps solve the BO problem more efficiently. The proposed method is a fully first-order method and the authors also establish the non-asymptotic convergence analysis for the proposed method. Experiments on toy examples as well as real deep learning tasks are conducted to demonstrate the effectiveness of the proposed method.
strengths_and_weaknesses: Strengths:

1. Theoretical Analysis: The convergence analysis for the proposed method is indeed one contribution to the bi-level community. The discussion on the condition of the lower-level objective $g$ is also remarkable. I understand when $g$ has multiple local minima, the analysis could become very tricky. Therefore, the introduction of the attraction points is very impressive.

2. Presentation: This paper is well-organized, straight forward and in general very easy to follow. I have no difficulty in grasping the main idea as well as the technical details of the proposed method.

Weakness:

1. Novelty: In general, I think the novelty of this paper is less significant and incremental. Firstly, the value function based bi-level optimization algorithm is well studied and known to not require the computation of the Hessian matrix. Secondly, as the authors mentioned in the paper for several times, the core algorithm used in the proposed method "Dynamic Barrier Gradient Descent" is an existing approach. The authors have yet to convince me that the integration of a proposed method is significant enough. The authors should make the difference between the proposed method and the existing method more distinctive, or discuss the essential difference between these two methods.

2. Experiments: The authors claim that their method is good at large-scale practical deep learning tasks. However, the current experiments all seem to be far away from "large-scale". Therefore, the authors are suggested to design some larger scale experiments to verify their argument. The current results all look good to me. 

3. The authors are also suggested to do an additional experiments on the few-shot meta-learning tasks, since this task is very widely accepted as one experiment to examine the feasibility of a BO method. 

4. Regarding the hyper-parameters, the author claim that "BOME is robust to the choice of $\eta$, T and $\alpha$ as varying them results in almost identical performance". I think this is counter-intuitive, since more inner steps T generally indicates a better lower-level solution, closer to the stationary point, which could lead to possible better results. Further, why do you choose $\eta=0.5$? Is there any logics behind this?
questions: Please address the comments and questions above in the "weakness" column.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
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 proposes a first-order bilevel algorithm which updates only based on first-order gradient information. The author provides convergence analysis for such algorithm and conducts different experiments to demonstrates its superior performances across different settings.
strengths_and_weaknesses: In terms of strengths, it is interesting to use value function approach to avoid Hessian computation in bilevel optimization. Such design helps to reduce the computational cost. Proposed algorithm has been demonstrated in various settings. In general, this paper is well written and presented. 

In terms of weakness, the convergence result is not standard (not in gradient norm form) which make it hard to compare such result with other benchmarks. In experiments, all algorithms have adopted GD to update while some algorithms (e.g. VRBO) is designed for update stochastically. It will be better to involve stochastic algorithms for comparison. In continual learning experiment, CTN (+BOME) does outperform CTN (+BVFSM).
questions: 1. It will be better to have a discussion about the comparison between convergence results of proposed algorithm and other benchmarks (e.g. AID, ITD, VRBO). 

2. In terms of experiments, it will be better to include several stochastic algorithms, e.g. (SUSTAIN [24], StocBiO [21])         
 for comparison to check if BOME ranks top among these algorithms.

3. The continual learning experiments (Table 1) do not show the superior performances of BOME compared with BVFSM. However, in Section 6.2, the author still claims that "BOME outerforms BVFSM across all experiments". 

4. In Line 290, the author states that FT=ACC+NBT. However, the results in Table 1 do not support such states. Any possible explanation?


limitations: Non negative societal impact.
review_title: null

Meta-review: metareview: There is general consensus among the reviewers that this paper is a valuable contribution to the bilevel optimization literature.

- The value function formulation is still relatively unexplored in bilevel optimization (althought not completely new). Having a new paper developing this direction will be a nice addition to the literature.
- The paper seems well written and sound.
- The experiments, though they don't really assess the scalability of the approach, are illustrative and diverse.

We therefore recommend acceptance.

To the authors: please take into account the reviewer comments in the camera-ready paper. Please be careful of not overselling the contributions with superlatives like "powerful method".
confidence: Less certain
Decision: Accept