- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper analyzes the same STORM recursion across objective geometries and oracle regularity conditions. Under average smoothness, it establishes an gradient-norm guarantee for nonconvex objectives and an leading stochastic term for the last iterate under PL. Without average smoothness, error shifting and a companion sequence sharing martingale innovations yield an nonconvex guarantee with fixed beta, and convex/strongly convex guarantees for averages and last iterates with horizon-dependent beta. Experiments use four ten-dimensional synthetic objectives and two oracle models.
Critical strengths
Theorem 3 genuinely permits fixed nonzero beta, rather than simply setting beta=0 and recovering SGD. Oracle (36) is a meaningful construction with bounded variance and no finite average-smoothness constant. Objectives with known gradients and minima are appropriate for checking consistency with the theory.
Critical weaknesses
-
The log-free, small-initial-batch performance in Theorem 1 is already available in [1].
-
The last-iterate block schedule also has a direct methodological predecessor [2], which is not cited.
-
The STORM algorithm can be viewed as a convex combination of the SARAH algorithm and the SGD algorithm, depending mainly on the parameter . When a_t = 0, the STORM algorithm reduces to the SGD algorithm, so it is natural that STORM still attains an result.
-
Theorem 6 uses , and Theorems 7-8 use , making STORM a perturbation that becomes increasingly close to SGD, but the resulting dominant rate is no better than that of SGD.
-
The experiment does not specify x_0, the construction of Q, the actual /// values, budget sequence, seeds, or uncertainty bars.
[1] Xu Y, Xu Y. Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization. Journal of Optimization Theory and Applications, 2023, 196(1): 266-297.
[2] Jain P, Nagaraj D, Netrapalli P. Making the last iterate of sgd information theoretically optimal. Conference on Learning Theory. PMLR, 2019: 1752-1755.
Questions for authors
see Weaknesses
4 comments
Dear Reviewer,
Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.
As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.
I appreciate the authors' responses. They have addressed my concerns.
Thank you for confirming that our responses have addressed all your concerns. We appreciate the time and effort you have devoted to reviewing our paper, as well as your positive assessment of our rebuttal. However, since the concerns have been addressed, would you please consider increasing your rating from “2: Weak rejection”?
Response to Reviewer cqAu
We thank the reviewer for the careful reading and constructive comments! We have uploaded a revised version of the manuscript that addresses your concerns in detail.
Thank you for pointing this out. We have cited this paper in our revised paper. Compared with their analysis, our Theorem 1 provides an alternative Lyapunov analysis of this known guarantee. Furthermore, our new results concern the broader convergence analysis of STORM, including the last-iterate guarantee under the PL condition and the nonconvex, convex, and strongly convex guarantees without average smoothness. Together, these results establish the standard convergence rates across the five settings summarized in Table 1.
Thank you for pointing out this omission. In our revised paper, we have explicitly cited their work where the schedule is introduced. Our contribution is the analysis needed to establish last-iterate guarantees for STORM. Its recursive estimator is conditionally biased, so the SGD guarantees cannot be applied directly. We construct a companion sequence driven by the same centered innovations, analyze its convergence, and control its difference from the actual STORM iterates. This establishes convex and strongly convex last-iterate guarantees under standard smoothness and bounded variance, without requiring average smoothness or globally bounded stochastic gradients for the STORM estimator.
First, in our notation, at=1 (equivalently, β=0) gives SGD, rather than at=0. Although some of our schedules use a small β, it remains strictly positive for every finite horizon. A small recursive coefficient alone does not establish that STORM inherits SGD’s convergence rate. Two points are relevant:
The estimator is conditionally biased. Unlike SGD’s unbiased stochastic gradient, STORM’s estimator generally retains a conditional bias from previous iterations when β>0. Our analysis explicitly controls this inherited error without average smoothness, so the guarantee is not a direct consequence of standard SGD analysis.
Our analysis also covers a fixed coefficient away from zero. In the nonconvex setting, Theorem 3 permits β=1/2, independently of T, and establishes the O(T−1/4) rate. We establish a fixed-coefficient guarantee for general smooth convex objectives, without average smoothness. Specifically, take β=1/2 and we can prove that E[F(xˉT)−F∗]≤LR2/T+23σR/T. The rate remains the same order for even larger β (e.g., 0.75 or 0.9), as long as β<1. Thus, the standard convex convergence rate is achievable while the recursive coefficient remains fixed, independently of the horizon. Approaching the SGD endpoint is therefore not necessary. We have included the complete theorem and proof in Appendix I.
We have to emphasize that our objective is to establish convergence guarantees for the original STORM framework across different settings, including convex and strongly convex last-iterate guarantees without average smoothness. We do not claim an improvement over SGD’s convergence order.
As discussed in our response to your Weakness 3, although Theorems 6–8 use small recursive coefficients, these coefficients remain strictly positive for every finite horizon. The estimator therefore retains a conditional bias, which our analysis must explicitly control. Closeness to SGD alone does not establish the stated guarantees. Furthermore, we have added a fixed-coefficient result for general smooth convex objectives in Appendix I. Even with 1/2≤β<1, we can also achieve the O(LR2/T+σR/T) rate under the same unbiased-oracle and bounded-variance assumptions, without average smoothness. This shows that the standard convex rate is achievable while retaining a recursive coefficient independent of the horizon.
Thank you for pointing out these omissions. We have added the initial point, the construction of Q, and the numerical parameter values in Section 6 of the revised paper.