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.

Many different organizations and devices, such as hospitals and mobile phones, possess valuable data for training machine learning models. However, sharing this data directly is often not possible due to privacy concerns. One solution is to use a method called decentralized optimization. With this approach, each client keeps its own data and trains models with other clients by communicating only model parameters. However, there are several challenges. Since communication between clients can be unstable or slow, reducing the communication costs is crucial. Additionally, reducing the computational cost on clients is also important, especially for those with very limited resources, such as mobile phones. In this paper, we propose a new algorithm, called Accelerated Stabilized Proximal Decentralized Optimization. This algorithm can run with lowest communication and computation costs among existing algorithms, making decentralized optimization more suitable for real-world use.