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

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

444 citations recorded by the source corpus.

Subfields: Computer Networks and Communications

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

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, neutral): “…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.,…”
DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, neutral): “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 (AL) [10].”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, positive): “Moreover, without a good intuition for what it is doing, it is difﬁcult to extend it to time-varying or directed graphs (the original proof in [32] only covered ﬁxed graphs).”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, positive): “…the numerous applications of distributed optimization in machine learning, many algorithms have recently emerged, that allow the minimization of objective functions f deﬁned as the average 1 n =1 f i of functions f i which are respectively accessible by separate nodes in a network [1, 2, 3, 4].”
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, neutral): “…(Mokhtari et al. (2015a,b)), decentralized dual averaging (Duchi et al. (2012); Tsianos et al. (2012b)), the exact ﬁrst order al-gorithm (EXTRA) (Shi et al. (2015)), as well as the alternating direction method of multipliers (ADMM) (Boyd et al. (2011); Shi et al. (2014); Iutzeler et al.…”
On Nonconvex Decentralized Gradient Descent (2016, neutral): “When fi’s are convex, the existing algorithms include the (sub)gradient methods [5], [6], [10], [13], [15], [23], [27], and the primaldual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [19], [20] and EXTRA [21], [22].”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “This approach includes well-known algorithms such as diffusion [5], [6] and consensus [11], [12], distributed ADMM (D-ADMM) [13]–[15], EXTRA [16], PG-EXTRA [17], DIGing [18], exact diffusion [19], NIDS [20], and beyond.”
Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, methodology): “Although, EXTRA and DIGing are traditional AL primal-dual methods, the analysis in this work does not cover these cases.”
A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization (2014, unknown): “More recently, numerous works extend ed this kind of algorithm to more involved multi-agent scenari os, see [17]–[28].”
Decentralized Consensus Algorithm with Delayed and Stochastic Gradients (2016, unknown): “A correction technique is developed for decentralized gradient descent with convergence rate as O (1 /T ) with constant step size in [34], which results in a saddle-point algorithm as pointed out in [24].”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, background): “1) have a long history, probably first studied in [5] and recently received a wide attention; see for example, [1, 6–11] and the recent survey paper [4].”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, unknown): “Problem (1.1) has been studied extensively in the literature under various distributed algorithms [48, 30, 31, 23, 19, 20, 44, 15, 40, 28, 50, 39], among which the distributed gradient descent (DGD) method proposed in [30] has drawn the greatest attention.”
Accelerated Distributed Nesterov Gradient Descent (2017, unknown): “The weight matrix W is chosen using the Laplacian method [31].”
Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges (2022, unknown): “Some examples are Decentralized Gradient Descent (DGD) [104], decentralized Alternating Direction Method of Multipliers (ADMM) [105], EXTRA [106], and ADMM based on Jacobi-Proximal [107].”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “1) has been studied extensively in the literature under various distributed algorithms [50, 31, 32, 23, 17, 18, 45, 13, 41, 29, 52, 40], among which the distributed gradient descent (DGD) method proposed in [31] has drawn the greatest attention.”
A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, unknown): “When the possibly-nondifferentiable term , we have in (2a) and (2b) and thus (4) In (3a) and (3b), we have and thus (5) The updates (4) and (5) are known as EXTRA, a recent algo-rithm for decentralized differentiable optimization [23].”