- 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 , where is a neighbor max-envelope of accumulated direction energy plus a same-point two-sample noise proxy. The fixed hyperparameters do not require or . Under mean-square smoothness and a.s. bounded centered noise, it proves , where is the cumulative expected conditional variance along the trajectory. This yields under bounded variance and 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 input. The node-scale mismatch bound 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 and the resulting sample complexity are those of plain SGD/AdaGrad-Norm, worse than the -type complexity of STORM-type methods such as GT-STORM. Centrally, STORM+ already achieves 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 or , fixed hyperparameters) in the foreground. However, Theorem 1 contains a constant that hides the dependence on extremely important parameters, such as the graph diameter and the spectral gap . The constant itself is defined in (A.56) through three further constants , , . 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 as constants), then in the worst case
For a ring with nodes (, ), which is the topology used in the experiments, this gives a dependence of order , so reaching would require . Even for a complete graph, grows linearly in , 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 and a linear speedup in is retained. The constant also depends on the a.s. noise bound , so the advertised adaptivity to 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 was itself chosen during exploration. Appendix C.1 reports that at the method does not beat every baseline, and at 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, ), 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 -type noise dependence, or is 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 on , , , and in the main text, and confirm or correct the estimate above (in particular, the 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 (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
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 and . Ignoring constants and logarithms, for ,
=(\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.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 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 , 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.
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.