CEDAS: A Compressed Decentralized Stochastic Gradient Method With Improved Convergence

In this article, we consider solving the distributed optimization problem over a multiagent network under the communication restricted setting. We study a compressed decentralized stochastic gradient method, termed “compressed exact diffusion with adaptive stepsizes (CEDAS),” and show that the method asymptotically achieves comparable convergence rate as centralized stochastic gradient descent (SGD) for both smooth strongly convex objective functions and smooth nonconvex objective functions under unbiased compression operators. In particular, to our knowledge, CEDAS enjoys so far the shortest transient time (with respect to the graph specifics) for achieving the convergence rate of centralized SGD, which behaves as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(n{C^{3}}/(1-\lambda _{2})^{2})$</tex-math></inline-formula> under smooth strongly convex objective functions and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(n^{3}{C^{6}}/(1-\lambda _{2})^{4})$</tex-math></inline-formula> under smooth nonconvex objective functions, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(1-\lambda _{2})$</tex-math></inline-formula> denotes the spectral gap of the mixing matrix, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$C&gt;0$</tex-math></inline-formula> is the compression-related parameter. In particular, CEDAS exhibits the shortest transient times when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$C &lt; \mathcal {O}(1/(1 - \lambda _{2})^{2})$</tex-math></inline-formula>, which is common in practice. Numerical experiments further demonstrate the effectiveness of the proposed algorithm.