2022/02/01 by Chung-Yiu Yau, Yau, Chung-Yiu, Hoi-To Wai +1 · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Parallel #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.00255
openalex publication_date 2022/02/01 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
This paper proposes the Doubly Compressed Momentum-assisted stochastic gradient tracking algorithm DoCoM 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 DoCoM finds a near-stationary solution at all participating agents satisfying 𝔼[ ‖ ∇ 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 DoCoM. As a corollary, our analysis also established the linear convergence of DoCoM to a global optimal solution for objective functions with the Polyak-Łojasiewicz condition. Numerical experiments demonstrate that our algorithm outperforms several state-of-the-art algorithms in practice.