Optimal Algorithms for Distributed Optimization
arXiv:1712.00232
Abstract
In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function $F(\xb) \triangleq \sum_{i=1}^{m}f_i(\xb)$ is strongly convex and smooth, either strongly convex or smooth or just convex. Our results show that Nesterov's accelerated gradient descent on the dual problem can be executed in a distributed manner and obtains the same optimal rates as in the centralized version of the problem (up to constant or logarithmic factors) with an additional cost related to the spectral gap of the interaction matrix. Finally, we discuss some extensions to the proposed setup such as proximal friendly functions, time-varying graphs, improvement of the condition numbers.
References in corpus (1)
Cited by in corpus (11)
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
- Recent theoretical advances in decentralized distributed convex optimization
- Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
- A Push-Pull Gradient Method for Distributed Optimization in Networks
- Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
- Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
- Distributed Differentially Private Computation of Functions with Correlated Noise
- Improved Differentially Private Decentralized Source Separation for fMRI Data
- Accelerated Sparsified SGD with Error Feedback
- A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks