D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization

By João F. C. Mota, Joao Xavier, Pedro M. Q. Aguiar, Markus Püschel. 2012

399 citations recorded by the source corpus.

We propose a distributed algorithm, named Distributed Alternating Direction Method of Multipliers (D-ADMM), for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem there is a private cost function and a private constraint set at each node. The goal is to minimize the sum of all the cost functions, constraining the solution to be in the intersection of all the constraint sets. D-ADMM is proven to converge when the network is bipartite or when all the functions are strongly convex, although in practice, convergence is observed even when these conditions are not met. We use D-ADMM to solve the following problems from signal processing and control: average consensus, compressed sensing, and support vector machines. Our simulations show that D-ADMM requires less communications than state-of-the-art algorithms to achieve a given accuracy level. Algorithms with low communication requirements are important, for example, in sensor networks, where sensors are typically battery-operated and communicating is the most energy consuming operation.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering

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

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “1 ADMM Applied to the OB(·) Formulation Here we compare consensus ADMM (Mota et al., 2013) applied to the problem (B) to the CoCoA framework, as discussed in Section 3.”
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 ”
Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges (2022, background): “Recently, several techniques have been proposed to limit overall communication overhead per federated iteration [8], [106].”
Balancing Communication and Computation in Distributed Optimization (2017, methodology): “This class of methods includes augmented Lagrangian methods and Alternating Direction Method of Multiplier (ADMM) [35], [36], [37], [38], [39], [40], [41], [42], [3], [43], [44], [45], [46].”
Asynchronous Distributed ADMM for Consensus Optimization (2014, methodology): “For example, Mota et al. (2013) developed a communication-efficient distributed algorithm extended from the multi-block ADMM algorithm.”
Distributed Ridge Regression with Feature Partitioning (2018, methodology): “However, works of [20], [21] assume a proper coloring scheme of the network and cannot be extended to a general graph labeling.”
Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes (2015, methodology): “Building on this method, distributed versions of Alternative Direction Method of Multipliers (ADMM [18]) have been proposed for solving the above same problem [19], [20].”
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.”
Learning Transferable Knowledge Through Embedding Spaces (2019, methodology): “we use the extended ADMM algorithm [247; 256].”
Quantized consensus ADMM for multi-agent distributed optimization (2015, background): “Many of the distributed optimization problems, such as those mentioned, can be cast as an optimization problem of the following form min x̃ N ∑ i=1 fi(x̃), (1) wherefi : RM → R∪ {∞} is the local objective function associated with agenti.”
Expander graph and communication-efficient decentralized optimization (2016, methodology): “for some norm ‖·‖ (where z is related to x), and decentralized ADMM [16], [17], [18]:”
Communication-Censored ADMM for Decentralized Consensus Optimization (2019, methodology): “algorithms where a node can utilize its local gradient during the optimization process, such as gradient descent method [20], diffusion method [21], exact first-order algorithm [22], and linearized ADMM [23], [24]; (iii) second-order algorithms where a node can compute or approximately compute its l”
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation (2017, background): “Such privacy-preserving cooperation is common for many secure multi-agent systems [17], [42], [43].”
Multi-Agent Distributed Optimization via Inexact Consensus ADMM (2014, neutral): “For example, the proposed IC-ADMM approximates the smooth functions f i ’s in C-ADMM, which is very different from the known inexact ADMM methods [29], [30], where only the quadratic penalty is approximated (thus does not always result in cheap PG steps).”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “…et al., 2014; Beck et al., 2014; Shi et al., 2015a,b; Aybat et al., 2015) and distributed ADMM methods (Boyd et al., 2011; Wei and Ozdaglar, 2012; Mota et al., 2013; Shi et al., 2014; Chang et al., 2015; Makhdoumi and Ozdaglar, 2017; Deng and Yin, 2016; Mokhtari et al., 2016) for…”
NEXT: In-Network Nonconvex Optimization (2016, methodology): “Distributed ADMM algorithms tailored for specific machine learning convexproblems and parameter estimation in sensor networks were proposed in [20], [21]; [22], [23], [24], studied the convergen c of synchronous distributed ADMM over undirected connected time-invariant graphs; some asynchronous inst”