Parallel Direction Method of Multipliers
By Huahua Wang, Arindam Banerjee, Zhi-Quan Tom Luo. 2014
53 citations recorded by the source corpus.
We consider the problem of minimizing block-separable (non-smooth) convex functions subject to linear constraints. While the Alternating Direction Method of Multipliers (ADMM) for two-block linear constraints has been intensively studied both theoretically and empirically, in spite of some preliminary work, effective generalizations of ADMM to multiple blocks is still unclear. In this paper, we propose a parallel randomized block coordinate method named Parallel Direction Method of Multipliers (PDMM) to solve optimization problems with multi-block linear constraints. At each iteration, PDMM randomly updates some blocks in parallel, behaving like parallel randomized block coordinate descent. We establish the global convergence and the iteration complexity for PDMM with constant step size. We also show that PDMM can do randomized block coordinate descent on overlapping blocks. Experimental results show that PDMM performs better than state-of-the-arts methods in two applications, robust principal component analysis and overlapping group lasso.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Andrews Cordolino Sobral
- Thierry Bouwmans
- Sajid Javed
- Soon Ki Jung
- Zongben Xu
- El-Hadi Zahzah
- Yan Yang
- Huibin Li
Citations in the corpus
- Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, background): “(2014) [381] Generalized Singular Value Thresholding (GSVT) Lu et al.”
- Deep ADMM-Net for Compressive Sensing MRI (2016, methodology): “To optimize the CS-MRI models, Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient variable splitting algorithm with convergence guarantee [4, 12, 13].”
- Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “Finally, it is worth mentioning that GADMM is closely related to other group-based ADMM methods as in [49], [50], but these methods consider more communication links per iteration than our proposed GADMM algorithm.”
- Exogenous Cost Allocation in Peer-to-Peer Electricity Markets (2019, background): “Several extensions and convergence rate improvements have been proposed in [20]–[23].”