Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes an adaptive variant of the recently proposed STORM algorithm for minimizing expectations of smooth, nonconvex losses. By doing so, it removes the hyperparameters necessary for running STORM.
It offers an analysis of the method and rates of convergence, but no empirical validation of the method.
main_review: The main argument for this method is practical : STORM requires parameters that are hard to access, namely the common lipschitz constant of the functions appearing in the expectation. It seems to me that it is therefore crucial to show experiments validating the proposed adaptive method. Additionally, it would be beneficial to compare the adaptive variant to the sublinear momentum variant on typical problems.
This explains my rating. I will be glad to modify it given empirical evidence of the proposed algorithm's performance. I would recommend a minima reproducing the experiments from the initial STORM paper, adding the STORM+ variants considered in this paper.

The worst case bound adapts to the magnitude of noise: is this the case in practice on toy experiments? It would be nice to check whether this is an artifact of the proof/worst case, or if this is also true in practice. Such experiments would help me modify my rating.

What is the point of section 5.2 ? I would argue to move this to appendix, saying that a version of the algorithm w/ sublinear momentum parameter also achieves the same aymptotic convergence rate, although the non-asymptotic rate does not adapt to the variance of the stochastic gradient estimator.
Rather than provide the analysis for the case sigma=0 and the case w/ sublinear momentum parameter, I would also rather see an extended sketch of the analysis of STORM+ in the main paper. It would also be helpful for the reader to re-state things when they are needed. 

The paper is not very well written, with quite a few typos. I would recommend working on the flow of the paper and its presentation : re-stating asumptions/lemma results when needed, relying less on bullet-point style presentation (cf line 182 - 206).

Comments on form:
Typo line 30: hanging sentence
Line 82: forgot the bar on x
It should be “Such that” instead of “such” in all the conditions (bounded values etc)
Line 84: why is x* a global minima, rather than a stationary point?
Line 92: notation consistency: maybe use greek letters for scalars? (a_t -> rho_t or beta_t to be consistent with the literature?)

Lemma 2: why is it written that p must be rational? This isn’t used in the proof in the appendix.
Proof of lemma 2 : the induction hypothesis must hold for n-1 >= 1, not > 1. It also needs to be said somewhere that b1 cannot be 0.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper is interesting and technically sound. It devises a thoroughly parameter-free algorithm named STORM+, on the basis of STORM. STORM+ obtains the optimal theoretical results and achieves comparable performance with respect to other adaptive methods. The merit of this paper is that it does not require the knowledge of any problem parameters and only initial step-size tuning suffices. 
main_review: 1. Perhaps several important findings/conclusions can be better presented in the form of theorems or lemmas, e.g., contents in Line 141-142 and Line 156-159.

2. The meaning of several sentences is not clear (e.g., in Line 209). Careful proofreading is recommended.

3. STORM+ and its simplified ones achieve the optimal rate $\frac{1}{\epsilon^3}$. What are the main differences between them? More discussion is needed to make this paper more solid.

4. Detailed derivations of $M_t$ in Line 413 are preferable, as well as $Y_t$ in Line436.

5. All mathematical symbols or operators used in the text are required to be defined.

6. More discussion and comparison between STORM+ and the existing nonconvex stochastic optimization methods are recommended.

7. The reviewer believes that the main conclusions of the article are solid. However, the current version is not suitable for publication and the reviewer would like to suggest the authors to make serious revision to the article in terms of logic, presentation and organization.

Typos: 

Line 146: $...\leq -\frac{1}{\eta_T}\Delta_{t+1} + …$ $\rightarrow$ $...\leq -\frac{1}{\eta_T}\Delta_{T+1}+ …$

Line 204: he$\rightarrow$the

limitations_and_societal_impact: More experiments should be conducted to demonstrate the effectiveness of the proposed method.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors provide a parameter-free version named STORM+ of the STORM algorithm. STORM+ uses the same single-loop recursive momentum (which leads to implicit variance reduction effects) and constant batchsizes as in STORM, but features a parameter-free design by constructing the learning rate \eta_t and momentum coefficient a_t using past parameters and momentums (as a comparison, STORM needs to tune these two factors manually). Theoretically, the authors show that STORM+ achieves the same near-optimal complexity as STORM but without needing to tune the parameters to ensure this guarantee.

main_review: After response:

Thanks a lot for your response. I appreciate the novel analysis in this paper to handle the hyperparameters' adaptivity in the original STORM method, and after my second reading, I feel that I am too picky at the assumptions and experiments in this paper. Therefore, I increase my score to 6.
....................................................................................................................................................................................

In this paper, the authors provide a parameter-free version named STORM+ of the STORM algorithm. STORM+ uses the same single-loop recursive momentum (which leads to implicit variance reduction effects) and constant batchsizes as in STORM, but features a parameter-free design by constructing the learning rate \eta_t and momentum coefficient a_t using past parameters and momentums (as a comparison, STORM needs to tune these two factors manually). Theoretically, the authors show that STORM+ achieves the same near-optimal complexity as STORM but without needing to tune the parameters to ensure this guarantee. My detailed comments are given as follows. 

Pros: 
1.	This paper is easy to following and overall well-written. The motivation is very clear, i.e., replacing the manually tuned learning rate and the momentum coefficients in STORM with adaptive ones based on past iterate information. The proof idea is easy to get based on the sketch in Section 5. Basically, it seems to me that the authors try to add d_i into \eta_t and a_t so that the resulting convergence results also contain a summation of d_i, and such a summation can be well handled after do the telescoping for the final convergence analysis. Overall, the idea is reasonable to me.

2.	It is good to show that the resulting scheme can achieve the same optimal complexity as STORM. Parameter-free optimization and variance reduction are both of great interest to the community, and of course parameter-free algorithm with near-optimal performance guarantee should be of interest. 

Cons:
1.	However, I have several concerns on the assumptions and the empirical justification. First, I note that compared to the analysis for STORM, this paper seems to additionally assume that the function value of f is bounded, i.e., max_{x,y\in R^d} |f(x)-f(y)|<\infty. As a result, the comparison to STORM in this paper here is not that fair. In addition, this is a very strong assumption as x is allowed to be any vector in R^d, which can be violated, e.g., for simple linear function f(x)=wx. I am wondering whether such value boundedness is necessary for the adaptivity proof. In STORM paper, they assume the gradient is bounded (as also made in this paper) because they can use this assumption to remove the variance factor \sigma in the learning rate. I am thinking whether this bounded value assumption is further used  to remove other manually tuned parameters? I hope the authors can explain a little bit. 

2.	No experiments are provided in this paper. Parameter-free optimization is interesting because it will help to eliminate the expensive hyperparameter selection process while achieving the same promising performance. STORM not only achieves the optimal complexity, but also has good practical performance (comparable to Adam). I strongly encourage the authors can test the performance of STORM+ and figure out whether it is comparable to (even better if it can outperform) STORM with the best hyperparameter tuning. I wish to see such a comparison in the authors’ response.

Overall, I feel this paper contains some interesting designs and analysis, but given my concerns in the assumption and the lacking experiments, I cannot accept it currently. However, I am open to increase my score based on other reviewers’ comments and the authors’ response.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes STORM+, which adopts the STORM method with a new way to set the learning rate (parameter free momentum based). The method also obtains the state-of-the-art convergence result for finding an approximate stationary point. 
main_review: Comments: 

1) The idea of applying the adaptive learning rate to the existing method is not new. This could be considered as a marginal work. However, I appreciate the convergence analysis of the paper. 

2) Numerical experiments (in the supplementary document) do not show any advantages of STORM+ over STORM. It is true that STORM+ does not require to tune the parameters because of the parameter-free choices of parameters, but from the experiments, it is not clear whether STORM uses the best tuning parameters. 

3) Comparing to other methods, STORM+ also does not show the benefits. This would raise a question why people have to consider this method but not using Adam. I would suggest the authors provide more experiments to verify the effectiveness of the proposed method. 

4) Since the paper focuses on the practical side of STORM, it would be nice to bring the numerical experimental part into main content. 

5) Hybrid-SGD in [Tran-Dinh et al, 2019] does not require “bounded values” and “bounded gradients” assumptions. Could you please have some discussion of why the proposed method has more advantage than Hybrid-SGD? I do not see much comparisons with this method. 


limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper generated a lot of discussion among reviewers. Overall it seems that the contribution is novel and provides an interesting new learning rate schedule meriting acceptance. However, the claims of optimality in the rates are not well-supported. The extra assumption that the objective is bounde above and below may invalidate current lower bounds. 

Decision: Accept (Poster)