On the Linear Convergence of the ADMM in Decentralized Consensus Optimization

By Wei Shi, Qing Ling, Kun Yuan, Gang Wu, Wotao Yin. 2013

877 citations recorded by the source corpus.

In decentralized consensus optimization, a connected network of agents collaboratively minimize the sum of their local objective functions over a common decision variable, where their information exchange is restricted between the neighbors. To this end, one can first obtain a problem reformulation and then apply the alternating direction method of multipliers (ADMM). The method applies iterative computation at the individual agents and information exchange between the neighbors. This approach has been observed to converge quickly and deemed powerful. This paper establishes its linear convergence rate for the decentralized consensus optimization problem with strongly convex local objective functions. The theoretical convergence rate is explicitly given in terms of the network topology, the properties of local objective functions, and the algorithm parameter. This result is not only a performance guarantee but also a guideline toward accelerating the ADMM convergence.

Subfields: Computer Networks and Communications, Optimization & Training, 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 Computer Networks and Communications

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, methodology): “The most popular ﬁrst-order choices for the convex setting are distributed gradient descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of ”
Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, methodology): “…schemes, including gradient-based meth-ods Li et al. (2014a,b); Hsieh et al. (2017); Ho et al. (2013) and ADMM-based methods Zhang et al. (2018); Shi et al. (2014); Zhang and Zhu (2016a); Huang et al. (2018), have been proposed to enable learning from distributed samples, since collecting data…”
COLA: Decentralized Linear Learning (2018, methodology): “Applying ADMM to decentralized settings [Shi et al., 2014] involves solving minxi,zij ∑L i=1 fi(xi) s.”
D2: Decentralized Training over Decentralized Data (2018, background): “Shi et al. [2014] and Mokhtari and Ribeiro [2015] analyzed the decentralized version of the ADMM optimization algorithm.”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “The augmented Lagrangian based primal-dual methods have linear convergence under strong convexity and Lipschitz gradient assumptions [4,30] or under the positive-deﬁnite bounded Hessian assumption [12,13].”
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, methodology): “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.”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “To avoid such expensive proximal operator computation, Ling et al. propose a linearized variant of D-ADMM named DLM (Ling et al., 2015).”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “Under the strong convexity assumption, the decentralized ADMM has been shown to have linear convergence for time-invariant undirected graphs [63].”
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, methodology): “Minor modification as it is, the use of this gradient difference in lieu of simple gradients, endows EXTRA with exact linear convergence to the optimal argument x̃∗ under mild assumptions (Shi et al. (2015)).”
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, methodology): “, 2008; Nedic & Ozdaglar, 2009; Lobel & Ozdaglar, 2011), ADMM-based algorithms (Wei & Ozdaglar, 2012; Ling & Ribeiro, 2014; Shi et al., 2014; Zhang & Kwok, 2014; Ling et al., 2016), and composite of subgradient and ADMM (Bianchi et al.”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “When fi’s are convex, the existing algorithms include the (sub)gradient methods [8], [10], [24], [37], [40], [46], [59], [65], and the primal-dual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [9], [51], [52], DLM [31], and EXTRA [53], [54].”
Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM (2020, methodology): “Similarly to (Shi et al., 2014), we generate randomly a network consisting of N workers with a connectivity ratio p .”