Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates a bi-level stochastic optimization problem in which the upper level function depends on the minimizer of the lower level objective. A new algorithm based on stochastic momentum-assisted gradient estimator is introduced, by exploiting prior iterations gradient estimates to improve the quality of the current gradient estimation (by reducing its variance). The new algorithm matches the best complexity bounds as the optimal SGD algorithms for single-level optimization. 
main_review: Overall comments

Table 1 provides an excellent and clear overview of existing results in bi-level optimization problems and a clear position of the new contributions; much appreciated. The paper is concise, well written and the theoretical results seem correct and improve upon the existing state of the art.


Detailed comments

1. Does the Stackelberg equilibrium in non-cooperative game theory fall in this class of bi-level optimization class? If so, this also could be mentioned in the introduction section. 

2. The curves in the figures of the numerical results are not distinguishable (in black and white print). Some markers could be included for clarity.

3. Theorem 3.3.  does not include the low-level momentum term. Some explanations on why this term is not required in strongly convex problems should be provided. 

4. The remark in the conclusion section regarding the rigurous lower bound for the sample complexity is not very clear. Some more details should be provided here. 


limitations_and_societal_impact: The paper is theoretical in nature and the reviewer does not see any evident negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tackles stochastic unconstrained bilevel optimization problems, where the lower level subproblem is strongly-convex and the upper level objective function is smooth. By applying momentum-assisted gradient estimator for both the upper and lower level updates, the paper proposes a new bilevel stochastic optimization method termed SUSTAIN. It has been established that the sample complexity of SUSTAIN matches the best-known complexity for single-level stochastic gradient algorithms. 
main_review: The paper is generally well-written. The followings are the positive points of the paper.
+	By applying momentum-assisted gradient estimator for both the upper and lower updates, the paper develops a new momentum-based bilevel optimization method. 
+	The paper established that the new stochastic bilevel optimization method matches the best-known complexity for single-level stochastic gradient algorithms. 
+	Some simulations have shown the empirical advantage of the proposed algorithm. 

However, I have concerns about the paper in the following aspects. 
-	The paper claims that it is a single-loop algorithm. However, by looking into the implementation of SUSTAIN, it seems that it needs another loop to calculate (7). 
-	The authors pose an interesting question at the bottom of page 5 that ``It is not clear which are the most important objects for which variance reduction shall be applied.’’ It seems that this question has not been addressed explicitly in the paper. 
-	The reduction of the SUSTAIN theory to existing results needs further elaboration. Specifically, what is the convergence rate if the momentum of lower-level update is off, e.g., eta^g=1; what is the convergence rate if the momentum of upper-level update is off, e.g., eta^f=1. Authors do provide some discussion in the strongly convex setting, but this should also be discussed in the nonconvex setting. 
-	The simulation is not convincing. The curve HOAG in Fig 1 looks a bit strange. It seems that authors do not plot all the accuracy at all the iterations but only at 2-3 iterations. It is important to see the performance of HOAG at the initial stage. Any particular reason for this?

I am happy to raise my score if my concerns are addressed appropriately. 


========= After rebuttal =======

Thanks for answering my questions. Most of my initial concerns have been addressed. I encourage the authors to add the discussion. 
I updated my score accordingly. 

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an algorithm with double momentum solve stochastic bilevel optimization. Both the sample complexity and per-iteration complexity are state-of-the-art. 
main_review: Merits: optimal sample complexity, low per-iteration complexity by replacing Hessian inverse process by an estimator from reference [14].

Flaws:
1. Some extra assumptions are made under Lemma C.1 in the appendix, including bounded stochastic gradients. It may help to make the settings more clear by moving these assumption to the main body of the paper. These are critical assumption in the area.

2. The authors cite Lemma C.1 from reference [18] without providing a proof here. I could not figure out how eq(106) is proved in [18] (or corresponding terms in [14]).
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The work developed a new algorithm for unconstrained bilevel optimization with strongly convex lower level subproblems. The proposed algorithm executes on a single-timescale, without the need to use either two-timescale updates, large batch gradients, or double-loop algorithm. Authors showed that SUSTAIN is both sample and computation efficient, because it matches the best-known sample complexity guarantees on single-level problems with non-convex and strongly convex objective functions, while matching the best-known per-iteration computational complexity for the same class of bi-level problems. 
main_review: The paper is well written and the demonstration is clear. 
limitations_and_societal_impact: The limitations have been addressed.
review_title: null

Meta-review: Large-scale bi-level and multi-level optimization has several emerging applications (e.g., robotics) where optimizers are themselves embedded in end-to-end deep learning pipelines as layers. Bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth is an interesting special case amenable to complexity bound analyses for reaching a stationary point. As such, the contributions of this paper should interest both numerical optimization and application communities. The reviews ask for a few clarifications in the final revision.
Decision: Accept (Poster)