CED-EF: Compressed Exact Diffusion with Error Feedback for Multi-Agent Learning

Abstract

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 \ge 0$, 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--Łojasiewicz condition, CED-EF attains a leading stochastic term $\tilde{\mathcal{O}}({\sigma }^2/(NK))$ with transient time on the order of $\tilde{\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.