Distributed Alternating Direction Method of Multipliers

By Ermin Wei, Asuman E. Ozdaglar. 2012

440 citations recorded by the source corpus.

We consider a network of agents that are cooperatively solving a global unconstrained optimization problem, where the objective function is the sum of privately known local objective functions of the agents. Recent literature on distributed optimization methods for solving this problem focused on subgradient based methods, which typically converge at the rate O (1/√k), where k is the number of iterations. In this paper, k we introduce a new distributed optimization algorithm based on Alternating Direction Method of Multipliers (ADMM), which is a classical method for sequentially decomposing optimization problems with coupled constraints. We show that this algorithm converges at the rate O (1/k).

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering, ML Systems & Hardware, 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

In Computer Networks and Communications

In Electrical and Electronic Engineering

In ML Systems & Hardware

In Mathematical Optimization

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…Johansson et al., 2010), or speciﬁcally 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., 2012; Nedi´c et al., 2015; Rabbat, 2015), primal-dual methods (Alghunaim…”
Decentralized Bayesian Learning over Graphs (2019, neutral): “This is unlike decentralized optimization and SGD based methods [15–21] where local (stochastic) gradients are computed for each instance of data and communication happens at a rate comparable to number of local updates.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The most popular algorithms are based on (sub)gradient descent (Nedi´c & Ozdaglar, 2009; Johansson et al., 2010), alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al., 2013) or dual averaging (Duchi et al., 2012; Nedi´c et al., 2015).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest (Duchi et al., 2012; Wei and Ozdaglar, 2012; Colin et al., 2016; Lian et al., 2017; Jiang et al., 2017; Tang et al., 2018; Lian et al., 2018).”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “Most of the work in fully decentralized learning and optimization has focused on the distributed consensus problem, where the goal is to find a single global model which minimizes the sum of the local loss functions (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2”
Deep learning with Elastic Averaging SGD (2014, methodology): “The standard methods for solving the consensus problem such as ADMM Boyd et al. (2011); Zhang & Kwok (2014); Wei & Ozdaglar (2012) therefore no longer apply.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “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, background): “The most popular of such approaches is the distributed alternating direction method of multipliers (D-ADMM) [2, 12, 5] and has led to a large number of variations and extensions.”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, methodology): “In this paper, we focus on the more general formulation (1) and propose an asynchronous decentralized algorithm based on the classical Alternating Direction Method of Multipliers (ADMM) (see [2], [3], [4], [5], [13] for convergence analysis of classical ADMM, and also [8], [11] for its applications ”
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].”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, background): “It has been shown that ADMM-based algorithms can converge at the rate of O ( 1 k ) while subgradient-based algorithms typically converge at the rate of O ( 1 √ k ) , where k is the number of iterations (Wei & Ozdaglar, 2012).”
Asynchronous distributed optimization using a randomized alternating direction method of multipliers (2013, background): “In [13], [14], agents operate in parallel, whereas [15] proposes a sequential version of ADMM where agents operate one after the other in a predetermined order.”
Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, methodology): “Methods based on Lagrangian dual [14], [15] converge faster but suffer from a high computational burden as they require solving a subproblem at each iteration.”
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].”
Proximity Without Consensus in Online Multiagent Optimization (2016, background): “…stochastic gradient is independent of random variables θ i,t [cf. (11)], and hence for all t , Also pertinent to analyzing the performance of the stochastic saddle point method is the fact that the primal stochastic gradient of the Lagrangian is an unbiased estimator of the true primal gradient.”
Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization (2015, methodology): “…only local communication, our node-based distributed algorithms require less communication burden and memory storage January 3, 2017 DRAFT Chen & Ozdaglar (2012) [20] composite convex Shi et al. (2015) [21] (PG-EXTRA) composite convex Aybat et al. (2015) [22] (DFAL) composite convex ) yes…”