## EXTRA: an Exact First-Order Algorithm for Decentralized Consensus OptimizationWei Shi, Qing Ling, Gang Wu, and Wotao Yin Published in Code for decentralized logistic minimization / Code for decentralized Huber minimization by Wei Shi, last update: Jan 2015
## OverviewRecently, there have been growing interests in solving consensus optimization problems in a multi-agent network. In this paper, we develop a decentralized algorithm for the consensus optimization problem which is defined over a connected network of agents, where each is held privately by agent and encodes the agent's data and objective. All the agents shall collaboratively find the minimizer while each agent can only communicate with its neighbors. Such a computation scheme avoids a data fusion center or long-distance communication and offers better load balance to the network. This paper proposes a novel decentralized EXTRA has the best known convergence rates among the existing first-order decentralized algorithms for decentralized consensus optimization with convex differentiable objectives. Specifically, if 's are convex and have Lipschitz continuous gradients, EXTRA has an ergodic convergence rate . If is also (restricted) strongly convex, the rate improves to linear at for some constant . ## Citation
## Related paperK. Yuan, Q. Ling, and W. Yin, On the Convergence of Decentralized Gradient Descent, UCLA CAM Report 13-61, 2013. « Back |