Cumulative-Variance-Adaptive Decentralized STORM

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 ${\sigma }^2$ yields a rate of $\tilde{O}(T^{-1/2}+\sqrt{\sigma }{T}^{-1/4})$, improving to $O(T^{-1/2})$ 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.