Venue: NeurIPS 2022 Conference

Reviews:

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: 1.	In this paper, the authors study two popular bilevel optimizers AID-BiO and ITD-BiO, whose implementations involve different choices of loops. The authors first establish unified convergence analyses that are applicable to all implementation choices of loops for both optimizers.
2.	The authors specialize their results to characterize the computational complexities for all implementations, and they then provide an explicit comparison across different implementations.

strengths_and_weaknesses: Strengths:
1.	The authors first establish unified convergence analyses that are applicable to all implementation choices of loops for both AID-BiO and ITD-BiO.
2.	The authors compare the computational complexities among all implementations of the optimizers. The numerical experiments further demonstrate their theoretical results.
3.	The paper is easy to follow.

Weaknesses:
1.	The exact definitions of some important notations such as $\Theta$ and $\Omega$ are missing.
2.	The authors consider a hyperparameter optimization problem on MNIST in the experiments on AID-BiO (in Line 315), while they consider another hyper-representation problem in the experiments on ITD-BiO (in Line 332). They may want to explain why they consider different problems for the two optimizers.
3.	In this paper, the authors only report the losses v.s. running time and the losses v.s. the number of iterations in experiments on AID-BiO and ITD-BiO, respectively. It would be more convincing if they report MV($\epsilon$)(the total number of Jacobian- and Hessian-vector product computations), Gc($\epsilon$)(the total number of gradient computations) or some more metrics in the experiments to support their theoretical results on the computational complexities.

questions: 1.	What are the exact definitions of the notations $\Theta$ and $\Omega$?
2.	The authors may want to provide references on the hypergradient in AID-BiO to help readers to understand the algorithms.
3.	The authors consider a hyperparameter optimization problem on MNIST in the experiments on AID-BiO (in Line 315), while you consider another hyper-representation problem in the experiments on ITD-BiO (in Line 332). Why do you consider different problems for the two optimizers?

limitations: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.
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 studies the fine-grained convergence of gradient-based algorithms for bilevel optimization problems. The focus is on establishing the unified convergence analysis for both AID-BiO and ITD-BiO and on the comparison between the rate of convergence under different numbers of steps in the inner and outer loops. Under reasonable assumptions, the paper shows that AID-BiO and ITD-BiO can benefit from double loops in certain sense. 
strengths_and_weaknesses: **Comments - Strengths**

(+) The unified convergence theory for AID-BiO is new, which captures all choices of the inner-level gradient steps N and the outer-level Hessian-inverse-vector steps Q. The lower-bound on the nonconvex-strongly convex bilevel problem seems new. 

(+) The conclusion that bilevel optimization is in contrast to minimax optimization, where no-loop gradient descent ascent (GDA) with N = 1 often outperforms (N-loop) GDA is interesting.

**Comments - Weaknesses**

*Major comments*

(-) The major concern I have is that the majority of the theory in this submission is a summary of previous convergence results in [17]. Indeed, this paper and [17] focus on the same setting, the same algorithms, and the same convergence results but now with explicit dependence on the number of steps in the inner $N$ and outer loops $Q$. While this is a good point to discuss, the technical content of this paper seems to be incremental. Therefore, this paper is more like a supplementary to [17].

(-) The second major concern I have is that the theoretical comparison between the double-loop and the single-loop is in terms of the complexity upper bound. Note that the larger upper bound may not mean worse performance since the single-loop algorithm may be harder to analyze, leading to looser worst-case performance. For example, it would be interesting to compare the lower bound of the single-loop algorithm with the upper bound of the double-loop algorithms. 

(-) The third major concern is on the experiments. The experiments did not closely match the theoretical analysis. Since the separation between no-loop and double-loop is on $N={\cal O}(1)$ or $N={\cal O}(\kappa)$, choosing $N, Q$ as $1, 20$ does not serve the purposes. In addition, it may be better to plot the dependence on $MV$ and $GC$ not the runtime nor the number of iterations.

*Minor comments*

(-) A similar conclusion for AID-Bio (e.g., $N={\cal O}(\kappa)$ is better than $N={\cal O}(1)$) has already been drawn in the stochastic bilevel algorithms; see ALSET (Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems). The connection and difference need to be discussed. 

(-) While the paper did provide a lower bound for ITD-Bio, it seems quite loose compared with the upper bound of ITD-Bio. They differ not only in the dependence on $\kappa$ but also the dependence on $K$. 

(-) The main theorems (e.g., Theorems 1, 2, and 3) in the paper are presented in a very complicated way. They depend on many irrelevant constants such as $M, \rho, r$, which make the main theorems difficult to interpret. 

questions: See my comments in weakness. 
limitations: Yes, it addresses the limitations.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a unified convergence rate analysis for existing two types of widely-used bilevel optimization algorithms via so-called approximate implicit differentiation (AID) and iterative differentiation (ITD), under all different choices of loop sizes. Some interesting theoretical findings are provided as well. In particular, for AID-based approaches, two major loops exist within the base loop, i.e., a loop of size N for approximating the lower-level solution and a loop of size Q for estimating the Hessian-inverse-vector (HIV) product in the hypergradient computation. In the comparison among different loop choices, they specify their theories to several typical choices of interest in practice, including N= 1 or \kappa and Q = 1 or \kappa. Based on such comparisons, they show that the lower-level loop can improve the overall computational complexity w.r.t. both the matrix-vector and gradient computations, and the loop for HIV estimation can reduce the gradient complexity. For ITD-based method, they show via upper and lower bounds that loop size needs to be large for achieving a vanishing convergence error induced by the lower-level and HIV approximations. Some empirical results are also provided and seem to validate the theories well. 
strengths_and_weaknesses: This work is well written and the motivation is clear to me. Bilevel optimization has attracted signification attention recently from both the deep learning and optimization communities, where AID and ITD are two widely-used methods so far. Characterizing a unified convergence guarantee for both of these two types of methods is fundamentally important because different loop schemes have been used in practice, but only some of them have guarantee. This work has done a good job in providing a tight characterization and systematic study for all these cases, which is a good contribution. 

The theoretical findings are interesting and provide useful insights for practical applications. By capturing different dependences on the condition number \kappa, they demonstrate the necessity of lower-level  optimization loops in both algorithms to improve the overall complexity, majorly in terms of the Hessian- and Jacobean-vector products. In particular, for ITD-based method, the lower bound is a nice and new contribution to justify the fundamental challenging for No loop scheme in achieving a vanishing error. Theories seem to be well supported by the experiments. 

The technical analysis introduces some new developments, which may be of interest to the bilevel optimization community. Existing works on the convergence rate of bilevel optimization  mainly focus on the case when the HIV is solved at a good accuracy via large Q, but this paper allows small Q by showing that the coupled error is decreasing iteratively. This kind of characterization may be used in other settings with AID types of bilevel optimization. 

questions: The paper is limited to the deterministic setting, and I am wondering if the developed analysis can be further extended to the stochastic setting with data sampling. Can the authors have some comments or provide some guidances on this extension?

In AID-based method, people sometimes use the acceleration methods for both the lower-level and HIV approximations to achieve a better complexity. It would be great to discuss how the current analysis can be extended to such scenarios, and whether the corresponding comparison still holds? 

Theorems 1, 2 and 3 seems involving complicated parameters and relations. It would be good to provide some proof outlines for readers to better understand the technical idea of this paper. 

limitations: the authors 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 provides a unified convergence theory to capture the computational differences among different implementations in bilevel optimization algorithms such as AID-BiO and ITD-BiO, with a focus on the different choices of inner and outer loops. By comparing different implementation, the paper draws the conclusion that different from the minmax case, in the bilevel optimization, having double loops always have some provable benefit. 
strengths_and_weaknesses: [Strengths]
* The paper is well written and the theoretical question studied in this paper is of practical interest.
* The paper has done a good job of summarizing the theoretical results into two tables that have an explicit dependence on $\kappa$ and $\epsilon$. 
* The non-convergent result (both upper and lower bounds) of No-loop ITD-Bio is interesting, which suggests a gap between the performance of AID-Bio and ITD-Bio. 

[Weaknesses]
* The lower-bound result in Theorem 4 is a bit loose. Not only because it has a large gap with the upper bound, but the worst-case example used in the proof also seems not carefully crafted. Does the lower bound also depend on $K$? Is there any possibility of improving the lower bound or upper bound? 

* The paper only focuses on the comparison of different *deterministic* bilevel optimization algorithms. Does the conclusion in this paper also hold in the *stochastic* setting? If not, it would be helpful by mentioning ``deterministic'' in the title or abstract. 

* It is not clear to me why the metic in the AID-Bio experiments is runtime, but that in the ITD-Bio experiments is iteration? Since the theory is mostly on the comparison on the number of iterations or MV and GC, comparing those metrics in both experiments will make more sense. 

questions: * The lower-bound result in Theorem 4. See [Weaknesses]. It would be helpful to clarify. 

* Applicability of the results to the stochastic bilevel algorithms. See [Weaknesses]. It would be helpful to clarify. 

* In practice, stochastic bilevel optimization algorithms may be used more frequently. How does the conclusion in this paper compare to the conclusion in the recent work on *stochastic* bilevel optimization algorithms; for example, Theorem 1 and Proposition 2 in [Chen et al' 2021]. It would be helpful to clarify. 

    Chen et al "Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems." Advances in Neural Information Processing Systems, 2021.

* The performance metrics in the experiments. See [Weaknesses]. It would be helpful to clarify. 

* In the AID-Bio, is it possible to provide the lower-bound similar to ITD-Bio? 

* The discussion on the setting with small response Jacobian (line 304) is not clear. What conclusion do the authors want to draw from this discussion? Is this consistent with the main results? 
limitations: The limitations and potential negative societal impact of their work have been properly discussed.
review_title: null

Meta-review: metareview: There seems to be a clear consensus among reviewers about the paper being well written and addressing relevant research questions pertaining to bi-level optimization, with a particular focus on two popular bilevel optimizers AID-BiO and ITD-BiO. Furthermore, Reviewer Kzzc stressed that this work provides several interesting convergence results, with a practical echo in applications such as meta-learning, NAS, some HO problems, etc. Kzzc also pointed out that, the convergence for ITD has not been well studied, and the results on upper and lower bounds in this work can be a good complement. rZSp joined Kzzc by pointing out that the authors first establish unified convergence analyses that are applicable to all implementation choices of loops for both AID-BiO and ITD-BiO. While at first critical on some aspects of the work (notation, references, tests), Reviewer rZSp went on with a score increase following the constructive discussion with the authors. The most critical Reviewer was KmZV, who questioned the originality of contributions compared to [17]. While the authors did give a detailed response during the discussion, this reviewer did not react. Overall, based on the reviews and the discussion, I assess the paper to be a valuable addition tot he existing literature and recommend it to be accepted to NeurIPS 2022.     
confidence: Certain
Decision: Accept