Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
This work addresses communication efficiency for multiagent networks in decentralized and stochastic optimization, offering incremental improvements over prior algorithms.
The paper tackles the communication bottleneck in decentralized optimization by proposing decentralized primal-dual algorithms, specifically DCS and SDCS, which reduce inter-node communication rounds to O(1/ε) for convex functions while maintaining optimal O(1/ε²) subgradient evaluations, achieving orders-of-magnitude reduction compared to existing methods.
We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual method which can find an $ε$-solution both in terms of functional optimality gap and feasibility residual in $O(1/ε)$ inter-node communication rounds when the objective functions are convex and the local primal subproblems are solved exactly. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions. By employing DCS, agents can still find an $ε$-solution in $O(1/ε)$ (resp., $O(1/\sqrtε)$) communication rounds for general convex functions (resp., strongly convex functions), while maintaining the $O(1/ε^2)$ (resp., $O(1/ε)$) bound on the total number of intra-node subgradient evaluations. We also present a stochastic counterpart for these algorithms, denoted by SDCS, for solving stochastic optimization problems whose objective function cannot be evaluated exactly. In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization.