Multi-Agent Distributed Optimization via Inexact Consensus ADMM

By Tsung-Hui Chang, Mingyi Hong, Xiangfeng Wang. 2014

Multi-agent distributed consensus optimization problems arise in many signal processing applications. Recently, the alternating direction method of multipliers (ADMM) has been used for solving this family of problems. ADMM based distributed optimization method is shown to have faster convergence rate compared with classic methods based on consensus subgradient, but can be computationally expensive, especially for problems with complicated structures or large dimensions. In this paper, we propose low-complexity algorithms that can reduce the overall computational cost of consensus ADMM by an order of magnitude for certain large-scale problems. Central to the proposed algorithms is the use of an inexact step for each ADMM update, which enables the agents to perform cheap computation at each iteration. Our convergence analyses show that the proposed methods converge well under some convexity assumptions. Numerical results show that the proposed algorithms offer considerably lower computational complexity than the standard ADMM based distributed optimization methods.

Citations in the corpus

• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, neutral): “…there are a variety of distributed optimization algorithms proposed in the literature, such as primal methods (Jakoveti´c et al., 2014; Nedi´c and Olshevsky, 2014; Nedi´c and Ozdaglar, 2009; Shi et al., 2015) and primal-dual methods (Chang et al., 2014a; Koppel et al., 2017; Bedi et al., 2019).”
• Robust and Communication-Efficient Collaborative Learning (2019, neutral): “…2016), distributed variants of the alternating direction method of multipliers (ADMM) (Schizas et al., 2008; Boyd et al., 2011; Shi et al., 2014; Chang et al., 2015; Mokhtari et al., 2016), dual averaging (Duchi et al., 2012; Tsianos et al., 2012), and several dual based strategies (Seaman et…”
• Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “onsfor relativelysimple convex functions fi (see also [20] for the applicationof mirrorprox method for solving these problems). These dual-based methods have been further studied via proximalgradient [9,8]. However, the local Lagrangian minimization problem associated with each agent cannot be solve”
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, neutral): “Building on (augmented) Lagrangian, a few improvements have been made via proximal-gradient [10], stochastic gradient [25], and second-order approximation [34, 35].”
• Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction (2015, unknown): “…of ADMM have subsequently been proposed, including specialized variants for decentralized systems (Mota et al., 2013), asynchronous updates (Zhang & Kwok, 2014; Ouyang et al., 2013), inexact solutions to subproblems (Chang et al., 2015), and online/stochastic updates (Ouyang et al., 2013).”
• A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, unknown): “The decentralized ADMM and its proximal-gradient variant can employ a fixed step-size to achieve O (1 /k ) rate under general convexity assumptions [8,14,43].”
• Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, unknown): “…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 decentralized optimization over general networks.”
• NEXT: In-Network Nonconvex Optimization (2016, unknown): “Consider a network composed of I autonomous agents aiming to cooperatively and distributively solve Problem (1).”
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, unknown): “Then with probability one, the iterates generated by the GADMM converge to an ss2 solution satisfying (39).”
• Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “In the distributed optimization literature, there are a variety of algorithms that are broadly categorized into primal meth-ods [27]–[30] and primal-dual methods [31]–[33].”
• Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, unknown): “(just like in the convex case, see discussions in [14]).”
• A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, unknown): “In addition, primal-dual type methods include [7], [27], which are based on DADMM.”
• Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, unknown): “1), such as, the accelerated primal-dual methods [26, 27], the alternating direction method of multipliers (ADMM) [28–32], and the distributed dual methods (mirror descent/dual averaging) [33–35].”
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients (2016, unknown): “, edges), and apply ADMM (possibly with linearization or preconditioning techniques) to derive an implementable decentralized consensus algorithm [6, 12, 14, 23, 35, 46].”
• Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development (2017, unknown): “It should be emphasized that condition (2), which is repeated in (3), is different from all previous algorithms studied in [23], [32]–[34], [36], [38], [42], [43], which require A to be symmetric and doubly stochastic (i.”