Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization
Authors:
- Yuki TakezawaYTYuki Takezawa
- Xiaowen JiangXJXiaowen Jiang
- Anton RodomanovARAnton Rodomanov
- Sebastian U. StichSSSebastian U. Stich
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order MethodsSIAM Journal on Optimization, 2013
- Accelerated linear iterations for distributed averagingAnnual Reviews in Control, 2011
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998
- New Proximal Point Algorithms for Convex MinimizationSIAM Journal on Optimization, 1992
- Monotone Operators and the Proximal Point AlgorithmSIAM Journal on Control and Optimization, 1976