Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper describes various MLMC debiasing schemes for computing stochastic gradient estimates, and applies them to conditional stochastic optimization problems. Here, unlike other more-standard problems in optimization it is impossible to compute true gradients of the objective function: the objective is an expected value over infinitely many points. However, as this paper observes, approximate minimizers to these problems may nevertheless be computed. The main ideas underlying this result are the use of sampling and a multi-level Monte Carlo (MLMC) to generate low-bias stochastic gradient estimates: these are then combined with stochastic gradient descent. 
main_review: Overall, the paper studies a very well-studied problem and achieves improved theoretical guarantees for it. I found the analysis highly technical and difficult to follow, but the results seem correct to me. The analyses of four different schemes for bias reduction may be helpful for future work on related problems, although the reason for including these is unclear (as the parameters a,b,c in the paper have specified values in the application to CSO)

However, the paper's result seems to essentially derive from combining SGD with standard MLMC-based gradient estimation schemes (for example, the ones in [4]). The utility of biased oracles in stochastic methods has been observed several times before. While some of the bias-reduced estimators given here are new, the bias and variance analyses of these estimators follows a standard template laid out in previous work [4,25] (indeed, the calculations of Lemmas 4 and 5 may be obtained by slight modifications of the calculations in Appendix C of [25]).

In addition, while the application to CSO is compelling I did not completely understand how the results compare to those of [19]. In particular, the paper claims a result that contradicts a lower bound of [19] and justifies this by stating that the oracle of [19] is more restricted than the setup considered here. Some more description of this behavior and a justification of the stronger access model presented here would be helpful . 
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a family of MLMC methods for gradient estimation and systematically analyses their performances under different stochastic optimization settings (strongly convex, convex, and nonconvex). In each setting, the order of the total cost is given in terms of the decay rates of the bias and variance, and the corresponding increasing rates of the oracle cost. It is shown in the CSO problems that some of the MLMC methods have lower computational costs compared to existing state-of-the-art (e.g., [19]).
main_review: Originality: The paper provides a comprehensive and systematic study on the computational costs of MLMC gradient descent methods, which is not available in the literature as far as I know and presents a good contribution.

Quality: The theoretical claims are well supported with detailed proofs.

It would be good if the authors can provide examples where b<c and b>c, corresponding to table 1. This would give stronger evidence that each regime is worth studying. For example, in Section 1.1, the DRO example, can you provide the values of a,b and c and which regimes it could correspond to in table 1? 

It seems that there is a sharp phase transition for the performance of RU-MLMC and RR-MLMC from c<b to c>=b, as seen in table 1. When c<b, they are the best. But when c>=b, they are not applicable at all. This seems to suggest some important considerations on the constant in the big-O notation that depends on these parameters. Discussions on this issue would be helpful.

Clarity: The paper is well organized and the main results are presented clearly. But some arguments could be explained more carefully:

In Theorem 1, it is not very clear to me why n_L should be chosen in the stated way. In remark 4, it is explained that this is a result of “optimizing the total cost with respect to n_L in the continuous space”, but I think the author(s) could provide a more concrete argument. Similarly, there should be some discussion of the choice of q_L in Theorem 2.

Line 240-241: If my understanding is correct, it seems that if 1>c/a, then V-MLMC is O(\epsilon^{-c/a}) better instead of O(\epsilon^{-1}) better then L-SGD (comparing line 240 and remark 3). 

Table 2: in the last column of the row for RU-MLMC, should n_l be q_l instead?

Significance: The study is theoretically significant and insightful in guiding the choice of MLMC gradient schemes. It also points to approaches that can outperform state-of-the-art methods.
limitations_and_societal_impact: Please see the comments and concerns in the quality and clarity parts above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper consider stochastic optimization when we only have access to a sequence of biased functions that converge to the true function. They apply various Multilevel Monte-Carlo methods (MLMC) to handle the bias-variance tradeoff. Convergence rate and computational complexity are computed for both convex and non-convex objective. They also demonstrate the superiority of MLMC gradient methods when applied to conditional stochastic optimization. 
main_review: The setting that one only have access to a sequence of approximations to the objective function is well motivated with some important applications like conditional stochastic optimization and distributionally robust optimization, so the problem that this paper studied is of interest to the optimization community. The idea of introducing MLMC to gradient based optimization is not new [1], so the main contribution of this paper is not the algorithms but the theoretical analysis of convergence rate and computational complexity. They make systematical convergence and complexity analysis for both convex and non-convex objectives with clear dependency on the assumptions parameters, which is novel to this area to the best of my knowledge. Although I didn’t fully check the detail proofs, the paper is in-general well-written and reasonably easy to follow. Here are some points that I would like to hear the response from the authors:

1. Numerical example is missing in Section 4. Sometimes the MLMC based method may involved a huge constant term in either the convergence rate or the complexity (especially the MLMC method that involve randomized level), so it would be better to have some numerical results to confirm the practical usefulness. 

2. Consider the conditional stochastic optimization problem, say min_x E[f(E[g(Y, x)|Z])]. With some smooth conditions on f and g, we are actually able to come up with unbiased estimator of E[f(E[g(Y, x)|Z])] or its gradient by randomized MLMC [2], because they are of the form h(E[W]). So perhaps we don’t really need to follow the current setting (sequence of approximated functions) to solve the problem? 

[1]: Jose Blanchet, Donald Goldfarb, Garud Iyengar, Fengpei Li, and Chaoxu Zhou. Unbiased simulation for optimizing stochastic function compositions. arXiv preprint arXiv:1711.07564, 2017.
[2]: Jose H Blanchet and Peter W Glynn. Unbiased monte carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pages 3656–3667. IEEE, 2015.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a systematic study of the bias-variance-cost tradeoff for several MLMC gradient methods and L-SGD, under the assumption that (i) there exist a sequence of obj. approximations; (ii)  there exist stochastic oracles which generate unbiased estimates of the gradient for the obj. approximations, and unbiased estimates of the difference between function approximation gradients. They assume three parameters a, b, c which respectively describe the bias, variance of the stochastic oracle, and cost to query the oracle, and provide insights on which class of algorithms work better under different configurations of a, b, c. They also show that for conditional stochastic optimization problems, MLMC methods can significantly reduce the sample complexity.
main_review: Overall this paper is well-written, and provides useful insights for practitioners regarding which MLMC method to use for real-world problems. The illustration on the CSO problem also demonstrates the value of MLMC. One question I have is that, in practice, since F(x) is unknown, how do you get an estimate of a, in order to know which is the proper MLMC method? I assume b and c can be estimated in some way since they only involve the function approximations, not the underlying true function. 

On Page 5 there seem to be some typos: L-SGD estimator: ... for n_L times to obtain {h^L}, not gradient of h? Same error also exists in Eq. (4); V-MLMC: ... to obtain {H}, not gradient of H.

It would also be helpful to provide some experimental comparisons of these MLMC methods, to (i) validate your theoretical results, and (ii) give convincing empirical evidence of the superiority and limitations of different methods under different situations. 

I personally expect to see the application of MLMC methods in min-max optimization, which you mentioned as part of the future directions. 
limitations_and_societal_impact: No. I do not think it is related to any negative societal impact.
review_title: null

Meta-review: The paper provides a systematic description and analysis of multilevel Monte-Carlo (MLMC) gradient estimators for stochastic convex optimization and describes application of these estimators to conditional stochastic optimization. Despite some reservations regarding the novelty of some of the developments in the paper, the reviewers appreciated its generality and agreed it could be of value to the NeurIPS community. Furthermore, the reviewers agreed that the experimental results outlined in the author response would be a useful combination to the paper.

In light of this, I recommend that the paper be accepted to NeurIPS and encourage the authors to carefully revise the paper to address the issues brought up during the review. In particular, the authors should include a comprehensive report of their experimental results, consulting the NeurIPS submission checklist to ensure that all the pertinent information is included. Moreover, in cases where experiments indicate the negative finding, that MLMC does not outperform standard bias SGD in practice, I encourage the authors to clearly and transparently highlight this conclusion, as it is as valuable to researchers as a positive finding.

Decision: Accept (Poster)