Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization

Reducing communication complexity is critical for efficient decentralized optimization. The proximal decentralized optimization (PDO) framework is particularly appealing, as methods within this framework can exploit functional similarity among nodes to reduce communication rounds. Specifically, when local functions at different nodes are similar, these methods achieve faster convergence with fewer communication steps. However, existing PDO methods often require highly accurate solutions to subproblems associated with the proximal operator, resulting in significant computational overhead. In this work, we propose the Stabilized Proximal Decentralized Optimization (SPDO) method, which achieves state-of-the-art communication and computational complexities within the PDO framework. Additionally, we refine the analysis of existing PDO methods by relaxing subproblem accuracy requirements and leveraging average functional similarity. Experimental results demonstrate that SPDO significantly outperforms existing methods. Algorithm Reference # Communication # Computation Assumptions Gradient Tracking Koloskova et al. ( 2021 ) Accelerated SONATA Tian et al. ( 2022 ) 1, 2, 3, 4 Accelerated Stabilized-PDO [new] Th. 5, 6 O δ µ(1-ρ) log( L µ ) log( 1 ϵ ) O L µ log( 1 ϵ ) 1, 2, 4