Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a variance reduction method based on the STORM algorithm. Not like STORM, their algorithm does not require access to specific problem parameters such as the Lipschitz constant and the gradient bound. They prove that this algorithm will converge at the rate of $O(T^{-1/3})$ under slightly weaker assumptions than STORM.
strength_and_weaknesses: Strength:
- Based on STORM’s framework, the paper designs an algorithm that does not require the knowledge of the Lipschitz constant or the variance bound constant, which is practical.
- The algorithm converges under the same iteration complexity of $O(T^{-1/3})$ as the pioneering work STORM+ without the assumption that the function value is bounded. Their assumption is also slightly weaker than that of the original STORM.
- The algorithms seem to have more stable convergence behavior than Adam and STORM+, and the heuristic version has a competitive convergence speed compared with Adam.

Weakness:
- The choice of parameter $p$ seems to have a large effect on the algorithm’s convergence.


clarity,_quality,_novelty_and_reproducibility: The paper is overall well organized and easy to follow. The analysis (that removes the previous bounded function assumption) is interesting. 
summary_of_the_review: The paper proposes a fully adaptive optimization method based on STORM and proves its convergence under mild assumptions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the variance reduction technique for nonconvex optimization, along the research line of STORM and STORM+. The proposed META-STORM extends STORM+ by relaxing the assumption of bounded function value STORM+ while achieving the optimal convergence rate.
strength_and_weaknesses: Strengths:

1: This paper is somewhat novel.

2: The theoretical analysis is technically sound.

3: This paper is well-written and easy to follow. 


Weaknesses:

1: The proposed META-STORM introduces an additional learning rate that needs to be tuned. (Note STORM and STORM+ do not require this additional hyperparameter.) Thus, META-STORM is not a fully adaptive algorithm. The authors need to explain this.

2: How will relaxing the assumption of bounded function value STORM+ affect the optimization process in practice? Can the authors provide some examples with unbound function values that STORM+ would fail? Or this assumption is only required for the analysis of STORM+? The authors may need to provide more explanations here. 
clarity,_quality,_novelty_and_reproducibility: Novelty: This paper is somewhat novel. The improvement is limited and not very interesting.

Quality: The theoretical analysis is technically sound with excellent analysis. Extensive experimental validation is provided.

Clarity: The paper is clearly written and easy to follow.

Reproducibility: The code needed to reproduce the experimental results is not provided.
summary_of_the_review: This paper extends STORM+ by relaxing the assumption of bounded function value STORM+ while achieving the optimal convergence rate. The improvement is somewhat novel, but not very interesting.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies variance reduced methods for nonconvex optimization. In particular, variants of STORM are proposed to remove the unreasonable assumptions in STORM+. Numerical results are then presented to demonstrate the proposed algorithms.
strength_and_weaknesses: **Strength:** 
Overall, the strength of this work lies in its theoretical part. What interests me the most is the theoretical frame work of updating $a_t$ in META-STORM. This novel design helps to remove unnecessary assumptions in previous works. 

**Weakness:**

The numerical experiments are relatively weak compared to its theoretical part. 

- (W1) Numerical experiments on Cifar10 is not optimal, for example I assume that there is no learning rate decay by examining the loss curve of SGD. And the final test accuracy seems not matching the best that one can achieve (93 to 94%).

- (W2) The paper is somehow contradicted: it motivates fully adaptively to parameters when choosing learning rates, yet has to tune through grid search for best numerical performance in numerical tests.  

- (W3) It is not clear what are the specific heuristics used for in META-STORM (H). Moreover, can the authors explain the reasons for coordinate-wise learning rate in META-STORM(H)? It looks to me that the b_t update is a normalized adaptive learning rate, which is a simplified version of coordinate-wise learning rate. It is hence less intuitive for me to make adaptivity adaptive.

- (W4) How does an epoch counts in the experiments? Since the proposed algorithms compute two gradients while SGD and Adam only needs one.

clarity,_quality,_novelty_and_reproducibility: The theory is clear but some of detailed implementation is not. Theory is novel.

summary_of_the_review: This works falls more into theoretical part. And it indeed removes unreasonable assumptions in previous works. The numerical results do not fully support the theoretical findings due to the suboptimal implementation and benchmarks.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a few improved variants of STORM+ that generalizes to a broader class of functions with weaker assumptions and better theoretical guarantees. STORM+ is a VR algorithm for non-convex stochastic optimization problems. However, prior methods suffer from assumption like boundedness of function value and the theoretical convergence depends on such parameters. In this work, the authors propose an adaptive framework for STORM+ that removes this dependence and relaxes a few other assumptions. They also corroborated their new algorithms with empirical experiments.
strength_and_weaknesses: The paper is well-motivated and structured in a way to help authors understand the technical contributions in proving the results. I think the writing and exposition may be improved from the following few aspects, and would be happy to re-evaluate the paper once these are addressed properly:

1) I think the technical section 3.1 and 3.2 could be written slightly more clearly to highlight which parts of the analysis are inherited from prior work, and which are new contributions. The current way written without reading the previous papers it is not immediate to me which part helps remove the additional / stronger assumptions in prior work. Also is there any difference in the adaptivity design part compared with prior work?

2) The final complexity result stated in theorems doesn't agree on units (i.e. see definition of kappa, Q_1 in the paper etc.). When scaling the function by an additional factor L, the convergence result doesn't seem scale-invariant, which is a bit counter-intuitive to me. Would there be a proper analysis that could make this scale-invariant?

3) The final high-probability bounds it may be helpful to directly state it using log(1/delta), and save the reasoning in the proof sketch. This makes the results more citable for future work.

4) In the experiments, the figure could be improved a little bit to make each line of comparison look clearer (i.e. the color of STORM+ and another META-STORM-SG(H) looks quite confusing). Also, some parts of the comparison doesn't feel very fair since you are comparing META-STORM with heuristic to STORM+ without. It may be beneficial to use same heuristic on both methods and then compare.
clarity,_quality,_novelty_and_reproducibility: The paper has a clear exposition and there seems to be some novelty in obtaining the results. I think the authors could make it clearer by comparing with prior work more and stating the concrete novel elements in the new proof. The experiment section could be written in a clear way (see last point in previous comment).
summary_of_the_review: I think the paper is studying an interesting problem and has some nice idea in it. I think both the theory and experiment part could be improved more to make the contributions and supporting arguments clearer. Due to these reasons I gave my recommendation of the paper as below but am open to changing once my concerns are properly addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a variance reduction method based on the STORM algorithm. The proposed META-STORM extends STORM+ by relaxing the assumption of bounded function value STORM+ while achieving the optimal convergence rate.

This paper is in borderline. However, the reviewers think that the contributions of the paper are marginal and most of the reviewers would not like to support publication of this paper. The authors could consider the following concerns: 

1) The proposed algorithm is incremental compared to STORM and STORM+. The improvement is limited in both theory and practice. In terms of the practical performance, it is not clear about the improvements. Therefore, the experiments are not convincing that the proposed algorithm is beneficial. 
2) The authors seem to ignore the whole core variance reduced methods in the literature. I believe that section 1.1 is not studied enough. 
3) In Tran-Dinh et al. Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization, 2019 (and its variants along this line of research), they proposed the analysis with less assumptions compared to this paper (No assumptions 4 and 5). I do not see any discussions as well as comparison to this algorithm in both theory and experiments. The authors mentioned that their contributions could deal with the unbounded functions while it can also be done in the literature, though different algorithm. Therefore, the theoretical contribution is not significant. 

I strongly encourage the authors to consider all points above to improve the paper for the future submission. The current result is not enough for the publication at ICLR. 

justification_for_why_not_higher_score: - The proposed algorithm is incremental compared to STORM and STORM+. The improvement is limited in both theory and practice. In terms of the practical performance, it is not clear about the improvements. 
- The authors seem to ignore the whole core variance reduced methods in the literature.
- The authors did not compare well with the results in Tran-Dinh et al. Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization, 2019.
Decision: Reject