A Unification and Generalization of Exact Distributed First Order Methods
arXiv:1709.01317
Abstract
Recently, there has been significant progress in the development of distributed first order methods. (At least) two different types of methods, designed from very different perspectives, have been proposed that achieve both exact and linear convergence when a constant step size is used -- a favorable feature that was not achievable by most prior methods. In this paper, we unify, generalize, and improve convergence speed of these exact distributed first order methods. We first carry out a novel unifying analysis that sheds light on how the different existing methods compare. The analysis reveals that a major difference between the methods is on how a past dual gradient of an associated augmented Lagrangian dual function is weighted. We then capitalize on the insights from the analysis to derive a novel method -- with a tuned past gradient weighting -- that improves upon the existing methods. We establish for the proposed generalized method global R-linear convergence rate under strongly convex costs with Lipschitz continuous gradients.
revised Dec 17, 2017
References in corpus (9)
- Constrained Consensus
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- ExtraPush for convex smooth decentralized optimization over directed networks
- Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
- Distributed Gradient Methods with Variable Number of Working Nodes
- Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
- Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
- Geometrical Convergence Rate for Distributed Optimization with Time-Varying Directed Graphs and Uncoordinated Step-Sizes