Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The author derives a general algorithm framework applicable to minmax, composition, and bi-level optimization. The convergence rates are improved for different classes by leveraging the hidden smoothness of the problem. This paper is well organized and easy to understand. The author illustrates the difficulty of the problem, and the proof sketch is clear enough. The author also applies the algorithm to the policy gradient reinforcement method and provides its convergence.


main_review: Strengthens:
   Please refer to the summary.

Weakness:
   1) Compared with STABLE, the inner loop for updating $y$ can not be ignored for ALSET as the $\kappa$ is large.
   2) Also the author doesn't mention the gradient evaluation complexity comparison between STABLE and ALSET in terms of $\kappa$ which can usually not be ignored.
   3) Even simple linear experimentation in terms of the sample complexity/gradient evaluation vs loss would be helpful to better understanding the benefits of ALSET.



limitations_and_societal_impact: No
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a new analysis of a stochastic gradient method, ALSET, for bilevel problems. It shows the convergence rate $O(\epsilon^{-2})$ for finding an approximate stationary point. The results further implies the same convergence rate in minimax, compositional optimization and actor-critic method. 
main_review: $\textbf{Originality}$: The analysis of this algorithm is new and original. 

$\textbf{Quality}$: All claims are supported by sound proofs. Please see the questions and concerns below. 

$\textbf{Clarity}$: The paper is clear and well organized. I suggest the author to mention the assumptions (such as strong-convexity in the lower level) in the abstract or early stage of the introduction. 

$\textbf{Significance}$: Since stochastic gradient methods are simple and popular, I believe that this work will have some impacts by providing the theoretical ground to this method in the bilevel optimization. 

$\textbf{Concerns}$: 
1. I think one of the drawback of the algorithm is that it still needs two loops. Only in the compositional problem, it can be reduced to one-loop algorithm, since the lower level is well-conditioned. The sentence in line 58 might be a little misleading. The algorithm in this paper can get rid of large batch size and increasing inner loop number, but not two loop structure. It still remains an open question what would happen if we only do one step for the lower level in each iteration. 
2. The algorithm requires to prefix the total number of iterations $K$. Is there anyway to use decreasing stepsize so that we do not need to pre-set $K$?
3. The analysis in the paper is neat due to the discovery of smoothness of $y^*(x)$. However, in the discussion of actor-critic method, the authors directly assuming $y*(\theta)$ to smooth, which a limitation. Also, in the minimax optimization, compared with other work, it additionally assumes the Lipchitz of the function, which might reduce the difficulty of the question greatly. 
4. In line 6 of Algorithm 1, $\alpha$ should be $\alpha_k$. 


=============after rebuttal===============
Thanks the authors for replying my questions. I am satisfied with the answer. I realize the authors use two-loops to achieve better dependency in the condition number. Would it be better if the author can also provide comparison of dependency of $\kappa$ in the table for bilevel problems?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper improves the sample complexity of alternating SGD in the classes of stochastic nested optimization and show that the new complexity results are better than existing methods in the three settings. The new results rely on a smoothness property on the smoothness of  $y^*(x)$.
main_review: The paper is well-written and easy to follow. The comparison with related methods in Table 1-3 help clarify the significance of the improved results. The techniques used to improve the convergence results are new.

I have the following comments on the theoretical results in the paper:
- The advantage in min-max problem is unclear since ALSET require additional Lipschits continuity while two-time-scale GDA use increasing batch size.
- Can the results on for other function other than quadratic in the compositional setting? Claiming advantages in this results compared with SCGD and NASA is not really fair since SCGD and NASA consider general g function.

Therefore, the advantages of the new analysis can be mostly seen in the bilevel setting which reduce the significance of the paper.


=======================Update==========================

After reviewing the authors response, I have updated my score.
limitations_and_societal_impact: The authors have adequately mentioned the limitation of the work. It would be better to emphasize the difference in analysis of ALSET in compositional problems since it considers a special case rather than the more general case in existing methods.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an improved sample complexity analysis for a stochastic bilevel (or nested) optimization algorithm. 

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 a double loop algorithm which applies the vanilla stochastic gradient method at the upper and lower levels for $K$ and $T$ steps respectively. In addition, to compute the upper-level gradient, the lower-level hessian inverse is computed with an estimator whose bias decreases exponentially with the number ($N$)  of stochastic hessian samples and the lower-level starting point for the stochastic gradient method is the lower-level approximate solution at the previous upper-level iteration (warm-start). This algorithm is quite simple and is commonly used in practice.

The improved analysis yields a sample complexity of $O(\epsilon^{-2})$ even when $T=1$ without using momentum, variance reduction, exact hessian inversion, or big batch sizes, which are instead needed by previous work to achieve the same or better complexity (the best-known complexity is $O(\epsilon^{1.5})$ using variance reduction and additional assumptions). The authors further show that using their analysis one can recover the best-known complexity in 3 special bilevel problems: stochastic min-max, compositional and actor-critic.
main_review: Since the authors included the main paper in the supplementary I will refer to the line numbers of the supplementary throughout the whole review.

#### **Originality**
1. Several works have recently tackled the complexity of (stochastic) bilevel optimization with smooth objectives and strongly convex lower-level problem. This work demonstrates $\tilde{O}(\epsilon^{-2})$ sample complexity for a widely used algorithm consisting in stochastic gradient descent applied to solve both the upper and the lower level problems and is the first to do so with $O(1)$ batch size. The authors state clearly the contributions of the work and how they differ from previous ones (see e.g. line 195). The authors also specialize their theoretical results to 3 particular bilevel problems: stochastic min-max, compositional and actor-critic, recovering the best-known complexity, which is something that I have not seen in recent related work.

#### **Quality**
2. The theoretical claims are well supported: the proofs for the bilevel optimization part seem sound except for one issue which can probably easily be solved (see the first major comment). 
3. 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. 
4. An additional limitation of the work (and of other related works) which is not emphasized by the authors is that the step-sizes ($\alpha_k$ and $\beta_k$) suggested by theory have to be tailored carefully based on the total number of iterations, on the unknown constants of the problem, and may be too small in practice. Comments on this, experiments showing how to choose step-sizes in practice and a comparison between the single timescale step sizes of this work and the two-timescale ones of the previous analysis could add value to the paper.
5. I did not check the supplementary material relative to the 3 special cases but the claims in the main paper seem correct except for one problem for the min-max setting (see point 8 in the main review).

#### **Clarity**
6. The paper is clearly written and the proofs are easy to follow for someone acquainted with recent works in bilevel optimization theory. However, the work could benefit from simple examples of bilevel optimization problems that could make it more accessible to people less familiar with the topic.

#### **Significance**
7. 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 shows that an algorithm which is commonly used in practice matches the best known complexity. This result theoretically justifies the use of such an algorithm and thus is of great significance to the machine learning community.

#### **Major comments**
8. RHS of eq. (48)  should be multiplied by 2. Consequently RHS of (51) is also multiplied by 2 and the final bound in Lemma 3 changes. I think this breaks the proof of Theorem 1 but the Young inequality at line 580 can be changed to make things work again. Constants will change but the all claims will remain valid.

9. Line 276: I think the assumption that $f(x, \cdot)$ is lipschitz continuous breaks the theory for the min-max case. Since the theory does not deal with  constrained optimization on the lower-level variable $y$, $g = - f$ and $g(x, \cdot)$ is strongly convex then $f(x, \cdot)$ is strongly concave and lipschitz smooth over all $\mathbb{R}^{d'}$ although no such function exists. It could be interesting to consider constrained optimization (where these properties are only required in a limited domain) either in the lower-level or upper-level problem to tackle this issue.

10. I believe that the complexity for bilevel optimization should be up to logarithmic terms since to compute the hessian estimator $N = O(\log(1/\epsilon^2))$ samples are used for each upper-level iteration. The authors report the big O complexity without tilde instead.

#### **Minor Comments**
11. Line 102: the cited work [16] has a higher $O(\epsilon^{-3})$ sample complexity.
12. $N$ is not set in the statement of Theorem 1
13. $\alpha$ not defined in the definition of $\alpha_k$ in eq. (12).
14. Probably $\alpha$  in line 6 of algorithm 1 should be $\alpha_k$

#### **Post Rebuttal**
I am satisfied with the author response and keeping my positive score.

#### **References**
[16] S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” arXiv preprint:1802.02246, 2018.

limitations_and_societal_impact: The author discuss a limitation of the work in the conclusion. I pointed out other limitations that I think should be addressed at point 3 and 4 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: This paper unifies several SGD-type updates for stochastic nested problems into a single nested SGD approach and presents a tighter sample complexity analysis that improves or matches the existing results. All reviewers give positive evaluation on this paper. So do I. Please update the final version according to the reviewers’ feedback. For example, I think it is necessary to provide comparison of dependency of kappa in the table for bilevel problems.
Decision: Accept (Spotlight)