A Proximal Gradient Algorithm for Decentralized Composite Optimization

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

318 citations recorded by the source corpus.

Subfields: Computational Mechanics, 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 Computational Mechanics

1. Ji Liu
2. Wotao Yin
3. Ce Zhang
4. Alexander Olshevsky
5. Hanlin Tang
6. Wei Shi
7. Angelia Nedić
8. Kun Yuan

In Computer Networks and Communications

1. Angelia Nedić
2. Ali H. Sayed
3. Wei Shi
4. Aryan Mokhtari
5. Alexander Olshevsky
6. Ji Liu
7. Wotao Yin
8. Kun Yuan

In Optimization & Training

1. Aryan Mokhtari
2. Wotao Yin
3. Ji Liu
4. Ali H. Sayed
5. Angelia Nedić
6. Martin Jaggi
7. Wei Shi
8. Ce Zhang

In Mathematical Optimization

1. Ali H. Sayed
2. Wotao Yin
3. Wei Shi
4. Angelia Nedić
5. Aryan Mokhtari
6. Qing Ling
7. Kun Yuan
8. Alexander Olshevsky

Citations in the corpus

• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “…there are a variety of distributed optimization algorithms proposed in the literature, such as primal methods (Jakoveti´c et al., 2014; Nedi´c and Olshevsky, 2014; Nedi´c and Ozdaglar, 2009; Shi et al., 2015) and primal-dual methods (Chang et al., 2014a; Koppel et al., 2017; Bedi et al., 2019).”
• 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.,…”
• D2: Decentralized Training over Decentralized Data (2018, background): “Existing decentralized consensus algorithms [Li et al., 2017, Shi et al., 2015b] use a modification of the doubly stochastic matrix such that λ > 0, i.e., choose W = ( ˜ W + I ) /2 where W is a doubly stochastic matrix.”
• Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “This issue was fixed later by Shi et al. [2015a], Wu et al. [2016] by using the gradients of last two instead of one iterates in each iteration, which was later improved in Li et al. [2017], Shi et al. [2015b] by considering proximal gradients.”
• Communication Compression for Decentralized Training (2018, methodology): “Two methods [Li et al., 2017, Shi et al., 2015] were proposed to blackuce the steady point error in decentralized gradient descent convex optimization.”
• 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.”
• 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.”
• A geometrically convergent method for distributed optimization over time-varying graphs (2016, background): “…that work over undirected fixed graphs and usually need a diminishing step size to reach exact convergence; references [16]–[21], [23], [24], [27] concern about primal-dual-like methods which can deploy constant step size and converge quickly and exactly to the solution over undirected…”
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization (2015, methodology): “In [21], the proximal gradient exact first-order algorithm (PG-EXTRA) is proposed; PG-EXTRA is an extension of the algorithm EXTRA [23] to handle the non-smooth terms { ξ i } i ∈N .”
• Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, background): “Work in [28], [29] investigates proximal-gradient methods which can tackle (1) with proximal friendly component functions.”
• Asynchronous Decentralized Online Learning (2021, background): “Learner i t receives a convex function f t from environment, and suffers the loss f t ( w i t ( t )) .”
• Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “In the distributed optimization literature, there are a variety of algorithms that are broadly categorized into primal meth-ods [27]–[30] and primal-dual methods [31]–[33].”
• Decentralization Meets Quantization (2018, methodology): “Two methods [Li et al., 2017, Shi et al., 2015] were proposed to blackuce the steady point error in decentralized gradient descent convex optimization.”
• A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization (2017, methodology): “We will show in Section 3 that the famous decentralized algorithm– Proximal Gradient EXact firsT-ordeR Algorithm (PG-EXTRA) [19] is exactly the primal-dual algorithm in (7), which is a generalization of (4) for solving (1).”
• Decentralized consensus optimization with asynchrony and delays (2016, methodology): “To establish convergence under delays, we cannot follow the existing analysis of PG-EXTRA [2]; instead, motivated by [30], [32], a new non-Euclidean metric is introduced to absorb the delays.”
• A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “By making a simple modification over PG-EXTRA [1], our proposed algorithm brings a big improvement in the speed and the dependency of convergence over networks.”