Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of bi-level optimization. In particular, it considers algorithms based on inexact implicit differentiation, where the inner problem and the implicit differentiation are not solved exactly. Warm-up is used when solving the inner problem and implicit differentiation. The convergence of the proposed method is analyzed by viewing the iterates of the proposed method as a dynamical system using the idea of singularly perturbed systems. 
main_review: The paper studies the problem of bi-level optimization using implicit differentiation. In particular, the paper focuses on methods that approximately solve the inner problem and the implicit differentiation. Warm-start strategy is used for solving the inner problem and the implicit differentiation, hence the name “amortized”, although I felt the word “amortized” is a bit less accurate than “warm-up” given that the method still does iterative updates with a warm-up strategy. 

The convergence of the proposed method is analyzed by viewing the iterates of the optimization as a dynamical system. It is different front the previous literature in the way that it analyzes approximate inner optimization and implicit differentiation with warm-up strategy and with faster convergence in the stochastic setting. But I didn’t check the proofs since I am not very familiar with the techniques used in the literature.

The experimental results show that the proposed method AmIGO is better than its counterpart without warm-start. 
In terms of weakness, I would hope to see how AmIGO compares to AID-BiO proposed in [1] with warm-start only for the inner-level problem or for solving the linear system in AID.

[1] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. International Conference on Machine Learning, pages 4882–4892. PMLR, 2021.

summary_of_the_review: The paper proposes a method that uses warm-up for both solving the inner problem and the linear system arising from AID. It also proposes an improved convergence analysis of the warm-start strategy with inspiration from the singularly perturbed systems. The proposed method shows faster convergence than its counterpart without warm-up. But I would like to see comparing it with warm-up only for the inner problem or for solving the linear system in AID.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a quite rigorous analysis of approximate implicit differentiation with warm starts applied to strongly convex upper level/strongly convex lower level and nonconvex upper level/strongly convex lower level bilevel optimization algorithms in a very general yet also very practical framework. They allow for stochastic errors in the algorithms solving the upper and lower level problems, making their work practical and applicable to real problems in machine learning (hyperparameter optimization), while analyzing in a way that is agnostic towards which algorithms are specifically used for the lower and upper level problems.
main_review: Their general proof strategy is to use previous results on singularly perturbed systems with different time scales and a lyapunov-esque analysis. Their rates/complexities improve significantly on previous works (except in the case of nonconvex upper level/strongly convex lower level stochastic methods, for which a previous work provides a better rate under a slightly stricter assumption) and their arguments encompass both the nonconvex upper level and strongly convex upper level cases at the same time (also the deterministic and stochastic cases at the same time), giving a unified analysis. 

The assumptions, claims, and arguments in the paper are rigorously stated and seemingly rigorously proved. However, the majority of the proofs are relegated to the supplementary material, which isn't required to be checked during the review. When I did check some of the proofs, I found an error in one of them that could affect the validity of other arguments. In particular, in the proof of prop 11 in the supplementary material, there is an error in the update equation (should be k-1 in psi subscript) which affects (perhaps only superficially) the definition of zeta_k and perhaps of some other things. In section 4, after “Outer-level problem”, it is written "and u\in [0,1]" Surely this should be u\in\{0,1\}? Is u ever taken to be in (0,1)? I am inclined to believe these can be easily fixed but it’s not completely clear due to the overall density of the paper.

Remarks about trivial/superficial details (I didn't use these for my evaluation but you might be happy to correct them anyways): 
* Immediately after proposition 1 it is written "... provides an expression for L in terms of partial derivatives of f and g evaluated at (x,y*(x))." Should this be “an expression for \nabla L”? 
* In Appendix A.2 the first line states "In order to prove Appendix A.2 ..." Should this be "In order to prove Theorem 1"? 
* In the proof of proposition 6 in the appendix it's written "This allows to deduce that ... any by application" Should this be "and by application"? 
* In B.3 it is written "the second inequality" but I can only find one inequality? 
* There are too many commas in the "Controlling the iterates z^n of B_k" section where it’s written “the following choices for A_n, A, \hat{b}, b:”
summary_of_the_review: * Pros: rigorous arguments, clearly stated assumptions, problem framework is applicable to practice, very good rates in all cases (strongly convex/nonconvex, stochastic/deterministic) except one case (in which the previous related work uses a slight stricter assumptions), comprehensive bibliography/related work section, compelling experiments on both synthetic and "real world" problems with comparisons to many other methods of interest in the literature, generally well written and clear given the subject and level of rigor employed.
* Cons: extremely dense and notation heavy for a conference paper (otherwise well written), I was unable to check several proofs in detail; in some sense this work is much better suited for a journal where it can be reviewed properly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of stochastic bilevel optimisation, proving convergence rates for an amortised algorithm which makes use of unbiased estimates of the inner and outer function. The main contributions are theoretical, where they prove sublinear convergence rates.
main_review: Strengths
Sections 1 to 3 of the paper is well written and provides a clear overview of the problem and algorithm. The authors also propose a unified analysis which encompasses many of the existing results in the literature.

Weaknesses
I find Section 4 difficult to read.  The downside to this unified analysis seems to be that the results are difficult to parse (making it difficult to see how to apply these results beyond the known settings).  Here are some of the issues with the exposition:
- Section 4.1 and 4.2 list properties of the inner and outer problem without providing any clear and concise statements on the conclusions. It would be better to first explain the main result (Theorem 1) before explaining the proof technique.
- Theorem 1 makes use of notation from Proposition 1 without explicitly mentioning this. 
- There are a list of corollaries about the case of W = 0 and W>0, but W is not really described and it is difficult to see what this quantity corresponds to -- e.g. what are the situations where W = 0?
- I'm not sure what the message of Proposition 4 is, it makes use of matrices and vectors P_k, U_k, V_k without saying anything about what these are, so I am not sure what to make of this proposition.


summary_of_the_review: In general, I feel that a 'unified' analysis should be elegant and more instructive than existing ad hoc analysis, but this does not seem to be the case here. There is a lot of notation introduced without proper explanation of what they represent, so it is difficult to properly read and check the proofs of this paper in the limited reviewing time of ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work focuses on bilevel optimization. The key innovation here is the warm start, which enables improved complexity bounds (under some settings). The analysis nicely builds on singularly perturbed systems (SPS). Numerical tests are also provided on both synthetic and real problems, where the merit of warm start is demonstrated.
main_review: This is an interesting paper that gives nice theoretical links between the proposed algorithm, SPS, and also the stochastic estimate sequence framework. Here are some questions for the authors.

Q1. In table 1, is it possible to include $\kappa_l$ and $\kappa_g$ dependence in stochastic settings as well?

Q2. After Corollary 1, the authors point out that $\kappa_g$ dependence can be further improved by using acceleration or variance reduction. Is it possible to have a more detailed comparison with [Ji and Liang 2021]?

Q3. It looks like the choice for ${\cal A}_k$ and ${\cal B}_k$ is critical. More discussions should be provided on this point.

Q4. In numerical tests, it looks like in real-world problems CG based algorithms (Amigo-CG and AID-CG) perform the best. Have the authors test it on other datasets? Some additional results to support nonconvex settings are also beneficial.
summary_of_the_review: In general this paper is theoretically interesting. This paper could benefit from more discussions on ${\cal A}_k$ and ${\cal B}_k$, as well as additional experiments.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes amortized implicit differentiation for the bilevel optimization when the inner  objective is strongly
convex.
main_review: This paper is not well-motivated, and the theoretical and experimental results are not convincing enough.

1. This paper focuses on a class of problems: the inner objective is strongly convex (the strongly convex constant can be negative). But the authors do not explain why such a problem is essential and why it deserves study.  This paper follows [Bilevel Optimization: Convergence Analysis and Enhanced Design] in many places. The authors need to explain more details on the difference between that paper.

2. The comparison between existing works (Table 1) is unfair. For example, the algorithm has no inner loop in [ A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic]. But in your method, the inner loops mean that your iteration complexity multiplies a large constant.

3. Even the number of the inner loop is small in the deterministic case. The theoretical results shown in Table 1 mean that the proposed algorithm seems worse than existing algorithms in the strongly convex case. While for the non-convex case, the authors indeed consider the weakly convex function rather than general non-convex cases. The comparison is not convincing.

4. The number of the inner loop $N=O(\kappa_g^3\sigma_{g_{yy}}^2)$, which seems very large. I doubt how to use the algorithm in practice, especially when  $\kappa_g$ is not small.

4. The experiments are weak. The authors only consider quadratic or linear ones. 
summary_of_the_review: Due to previous work  [Bilevel Optimization: Convergence Analysis and Enhanced Design], I deem that the novelty of this paper is limited. I vote to reject.
review_title: null

Meta-review: The paper presents a quite rigorous analysis of approximate implicit differentiation with warm starts applied to strongly convex upper level/strongly convex lower level and nonconvex upper level/strongly convex lower level bilevel optimization algorithms in a very general yet also very practical framework. They allow for stochastic errors in the algorithms solving the upper and lower level problems, making their work practical and applicable to real problems in machine learning (hyperparameter optimization), while analyzing in a way that is agnostic towards which algorithms are specifically used for the lower and upper level problems.

Three out of four reviewers were rather positive of the paper (scores: 6, 6, 8). One reviewer was very negative (score: 3). To my knowledge, the authors have convincingly answered all the points raised by the reviewer. Unfortunately, the reviewer did not follow up.

Similarly to reviewers, I found sections 1-3 to be extremely well-written and to give a nice overview of the field. Section 4 had slight clarity issues (dense notation) that were addressed in the revision. Reviewer 6zLQ partially proof-read proofs.

Overall, I recommend acceptance as a poster, as this paper is advancing stochastic implicit differentiation and should be of interest to many at the ICLR conference.
Decision: Accept (Poster)