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 (12)
- TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Optimization and Analysis of Distributed Averaging with Short Node Memory
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
- Primal-dual subgradient methods for minimizing uniformly convex functions
- Distributed Learning for Cooperative Inference
- Restarting accelerated gradient methods with a rough strong convexity estimate
- Convex optimization in Hilbert space with applications to inverse problems
- Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
- Gradient and gradient-free methods for stochastic convex optimization with inexact oracle
Cited by in corpus (13)
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- 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
- Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
- A Push-Pull Gradient Method for Distributed Optimization in Networks
- 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
- The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
- Accelerated Sparsified SGD with Error Feedback
- A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks