Search papers, labs, and topics across Lattice.
This paper introduces CED-EF, a decentralized stochastic optimization method that leverages exact diffusion with error feedback to optimize communication among $N$ agents using compressed model-sized vectors. The method achieves improved convergence rates for smooth nonconvex objectives, demonstrating a leading stochastic term of $\mathcal O(\sigma/\sqrt{NK})$ and a transient time that scales favorably with the number of agents and compression levels. Numerical experiments validate the theoretical findings, showing that CED-EF outperforms existing methods in practical scenarios involving least-squares and logistic regression problems.
CED-EF achieves faster convergence in decentralized optimization while using significantly less communication bandwidth, reshaping the landscape of multi-agent learning.
We study decentralized stochastic optimization over a network of $N$ agents under compressed communication. We propose CED-EF, an exact diffusion-based method with error feedback that directly accommodates biased $\delta$-contractive compressors while communicating one compressed model-sized vector per node per iteration. For smooth nonconvex objectives with unbiased stochastic gradients whose variance is bounded by $\sigma^2$, where $\sigma\geq0$, we establish a convergence rate whose leading stochastic term is $\mathcal O(\sigma/\sqrt{NK})$. For $\sigma>0$, the dominant dependence of the corresponding transient time on the number of agents, compression level, and spectral gap $\Delta_\lambda$ is $\mathcal O(N^3/(\delta^4\Delta_\lambda^4))$, with fixed problem-dependent factors suppressed. Under the Polyak--\L{}ojasiewicz condition, CED-EF attains a leading stochastic term $\widetilde{\mathcal O}(\sigma^2/(NK))$ with transient time on the order of $\widetilde{\mathcal O}(N/(\delta^2\Delta_\lambda^2))$. These dependencies improve the compression and/or network dependence of existing results. Numerical experiments on least-squares and logistic-regression problems illustrate the performance advantages of CED-EF.
