Asynchronous distributed optimization using a randomized alternating direction method of multipliers

By Franck Iutzeler, Pascal Bianchi, Philippe Ciblat, Walid Hachem. 2013

186 citations recorded by the source corpus.

Consider a set of networked agents endowed with private cost functions and seeking to find a consensus on the minimizer of the aggregate cost. A new class of random asynchronous distributed optimization methods is introduced. The methods generalize the standard Alternating Direction Method of Multipliers (ADMM) to an asynchronous setting where isolated components of the network are activated in an uncoordinated fashion. The algorithms rely on the introduction of randomized Gauss-Seidel iterations of Douglas-Rachford splitting leading to an asynchronous algorithm based on the ADMM. Convergence to the sought minimizers is provided under mild connectivity conditions.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “, 2010), or specifically designed methods relying on problem structure, such as alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al., 2013), dual averaging (Duchi et al.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “, 2010), alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al., 2013) or dual averaging (Duchi et al.”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Several peer-to-peer algorithms have been developed for decentralized averaging (Kempe et al., 2003; Boyd et al., 2006; Colin et al., 2015) and optimization (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013; Colin et al., 2016).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “, 2010; Bianchi & Jakubowicz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al., 2013) or dual averaging (Duchi et al.”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “Moreover, neither of the works [6] and [10] provides a rate of convergence analysis of the asynchronous algorithm.”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, methodology): “Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
Asynchronous Online Federated Learning for Edge Devices (2019, background): “Numerous other distributed optimization methods [2, 19, 25, 34, 40, 41] in recent years are also not suitable for on-device learning.”
Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control (2014, unknown): “The first rigorous analysis of this problem was given in [58] and the problem has received considerable attention in recent years due its repeated appearance throughout distributed computing and multi-agent control; we mention [58, 59, 52, 70, 72, 42, 41, 79, 81, 80, 84, 34, 35, 8, 51, 37, 76, 17], ”
NEXT: In-Network Nonconvex Optimization (2016, background): “Consider a network composed of I autonomous agents aiming to cooperatively and distributively solve Problem (1).”
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification (2017, background): “Also, according to the different communication protocols, the distributed ADMM can be summarized into two classes: 1) asynchronous, where some nodes of the network are allowed to wake up at random and perform local updates in a noncoordinated fashion [23], [24] and 2) synchronous, where the master n”
Balancing Communication and Computation in Distributed Optimization (2017, methodology): “This class of methods includes augmented Lagrangian methods and Al-ternating Direction Method of Multiplier (ADMM) [35], [36], [37], [38], [39], [40], [41], [42], [3], [43], [44], [45], [46].”
Asynchronous Multi-task Learning (2016, methodology): “In order to avoid introducing multiple local copies and introduce asynchrony, Iutzeler et al. proposed an asynchronous distributed approach using randomized ADMM [3] based on randomized Gauss-Seidel iterations of a Douglas-Rachford splitting (DRS) because ADMM is equivalent to DRS.”
Asynchronous Decentralized Accelerated Stochastic Gradient Descent (2018, background): “, [23], [25], [26], [27]) has been studied in different asynchronous setting.”
Asynchronous Online Federated Learning for Edge Devices with Non-IID Data (2019, background): “Due to problems with stragglers and the non-IID character of edge device data, numerous other distributed optimization methods [12], [14]–[18] in recent years are also not suitable for on-device learning.”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, methodology): “Several classic algorithms have been ported and analyzed in the gossip setting, such as subgradient methods for convex objectives [37, 29, 44] or ADMM [50, 28].”