Parallel Direction Method of Multipliers

Abstract

We consider the problem of minimizing block-separable 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 randomized block coordinate method named Parallel Direction Method of Multipliers (PDMM) to solve the optimization problems with multi-block linear constraints. PDMM randomly updates some primal and dual 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.

This paper has been withdrawn by the authors. There are errors in Equations from 139-195

References in corpus (14)

• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• Alternating Direction Algorithms for ${\ell }_1$-Problems in Compressive Sensing
• The composite absolute penalties family for grouped and hierarchical variable selection
• Latent variable graphical model selection via convex optimization
• Smoothing proximal gradient method for general structured sparse regression
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Bregman Alternating Direction Method of Multipliers
• Fast L1-Minimization Algorithms For Robust Face Recognition
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• Parallel Multi-Block ADMM with o(1/k) Convergence
• Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian

Cited by in corpus (2)

• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Distributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints