Push-Sum Distributed Dual Averaging for convex optimization

By Konstantinos I. Tsianos, Sean F. Lawlor, Michael G. Rabbat. 2012

326 citations recorded by the source corpus.

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

In Computer Networks and Communications

Citations in the corpus

Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, methodology): “The algorithm design mainly follows the pattern of push-sum algorithm (Tsianos et al., 2012), but here we further generalize it into on-line setting.”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…direction method of multipliers (ADMM) (Schizas et al., 2008; Boyd et al., 2011; Shi et al., 2014; Chang et al., 2015; Mokhtari et al., 2016), dual averaging (Duchi et al., 2012; Tsianos et al., 2012), and several dual based strategies (Seaman et al., 2017; Scaman et al., 2018; Uribe et al., 2018).”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “ng agents to propagate the distributed information to every location in the network. One of the most well-studied techniques in decentralized optimization are the subgradient based methods (see e.g., [39,35,57,37,14,27,52]), where at each step a local subgradient is taken at each node, followed by t”
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization (2013, methodology): “Related Work Besides the ADMM, existing decentralized approaches for so lving (1) include belief propagation [7], incremental optimization [22], subgradient descent [ 15]–[17], dual averaging [18], [19], etc.”
Distributed optimization over time-varying directed graphs (2013, background): “The papers [20], [21] proved the convergence of a subgradient algorithm in a directed but fixed topology; implementation of the protocol appears to require knowledge of the graph or of the number of agents.”
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, methodology): “…(2009); Jakovetic et al. (2014); Yuan et al. (2013)), network Newton (Mokhtari et al. (2015a,b)), decentralized dual averaging (Duchi et al. (2012); Tsianos et al. (2012b)), the exact first order algorithm (EXTRA) (Shi et al. (2015)), as well as the alternating direction method of multipliers…”
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].”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “We specifically mention [36], [37], which were the first papers to suggest the use of push-sum-like updates for optimization over directed graphs as well as [39] and [42] which derived O(1/t) convergence rates in the less stringent setting when every graph is fixed and undirected.”
An Exact Quantized Decentralized Gradient Descent Algorithm (2018, methodology): “The most commonly used algorithms are decentralized gradient descent or gradient projection method [10]–[13], distributed alternating direction method of multipliers (ADMM) [14]–[16], decentralized dual averaging [17], [18], and distributed Newton-type methods [19]–[21].”
Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives (2015, methodology): “[2] and later extended in [32] and in [15], [16] to distributed optimization.”
NEXT: In-Network Nonconvex Optimization (2016, methodology): “Algorithms belonging to the former class include: i) consensus-based (sub)gradien t schemes [1]–[4] along with their accelerated and asynchron ous versions [5]–[7]; ii) the (sub)gradient push-method [8], [ 9]; iii) the dual-average method [10], [11]; and iv) distributed sec ondorder-based schemes [1”
Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning (2012, methodology): “A different solution is proposed in [12], [23] by employing an algorithm called Push-Sum [19].”
Distributed Optimization Over Time-Varying Directed Graphs (2015, unknown): “The papers [30], [31], [32], [29] proposed a distributed subgradient algorithm which is very similar to the one we study here, involving the introduction of subgradients into an information aggregation procedure known as “push-sum.”
Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development (2017, methodology): “employ the useful push-sum technique, which requires A to be right (rather than left) stochastic, i.e., Ais required to satisfy instead1A1 N = 1 N. For instance, the push-sum implementations in [40], [44]–[47] replace the rightmost condition in (3) by w k;i+1 = XN ‘=1 a ‘k ‘;i; where XN k=1 a ‘k = 1”