On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers

By Ermin Wei, Asuman E. Ozdaglar. 2013

362 citations recorded by the source corpus.

We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/√k) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O (1=k).

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health, 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 Computer Networks and Communications

In Public Health, Environmental and Occupational Health

In Optimization & Training

Citations in the corpus

COLA: Decentralized Linear Learning (2018, methodology): “Under a strong convexity assumption, decomposition techniques such as decentralized ADMM (DADMM, also known as consensus ADMM) have linear convergence for time-invariant undirected graphs, if subproblems are solved exactly [Shi et al., 2014, Wei and Ozdaglar, 2013].”
DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “They use techniques ranging from distributed (sub)gradient descent [4], [5] to more elaborate techniques such as EXTRA [6], distributed ADMM [7], [8], dual averaging [9], and distributed augmented Lagrangean [10].”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “At the cost of introducing many auxiliary variables, they cast the objective function as a partial consensus problem over the network which can be solved using a decentralized gossip ADMM algorithm (Wei and Ozdaglar, 2013).”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “This general method is a popular way to solve consensus problems of the form (2) in the distributed and decentralized settings (see e.g., Boyd et al., 2011; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “The most popular algorithms are based on (sub)gradient descent (Johansson et al., 2010; Nedi´c & Ozdaglar, 2009; Ram et al., 2010; Bianchi & Jakubow-icz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al., 2013) or dual averaging (Duchi et al., 2012; Yuan et al., 2012; Lee et al., 2015; Tsiano”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “For general convex functions and assuming closed and bounded feasible sets, the decentralized asynchronous ADMM [32] is proved to have a rate of O 1 k in terms of expected objective error and feasibility violation.”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “, [4,62,10]), where at each step for a fixed dual variable, the primal variables are solved to minimize some local Lagrangian related function, then the dual variables associated with the consistency constraints are updated accordingly.”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “The first work to address the development of decentralized ADMM over a network is [107]–[109], and it has been investigated in [110], while its linear rate has been shown in [111].”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “However, de-synchronization and extensions of these methods to time-varying undirected graphs are more involved [25, 69], while their extensions to directed graphs are non-existent in the current literature.”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “Our work is most closely related to recent developments in [11], [35]–[38], and [42].”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, result): “We note that the randomized version of Algorithm 2 is similar to that of the convex consensus algorithms studied in [47] and [48].”
Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control (2014, neutral): “ous analysis of this problem was given in [32] and the problem has received considerable attention in recent years due its repeated appearance throughout distributed computing and multi-agent control [21,22,28,29,32,33,41,43{46,49]. For specic applications, we mention robust statistical inference [4”
Asynchronous Distributed ADMM for Consensus Optimization (2014, methodology): “To alleviate the order problem, Wei & Ozdaglar (2013) proposed the asynchronous ADMM algorithm, in which workers are partitioned into groups according to their interconnection pattern.”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, background): “The decentralized ADMM and its proximal-gradient variant can employ a fixed step-size to achieve O(1/k) rate under general convexity assumptions [29]–[31].”
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach (2014, methodology): “The second major difference with the existing literature is about the tasks performed by the distributed nodes: in [37], [44], [45] each node directly optimizes the augmented Lagrangian, while here each node computes the gradient of their respective component functions.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “Edge-based methods have also been proposed before; in particular in [84] an asynchronous distributed ADMM algorithm presented for solving the more general consensus optimization problem with convex functions.”
Harnessing smoothness to accelerate distributed optimization (2016, methodology): “We note that there are other types of distributed optimization algorithms, like second-order distributed algorithms [30]–[32], Alternating Direction Method of Multipliers (ADMM) [33], [34] etc.”