DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity

This paper proposes the Doubly Compressed Momentum-assisted stochastic gradient tracking algorithm textttDoCoM for communication-efficient decentralized optimization. The algorithm features two main ingredients to achieve a near-optimal sample complexity while allowing for communication compression. First, the algorithm tracks both the averaged iterate and stochastic gradient using compressed gossiping consensus. Second, a momentum step is incorporated for adaptive variance reduction with the local gradient estimates. We show that textttDoCoM finds a near-stationary solution at all participating agents satisfying mathbbE[ | nabla f( θ ) |2 ] = O( 1 / T2/3 ) in T iterations, where f(θ) is a smooth (possibly non-convex) objective function. Notice that the proof is achieved via analytically designing a new potential function that tightly tracks the one-iteration progress of textttDoCoM. As a corollary, our analysis also established the linear convergence of textttDoCoM to a global optimal solution for objective functions with the Polyak-Lojasiewicz condition. Numerical experiments demonstrate that our algorithm outperforms several state-of-the-art algorithms in practice.