Venue: NeurIPS 2022 Conference

Reviews:

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 work studies fully single-loop stochastic algorithms for bilevel optimization problems where the inner problem is strongly convex and the inner and outer objective are smooth and given by a finite sum. In particular, it provides a unified framework where outer ($x$) and inner ($z$) variables  together with the variable used to solve a linear system in the bilevel gradient expression ($v$), evolve jointly. The authors propose 2 methods: SOBA and SABA. SOBA  updates $x, z, v$ similarly to single-level SGD and uses two-timescales decreasing step-sizes for the inner and outer variable, while SOBA uses variance reduction with constant step-sizes, similarly to SAGA, thus taking advantage of the finite-sum structure of the problem. The authors prove $O(T^{2/5})$ and $O(1/T)$ stationary point rates, where $T$ is the number of iterations, for SOBA and SABA respectively. Furthermore, SABA converges linearly to the solution when on bilevel problems satisfying the PL-condition. Experiments in optimizing one regularization parameter per feature on IJCNN1 and data hyper-cleaning on MNIST show that SABA outperforms several other bilevel methods introduced recently.

strengths_and_weaknesses: Strengths:
1. The presented framework is clean and allows to analyze fully single-loop algorithms. Previous analysis except for [1] usually did not consider updating the linear system variable online and with one descent step. Furthermore [1] directly consider variance reduction while here an analysis of a simpler algorithm (SOBA) is also provided.
2. This is the first work exploiting the finite sum assumptions for this kind of bilevel problems and reaching the same rates as in single-level optimization.
3. Experimental comparison is well done.  SABA is promising also in terms of practical performance. 
4. Very well written.

Weaknesses:
1. Some possible discrepancy between the proposed algorithm and how it is actually implemented: the average for the variance reduction is a rolling average in practice, and this is not covered by the theory. 
2. Rate for SOBA is not optimal and it is not clear why.
3. Experiments are quite small in scale and can be slightly improved. No experiment under the PL-condition. No plots showing how the performance varies w.r.t. the number of single-sample gradients and hessian-vector products. 

Some of the points are expanded in the Questions section.

[1] Li, Junyi, Bin Gu, and Heng Huang. "A fully single loop algorithm for bilevel optimization without hessian inverse." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 7. 2022.

**Post authors’ response.**

The authors have thoroughly addressed my concerns in their revision and response. In particular, concerning weakness 2, they now achieve optimal rates for SOBA under additional smoothness assumptions which are still realistic. Therefore I accordingly increased the score from 7 to 8.

questions: I have the following questions and comments.

- Authors say that the sum to compute the variance reduced gradients in SOBA is done in practice using a rolling average (Lines 177-178). Is this the case also in the presented experiments? If so it should be stated more explicitly. How is the rolling average computed exactly? I could not find details on this in the Appendix and I think they should be included. The authors should comment on the fact that this approximation is not covered by the theoretical analysis and maybe do an experiment comparing the exact and approximate average.

- The authors should add the finite sum assumptions in the abstract to make it clearer, since it is not standard in the related literature on bilevel rates.

- Can the analysis of SOBA be improved following [1]? The main difference between the two methods is that [1] uses a Neumann series approximation for the hypergradient, while SOBA updates the linear system variable online. What are the challenges in obtaining the rates in [1]? Explaining this could strengthen the paper.

- Line 294-299: on the “real” sample complexity of SABA and SOBA in full batch mode. The authors say that the step-sizes in SABA are proportional to the inverse of the number of examples, which makes the sample complexity of SABA and SOBA using all the examples (full batch mode) equal, while empirical results show that SABA performs better. Isn’t this because the analysis does not take into account the correlations between the single sample gradients? I believe the stronger this correlation, the stronger the gap between SABA and SOBA full batch.

- Plots for the experiments show how the performance varies over time. It could be interesting to see how the performance varies also in terms of the number of single sample gradients and jacobian vector products, which is not dependent on the hardware used.

- The authors present rates also under the PL-condition for the outer objective. Are there some interesting bilevel applications where this condition holds? If so, an experiment under this setting could improve the paper.

- Figure 1 shows SOBA and SABA performance in a toy problem. I could not find any detail on the specific problem. I suggest either to remove Figure 1 or to add some, even brief, details in the main body and/or in the Appendix. 



Minor:
- Line 59 and 61: I think there should be an expectation in the inequalities for the rates. 

- Lines 93-96: reference to Hong et al.. Do the authors mean that only one element of the Neumann series is used? This is incorrect since they use more than one in that paper. I also found that paragraph a bit too fast.


[1] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. "Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems." Advances in Neural Information Processing Systems 34 (2021): 25294-25307.

limitations: Limitations are only partially addressed. The non standard finite sum assumption is properly discussed in the theoretical analysis section but could be anticipated in the abstract. The discrepancy between the theoretical and practical updates of SABA is mentioned briefly and not properly addressed (See Question section).
review_title: null

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: This paper proposes a simple framework for solving bilevel optimization. The framework involves only 3 unbiased estimation in each iteration. The authors provide theoretical convergence guarantees for both SGD version and variance reduction version based on SAGA. Experimental results are provided showing their superior performance.
strengths_and_weaknesses: Strengths:
1. The proposed framework is very simple and clear. The idea of simplifying solving bilevel optimization into three unbiased estimation makes the theory more intuitive and straightforward.
2. Many theoretical guarantees are provided, which makes the statements well-supported. To my best knowledge, the convergence analysis shows optimal convergence rate under corresponding settings.

Weaknesses:
1. From what I can see, the key idea of this framework is the way of estimating the Hessian-vector product, i.e. 'v' (equation (5) in the text). However, as the authors mention in line 92, this idea is not novel.
2. In the discussion of convergence, the comparison is made in terms of iteration complexity. But the experiments part only shows comparison in terms of running time.
2. The experiments are only performed on one dataset for each application.

questions:   
limitations:
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: In this paper, the author consider a finite-sum stochastic bilevel optimization problem:
$$\min_x F(x,z)\qquad s.t. \qquad z = \arg\min_{z'} G(x,z')$$
where $F(x,z) = \frac{1}{m} \sum_{i=1}^m F_i(x,z)$, $G(x,z) = \frac{1}{n} \sum_{j=1}^n G_j(x,z)$, and $G$ is strongly convex. 
For $h(x) = F(x,z^*(x)), z^*(x):=\arg\min_{z'} G(x,z')$, it is known that the gradient of $h$ can be written as 
$$\nabla h(x) = \nabla_x F(x,z^*(x)) - \nabla_{xz}G(z^*(x),x)\nabla_{zz}G(z^*(x),x)^{-1}\nabla_zF(x,z^*(x)).$$
Due to the finite sum feature of the objective function, it may not be easy to estimate the matrix inverse in the above formula. However, one should notice that $\nabla_{zz}G(z^*(x),x)^{-1}\nabla_zF(x,z^*(x)) = \arg\min_v \frac{1}{2}v^T\nabla_{zz}G(z^*(x),x)v - v^T\nabla_zF(x,z^*(x))$, the authors propose to update $v$ and $z$ by one step of the gradient descent while updating $x$ by one step of ``gradient descent'' where the inverse-vector product is replaced with $v$. 

Compared to many previous algorithms, the proposed framework is matrix-inversion free and is very convenient to incorporate the SGD or SAGA variance reduction technique. 

The reviewer think the proposed framework for stochastic bi-level optimization is convenient and  flexible. Most importantly, it is conceptually simple and implementation friendly.  However, the current work also has some room to improve. For example, for a typical finite-sum/stochastic optimization problem, the efficiency measure should be sample complexity or oracle complexity, instead of the iteration complexity that is presented in this work. Finally, the sample complexity dependence of SABA on $m+n$ is linear, which is a bit confusing to me since SAGA usually improve the dependence to $(m+n)^{2/3}$.

Overall, the paper does provide some novel and interesting ideas. However, the theoretical result does not justify the reason for using variance reduction. If the authors can answer this question, the reviewer is very willing to adjust to a higher rating. 
strengths_and_weaknesses: Strength \# 1: The framework is new and is conceptually simple and is very flexible to incorporate different variance reduction techniques. 
Strength \# 2: The whole algorithm is Hessian inverse free, which is easy to implement. (Though this is not the only work that is matrix inverse free)
Strength \# 3: The paper is very clear and well organized. Very well-written and easy to follow. 


Weakness \# 1: The main theorems in the main paper only discuss iteration complexity instead of sample complexity. 
Weakness \# 2: The sample complexity in the appendix for SABA  is $O((m+n)\epsilon^{-1})$, which seems exactly the same as the full batch deterministic version of the algorithm. Theoretically, this does not provide any advantage of using SAGA variance reduction scheme. 
I'm confused why SAGA doesn't improve the factor $(m+n)$ to $(m+n)^{2/3}$. 
questions: Major issue. 
1. Please discuss the sample complexity in the paper, in particular the dependence on m and n. This is because when we use sample average approximation to construct the empirical objective function, $m,n$ are often very large (In fact they are $\Omega(\epsilon^{-1})$, where $\epsilon$ is for measuring $\|h(x)\|^2$)
2. The authors should carefully justify why SAGA scheme does not provide any theoretical improvement over full batch method. 

Minor issue. 
1. The term ``global'' in the title is confusing, I'm not sure what this global means. 
2. In the appendix, in the table that list the complexity of the algorithms, a ``)'' is missing for SABA.

limitations: NA. This is a theoretical paper.
review_title: null

Meta-review: metareview: The main topic of this work is stochastic bilevel optimization. It provides an efficient algorithm for this task, and provides theoretical results in this setting.  

The reviewers are unanimous that this is well-presented work of high quality and should be accepted, and so do I.
confidence: Certain
Decision: Accept