Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces D-NSS, a decentralized stochastic optimization algorithm designed to handle heterogeneous variances in stochastic gradient estimators across nodes in distributed networks. The algorithm achieves a sample complexity that depends on the arithmetic mean of local standard deviations, improving upon existing methods that rely on worst-case or quadratic mean dependencies. The authors also prove a matching sample complexity lower bound, demonstrating the optimality of the arithmetic-mean dependence, and propose a variance-reduced version, D-NSS-VR, with improved sample complexity under mean-squared smoothness.
Decentralized learning can be faster and more efficient than previously thought by optimizing for the *average* variance across nodes, not the worst-case.
Decentralized optimization is critical for solving large-scale machine learning problems over distributed networks, where multiple nodes collaborate through local communication. In practice, the variances of stochastic gradient estimators often differ across nodes, yet their impact on algorithm design and complexity remains unclear. To address this issue, we propose D-NSS, a decentralized algorithm with node-specific sampling, and establish its sample complexity depending on the arithmetic mean of local standard deviations, achieving tighter bounds than existing methods that rely on the worst-case or quadratic mean. We further derive a matching sample complexity lower bound under heterogeneous variance, thereby proving the optimality of this dependence. Moreover, we extend the framework with a variance reduction technique and develop D-NSS-VR, which under the mean-squared smoothness assumption attains an improved sample complexity bound while preserving the arithmetic-mean dependence. Finally, numerical experiments validate the theoretical results and demonstrate the effectiveness of the proposed algorithms.