IEEE Transactions on Automatic Control · 2019 · 190 citations · 37 references
ComputingComputer ScienceAlgorithmsDistributed SystemsOptimizationConsensus AlgorithmsConvex OptimizationDistributed AlgorithmsDistributed ComputingDistributed ConsensusGradient-based OptimizationAverage ConsensusConsensusConvergenceConvex FunctionsDistributed OptimizationFirst-order OptimizationLinear ConvergenceState Transformation
We study distributed optimization to minimize a sum of smooth and strongly-convex functions. Recent work on this problem uses gradient tracking to achieve linear convergence to the exact global minimizer. However, a connection among different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are related with a simple state transformation, at the heart of which lies a recently introduced algorithm known as AB. We then present distributed heavy-ball, denoted as ABm, that combines AB with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both rowand column-stochastic weights, ABm removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation. ABm thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that ABm has a global R-linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that ABm achieves acceleration, particularly when the objective functions are ill-conditioned.
37
Gossip-based computation of aggregate information
David Kempe, Alin Dobra, Johannes Gehrke · 2004 · 1.5K citations
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Wei Shi, Qing Ling, Gang Wu et al. · SIAM Journal on Optimization · 2015 · 1.3K citations