acceptodds
Under review as a conference paper at ICLR 2027

Cumulative-Variance-Adaptive Decentralized STORM

Abstract

Gradient noise in decentralized optimization may vary along the optimization trajectory, while the smoothness constant is often unknown. We propose Noise-Adaptive Decentralized STORM, which combines locally accumulated direction energy, a two-sample noise proxy, and a neighbor max-envelope to jointly adapt stepsizes and gradient-estimator refresh coefficients. Its horizon-independent fixed hyperparameters require no prior knowledge of the smoothness constant or noise level. Under mean-square smoothness, bounded centered noise, and the stated synchronous-network assumptions, we establish an expected gradient-norm guarantee governed by cumulative expected conditional variance along the optimization trajectory. A uniform variance bound yields a rate of , improving to under bounded cumulative variance, including zero noise, with the same hyperparameters. Experiments show robustness to increased stepsize multipliers and fewer queries to prespecified stationarity thresholds than the evaluated baselines in the tested vanishing-noise environments. Classification experiments additionally characterize the accuracy–resource tradeoff.

Primary area:
optimization
Keywords:
decentralized stochastic optimization, nonconvex optimization, noise-adaptive optimization, cumulative variance, variance reduction, gradient tracking

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_wpTBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1(−1)
Soundness
2
Read review
Paper summary

The paper proposes Noise-Adaptive Decentralized STORM. It combines gradient tracking and a STORM estimator with stepsizes and refresh coefficients set from Qt\sqrt{Q_t}, where QtQ_t is a neighbor max-envelope of accumulated direction energy plus a same-point two-sample noise proxy. The fixed hyperparameters do not require LL or σ\sigma. Under mean-square smoothness and a.s. bounded centered noise, it proves E∥∇F(xt^I)∥≤C⋆T−1/2(1+VT1/4)log⁡(2+VT)\mathbb{E}\|\nabla F(x^I_{\hat t})\| \le C_\star T^{-1/2}(1+V_T^{1/4})\sqrt{\log(2+\sqrt{V_T})}, where VTV_T is the cumulative expected conditional variance along the trajectory. This yields O~(T−1/2+σT−1/4)\tilde O(T^{-1/2}+\sqrt{\sigma}T^{-1/4}) under bounded variance and O(T−1/2)O(T^{-1/2}) under bounded cumulative variance. Experiments use 4-node rings with 20-dimensional synthetic objectives (including a constructed vanishing-noise oracle) and a 784–64–10 MLP on Fashion-MNIST and KMNIST.

Critical strengths

(1) A decentralized guarantee that adapts to cumulative trajectory variance with fixed, horizon-independent hyperparameters and no LL input. The node-scale mismatch bound κ\kappa is derived rather than assumed, and the proof avoids circularity by establishing scale comparability (Lemma A.4) before the budget closure. (2) The cost accounting is unusually transparent: queries, independent samples, vector mixes and scalar envelope messages are all counted explicitly.

Critical weaknesses

(1) The main result is weak, and the constant in Theorem 1 hides a very strong dependence on the network. The rate itself brings nothing new. The method pays for STORM (mean-square smoothness, same-sample two-point evaluations, 3 queries per update), yet the bounded-variance rate σT−1/4\sqrt{\sigma}T^{-1/4} and the resulting sample complexity O~(ε−2+σ2ε−4)\tilde O(\varepsilon^{-2}+\sigma^2\varepsilon^{-4}) are those of plain SGD/AdaGrad-Norm, worse than the O(ε−3)O(\varepsilon^{-3})-type complexity of STORM-type methods such as GT-STORM. Centrally, STORM+ already achieves σ1/3T−1/3\sigma^{1/3}T^{-1/3} adaptively. The adaptivity is thus bought by giving up the main reason to use recursive momentum. Theorem 1 therefore does not provide a fundamentally new asymptotic convergence rate. The authors seem to agree: Section 2.3 states that the main novelty is “not the noise proxy or the σ-dependent rate itself”, and the paper puts the weak assumptions on the problem (no knowledge of LL or σ\sigma, fixed hyperparameters) in the foreground. However, Theorem 1 contains a constant C⋆C_\star that hides the dependence on extremely important parameters, such as the graph diameter dGd_G and the spectral gap 1−ρ1-\rho. The constant itself is defined in (A.56) through three further constants cYc_Y, chc_h, cPc_P. Those, in turn, rely on a long chain of auxiliary constants ((A.16), (A.21), (A.26), (A.27), (A.38), (A.42), (A.53), (A.55); by my count more than fifteen) that carry no meaning beyond shortening the notation. As a result, the dependence on the key network parameters cannot be seen anywhere in the main text. Beyond being hidden, this dependence is also quite strong. If I unwound the chain correctly (treating η,s0,γ\eta, s_0, \gamma as constants), then in the worst case

C⋆=O~(n dG3/2L3(1−ρ)3+n L2(1−ρ)4+n dG3/2K3+…).C_\star=\tilde O\Big(\frac{n\,d_G^{3/2}L^3}{(1-\rho)^3}+\frac{\sqrt n\,L^2}{(1-\rho)^4}+\sqrt n\,d_G^{3/2}K^3+\dots\Big).

For a ring with nn nodes (1−ρ=Θ(n−2)1-\rho=\Theta(n^{-2}), dG=Θ(n)d_G=\Theta(n)), which is the topology used in the experiments, this gives a dependence of order n8.5n^{8.5}, so reaching C⋆/T≤εC_\star/\sqrt T\le\varepsilon would require T≳n17/ε2T\gtrsim n^{17}/\varepsilon^2. Even for a complete graph, C⋆C_\star grows linearly in nn, so the bound shows no speedup in the number of nodes. This is far worse than the network dependence of known decentralized methods (e.g., D-PSGD or gradient-tracking analyses), where the network enters through low powers of 1/(1−ρ)1/(1-\rho) and a linear speedup in nn is retained. The constant also depends on the a.s. noise bound KK, so the advertised adaptivity to VTV_T sits under a worst-case constant that can easily dominate. (2) The experiments are weak and not on equal footing. According to Appendix B.1, the proposed method’s hyperparameters were selected by screening 64 candidates on validation problems, while the baselines “retain their historical reference selections” whose tuning histories are not asserted to be identical. The vanishing-noise parameter δ=0.1\delta=0.1 was itself chosen during exploration. Appendix C.1 reports that at δ=0.03\delta=0.03 the method does not beat every baseline, and at δ=0.3\delta=0.3 the No-proxy variant is better than the full method. In the confirmation environment, the noise becomes low-variance after a median of about 283 queries, so the gains mainly reflect finite-budget behavior after early noise decay. GT-STORM is better under persistent noise and at every tested nonzero constant noise level (Table 11). The scale is very small (4 nodes, p=20p=20), so the network dependence discussed above is never tested. In classification, the method trails D-NASA and GT by about 0.5–1.1 pp; the payload and time savings follow mechanically from fewer updates at a fixed query budget.

Questions for authors

(a) Can the analysis recover T−1/3T^{-1/3}-type noise dependence, or is σT−1/4\sqrt{\sigma}T^{-1/4} intrinsic to the envelope scaling? If intrinsic, what does the STORM estimator add over a gradient-tracked AdaGrad-Norm? (b) Could you state the explicit dependence of C⋆C_\star on nn, dGd_G, 1−ρ1-\rho, LL and KK in the main text, and confirm or correct the estimate above (in particular, the O~(n8.5)\tilde O(n^{8.5}) dependence for a ring)? Is this dependence an artifact of the analysis, e.g., of the max-envelope propagation bound in Lemma A.4? (c) Please tune all baselines with the same protocol and budget as the proposed method, report results across the range of δ\delta (including 0.03 and 0.3), and test larger networks and other topologies. (d) Can the result be stated under bounded variance instead of a.s. bounded centered noise?

6 comments
AuthorsOpenReview ↗

Response to Reviewer wpTB

Thank you for the questions. We address the original construction and the revisions below.

(a) Rate and the technical benefit of STORM

We chose STORM for same-sample error correction and cumulative-variance adaptation, not to target a faster stochastic exponent. It reuses the previous estimate while controlling new estimation error through scaled variance and model movement:

\le(1-\beta_t^i)\\|e_t^i\\|^2 +2(\beta_t^i)^2\varsigma_i^2(x_{t+1}^i) +2L^2\\|x_{t+1}^i-x_t^i\\|^2.$$ Here $e_t^i$ is the original estimator error and $\varsigma_i^2$ is local noise variance. With $\alpha_t^i=\frac{\eta}{s_0}\beta_t^i$, incorporating network errors into the energy bound produces $\frac{\mathcal V_T^{1/4}}{\sqrt T}$. Substituting $\mathcal V_T\le T\sigma^2$ gives $\sqrt\sigma T^{-1/4}$. This analysis does not recover a $T^{-1/3}$ stochastic term or establish an intrinsic limitation of envelope design. The correction is a technical choice, not a prerequisite for cumulative-variance adaptation. Together with the independent noise proxy, it requires three queries per update without improving the final stochastic exponent over simple normalized tracking. This cost motivated the revised method combining EMA and gradient tracking, with one query and one neighbor exchange. Theorem 1 retains cumulative-variance adaptation: zero or bounded cumulative variance gives the $T^{-1/2}$ time exponent up to logarithms on a fixed network under the same configuration. Section 5.3 and Appendix A give the proof. **(b) Explicit constants and the ring exponent** The original $n^{8.5}$ dependence is confirmed for its defined proof prefactor. Write $r=\\|W-J\\|_2$. The leading network terms are $$\frac{n d_G^{3/2}L^3}{(1-r)^3}, \qquad \frac{\sqrt nL^2}{(1-r)^4}.$$ On the ring with weight $1/3$ for each node itself and its two neighbors, $d_G=\Theta(n)$ and $1-r=\Theta(n^{-2})$. With fixed positive $L$, fixed algorithm parameters, and common bounds on noise and initialization quantities, $C_\star=\Theta(n^{17/2}\log n)$. Cross-node envelope comparison produces the first contribution; successive estimates of model movement and tracking error produce the second. This is a proof bound, not an algorithmic lower bound. Reviewer supplement Section 3 expands all $L,K$ terms, including $L^3,K^3,LK^2,KL^2$. Revised OptEMA Theorem 2 gives $$\widetilde O\left(\frac{n^4}{\sqrt T}+\frac{n^{9/4}\sqrt\sigma}{T^{1/4}}\right)$$ on that ring family with fixed base step, dimension, and common problem bounds. Corollary 1 gives coefficients $n^2$ and $n^{5/4}$ using $L$, the spectrum, and a valid amplitude bound to select the step, including its reciprocal cost. These ring results use a uniform variance bound; Theorem 1 separately retains cumulative variance for general fixed networks. **(c) Tuning, noise ranges, and network tests** Comparisons include NGT, GT-STORM, D-NASA, and AdaMDOS. The selection allowance per node, context, and policy is $16\times2\times601+4\times2\times3001=43,240$ queries. Joint and per-context policies share screening. OptEMA and NGT retain earlier selections under this protocol; added baselines receive the same allowance. Historical exploration is accounted for separately. Parameters freeze before held-out testing (Appendix B.2–B.4). At 48,001 queries with joint selection and relative noise 4, the geometric mean ratio of OptEMA's final-quarter error to NGT's is 0.807 [0.800,0.813], favorable in 14 of 16 contexts. The corresponding ratio to GT-STORM is 2.020 [1.930,2.119], with GT-STORM better in all 16. At noise 0.1, NGT, GT-STORM, and D-NASA are better in all 16. Zero-noise median target queries are 80.83 [75.83,85.34] for OptEMA and 36.42 [34.83,39.25] for NGT. These are pointwise 95% paired-seed bootstrap intervals using 5,000 resamples, with contexts and configurations fixed. Tests cover persistent and vanishing state-dependent noise at $\delta=0.03,0.1,0.3$, rings with 4, 8, 16, and 32 nodes, and grids and complete graphs with 16 nodes. On the zero-noise grid, OptEMA needs 1,032.25 queries and NGT 83.75. NGT is faster in classification timing tests on a single host using CPUs and Gloo. Reviewer supplement Section 5 retains full STORM comparisons, including its communication and runtime advantages. Target costs are first recorded sustained hits without interpolation; Appendix B.3 specifies checkpoints, and B.6 and B.12 report intervals. **(d) Bounded variance alone** The revised guarantee uses bounded conditional variance and a uniform almost-sure bound on sampled gradients. Variance controls cumulative noise; amplitude bounds control weighted tracking and historical errors. The amplitude condition is sufficient for this proof, not established as necessary for convergence. Section 3 and Appendix A.12 specify its scope and uses.
AuthorsOpenReview ↗

Cumulative-Variance Adaptation, STORM, and Noise Assumptions

Thank you for examining the rate, network constants, and experimental comparisons.

Our first response introduced an alternative OptEMA algorithm. We apologize for the confusion. The current revision retains the original STORM algorithm. This follow-up supersedes the OptEMA-specific claims in our previous response; those costs, guarantees, and experiments should not be attributed to STORM.

Weakness 1 and question (a): noise adaptation and the role of STORM

Our objective is to retain cumulative trajectory variance under jointly adapted nodewise stepsizes and refresh coefficients, with fixed hyperparameters requiring neither smoothness nor noise inputs. This concerns low and diminishing noise as well as persistent noise.

To further clarify the rate stated in the submitted revision, we provide the following comparison here in the response. Consider the stochastic terms σ1/2T−1/4\sigma^{1/2}T^{-1/4} and σ1/3T−1/3\sigma^{1/3}T^{-1/3}. Ignoring constants and logarithms, for σ>0\sigma>0,

=(\sigma^2T)^{1/12}.$$ Thus the former term is smaller when $0<\sigma<T^{-1/2}$, and the terms coincide at $\sigma=T^{-1/2}$. Conversely, when $\sigma>T^{-1/2}$, the STORM+ stochastic term is smaller under the same comparison. Comparing only the powers of $T$ misses this dependence on noise and horizon. This is a comparison of stochastic terms, not a claim of a better complete convergence order. STORM+ also has a $T^{-1/2}$ term, so both expressions enter a $T^{-1/2}$-dominated regime below that threshold. Assumptions, constants, network effects, and query costs must also be matched. The threshold explains the bounds; it is not an algorithmic switching rule or an input to our method. Our actual guarantee retains $\mathcal V_T$, rather than replacing every trajectory variance by a uniform worst-case value: $$\mathbb E\|\nabla F(x_{\widehat t}^{I})\| \le \frac{C_\star}{\sqrt T}(1+\mathcal V_T^{1/4}) \sqrt{\log(2+\sqrt{\mathcal V_T})}.$$ The time and node are sampled uniformly and independently of the run. Bounded cumulative expected variance gives $O(T^{-1/2})$ with the same fixed hyperparameters. This includes trajectories with nonzero but summable expected variance, not only zero-noise oracles. For fixed nonzero noise, we agree that our persistent-noise order is weaker than the stronger STORM-type order and does not improve the SGD/AdaGrad-Norm order. We neither recover $T^{-1/3}$ nor prove that $T^{-1/4}$ is intrinsic to the envelope. No lower bound establishing such a limitation is claimed. STORM's same-sample correction supplies the estimation-error recurrence, with gradient increments controlled by mean-square smoothness and model motion. This recurrence is coupled to the local scale through the refresh coefficient. That explains its role in our analysis, but does not prove it necessary or superior to a gradient-tracked AdaGrad-Norm method. The independently tuned Local-norm GT and other controls examine that empirical question; their advantages in some environments are retained. Updates still require three gradient evaluations from two fresh samples. The bounded-variance per-node query order remains $\widetilde O(\varepsilon^{-2}+\sigma^2\varepsilon^{-4})$. Sections 2 and 5.4 and Appendix D clarify the contribution and distinguish established components from the analysis of their local coupling. Question (d): bounded variance instead of almost-sure bounded noise The revised Assumption 3.2 requires finite moments and $$\mathbb E\|\delta_i(x;\xi)\|^4 \le R\,\mathbb E\|\delta_i(x;\xi)\|^2,$$ where $\delta_i=g_i-\nabla f_i$ and finite $R$ is uniform over nodes, query points, and horizons. It is not an algorithm input. No uniform true-gradient bound or positive noise floor is added. This strictly weakens the original condition: $\|\delta_i\|\le K$ almost surely implies it with $R=K^2$. Proposition A.1 gives a compatible unbounded-noise example, $g_i(x;\xi)=x+\sin(x)\xi$ for $f_i(x)=x^2/2$ and standard Gaussian $\xi$. It satisfies the moment condition with $R=3$ and mean-square smoothness with $L=\sqrt2$. Expected proxy budgets and delayed scale conversion replace the old bounded-noise argument. The condition yields $\mathbb E_t z^2\le2R\mathbb E_t z$ for the two-sample proxy, which Lemma A.3 uses to control refresh-weighted variance by expected logarithmic budget growth. Bounded variance alone need not justify this step. The condition is not merely finite fourth moments, and $C_\star$ still depends on $R$. We have established neither a general variance-only theorem nor its impossibility.
AuthorsOpenReview ↗

Local Adaptive Scales and the Improved Network Bound

Weakness 1 and question (b): why local adaptation complicates the network analysis, and what has improved

Your O~(n8.5)\widetilde O(n^{8.5}) assessment of the original ring prefactor was justified under the fixed-parameter convention. We agree that this dependence should have been explicit.

Relative to a common-stepsize D-PSGD update, our method adds node-dependent scaling: each stepsize depends on a local cumulative budget and previously received neighbor envelopes. This is scalar adaptation at each node, not a full Adam-style coordinate preconditioner.

The additional analytical issue can be seen in the average update. Tracking preserves wˉt=uˉt\bar w_t=\bar u_t, but

r_t=\frac1n\sum_i\alpha_t^i(w_t^i-\bar u_t).$$ The residual vanishes with a common stepsize, but generally not with unequal local stepsizes. Noise observations also change local budgets before the information propagates across the network. The analysis must therefore handle scale heterogeneity, estimation/tracking errors, and propagation delay together. These are additional proof obligations, not evidence that the original large network exponent is unavoidable or that adaptive methods cannot match D-PSGD's network dependence. We instead tightened the proof while retaining the algorithm. For $X_{t+1}=WX_t-P_t^{\rm mat}$, with rows of $P_t^{\rm mat}$ equal to $\alpha_t^iw_t^i$ and common initialization, Lemma A.4 gives $$\sum_{t<T}\|X_{t+1}-X_t\|_F^2 \le \frac4{\nu^2}\sum_{t<T}\|P_t^{\rm mat}\|_F^2,\qquad \nu=1+\lambda_{\min}(W)>0.$$ This preserves cancellation between mixing and local steps, avoiding the extra cost of first controlling motion through disagreement. Delayed conversion (Lemma A.5), using one-hop envelope propagation, replaces the original deterministic same-time scale-ratio argument. Together, these changes remove two inverse-gap factors from the motion/tracking chain; the delay cost appears as $d_G^2$. For explicit dependence on $L$ and noise as well, Appendix A.4 sets $a=\eta/s_0$, $d=d_G$, $A_\rho=2(1+\rho^2)/(1-\rho^2)^2$, $N=s_0^2/\gamma+2R$, and gives $$P=\Delta_0+a\left[ \frac{2\rho^2(H_0+v_0)}{1-\rho^2} +2\rho^2A_\rho v_0+2(1+d)v_0\right],$$ $$H=a\left[L^2\eta^2A_\rho+ \rho^2A_\rho\left(8N+\frac{40L^2\eta^2}{\nu^2}\right) +4(1+d^2)\left(N+\frac{4L^2\eta^2}{\nu^2}\right)\right] +\frac{L\eta^2}{2}.$$ Here $\rho=\|W-J\|_2$, $v_0\le R$ is the average initial variance, and $\Delta_0,H_0$ describe initialization. With $S=1+P+H$, the propagation gives $C_\star=O(\sqrt n\,S\log(2+\sqrt nS))$ under the stated fixed-parameter convention. Eq. (A.16) defines the explicit prefactor. For fixed positive $L,\eta,s_0,\gamma$ and uniform bounds on $R,\Delta_0,H_0$, the network dependence is $$C_\star=\widetilde O\!\left[ \frac{\sqrt n}{\nu^2}\left((1-\rho)^{-2}+d_G^2\right) \right].$$ Only logarithmic network factors are suppressed; the other constants depend on the fixed quantities above. Within the original bounded-noise class, take $R=K^2$. Thus retaining $\mathcal V_T$ does not eliminate dependence on a uniform noise parameter, which may still affect the bound substantially. For the original $1/3$-weight ring, $\nu\ge2/3$, $1-\rho=\Theta(n^{-2})$, and $d_G=\Theta(n)$, so $$C_\star=O(n^{9/2}\log n),$$ instead of $O(n^{17/2}\log n)$. The original exponent therefore included removable analytical slack. The remaining dependence is substantial. For complete averaging, $W=J$, our displayed bound is $O(\sqrt n\log(2+n))$, so it does not establish linear speedup. We also establish neither topology optimality nor a lower bound showing the remaining exponent is intrinsic. The factor $\nu$ must be retained for matrices with eigenvalues near $-1$. Section 5.2 states the network bound and limitations; Appendix A.4 provides the constant propagation. These are upper bounds from the proof, not predictions of measured runtime. Larger-network experiments are discussed in the following response.
Reviewer_csB4OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work proposes a new algorithm for optimization problem over a network, which is noise-Adaptive Decentralized STORM. This algorithm can adjust this step size and update its gradient estimate using past updates, gradient noise and neighbor's information without knowing the smoothness constant and noise level in advance. This work also provided convergence guarantee as O(1/T)O(1/\sqrt{T}).

Critical strengths
  1. The adaptive update rule is well-motivated: It used the same local scale to adjust both the step size αti\alpha_t^i and refresh coefficient βti\beta_t^i, which is a meaningful algorithmic contribution.
  2. The differences between local scales are controlled: This work used communication through neighborhood to make the local scales closer to each other without requiring a global coordinator.
Critical weaknesses
  1. The assumption of gradient noise is strict: The convergence analysis requires uniformly bounded gradient noise, which is stronger than the commonly used bounded variance. It may limit the range of settings covered by theoretical guarantees.
  2. The novelty can be improved: The method builds on established ideas, such as STORM updates, gradient tracking, and a two-sample noise estimate. The convergence analysis is valuable, however, the advance in algorithm design is a little bit modest.
Questions for authors

I would like to ask: Why is bounded variance alone insufficient so we need uniformly bounded gradient noise?

2 comments
AuthorsOpenReview ↗

Response to Reviewer csB4

Thank you for the questions about noise assumptions and novelty.

1. The amplitude assumption and bounded variance

The amplitude bound is a sufficient condition for the present proof; we have not established it as necessary for convergence. Bounded variance alone does not imply the deterministic bounds on adaptive weights used in this argument.

In the original construction, bounded variance controls the conditional expectation of the noise proxy formed from two samples. The stronger centered-noise bound KK controls realized estimator increments and comparisons between local scales. Reviewer supplement Section 3 makes its contribution to the constants explicit.

The revised theorem assumes conditional unbiasedness and bounded conditional variance at actual query points, together with

\quad\text{almost surely for all sampled }t,i.$$ This deterministic bound is uniform over time and independent of the horizon. It bounds sampled stochastic gradients, whereas the original $K$ bounds centered noise; these are distinct assumptions. The amplitude condition has two concrete roles. First, it bounds tracking inputs and EMA states, giving $$P_{t,i}\succeq(\varepsilon+\widehat G)^{-1}I,$$ where $\widehat G$ is the tracking-amplitude bound. This supplies a uniform positive coefficient in the descent estimate. Second, summation by parts introduces historical-noise boundary and variation terms involving $$\\|z_{t,i}\\|\\,\\|\nabla f(\bar x_t)\\|,$$ coupled to random historical weights. The proof controls these using amplitude bounds and the total variation of preconditioners. A variance-only extension would require alternative estimates for these weighted quantities. Section 3 separates the variance and amplitude assumptions. Appendix A.12 proves the trajectory-dependent bounds and connects them to the descent and Abel estimates in A.5–A.6. Smoothness and consensus control the average-point gradient; a uniform stochastic-gradient bound over the entire space is not assumed. **2. Contribution beyond established components** The contribution is a cumulative-variance analysis of independently maintained local adaptive states. EMA, gradient tracking, and spectral mixing provide established ingredients; the additional analysis handles their coupling through node-dependent random weights and historical errors. Current innovations cancel under predictable old weights. Historical noise retains its sign and is controlled by Abel summation. Neighbor-propagated cumulative scales connect local weights to the final energy bound. This yields one gradient query and one neighbor exchange per update, with the same parameter configuration recovering the $T^{-1/2}$ time exponent up to logarithms on a fixed network when cumulative variance is bounded. Section 5.3 identifies reused tools and new interfaces, and Appendix C compares related methods. Section 6.4 also reports the mechanisms' different empirical effects. Matched scalar and coordinatewise scaling perform similarly in the tested high-noise cases for both the base and stress objectives. Removing first-moment EMA lowers error at the extended query budget in 14 of the 16 high-noise contexts, but increases the zero-noise median target cost from 80.8 to 204.9 queries. These results distinguish persistent-noise performance from zero-noise query efficiency.
AuthorsOpenReview ↗

Relaxing the Noise Assumption and Clarifying the Contribution

Thank you for your assessment and for raising the noise-assumption and novelty concerns.

Our previous response introduced an alternative OptEMA algorithm and a trajectory-gradient amplitude bound. It did not relax the noise assumption for the submitted STORM algorithm. We apologize for the confusion. The current revision retains the original STORM algorithm. This follow-up supersedes the OptEMA-specific claims in our previous response; they should not be attributed to STORM.

  1. Weakness 1 and your question: is uniformly bounded noise necessary, and why not bounded variance alone?

Almost-sure bounded noise is not necessary for our revised convergence proof. We have replaced it with a strictly weaker condition. However, we have not proved that bounded variance alone suffices, or that it is insufficient for convergence. We distinguish a sufficient assumption for our analysis from a necessary condition on the algorithm.

Revised Assumption 3.2 requires

\le R\,\mathbb E\|\delta_i(x;\xi)\|^2, \qquad \delta_i(x;\xi)=g_i(x;\xi)-\nabla f_i(x),$$ with finite second and fourth moments and a finite deterministic $R$ uniform over nodes, query points, and horizons. Fresh sampling, unbiasedness, mean-square smoothness, and network assumptions are retained. No uniform bound on true gradients or positive noise floor is added. $R$ is not an algorithm input. This is a strict relaxation: $\|\delta_i\|\le K$ almost surely implies the condition with $R=K^2$, but the converse fails. Proposition A.1 gives $$f_i(x)=x^2/2,\qquad g_i(x;\xi)=x+\sin(x)\xi,\qquad \xi\sim N(0,1).$$ Here the variance is $\sin^2x$ and the fourth centered moment is $3\sin^4x\le3\sin^2x$, so $R=3$ works uniformly. The oracle satisfies mean-square smoothness with $L=\sqrt2$, and the objective is lower bounded. Yet the noise at $x=\pi/2$ is unbounded. The variance can also vanish. This example satisfies the remaining problem assumptions. 2. Where the stronger-than-variance condition enters the proof The original proof used bounded noise to obtain a deterministic same-time ratio between node scales. With unbounded noise, a large local proxy can change one node's scale before its envelope reaches other nodes. Appendix A gives a two-node Gaussian counterexample to reusing that ratio lemma. It is a counterexample to the lemma, not to convergence. The revised proof instead uses expected proxy budgets and delayed scale propagation. For the two-sample proxy $z=\|\delta-\delta'\|^2/2$ and local variance $v$, $$\mathbb E_t z=v,\qquad \mathbb E_t z^2\le2Rv.$$ The second estimate is used in Lemma A.3 to control refresh-weighted variance by expected logarithmic budget growth. Bounded variance alone controls $\mathbb E_t z$ but need not control $\mathbb E_t z^2$, so it does not justify this step. This identifies the remaining proof requirement rather than establishing an impossibility result. One-hop envelope propagation then gives $\bar\alpha_t\le\alpha_{t-d_G}^i$ for $t\ge d_G$. Delayed conversion (Lemma A.5) replaces same-time scale comparison. The proof retains the dependence between adaptive coefficients and estimation errors and allows the estimator and proxy to share an evaluation. Theorem 1 and Theorem A.6 preserve $$\mathbb E\|\nabla F(x_{\widehat t}^{I})\| \le \frac{C_\star}{\sqrt T}(1+\mathcal V_T^{1/4}) \sqrt{\log(2+\sqrt{\mathcal V_T})}.$$ The output is an independent uniformly sampled local iterate. Bounded cumulative variance still gives $O(T^{-1/2})$ with fixed hyperparameters. The condition is stronger than bounded variance alone and is not merely finite fourth moments; $C_\star$ depends on $R$. The general variance-only extension remains open in this work. 3. Weakness 2: novelty relative to established components We agree that STORM recursion, gradient tracking, and the two-sample proxy are established ingredients. We do not claim them individually as new. The contribution is their specific coupling through local cumulative budgets and neighbor envelopes, together with a cumulative-variance guarantee for jointly adapted local stepsizes and refresh coefficients. Unequal local stepsizes leave a residual in the average-model update even when the tracker preserves the average estimate. The analysis must control this residual and estimation errors under history-dependent node scales. The revised expected-budget, delayed-conversion, and direct-motion arguments address these issues for the original algorithm; we do not claim the underlying proof tools themselves as inventions. Neither the persistent-noise exponent nor the three-query update cost is improved. Sections 2 and 5.4 and Appendix D clarify the contribution. Assumption 3.2 and Appendix A state the weaker condition and its proof. Revisions are marked in blue.
Reviewer_kxZsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes an adaptive stochastic recursive gradient algorithm for decentralized optimization. The authors consider the unknown smoothness and varied gradient noise setting, and shows a O~(T−1/2+sigmaT−1/4)\tilde O(T^{-1/2}+\sqrt{sigma}T^{-1/4}) convergence. They empirically compare their method with the baselines.

Critical strengths

This paper consider a different decentralized setting with other existing method, i.e., the unknown smoothness and varied gradient noise setting. This setting is more practical, and the algorithm/theoretical analyses seem not a trivial combination of existing methods.

Critical weaknesses

While I try to follow the details and the proof, it is really hard to see how it achieves the bound and what is the most important part of their algorithm. While the main algorithm is complex and the notations are complicated, the paper is more like a technique report, not a fully polished paper. Actually, the related work part lacks a clear comparison of the related methods, or a clear table to tell the difference between their algorithm and the related methods. The authors may revise the paper to clearly show which techniques are existing/which part are novel, and give a general description on how they achieve the bound.

Questions for authors
  1. As discussed in the weaknesses, could you give a general description on the algorithm and how you achieve the bound?

  2. How does the dependence of C⋆C_\star on the number of nodes, spectral gap, and graph diameter compare with existing decentralized methods? Does the result provide any linear-speedup or topology-optimal guarantee?

  3. What is the influence of the initial value of s0s_0 on the theoretical and the empirical result of the proposed algorithm? Is it somehow similar to the role of smoothness parameter? In Table 3, why η=4.655282388394825\eta = 4.655282388394825, s0=0.3264847403863s_0 = 0.3264847403863? The value seems strange.

3 comments
AuthorsOpenReview ↗

Response to Reviewer kxZs

Thank you for the questions about the contribution, proof, network dependence, and parameter choices.

1. Algorithm and proof mechanism

The original method accumulates direction energy and noise estimates, then propagates neighboring maxima to construct adaptive scales for the stepsizes and STORM refresh coefficients. Its proof compares scales across nodes, controls estimation and tracking errors, and incorporates these errors into weighted descent to derive the final energy bound.

The revision retains the noise-adaptation objective. Considering the query cost, we replace the three-query construction with a method combining EMA and gradient tracking that needs one query per node per update. The key difficulty is that local adaptive weights cannot be factored out of the average update: xˉt+1=xˉt−θn∑iγt,iPt,imt,i.\bar x_{t+1}=\bar x_t-\frac{\theta}{n}\sum_i\gamma_{t,i}P_{t,i}m_{t,i}. Each weight depends on its node's history and is correlated with historical tracking errors.

We reuse OptEMA's EMA expansion, weighted descent, and energy conversion, together with D-PSGD's spectral contraction and convolution tools. The additional analysis separates average signals from disagreement, cancels current innovations under predictable old weights, and controls signed historical noise by Abel summation, including boundary terms and changes in preconditioners. Neighbor-propagated cumulative scales provide comparisons between local weights and complete the energy bound.

The guarantee retains expected cumulative trajectory variance while each node maintains its own adaptive states and uses one gradient query and one neighbor exchange per update. On a fixed network, bounded cumulative variance gives the T−1/2T^{-1/2} time exponent up to logarithms with the same parameter configuration. Sections 4 and 5.3 explain the algorithm and proof; Appendix A gives the derivation. Section 2 and Appendix C compare related methods and clarify the contribution.

2. Network dependence and speedup

The current guarantees do not establish linear node speedup or topology optimality. For the original method, define g=1−∣W−J∣2g=1-\\|W-J\\|_2 and let dGd_G be the graph diameter. With fixed positive LL, fixed algorithm parameters, and common bounds on noise and initialization quantities, the leading dependence is C⋆=O~(ng4+ndG3/2g3).C_\star=\widetilde O\left(\frac{\sqrt n}{g^4}+\frac{n d_G^{3/2}}{g^3}\right). On the ring assigning weight 1/31/3 to each node itself and its two neighbors, g=Θ(n−2)g=\Theta(n^{-2}) and dG=Θ(n)d_G=\Theta(n), giving Θ(n17/2log⁡n)\Theta(n^{17/2}\log n) for the defined proof prefactor. Reviewer supplement Section 3 expands all constants.

For revised OptEMA, Theorem 2 gives O~(n4T+n9/4σT1/4)\widetilde O\left(\frac{n^4}{\sqrt T}+\frac{n^{9/4}\sqrt\sigma}{T^{1/4}}\right) on that ring family, with fixed base step, dimension, and common problem bounds. Corollary 1 gives coefficients n2n^2 and n5/4n^{5/4} when the step uses LL, spectral information, and a valid trajectory-amplitude bound; the reciprocal-step cost is included. Theorem 1 separately retains cumulative variance on general fixed networks.

3. The role of s0s_0 and the reported decimals

In the original method, s0s_0 initializes the cumulative budget and controls the refresh scale:

\beta_t^i=\frac{s_0}{\eta}\alpha_t^i.$$ Thus it controls the stepsize cap and the ratio of the refresh coefficient to the stepsize; it is not an estimate of $L$. The constants contain inverse powers of $s_0$ and terms such as $\frac{s_0^2}{\gamma}$. Fixed positive choices affect constants, not the stated time exponents. The bound gives no monotone improvement as $s_0$ increases. The recorded search varied $s_0$ jointly with other parameters. The original sensitivity sweep varied $\eta$ with $s_0$ fixed, so it does not isolate the empirical effect of $s_0$. The reported $\eta=4.655282388394825$ and $s_0=0.326484740386302$ are the stored values of candidate 9. The protocol screened 64 candidates on two validation problems at 3,001 queries and confirmed eight on three other problems at 24,001 queries. The decimals reflect storage precision. Reviewer supplement Sections 3–4 provide the constant expansion and parameter provenance.
AuthorsOpenReview ↗

Clarification of Contributions, Algorithm, and Proof Structure

Thank you for identifying the difficulties in following the algorithm, proof, and comparison with prior work.

We first clarify the scope of this follow-up. Our previous response introduced an alternative OptEMA algorithm rather than directly addressing the submitted STORM method. We apologize for the confusion. The current revised manuscript retains the original STORM algorithm and revises its analysis, presentation, and experiments. This follow-up supersedes the claims and guarantees specific to OptEMA in our previous response; those claims should not be attributed to STORM. Please refer to the current revised manuscript and the explanations below for our response concerning the original method.

Weaknesses: presentation and relationship to existing work

We agree that the original exposition did not adequately distinguish established ingredients from the contribution of their coupling and analysis. STORM recursion, gradient tracking, and same-point two-sample noise estimation are established tools; we do not claim them individually as new.

Our focus is their coupling through nodewise cumulative budgets and a neighbor max-envelope that determines both local stepsizes and estimator-refresh coefficients. The guarantee retains cumulative trajectory variance, with fixed hyperparameters requiring neither smoothness nor noise levels as inputs.

Section 2 (p. 2) now makes the comparisons explicit:

  • GT-STORM combines recursive estimation and tracking and achieves a better persistent-noise complexity order. We do not improve that order; we study cumulative-variance adaptation for the stated local coupling.
  • D-NASA already avoids smoothness-constant input. This property alone is therefore not our novelty.
  • AdaMDOS establishes near-optimal stochastic sample complexity under its assumptions. We do not claim to match or improve that complexity.
  • Centralized adaptive methods already use accumulated scales and related noise proxies. Nodewise scales introduce unequal-step residuals and propagation delays that require additional control.

In particular, tracking preserves wˉt=uˉt\bar w_t=\bar u_t, but unequal stepsizes leave

r_t=\frac1n\sum_i\alpha_t^i(w_t^i-\bar u_t).$$ Thus, tracking alone does not cancel the residual. The analysis must control estimation, tracking, and model disagreement under the actual history-dependent coefficients. We do not claim that basic proof tools such as energy estimates are themselves new. We retained all three related-work subsections and expanded their comparisons. Appendix D (pp. 28–29), including Table 14, separates established components from the additional proof obligations. Question 1: algorithm overview and route to the bound Each node maintains a model $x_t^i$, recursive gradient estimate $u_t^i$, and direction $w_t^i$ tracking the average estimate. Existing budgets, current direction energy, and previously received neighbor envelopes determine $s_t^i$, which sets $$\alpha_t^i=\eta/s_t^i,\qquad \beta_t^i=s_0/s_t^i.$$ The model moves before fresh sampling. One sample evaluated at the old and new points gives the STORM correction; an independent second sample at the new point forms the noise proxy $$z_{t+1}^i=\tfrac12\|g_i(x_{t+1}^i;\xi)-g_i(x_{t+1}^i;\xi')\|^2.$$ Its conditional expectation equals the local variance. The budget accumulates $\|w_t^i\|^2+\gamma z_{t+1}^i$. New noise observations affect subsequent stepsizes. Neighbor envelopes propagate one hop per round without a global maximum. The proof has three steps. (i) Expected noise budget: Lemma A.3 controls the proxy budget under the uniform condition $\mathbb E\|\delta\|^4\le R\mathbb E\|\delta\|^2$. This weakens almost-sure bounded noise but remains stronger than bounded variance alone. The proof allows the estimator and proxy to share an evaluation. (ii) Unequal-scale errors: envelope propagation gives $\bar\alpha_t\le\alpha_{t-d_G}^i$ for $t\ge d_G$. Delayed conversion (Lemma A.5) and direct model-motion control (Lemma A.4) bound the relevant errors without the original deterministic same-time scale-ratio requirement. (iii) Budget closure: descent combines these errors with direction energy and bounds the expected raw budget through cumulative variance $\mathcal V_T$. Theorem A.6 yields $$\mathbb E\|\nabla F(x_{\widehat t}^{I})\| \le \frac{C_\star}{\sqrt T}(1+\mathcal V_T^{1/4}) \sqrt{\log(2+\sqrt{\mathcal V_T})}.$$ Here $\widehat t$ and $I$ are independent uniform time/node draws, independent of the run. Bounded cumulative variance gives $O(T^{-1/2})$; $\mathcal V_T\le T\sigma^2$ gives $\widetilde O(T^{-1/2}+\sqrt{\sigma}T^{-1/4})$. The persistent-noise exponent is unchanged. Section 4.1 (p. 4) now explains the iteration before its formulas; Section 5.4 (pp. 6–7) presents these proof steps. Revised passages are marked in blue.
AuthorsOpenReview ↗

Network Dependence and the Role of the Initial Scale s0

Question 2: network dependence, linear speedup, and topology optimality

The revised bound is explicit. Let ρ=∥W−J∥2\rho=\|W-J\|_2 and ν=1+λmin⁡(W)>0\nu=1+\lambda_{\min}(W)>0. For fixed positive L,η,s0,γL,\eta,s_0,\gamma and uniform bounds on the noise/initialization quantities R,Δ0,H0R,\Delta_0,H_0,

\frac{\sqrt n}{\nu^2}\left((1-\rho)^{-2}+d_G^2\right) \right].$$ Suppressed factors are logarithmic in network quantities; other constants depend on the fixed quantities stated above. The improvement comes from direct model-motion control. With rows of $X_t$ and $P_t$ equal to $x_t^i$ and $\alpha_t^i w_t^i$, common initialization gives $$\sum_{t<T}\|X_{t+1}-X_t\|_F^2 \le \frac4{\nu^2}\sum_{t<T}\|P_t\|_F^2.$$ This preserves cancellation between mixing and local steps. Its propagation through the analysis removes two inverse-gap factors from the original motion/tracking constant chain; the delayed-conversion cost appears explicitly as $d_G^2$. For the original ring with self/neighbor weights $1/3$, we have $1-\rho=\Theta(n^{-2})$, $d_G=\Theta(n)$, and $\nu\ge2/3$. Consequently, $$C_\star=O(n^{9/2}\log n),$$ improving the original $O(n^{17/2}\log n)$. Within the original bounded-noise class, take $R=K^2$ to compare the two analyses. This does not establish linear speedup or topology optimality. Even for complete averaging, $W=J$, the displayed prefactor is $O(\sqrt n\log(2+n))$, which does not show speedup with increasing node count. Existing methods, including D-NASA, provide linear-speedup guarantees under their assumptions. We do not claim better network dependence than those guarantees. Comparisons must also match assumptions, stationarity metrics, and per-node versus network-wide costs. Our conclusion is that the original algorithm's network bound can be substantially tightened while retaining its cumulative-variance guarantee. These are proof upper bounds, not lower bounds on algorithmic cost or runtime predictions. Section 5.2 (p. 6) states the bound and limitation; Appendix A.4 (pp. 18–19) gives the constant propagation and graph specializations. Question 3: the role of $s_0$ and the reported decimal values Theoretical role. The initialization and coefficients satisfy $$B_0^i=Q_{-1}^i=s_0^2,\qquad \alpha_t^i=\eta/s_t^i\le\eta/s_0,\qquad \beta_t^i=s_0/s_t^i.$$ In particular, $$\alpha_0^i=\frac{\eta}{\sqrt{s_0^2+\|w_0^i\|^2}},\qquad \beta_0^i=\frac{s_0}{\sqrt{s_0^2+\|w_0^i\|^2}}.$$ Thus $s_0$ sets the initial scale, limits stepsizes, and affects retention of the recursive correction through $1-\beta_t^i$. It also changes later trajectories and convergence constants. It is not an estimate or required upper bound of $L$: $L$ is an oracle property, whereas $s_0$ is a user-selected scale parameter. The theorem permits arbitrary fixed positive $\eta,s_0,\gamma$, but its constants are not uniform over all choices. Not needing $L$ as input does not make parameter selection irrelevant. Decimal values. The reported $\eta=4.655282388394825$ and $s_0=0.326484740386302$ are the stored full-precision values of candidate 9 from the original validation search. They are not theoretically prescribed. Their precision identifies the configuration actually evaluated; the proof does not require those digits. We have not established that rounding them leaves experimental results unchanged. Empirical effect. We added an isolated sweep fixing the original $\eta,\gamma$ and varying only $s_0$ by multipliers $1/4,1/2,1,2,4$. Six noise environments use five fresh problems, with five oracle streams per nonzero-noise problem and one for zero noise. Each configuration uses 24,001 queries per node. The protocol was fixed before execution; no winner was selected from the sweep. For constant noise $\sigma=4$, mean normalized ergodic gradient metric $M_T$ (lower is better) is $0.02171$ at the original value, versus $0.04228$ at multiplier $1/4$ and $0.03387$ at $4$. For persistent noise $\delta=0.1$, halving $s_0$ gives approximately $0.0175$, versus $0.0208$ at the original value. For vanishing noise $\delta=0.1$, the metric decreases from $0.00547$ to $0.000661$ as the multiplier increases from $1/4$ to $4$. Therefore, $s_0$ has a regime-dependent effect; it is neither empirically irrelevant nor universally optimal at the original value. Its influence involves both stepsizes and estimator refresh. Appendix E.5 (p. 34) reports all six environments and uncertainty estimates; Section 4 and Appendix A describe its theoretical role.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.