EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

By Wei Shi, Qing Ling, Gang Wu, Wotao Yin. 2014

1,201 citations recorded by the source corpus.

Recently, 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 $$\min\limits_{x\in\mathbb{R}^p}~\bar{f}(x)=\frac{1}{n}\sum\limits_{i=1}^n f_i(x),$$ which is defined over a connected network of $n$ agents, where each function $f_i$ is held privately by agent $i$ 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 EXact firsT-ordeR Algorithm (abbreviated as EXTRA) to solve the consensus optimization problem."exact"means that it can converge to the exact solution. EXTRA can use a fixed large step size, {which is independent of the network size}, and has synchronized iterations. The local variable of every agent $i$ converges uniformly and consensually to an exact minimizer of $\bar{f}$. In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer. EXTRA and DGD have the same choice of mixing matrices and similar per-iteration complexity. EXTRA, however, uses the gradients of last two iterates, unlike DGD which uses just that of last iterate. EXTRA has the best known convergence rates among the existing first-order decentralized algorithms. Specifically, if $f_i$'s are convex and have Lipschitz continuous gradients, EXTRA has an ergodic convergence rate $O(\frac{1}{k})$ in terms of the first-order optimality residual. If $\bar{f}$ is also restricted strongly convex, EXTRA converges to an optimal solution at a linear rate $O(C^{-k})$ for some constant $C>1$.

Subfields: Computer Networks and Communications, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “This phenomena has been discussed (and sometimes been adressed by modifing the SGD updates) for example in (Shi et al., 2015; Lee et al., 2015; Nedić et al., 2016) and been rediscovered frequently in the context of stochastic optimization (Zhao et al.”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “For example, decentralized SGD (Shi et al., 2014; Yuan et al., 2013; Lian et al., 2017) avoids congesting the central server node and improves the scalability by removing the server, and letting the workers communicate with their neighbours only.”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “In another approach, option II in (6) which is known as gradient-tracking in decentralized algorithms (Shi et al., 2015; Nedich et al., 2016) uses By using an average of many stochastic gradients, option II has lower variance at the cost of slightly higher bias.”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of the alternating direction method of multipliers (ADMM) (Schizas et al.,…”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “, 2011), where the network is designed to ensure that all workers can get information from all others, and decentralized design (He et al., 2018a; Li & Yan, 2017; Lian et al., 2017; 2018; Shi et al., 2015; Tang et al., 2018b), where each worker is only allowed to communicate with its neighbors.”
COLA: Decentralized Linear Learning (2018, methodology): “…network topologies and with varying subproblem quality ⇥ ; secondly, we compare C O L A with state-of-the-art decentralized baselines: 1 � , DIGing [Nedic et al., 2017], which generalizes the gradient-tracking technique of the EXTRA algorithm [Shi et al., 2015], and 2 , Decentralized ADMM (aka.”
DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “They use techniques ranging from distributed (sub)gradient descent [4], [5] to more elaborate techniques such as EXTRA [6], distributed ADMM [7], [8], dual averaging [9], and distributed augmented Lagrangean [10].”
D2: Decentralized Training over Decentralized Data (2018, background): “Recently, Li and Yan [2017] show that λ n > − 1/3 is optimal in the convergence of EXTRA.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, background): “Decentralized gradient descent on convex and strongly convex problems was analyzed in Yuan et al. [2016]. Nedic and Ozdaglar [2009], Ram et al.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “Many algorithms were proposed to solve the decentralized optimization of an average of functions (see for example [1, 11, 3, 4, 12, 2, 13, 5]), and a sheer amount of work was devoted to improving the convergence rate of these algorithms [5, 6].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “Given the numerous applications of distributed optimization in machine learning, many algorithms have recently emerged, that allow the minimization of objective functions f defined as the average 1 n ∑n i=1 fi of functions fi which are respectively accessible by separate nodes in a network (Nedic & ”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “EXTRA (Shi et al., 2015a) improves over DGD by incorporating information from the last two iterates and is shown to converge linearly.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Although linearly convergent distributed optimization methods over ﬁxed graphs were ﬁrst developed in [62], extending the proof of [62] to time-varying graphs does not appear to be possible.”
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, methodology): “Minor modiﬁcation as it is, the use of this gradient diﬀerence in lieu of simple gradients, endows EXTRA with exact linear convergence to the optimal argument ˜ x ∗ under mild assumptions (Shi et al. (2015)).”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, methodology): “…attention during the last decade, mostly focusing on three classes of algorithms, namely, the alternating direction method of multipliers (ADMM) [1,17,33,35], distributed dual methods (mirror descent/dual averaging) [6,9,14,34,37], and distributed gradient algorithms [3–5,13,16,22,23,27,29,32,38].”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “When fi’s are convex, the existing algorithms include the (sub)gradient methods [8], [10], [24], [37], [40], [46], [59], [65], and the primal-dual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [9], [51], [52], DLM [31], and EXTRA [53], [54].”
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, background): “, achieving the same O(1/k) convergence rate with constant step-size [18] or even under time-varying network graphs [19]).”
Variance Reduced Local SGD with Lower Communication Complexity (2019, background): “Among them, Shi et al. [2015] propose a novel decentralized algorithm, EXTRA, which provides an ergodic convergence rate for convex problems and a linear convergence rate for strongly convex problems beneﬁting from eliminating the variance among workers.”