DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

By Aryan Mokhtari, Wei Shi, Qing Ling, Alejandro Ribeiro. 2015

122 citations recorded by the source corpus.

This paper considers decentralized consensus optimization problems where nodes of a network have access to different summands of a global objective function. Nodes cooperate to minimize the global objective by exchanging information with neighbors only. A decentralized version of the alternating directions method of multipliers (DADMM) is a common method for solving this category of problems. DADMM exhibits linear convergence rate to the optimal objective for strongly convex functions but its implementation requires solving a convex optimization problem at each iteration. This can be computationally costly and may result in large overall convergence times. The decentralized quadratically approximated ADMM algorithm (DQM), which minimizes a quadratic approximation of the objective function that DADMM minimizes at each iteration, is proposed here. The consequent reduction in computational time is shown to have minimal effect on convergence properties. Convergence still proceeds at a linear rate with a guaranteed factor that is asymptotically equivalent to the DADMM linear convergence rate factor. Numerical results demonstrate advantages of DQM relative to DADMM and other alternatives in a logistic regression problem.

Subfields: Computational Mechanics, Computer Networks and Communications

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

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 ”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “Second-order approximation methods [29, 30] have been studied in order to handle this issue, but due to the nature of these methods differentiability of the objective function is necessary in this case.”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, background): “Real world tasks commonly suffer from the ill-conditionness of the underlying problem, which deteriorates the performance of existing methods due to their heavy dependence on the problem condition number (Shi et al., 2015a; Mokhtari et al., 2016).”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Building on (augmented) Lagrangian, a few improvements have been made via proximal-gradient [10], stochastic gradient [25], and second-order approximation [34, 35].”
An Exact Quantized Decentralized Gradient Descent Algorithm (2018, methodology): “The most commonly used algorithms are decentralized gradient descent or gradient projection method [10]–[13], distributed alternating direction method of multipliers (ADMM) [14]–[16], decentralized dual averaging [17], [18], and distributed Newton-type methods [19]–[21].”
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”
A survey of distributed optimization (2019, methodology): “The primal-dual interpretation of the EXTRA has been offered in Mokhtari and Ribeiro (2016) and Mokhtari, Shi, Ling, and Ribeiro (2016) based on the augmented Lagrangian function.”
A geometrically convergent method for distributed optimization over time-varying graphs (2016, methodology): “Among all these references, methods introduced in references [11]–[15], [22], [22], [25], [26] are all primal-only-like methods that work over undirected fixed graphs and usually need a diminishing step size to reach exact convergence; references [16]–[21], [23], [24], [27] concern about primal-dual”
Distributed nonconvex constrained optimization over time-varying digraphs (2018, methodology): “ual updates, aiming at converging to a saddle point of the (augmented) Lagrangian function. Examples of such algorithms include ADMM-like methods [9,22,39,45] as well as inexact primal-dual instances [10,25,26]. All these algorithms can handle only static and undirected graphs. Their extensions to t”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “…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.”
Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development (2017, background): “Some useful variations of distributed ADMM [35]–[37] may alleviate the computational burden, but their recursions are still more difficult to implement than consensus or diffusion.”