CED-EF: Compressed Exact Diffusion with Error Feedback for 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 \ge 0$, we establish a convergence rate whose leading stochastic term is $\mathcal{O}(\sigma \mathrm{/}\sqrt{NK})$. For $\sigma >0$, the dominant dependence of the corresponding transient time on the number of agents, compression level, and spectral gap ${\mathrm{\Delta }}_{\lambda }$ is $\mathcal{O}(N^3\mathrm{/}({\delta }^4{\mathrm{\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\mathrm{/}(NK))$ with transient time on the order of $\tilde{\mathcal{O}}(N\mathrm{/}({\delta }^2{\mathrm{\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.