Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization

By Necdet Serhat Aybat, Zi Wang, Tianyi Lin, Shiqian Ma. 2015

150 citations recorded by the source corpus.

Given an undirected graph <inline-formula><tex-math notation="LaTeX">$\mathcal {G}=(\mathcal {N},\mathcal {E})$ </tex-math></inline-formula> of agents <inline-formula><tex-math notation="LaTeX">$\mathcal {N}=\lbrace 1,\ldots,N\rbrace$</tex-math></inline-formula> connected with edges in <inline-formula><tex-math notation="LaTeX"> $\mathcal {E}$</tex-math></inline-formula>, we study how to compute an optimal decision on which there is consensus among agents and that minimizes the sum of agent-specific private convex composite functions <inline-formula> <tex-math notation="LaTeX">$\lbrace \Phi _i\rbrace _{i\in \mathcal {N}}$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\Phi _i\triangleq \xi _i + f_i$</tex-math></inline-formula> belongs to agent-<inline-formula><tex-math notation="LaTeX">$i$</tex-math></inline-formula>. Assuming only agents connected by an edge can communicate, we propose a distributed proximal gradient algorithm (DPGA) for consensus optimization over both unweighted and weighted static (undirected) communication networks. In one iteration, each agent-<inline-formula> <tex-math notation="LaTeX">$i$</tex-math></inline-formula> computes the prox map of <inline-formula> <tex-math notation="LaTeX">$\xi _i$</tex-math></inline-formula> and gradient of <inline-formula> <tex-math notation="LaTeX">$f_i$</tex-math></inline-formula>, and this is followed by local communication with neighboring agents. We also study its stochastic gradient variant, SDPGA, which can only access to noisy estimates of <inline-formula><tex-math notation="LaTeX">$\nabla f_i$</tex-math></inline-formula> at each agent-<inline-formula> <tex-math notation="LaTeX">$i$</tex-math></inline-formula>. This computational model abstracts a number of applications in distributed sensing, machine learning and statistical inference. We show ergodic convergence in both suboptimality error and consensus violation for the DPGA and SDPGA with rates <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(1/t)$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(1/\sqrt{t})$ </tex-math></inline-formula>, respectively.

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

Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Decentralized ADMM algorithms were analyzed in Aybat et al. [2015], Shi et al., Zhang and Kwok [2014].”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Other decentralized algorithms In other areas including control, privacy and wireless sensing network, decentralized algorithms are usually studied for solving the consensus problem [Aysal et al., 2009, Boyd et al., 2005, Carli et al., 2010, Fagnani and Zampieri, 2008, Olfati-Saber et al., 2007, Sch”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “In [89] the ADMM with linearization has been proposed for special composite optimization problems over graphs.”
Asynchronous Decentralized Accelerated Stochastic Gradient Descent (2018, unknown): “, [11], [12], [13], [14], [15], [16], [17], [18], [19].”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “This approach includes well-known algorithms such as diffusion [1], [2] and consensus [7], [8], distributed ADMM (D-ADMM) [9]–[13], EXTRA [14], PG-EXTRA [15], DIGing [16], exact diffusion [17], NIDS [18], and beyond.”
A survey of distributed optimization (2019, methodology): “Other proximal algorithms for composite optimization are also available in the literature, see, e.g., Aybat, Wang, and Iyen-gar (2015) ; Aybat, Wang, Lin, and Ma (2018) ; Dhingra, Khong, and Jovanovi ´c (2019) and Xu, Zhu, Sohy, and Xie (2018b) .”