acceptodds
Under review as a conference paper at ICLR 2027

Convergence Analysis of STORM Under Different Geometries

Abstract

Stochastic recursive momentum (STORM) achieves fast convergence for nonconvex optimization via the variance reduction effect, but existing analyses rely on the strong average smoothness assumption. In this paper, we study the convergence of STORM for different objectives without average smoothness. We first revisit the results under average smoothness, obtaining the bound for nonconvex objectives and the bound for last-iterate output under the -Polyak-Lojasiewicz (PL) condition. Without average smoothness, we design an auxiliary sequence and compare the STORM update with it in the analysis. With the help of this sequence, we prove that STORM still attains an rate for nonconvex objectives, which is optimal under standard smoothness. For convex and -strongly convex objectives, we further prove averaged and last-iterate bounds with optimal rates of and , respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.

Primary area:
learning theory
Keywords:
Variance reduction, sample complexity, strongly convex objectives

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cqAuOpenReview ↗
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 O(T(−1/3))O(T^{(-1/3)}) gradient-norm guarantee for nonconvex objectives and an O(σ2/(μT))O(\sigma^2/(\mu T)) leading stochastic term for the last iterate under PL. Without average smoothness, error shifting and a companion sequence sharing martingale innovations yield an O(T(−1/4))O(T^{(-1/4)}) 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
  1. The log-free, small-initial-batch performance in Theorem 1 is already available in [1].

  2. The last-iterate block schedule also has a direct methodological predecessor [2], which is not cited.

  3. The STORM algorithm can be viewed as a convex combination of the SARAH algorithm and the SGD algorithm, depending mainly on the parameter ata_t. When a_t = 0, the STORM algorithm reduces to the SGD algorithm, so it is natural that STORM still attains an O(T−1/4)O(T^{-1/4}) result.

  4. Theorem 6 uses β=1/(T+2)\beta=1/(T+2), and Theorems 7-8 use β=1/(T+s+1)\beta=1/(T+s+1), making STORM a perturbation that becomes increasingly close to SGD, but the resulting dominant rate is no better than that of SGD.

  5. The experiment does not specify x_0, the construction of Q, the actual LL/μ\mu/λ\lambda/ss 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
AuthorsOpenReview ↗

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.


Weakness 1. The log-free rate with a small initial batch in Theorem 1 is already available in [1].

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.


Weakness 2. The last-iterate block schedule has a methodological predecessor that is not cited.

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.


Weakness 3. The STORM algorithm can be viewed as a convex combination of the SARAH algorithm and the SGD algorithm, depending mainly on the parameter ata_t. When at=0a_t=0, the STORM algorithm reduces to the SGD algorithm, so it is natural that STORM still attains an O(T−1/4)O(T^{-1/4}) result.

First, in our notation, at=1a_t=1 (equivalently, β=0\beta=0) gives SGD, rather than at=0a_t=0. Although some of our schedules use a small β\beta, 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:

  1. The estimator is conditionally biased. Unlike SGD’s unbiased stochastic gradient, STORM’s estimator generally retains a conditional bias from previous iterations when β>0\beta>0. Our analysis explicitly controls this inherited error without average smoothness, so the guarantee is not a direct consequence of standard SGD analysis.

  2. Our analysis also covers a fixed coefficient away from zero. In the nonconvex setting, Theorem 3 permits β=1/2\beta=1/2, independently of TT, and establishes the O(T−1/4)O(T^{-1/4}) rate. We establish a fixed-coefficient guarantee for general smooth convex objectives, without average smoothness. Specifically, take β=1/2\beta=1/2 and we can prove that E[F(xˉT)−F∗]≤LR2/T+23σR/T\mathbb E[F(\bar x_T)-F^*]\le LR^2/T+2\sqrt3 \sigma R/\sqrt T. The rate remains the same order for even larger β\beta (e.g., 0.750.75 or 0.90.9), as long as β<1\beta < 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.


Weakness 4. The convex and strongly convex schedules approach SGD, while their dominant rates match SGD.

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≤β<11/2 \leq \beta <1, we can also achieve the O(LR2/T+σR/T)O(LR^2/T+\sigma R/\sqrt 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.


Weakness 5. The experiments omit initialization, the construction of Q, parameter values, budgets, seeds, and uncertainty definitions.

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.

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”?

Reviewer_AgByOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper analyzes the original STORM recursion for optimization with nonconvex, PL, convex, and strongly convex objectives. Under average smoothness, the authors establish an O(T−1/3)O(T^{-1/3}) bound on the expected gradient norm using a single initial sample, and a last-iterate bound with a leading stochastic term of order O(σ2/(μT))O(\sigma^2/(\mu T)) under the PL condition.

The main contribution concerns the convergence of STORM without average smoothness. Under standard smoothness and an unbiased stochastic oracle with bounded variance, the authors establish an O(T−1/4)O(T^{-1/4}) bound on the expected gradient norm for nonconvex objectives. For convex and strongly convex objectives, parameter choices depending on TT give convergence guarantees for both the weighted mean and the last iterate. Numerical experiments illustrate these results.

Critical strengths

Without average smoothness, the paper proves that STORM, with a fixed correction coefficient 0<β≤1/20<\beta\le1/2 independent of TT, still achieves the SGD rate of O(T−1/4)O(T^{-1/4}) in expected gradient norm for nonconvex objectives.

Critical weaknesses
  1. Theorems~6--8 choose β=1−a=O(T−1)\beta=1-a=O(T^{-1}), so the estimator approaches SGD as the iteration number TT increases. Here, β\beta multiplies dt−g(xt,ξt+1)d_t-g(x_t,\xi_{t+1}) in the estimator update; β=0\beta=0 gives SGD. The bounds therefore do not cover a positive β\beta independent of TT.

  2. The convex and strongly convex experiments omit SGD and choices of β\beta independent of TT. Moreover, results are plotted against updates, although STORM usually evaluates two stochastic gradients per update and SGD evaluates one. Therefore, the experiments do not isolate the benefit of STORM over SGD.

  3. Theorem 8 requires s≥4κ2s\ge4\kappa^2. Even the smallest admissible ss gives an initialization term of order O(λκ4R2/T2)O(\lambda\kappa^4R^2/T^2). For large κ\kappa, this term may dominate the upper bound despite the optimal O(σ2/(λT))O(\sigma^2/(\lambda T)) stochastic term. When σ=0\sigma=0, only the initialization term remains. The claim of an optimal rate should therefore be qualified.

  4. The experiments use only four objectives in dimension ten. Further numerical experiments on real-data problems would help assess the performance of the prescribed schedules.

Questions for authors
  1. What guarantees can be established for convex and strongly convex objectives when β\beta is independent of the iteration number TT? How should the results with β=O(T−1)\beta=O(T^{-1}) be interpreted relative to SGD?

  2. Can the convex and strongly convex experiments include SGD and several fixed-β\beta choices with the same number of stochastic gradient evaluations?

  3. Is the κ4\kappa^4 dependence in the initialization term necessary, or can it be improved in the analysis? Please clarify in what sense the rate is optimal, including in the noiseless case.

3 comments
AuthorsOpenReview ↗

Response to Reviewer AgBy

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.


Weakness 1. Theorems 6–8 use a vanishing recursive coefficient and do not cover a positive β\beta independent of TT.

The coefficient β=Θ(1/T)\beta=\Theta(1/T) approaches zero as T→∞T\to\infty, but remains strictly positive for every finite horizon. The recursive correction term is therefore retained in the algorithm. Besides, we choose a small β\beta primarily to simplify the analysis, and there is nothing problematic about using a small positive β\beta. Furthermore, our analysis does not generally require β\beta to approach zero. To show this, we additionally establish a fixed-coefficient guarantee for general smooth convex objectives. Specifically, take β=1/2\beta=1/2 and we can prove that E[F(xˉT)−F∗]≤LR2/T+23σR/T\mathbb E[F(\bar x_T)-F^*]\le LR^2/T+2\sqrt3 \sigma R/\sqrt T. The rate remains the same order for even larger β\beta(e.g., 0.750.75 or 0.90.9), as long as β<1\beta < 1. Thus, the standard convex convergence rate is achievable while the recursive coefficient remains fixed, independently of the horizon. We have included the complete theorem and proof in Appendix I.


Weakness 2. Missing SGD and fixed-coefficient comparisons accounting for computational cost.

Thank you for this suggestion. We have added comparisons with SGD and STORM with fixed recursive coefficients in the experiments. We also plot performance against measured wall-clock time to account for differences in computational cost. The results are provided in Figure 4 in Appendix L.


Weakness 3. The initialization term in Theorem 8 can dominate, so the optimality claim needs qualification.

Regarding the κ4\kappa^4 dependence, it appears only in the T−2T^{-2} initialization term and does not appear in the leading stochastic term O(σ2/(λT))O(\sigma^2/(\lambda T)), so we do not pay much attention to it. However, following the reviewer's suggestion, we have strengthened the strongly convex last-iterate analysis and obtained two results under the same assumptions, without average smoothness:

  1. Improved polynomial dependence. A refined analysis allows the choice s=O(κ)s=O(\kappa) in the same stepsize formula and gives E[F(xT)−F∗]=O(λκ2R2/T2+σ2/(λT))\mathbb E[F(x_T)-F^*]=O(\lambda\kappa^2R^2/T^2+\sigma^2/(\lambda T)). Thus, the initialization term's dependence on the condition number improves from κ4\kappa^4 to κ2\kappa^2 with this new parameter choice.

  2. Exponential initialization decay. Using a constant stepsize in the first phase, followed by the rounded harmonic schedule, gives E[F(xT)−F∗]=O(LR2exp⁡(−T/(51κ))+σ2/(λT))\mathbb E[F(x_T)-F^*]=O(LR^2\exp(-T/(51\kappa))+\sigma^2/(\lambda T)). This preserves the stochastic order while making the initialization term decay exponentially. In particular, when σ=0\sigma=0, the bound gives linear convergence.

The precise statements, parameter choices, and complete proofs are provided in Appendix J (Theorems 18 and 19). We have also revised the paper to emphasize that our optimal-rate claim refers specifically to the leading stochastic term, avoiding potential misunderstandings.


Weakness 4. Limited empirical evaluation on realistic learning tasks.

Thank you for this suggestion. We have added CIFAR-10 classification experiments with ResNet-18 in Section 6. The baselines include SGD, momentum SGD, STORM+, META-STORM, and Ada-STORM. Representative comparisons are presented in Figure 3. We report the results against measured wall-clock time. These additions complement the synthetic experiments with evaluation on a realistic learning task.


Question 1. What guarantees hold for convex and strongly convex objectives when β\beta is independent of TT, and how should the results with β=Θ(1/T)\beta=\Theta(1/T) be interpreted relative to SGD?

See our response to Weakness 1.


Question 2. Can the convex and strongly convex experiments include SGD and several fixed-beta choices with the same number of stochastic gradient evaluations?

See our response to Weakness 2.


Question 3. Can the condition-number dependence be improved, and in what sense is the rate optimal?

See our response to Weakness 3.

I appreciate the authors' responses. They have addressed my concerns.

Thank you for your kind response! We are glad that our responses have addressed your concerns. In light of this, we would appreciate it if you could consider updating your rating to reflect your revised assessment of the paper. Thank you again for your time and effort in reviewing our paper!

Reviewer_a1YzOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes the original STORM recursion for nonconvex, Polyak–Łojasiewicz, convex, and strongly convex objectives, both with and without average smoothness. Under average smoothness it removes a logarithmic factor in the nonconvex rate and gives an O(σ2/(μT))O(\sigma^2/(\mu T)) PL last-iterate term; under ordinary population smoothness it derives standard SGD-order nonconvex, convex, and strongly convex guarantees using shifted or companion iterates. Convex last-iterate results use geometrically shrinking step-size blocks, while strong convexity yields weighted-mean and last-iterate O(σ2/(λT))O(\sigma^2/(\lambda T)) terms. The proofs appear internally coherent and the auxiliary-sequence analysis is useful, but the weak-assumption parameter choices make STORM nearly collapse to SGD and the practical and condition-number implications are not convincingly assessed.

Critical strengths
  1. The shifted-iterate and same-noise companion-trajectory arguments are clean, reusable proof devices for controlling the conditionally biased recursive estimator without samplewise or average smoothness.
  2. The paper handles several geometries and output conventions in one framework, including technically nontrivial last-iterate bounds, and provides full proofs with explicit constants and schedules. A detailed audit did not identify a clear algebraic error.
  3. Under average smoothness, the analysis improves useful details of prior STORM results by removing the original logarithmic loss without a large initial batch and by obtaining a transparent PL last-iterate guarantee.
Critical weaknesses
  1. The principal “STORM without average smoothness” result is close to an SGD degeneration. With β=1−a\beta=1-a, the convex and strongly convex theorems choose β=Θ(1/T)\beta=\Theta(1/T), so a≈1a\approx1 and the recursive correction β(dt−g(xt,ξ))\beta(d_t-g(x_t,\xi)) vanishes with the horizon; setting β=0\beta=0 recovers SGD exactly. The nonconvex theorem permits any fixed 0<β≤1/20<\beta\le1/2 and obtains precisely the classical SGD rate rather than a variance-reduced rate. Thus the results show that a near-SGD endpoint of the STORM recursion inherits SGD-order guarantees, not that STORM's defining variance-reduction mechanism remains effective without average smoothness.

  2. The schedules are strongly horizon- and parameter-dependent. The theorems require advance knowledge of TT, LL, noise/initialization scales, and μ\mu or λ\lambda, with different schedules for random, averaged, and last-iterate outputs. The PL theorem requires s≥16(L/μ)2s\ge16(L/\mu)^2, and the strongly convex last-iterate theorem requires s≥4κ2s\ge4\kappa^2 while carrying a bias term proportional to (s+1)2/T2(s+1)^2/T^2, potentially producing a κ4\kappa^4 transient. Calling the rates optimal based only on the exponent of TT obscures potentially severe finite-time and condition-number dependence.

  3. The average-smoothness contribution is an analysis refinement rather than a new algorithmic result. The original STORM paper already established the T−1/3T^{-1/3}-order variance-reduced regime, while STORM+ and Ada-STORM address adaptivity and logarithmic factors under related assumptions. The genuinely new contribution is the companion-sequence proof under ordinary smoothness and its last-iterate bookkeeping, whose algorithmic benefit over classical SGD remains unclear.

  4. The empirical evidence is too narrow. Experiments use four constructed ten-dimensional objectives with known constants and synthetic Gaussian or heavy-frequency noise, theorem-specific hyperparameters, and no realistic learning task. There is no wall-clock or oracle-normalized comparison with tuned momentum SGD, STORM+, META-STORM, Ada-STORM, or recent double-momentum methods. The weak-assumption STORM curves are nearly indistinguishable from SGD, reinforcing the concern that the analyzed regime is simply a perturbation of SGD.

  5. The paper does not establish when a practitioner should prefer these schedules. STORM uses two related stochastic-gradient evaluations per iteration to match rates available from one-gradient SGD, yet the paper reports results by iteration rather than oracle call. The rounded last-iterate blocks are designed for a fixed terminal horizon and must be rescheduled if training stops early. Without an anytime/parameter-free construction or a demonstrated constant-factor, stability, or accuracy advantage, the practical significance remains limited.

Questions for authors
  1. Can a no-average-smoothness guarantee be proved with the recursive coefficient bounded away from zero, or is degeneration toward SGD necessary?
  2. What substantive improvement remains over the exact β=0\beta=0 recursion when individual stochastic-gradient evaluations rather than iterations are counted?
  3. Can the schedules be made anytime and adaptive to T,L,λ,μ,σ,Δ0,RT,L,\lambda,\mu,\sigma,\Delta_0,R without losing the stated last-iterate rates?
  4. How large must TT be as a function of κ\kappa before the O(σ2/(λT))O(\sigma^2/(\lambda T)) term dominates the initialization term?
  5. Can the experiments include realistic learning tasks and matched-oracle comparisons with SGD, momentum SGD, STORM+, META-STORM, Ada-STORM, and double-momentum baselines?
5 comments
AuthorsOpenReview ↗

Response to Reviewer a1Yz (Part 1)

We thank the reviewer for the constructive comments! We have uploaded a revised version of the paper that addresses most of your concerns.


W1. The principal STORM without average smoothness result is close to an SGD degeneration.

First, we would like to clarify that our paper never claims that STORM retains a variance-reduction effect without average smoothness. Matching stochastic convergence orders for STORM under different assumptions is our intended theoretical result.

Second, coefficient β=Θ(1/T)\beta=\Theta(1/T) approaches zero as T→∞T\to\infty, but it remains strictly positive for every finite horizon. The recursive correction term is therefore retained in the algorithm. For comparison, the learning rate in Theorem 1 is η=1/[2L(T+2)1/3]\eta=1/[2\mathcal L(T+2)^{1/3}], which also approaches zero as T→∞T\to\infty. This does not mean that the learning rate is zero and the algorithm performs no updates. Likewise, the limiting value of the correction coefficient alone cannot replace an analysis of the finite-horizon recursion. Specifically, the recursive estimator introduces inherited conditional bias, so its convergence guarantees do not follow from the unbiased-SGD analysis. Our companion-sequence argument controls this bias using the nonexpansiveness or contraction of the population gradient map. This provides finite-horizon guarantees while explicitly accounting for the recursive correction.

Third, we choose a small β\beta primarily to simplify the analysis, and our analysis does not generally require β\beta to approach zero. As shown in our response to your Question 1, taking the fixed value (e.g., β=0.5\beta=0.5, β=0.9\beta=0.9 ) also yields the standard convex convergence rate. This provides concrete evidence that our analysis is not restricted to a degeneration toward SGD.


W2. The schedules are strongly horizon- and parameter-dependent.

Thank you for this comment! Developing a parameter-free/adaptive STORM algorithm is not the objective of this paper, and our goal is to establish that the original STORM recursion attains the standard convergence rates across the five settings summarized in Table 1. Nevertheless, following your suggestion, we have added a parameter-free, anytime last-iterate guarantee under the PL condition and average smoothness in Appendix K. This result demonstrates that our analysis can support further progress toward parameter-free STORM, although the parameter-free analysis remains beyond the scope of this paper.

Regarding the κ4\kappa^4 dependence, it appears only in the T−2T^{-2} initialization term and does not appear in the leading stochastic term O(σ2/(λT))O(\sigma^2/(\lambda T)), so we do not pay much attention to it. Nevertheless, a more refined analysis can improve the initialization term, and we have included such improvements in Appendix J of the revised paper. First, the refined analysis permits s=O(κ)s=O(\kappa) and yields O(λκ2R2/T2+σ2/(λT))O(\lambda\kappa^2R^2/T^2+\sigma^2/(\lambda T)), reducing the dependence from κ4\kappa^4 to κ2\kappa^2. Second, a two-phase stepsize schedule yields O(LR2e−T/(51κ)+σ2/(λT))O(LR^2 e^{-T/(51\kappa)}+\sigma^2/(\lambda T)), giving exponential decay of the initialization term. We have also revised the paper to emphasize that our optimal-rate claim refers specifically to the leading stochastic term, avoiding potential misunderstandings.


W3. The average-smoothness contribution is an analysis refinement rather than a new algorithmic result.

As stated in the paper, our objective is to provide new convergence analyses for STORM under different settings, not to propose a new algorithm or demonstrate superiority over SGD. Our new results establish convergence under standard smoothness alone for nonconvex, convex, and strongly convex objectives, including averaged and last-iterate guarantees for STORM in the convex and strongly convex settings. This broadens the theoretical understanding of STORM beyond the assumptions and objective geometries covered by its previous analyses.

To further demonstrate how STORM differs from SGD in practice, we have added direct comparisons with SGD in Section 6, including classification experiments on CIFAR-10, where STORM shows improved performance over SGD.


W4. The empirical evidence is too narrow.

As explained in the original submission, "Our contribution is an analysis of the original STORM algorithm and its empirical performance has already been studied extensively in previous literature". Since we do not propose a new algorithm, the initial experiments focused on illustrating our theoretical results.

However, following the reviewer’s suggestion, we have added experiments on the CIFAR dataset in Section 6 and added many baselines, including SGD, momentum SGD, STORM+, META-STORM, and Ada-STORM. These experiments also show different numerical results between STORM and SGD, providing evidence that the recursive correction can meaningfully affect practical training and that STORM is not a simple perturbation of SGD.

AuthorsOpenReview ↗

Response to Reviewer a1Yz (Part 2)

W5. The paper does not establish when a practitioner should prefer these schedules...

Our schedules provide theoretically justified parameter choices for STORM across the five settings in Table 1, including last-iterate guarantees. Our objective is to establish these guarantees, without claiming that the proposed schedules outperform SGD or adaptive alternatives in practice. We view our analysis as a first step toward understanding STORM across these five settings. Regarding computational cost, our new CIFAR experiments in Section 6 plot performance against wall-clock time rather than iteration number for a fairer comparison.


Q1. Can a no-average-smoothness guarantee be proved with the recursive coefficient bounded away from zero, or is degeneration toward SGD necessary?

Such a guarantee can be proved with the recursive coefficient bounded away from zero. For nonconvex objectives, Theorem 3 already allows any fixed β∈(0,1)\beta\in(0,1). In particular, β=1/2\beta=1/2 gives the O(T−1/4)O(T^{-1/4}) guarantee without average smoothness.

We additionally establish a fixed-coefficient guarantee for general smooth convex objectives, without average smoothness. Specifically, take β=1/2\beta=1/2 and we can prove that E[F(xˉT)−F∗]≤LR2/T+23σR/T\mathbb E[F(\bar x_T)-F^*]\le LR^2/T+2\sqrt3 \sigma R/\sqrt T. The rate remains the same order for even larger β\beta (e.g., 0.750.75 or 0.90.9), as long as β<1\beta < 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.


Q2. What substantive improvement remains when individual stochastic-gradient evaluations rather than iterations are counted?

For our results, we do not claim an oracle-complexity improvement over SGD. Our contribution is to establish convergence guarantees for the original STORM recursion under standard smoothness and across different objective geometries. To assess practical performance while accounting for the additional computation, our newly added CIFAR experiments plot performance against wall-clock time. These comparisons complement the theoretical guarantees, and the results can be found in Section 6.


Q3. Can the schedules be made anytime and adaptive to T,L,λ,μ,σ,Δ0,RT, L,\lambda,\mu,\sigma,\Delta_0, R without losing the stated last-iterate rates?

Thank you for this question. Following your suggestion, we have established an anytime, parameter-free last-iterate guarantee under the PL condition and average smoothness, with the complete proof in Appendix K. Specifically, the fixed schedule ηt=(t+3)−2/3\eta_t=(t+3)^{-2/3} and at+1=2/(t+3)a_{t+1}=2/(t+3) require neither a prescribed horizon nor knowledge of the problem parameters, including the average-smoothness constant. For every deterministic T≥0T\ge0, it guarantees E[F(xT)−F∗]≤CU33(T+3)3+4σ2μ(T+3)\mathbb E[F(x_T)-F^*] \le \frac{CU_3^3}{(T+3)^3} +\frac{4\sigma^2}{\mu(T+3)}, where CC and U3U_3 are explicit parameter-dependent constants defined in Appendix K and are used only in the analysis.

Thus, in this setting, the original STORM recursion admits an anytime, parameter-free schedule while retaining the optimal leading stochastic rate for the actual last iterate. This result demonstrates that our analysis can support further progress toward adaptive STORM, although the adaptive analysis remains beyond the scope of this paper.


Q4. How large must TT be as a function of κ\kappa before the 1/T1/T stochastic term dominates the initialization term?

As mentioned in our response to Weakness 2, the new results in Appendix J improve the condition-number dependence of this threshold. For σ>0\sigma>0, write ρ=λR/σ\rho=\lambda R/\sigma.

First, with s=50κs=50\kappa, Theorem 18 gives E[F(xT)−F∗]≤32eλ(50κ+1)2R2(T+1)2+225σ2λ(T+1).\mathbb E[F(x_T)-F^*] \le \frac{32e \lambda(50 \kappa +1)^2R^2}{(T+1)^2} +\frac{225\sigma^2}{\lambda(T+1)}. The initialization term is no larger than the stochastic term when T+1≥(32e/225)(50κ+1)2ρ2T+1\ge(32e/225)(50\kappa+1)^2\rho^2. Thus, for fixed ρ>0\rho>0, the sufficient horizon scales as κ2\kappa^2, improving upon the original κ4\kappa^4 dependence.

Second, for the two-phase schedule in Theorem 19, the ratio of the initialization term to the stochastic term in its more precise bound is at most 4κρ2e−T/(51κ)4\kappa\rho^2 e^{-T/(51\kappa)}. Consequently, T≥51κlog⁡(1+4κρ2)T \ge 51\kappa\log(1+4\kappa\rho^2) suffices, giving a κlog⁡κ\kappa\log\kappa scaling.


Q5. Can the experiments include realistic learning tasks and matched-oracle comparisons with SGD, momentum SGD, STORM+, META-STORM, Ada-STORM, and double-momentum baselines?

Thank you for this suggestion. We have conducted additional experiments on CIFAR-10 and added the baselines you mentioned, including SGD, momentum SGD, STORM+, META-STORM, and Ada-STORM. The results can be found in Section 6.

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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.