Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a procedure that converts any optimal stochastic gradient method into an estimator of the optimum $x^*$ using the multilevel Monte-Carlo approach. The estimator has a smaller expected cost of stochastic gradient computation compared with the original stochastic gradient method. The authors demonstrate that the proposed estimator can be combined with existing methods to improve the computation complexity and provide alternative algorithms to other methods in different applications. 

main_review: This paper has a strong theoretical impact on stochastic optimization due to the introduction of the simple optimum estimator, which has potentially lots of applications in the field. However, some necessary empirical evidence is needed to demonstrate the efficiency and the advantage of the proposed estimator versus existing alternatives. 

Can you provide an example where you have to call ODC multiple times to get the estimator in (1)? In addition, there are many theoretical results in the main paper that are not followed by any discussion on the optimality and the comparison with existing methods. For example, for Theorem 4, it is as least interesting to the readers in what scenarios the proposed Algorithm 5 will have advantage over the method in [32]. Even if your goal is not to beat their algorithm, it is still helpful to convey the proper message to readers how the results stated here are positioned in the literature.

It is a little bit concerning to claim Theorem 5 as a theorem since it is not completely proved. The conclusion in Theorem 5 depends on Conjecture 1, which is not proved but shown to be hard to prove at the end of this paper. 

It is nice to see the theoretical improvement of the proposed estimator. However, since its biggest advantage is to reduce the sampling cost of stochastic gradient estimators in computation, there should be at least some simulation study on the applications discussed in this paper to compare the empirical performance of the estimator with other alternatives.   

Typos:
L10: “up logarithmic factors”
L74: “we instead instead apply ...”

---post rebuttal---
I have read the authors’ responses. I will keep my score as “accept” as long as the authors made the promised revision about discussions of theoretical results and conjecture.

limitations_and_societal_impact: The major limitation of this paper is the lack of empirical comparison with existing methods, while its main contribution is to develop efficient and nearly unbiased gradient estimators, which are claimed to achieve optimal bias to the optimum point with much fewer stochastic gradient evaluations. 

I do not see any potential negative societal impact directly related to this work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a constructive way to obtain an estimator of the minimizer of a Lipschitz strongly convex function $f$. Assuming that we have an access to a stochastic subgradient of $f$, we can run a variant of SGD that guarantees good complexity. Furthermore, the authors demonstrate on several examples how this estimator leads to new algorithms with a better complexity.


I think it is a good paper.

main_review: 
1. Although for optimization tasks (projection-efficient or gradient-efficient methods) different algorithms with the same complexity were known, I would say the proposed idea is more natural and easier to remember. The chapter with a non-smooth private convex optimization was not that interesting, especially taking into account the need to consider conjecture as an assumption.

2. Comparing the proposed approach with [32] or [46], the authors state that the former is a "simple alternative". I understand it as previous approaches are more complicated. However, from the algorithmic point of view I don't see it, perhaps even the opposite.

3. Corollary 2.1: I am not sure I understand the final complexity. In order to apply previous result, we have to use $\sigma:=\frac{\sigma}{\lambda}$ and $\delta := \frac{\delta}{\lambda}$, but this will give us a slightly different fractions in $O(\cdot)$.

4. I only checked mathematics for main results relating to the stochastic estimator, and they seem correct. The rest is a rather tedious calculation of various complexity bounds. Although it is possible that the authors have made a mistake, there is nothing contradictory in their statements and I am inclined to trust their results.



__Minor__:
1. line 74: two instead.
2. line 84: subproblems.
3. line 124: what is $X$?
4. line 173: Why do we ignore $\sigma$ as a constant in $\tilde O(1)$?
5. line 263: Why is $O(L^2R^2/\epsilon^2)$ optimal? Subgradient method needs $O(LR/\epsilon^2)$.
6. The authors call their stochastic estimator as low-bias and low-cost. To me it sounds a big vague. First, these two notions are dependent: the smaller the bias, the larger the cost. Second, in general why $O(1/\sigma^2)$ is considered to be as a low cost?


limitations_and_societal_impact: 0
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper develops a new primitive for stochastic optimization – a low-biased and low-cost estimator the minimizer x* for any Lipschitz strongly-convex function. Specially, the author(s) use a multi-level Monte-Carlo method to turn any optimal stochastic gradient method into an estimator x*. The paper also shows the potential of the estimator through four applications. 
main_review: The results could be interesting. However, the authors should explain why the contributions of the paper are important. I am still questionable about the contributions.

1) Can you please explain what is “nearly unbiased gradient estimators” and “nearly linear-time”? Through the paper, I am still confused what these terms are. 

2) It is not clear what set X could be. Does it require to be bounded, closed, or convex? Or it could be for any set? 

3) For the strongly convex function in R^d, there is a unique optimal solution x*. In order to determine the set X containing the optimal solution x*, the computational cost may be high. If x* is not in X, then the problem of finding argmin_{x in X} F ( x ) may not be interesting since the solution could be on the boundary of X. 

4) Assumption 1 should be correct if set X is bounded. However, as discussed in [Nguyen et al, “SGD and Hogwild! Convergence Without the Bounded Gradients Assumption”, ICML 2018], if X = R^d, then the \mu-strongly convex function f cannot be bounded gradients E || \hat{\nabla} F ( x ) ||^2 <= G^2 for all x in R^d. 

5) There are four applications listed in the paper, some numerical experiments to verify theory could be useful. I wonder if the author(s) could provide some interesting experiments to support the results. 

6) Proposition 2 and Theorem 3 require \epsilon to be smaller than some fixed number. Therefore, the results in Proposition 2 and Theorem 3 cannot be considered as complexity result since it should hold for any \espilon > 0. 

7) It seems that this paper can apply only for convex case. I am not sure how to generalize it to the non-convex case since it would have more applications. 

I am happy to raise the scores if my concerns have been addressed properly. 

---------------------

After rebuttal: 

Thank the authors for the response. I am still not convinced with the bounded assumption in the strongly convex case. Moreover, the lack of experiments is the true weakness of this paper. I have decide to keep my score unchanged. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper uses a multilevel Monte Carlo technique to produce a minimizer with a reduced cost and bias of a Lipschitz strongly convex function $f$ . The paper then applies this technique to obtain a cheap and nearly unbiased estimator for gradient of the Moreau envelope of Lipschitz convex functions, and presents different applications of this technique.
main_review: The current paper uses the Multilevel Monte Carlo method to find an estimator $\hat x_*$ of the minimizer $x_*$ of a function $F$ that satisfies certain assumptions (see Definition 2.1). The bias of $\hat x_*$ is $O(\delta)$, the variance is $O(\log(1/\delta))$ and the expected number of gradient evaluations required by the estimator is  $O(\log(1/\delta))$ (see Proposition 1). This result is interesting and is new to me. Averaging $m$ independent draws of this estimator yields an estimator with bias $O(\delta)$ and variance $O(\log(1/\delta)/m)$, which implies Theorem 1 for a suitable choice of $m$. 

Using the fact that the gradient of the Moreau envelope of a Lipschitz convex function can be calculated easily from the proximal operator, the paper shows that their technique can be applied to obtain a cheap and nearly unbiased estimator for the gradient of the Moreau envelope (see Corollary 2.1). 

The paper uses this gradient estimator and an accelerated gradient descent algorithm to design a projection-efficient convex optimization algorithm (Theorem 2). The authors note that their algorithm matches, up to polylogarithmic factors, the performance of a previous algorithm by Thekumparampil et al [39]. 

The authors also use their technique to minimize the maximum of $N$ Lipshitz convex functions with $\tilde O(N\epsilon^{-2/3}+\epsilon^{-2})$ complexity, improving upon a previous result by Carmon et al [14] (Theorem 3). 

Finally, the authors use their technique to provide a gradient-efficient composite acceleration algorithm that matches a previous algorithm by Lan [29] up to logarithmic factors (Theorem 4).

The paper also discusses potential applications to private convex optimization.

The results in this paper, especially those that improve upon previous results, seem interesting to me. On the negative side, the paper contains no numerical experiments, and I find it hard to read. Some suggestions:

--It is probably better to present the applications in Section 1.2 in the same order as in later sections.

--It is probably better to clarify the assumptions made on $\psi$, rather than putting them in a footnote (page 4).
 
--Line 138: the reference [26] shows how to optimize the function $f$, rather than the function $F$. This point needs to be clarified.

--In (1), is it assumed that $J\ge1$?  

--It may be better to put Algorithm 9 in the main paper, rather than the appendix.

------after feedback----- The authors address my comments well, so I increased my score.
limitations_and_societal_impact: I am not aware of limitations of the paper, except that it is not clear whether the algorithms in the paper are efficient in practice.
review_title: null

Meta-review: Although there was no consensus here, I think the paper should be accepted based on the the new theoretical results and the novelty of the algorithm.

One issue that was discussed quite a bit was the lack of empirical evaluation, which is strange for a NeurIPS paper proposing a new algorithm (as opposed to COLT, for example). Most NeurIPS readers will ask "does this algorithm actually work in practice", and without an answer to this the paper seems incomplete. Indeed, without this information it is likely that several poor graduate students will spend time implementing and trying out the method. The authors could save these people by doing it once, particularly if the algorithm does not work well in practice. Further, there might be some hidden assumption/disadvantage that makes the algorithm work much-worse in practice than the theory indicates (a classic example is the finite-termination of conjugate gradient which never actually happens empirically). Because of this, I am recommending acceptance but do not think the paper should be considered for a spotlight or oral or awards.

Finally, the camera-ready version should *at least* include a qualitative discussion of how the algorithm works empirically. Some examples:
- "Despite its theoretical properties, we found that the algorithm did not perform well empirically. More research is needed on this topic."
- "Although theoretically-faster in the worst case, the algorithm performed similarly to competing methods when we implemented it."
- "The algorithm outperformed method YYY in a preliminary implementation on the standard problem of ZZZ, although we did not explore extensive numerical experiments."
- "The algorithm converged very-quickly in practice, although more work needs to be done on decreasing the iteration cost."
- "The algorithm does not appear practical at all, but we hope our work will inspire others to develop practical variants with similar complexity bounds."
Decision: Accept (Poster)