Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors developed two algorithms MRBO and VRBO for  bilevel stochastic optimization problem, and showed that their computational complexities ($\mathcal{O}(\epsilon^{-1.5})$) outperform all existing algorithms ($\mathcal{O}(\epsilon^{-2})$) orderwisely. The authors claim two main contributions. First, MRBO is the first momentum algorithm that exhibits the orderwise improvement over SGD-type algorithms for bilevel optimization. Second, VRBO is the first that adopts the recursive variance reduction technique to accelerate bilevel optimization. Their experiments demonstrate that these algorithms  outperform existing algorithms, and suggest that the double-loop design may be more suitable for bilevel optimization than the single loop structure.
main_review: Originality: 
The authors proposed two new algorithms for solving stochastic bilevel optimization program: MRBO is the first momentum algorithm that exhibits the orderwise improvement over SGD-type algorithms for bilevel optimization; VRBO is the first that adopts the recursive variance reduction technique to accelerate bilevel optimization. Both of these two algorithms improve the computational efficiency by a order of $\mathcal{O}(\epsilon^{0.5})$.


Quality: 
Both algorithms are supported with proofs of convergence guarantees. Also, experiments on simple MNIST tasks are conducted to demonstrate the superior performance of the proposed algorithms.

Clarity: 
This paper is well-organized and  provides clear statements of algorithms and proofs.

Significance: 
Bilevel optimization is an important tool for many ML tasks such as hyperparameter tunning. However, it is also well-know solving Bilevel optimization program is NP-hard. This paper proposes two algorithms that are well suited for a class of such programs.
limitations_and_societal_impact: Although the proposed algorithms are demonstrated in simple MNIST tasks, more experiments on large scale data (e.g., CIFAR or ImageNet) are necessary to further valid the computational efficiency.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper extends to usual algorithms of convex optimization with finite sum to bilevel optimization: SGD with momentum and SVRG. The main contribution of the paper theoretical: authors derive accelerated convergence rates toward the solution of the bilevel problem.

main_review: 
Theoretical results are interesting for the bilevel community, although this work does not fix the practical problem of hand-tuned stepsizes.

Comments:
- In algorithm 1 and 2, how do you choose the stepsize s $\lambda$, $\gamma$, $\alpha$ and $\beta$ in practice. Do you have any insights on how to set in practice? From my experience, algorithms are very sensitive this hyperparameters.
- How do you select $Q$ in practice? (the size of the "Neumann serie")
From my experience it can also have a large influence of the result of the bilevel optimization algorithm.
How robust is the algorithm to this parameter?
- Since computing $\hat \nabla \Phi(x_k, B_k)$ (through (4)) requires an iterative procedure, I think it is misleading to talk about "single" loop algorithm for Algorithm 1, and "double loops" algorithm for Algorithm 2, do authors agree that the computation of $\hat \nabla \Phi(x_k, B_k)$ add another loop?
- Authors claim that the proposed techniques are order of magnitude faster than usual algorithms, regarding the experimental results, I would be less assertive.

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents two algorithms (one single-loop and one double-loop) which exploit variance reduction techniques to improve the best known sample complexity for stochastic bilevel optimization problems with strongly convex lower-level from $O(\epsilon^{-2})$ to  $O(\epsilon^{-1.5})$. 


Bilevel optimization consists in two nested optimization problems: the upper-level aims at minimizing an objective function where some of the variables are a solution of the lower-level problem. In the stochastic setting, upper and lower-level objectives are not accessible and are instead replaced by unbiased estimators. In addition to several smoothness assumptions, this work and several recent others consider the case when the lower-level problem is strongly-convex, which guarantees that the lower-level solution is unique, the existence of the upper-level gradient, and allows to provide convergence guarantees to stationary points even when the lower-level solution is not computed exactly. 

This work studies two algorithms (MRBO and VRBO) which both achieve a sample complexity of $O(\epsilon^{-1.5})$, which improves upon the previous optimal complexity of $O(\epsilon^{-2})$. Both algorithms exploit variance reduction  to achieve the desired complexity. MRBO is single loop and combines variance reduction and momentum while VRBO is double loop and uses large-batch gradients to reduce the variance. Recent works have already applied momentum and variance reduction to solve stochastic bilevel problems but this one is the first (together with two concurrent works) to achieve a sample complexity this low. The authors present experiments on the data hyperclearner setting which show that VRBO performs the best and double-loop algorithms seem to outperform single-loop ones.

main_review: The authors corrected Theorem 1 and 2 with related corollaries in the supplementary. For this reason I will only refer to the restated results of the supplementary.

#### **Originality**
1. Several works have recently tackled the sample complexity of (stochastic) bilevel optimization with smooth objectives and strongly convex lower-level problem. This work, together with two concurrent ones, is the first that achieves a convergence rate of $\tilde O(\epsilon^{1.5})$ using variance reduction techniques. Furthermore, the rate is achieved  with two algorithms (MRBO and VRBO). MRBO is very similar to the concurrent work SUSTAIN [20], while VRBO is the first that combines double-loop and variance reduction.  The contributions are stated clearly and related work is properly cited. 

#### **Quality**
2. The theoretical claims (Corrected in the appendix) seem more or less correct, although I checked just a little part of the proofs also because they were not easy to follow (see major comment 8) and I am not so familiar with variance reduction techniques.
3.  Drawbacks of the analysis could be discussed more. For example the fact that some parameters like step sizes or batch sizes depend on unknown constants and on the accuracy threshold. Also, I think that adding an additional discussion of the assumptions will be valuable since they seem quite restrictive.
4. Experimental evaluation is narrow. Only one setting (data hypercleaner) is presented, despite that the strength of  the bilevel framework is that it can be applied to several practical scenarios. The authors could either comment on this in the contributions section or perform experiments on at least another setting like optimizing the regularization hyperparameter. On the positive side, they compare their methods with several others from recent literature.

#### **Clarity**
5. The main ideas of the paper are easy to grasp for someone acquainted with recent works in bilevel convergence rates. The paper contains numerous typos (see minor comments) and the proofs are quite hard to follow (see major comment 8). The work could also benefit from simple examples of bilevel optimization problems that could make it more accessible to people less familiar with the bilevel setting.

#### **Significance**
6. Bilevel optimization is becoming more and more relevant in machine learning since many problems like instances of meta-learning and hyperparameter optimization can be cast into this framework. This work develops two principled and efficient algorithms that improve the optimal rate for stochastic bilevel optimization with a strongly convex lower level problem. Although the experimental evaluation is narrow, the results are promising and show the potential advantage of these approaches in practice.

#### **Final Score**
7. I am giving 6 to the paper but I could increase the score if the authors improve the proofs section in the supplementary, comment more on the drawbacks of the analysis, or improve the experimental section.


#### **Major comments**
8. Proofs (in the supplementary) are quite hard to follow, they contain some typos and several references to lemmas contained in recent related works. I think they need more polishing and at least some referenced lemmas could be written in the supplementary to make it more self-contained. 
9. I think the complexity reported in the abstract and in the contribution should be up to logarithmic terms ($\tilde O$ instead of $O$) to account for the hessian-vector products, which generally are more expensive than gradients.
10. This work and related ones lack a more detailed discussion on the assumptions which it looks like they can be too restrictive in some cases unless the optimization problem(s) is over a convex compact set, a setting which this work does not cover. 
11. Since the authors mention concurrent work, it will bring value to the paper to include it not only in lines 131-142 but throughout the manuscript when comparing with related works, for example in Table 1.
12. I think that the Justification in lines 100-105 is not well supported experimentally. Furthermore, it should not be in the contribution section.
13. The concurrent methods SUSTAIN [20] and BSA [8] can be also applied with bigger batch sizes, while the authors seem to only consider batch size = 1 for these methods in the experiments (from the provided code). I think it will be good to see the performance of these methods with larger batch sizes. Probably in this case SUSTAIN will be equivalent to MRBO.


#### **Minor Comments  and typos**
14. From Theorem 2 statement it is unclear why the final complexity in Corollary 2 $O(\epsilon^{1.5})$ holds, probably because the dependence on $\mathcal{S}_2$ and $q$ is hidden in (12). It seems that the complexity is just $\tilde{O}(\epsilon^{-1})$. I do not know if there is a simple way to make it more clear.
15. Experiments could be better detailed in the appendix by specifying what metric is used to fine-tune the parameters for best performance and what kind of CPU is used.
16. I think adding some plots with the number of samples on the x axis to have results which are independent of the particular implementation and hardware can add value to the paper.
17. Contribution section could be shorter by removing some details.
18. Line 203. I think Assumption 1 should not include $\Phi$ being non-convex. The results would hold also for convex $\Phi$.
19. Assumption 2 requires everything to be uniform also w.r.t. the random variables. This may be commented on because it is not present in works which instead do not use variance reduction.
20. VRBO (Algorithm 2) could be written more clearly since it seems that uses different $\tilde x$-s inside the $t$ for loop but then writes $\tilde x_{k,t+1} = \tilde x_{k,t}$. It would be clearer if $\tilde x $ had only the $k$ subscript.
21. I would change “by the order of magnitude” in line 72.
22. Line 87 “periodically at each outer loop” is unclear.
23. Line 92: unclear what “Hessian-vector type” means.
24. Line 100: “outer-loop estimation”?
25. Line 101: “inner loop output y” not clear, i would remove “y”.
26. Line 109: “to further simplify the implementation”?
27. order-wisely -> order-wise at lines 115, 174, 350.
28. equations (2) and (3) could be with $x$ instead of $x_k$. Furthermore in (3) the last product could probably be replaced by an exponent since the index $j$ is not used.
29. Line 231 “of dataset” can be removed
30. Line 239: “one step iteration” -> “one iteration”
31. whether -> when at line 68.

#### **Post Rebuttal**
The authors have properly addressed my concerns and claimed to make several (quite straightforward) modifications for the next version of the paper. Thus I am increasing the score from 6 to 7. 


#### **References**
[8] S. Ghadimi and M. Wang. Approximation methods for bilevel programming.arXiv preprint376arXiv:1802.02246, 2018.

[12] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel386optimization.arXiv preprint arXiv:2105.02266, 2021.

[19] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization. arXiv preprint arXiv:2102.07367v1, 2021.

[20] Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2021). A near-optimal algorithm for stochastic bilevel optimization via double-momentum.arXiv preprint arXiv:2102.07367

limitations_and_societal_impact: Unaddressed limitation are at point 3 of the main review.

The authors justify the absence of a discussion about potential negative societal impact writing in the checklist that the nature of the work is theoretical. I agree with the authors.
review_title: null

Meta-review: Reviewers unanimously agree that this is a paper of high originality and soundness of the results. Some reviewers have raised concerns over inflated claims in light of experimental validation (5eE2, VGzP), as well clarity of the proofs and discussion of the limitations (VGzP). After a strong rebuttal and engaging in discussion with the authors, the reviewers have found that the authors have addressed their remark, and some reviewers increased their score.
Decision: Accept (Spotlight)