Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
arXiv:2106.04469
Abstract
We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network whose links are allowed to change in time. We solve two fundamental problems for this task. First, we establish the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an -accurate solution. Second, we design two optimal algorithms that attain these lower bounds: (i) a variant of the recently proposed algorithm ADOM (Kovalev et al., 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access to the dual gradients is assumed, and (ii) a novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is assumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
References in corpus (10)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Learning: Strategies for Improving Communication Efficiency
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Multi-consensus Decentralized Accelerated Gradient Descent
- ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
- Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
- Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
- An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints