EXTRA: AN EXACT FIRST-ORDER ALGORITHM FOR DECENTRALIZED CONSENSUS OPTIMIZATION

EXTRA: AN EXACT FIRST-ORDER ALGORITHM FOR DECENTRALIZED CONSENSUS OPTIMIZATION

30 Nov 2014 | WEI SHI, QING LING, GANG WU, AND WOTAO YIN
This paper introduces a novel decentralized exact first-order algorithm called EXTRA for solving consensus optimization problems in a multi-agent network. The problem is defined as minimizing the sum of convex functions, each held privately by a different agent, over a connected network. EXTRA allows agents to communicate only with their neighbors, avoiding the need for a central fusion center or long-distance communication, and offers better load balancing. The key contributions of this paper include: 1. **Algorithm Development**: EXTRA is derived by modifying the decentralized gradient descent (DGD) update, ensuring that the sequence of iterates converges to a point that satisfies both consensus and optimality conditions. 2. **Convergence Analysis**: EXTRA achieves an ergodic convergence rate of \(O(\frac{1}{k})\) for general convex objectives with Lipschitz differentials, and a linear convergence rate if the sum of the functions is also (restricted) strongly convex. 3. **Performance Comparison**: Numerical simulations demonstrate that EXTRA outperforms DGD in terms of convergence speed and accuracy. The paper also discusses the choice of mixing matrices and provides theoretical guarantees for the convergence rates of EXTRA. The proposed algorithm is shown to be more efficient and accurate compared to existing decentralized methods, making it a valuable tool for decentralized consensus optimization problems.This paper introduces a novel decentralized exact first-order algorithm called EXTRA for solving consensus optimization problems in a multi-agent network. The problem is defined as minimizing the sum of convex functions, each held privately by a different agent, over a connected network. EXTRA allows agents to communicate only with their neighbors, avoiding the need for a central fusion center or long-distance communication, and offers better load balancing. The key contributions of this paper include: 1. **Algorithm Development**: EXTRA is derived by modifying the decentralized gradient descent (DGD) update, ensuring that the sequence of iterates converges to a point that satisfies both consensus and optimality conditions. 2. **Convergence Analysis**: EXTRA achieves an ergodic convergence rate of \(O(\frac{1}{k})\) for general convex objectives with Lipschitz differentials, and a linear convergence rate if the sum of the functions is also (restricted) strongly convex. 3. **Performance Comparison**: Numerical simulations demonstrate that EXTRA outperforms DGD in terms of convergence speed and accuracy. The paper also discusses the choice of mixing matrices and provides theoretical guarantees for the convergence rates of EXTRA. The proposed algorithm is shown to be more efficient and accurate compared to existing decentralized methods, making it a valuable tool for decentralized consensus optimization problems.
Reach us at info@study.space