Parallel Multi-Block ADMM with o(1/k) Convergence

Abstract

This paper introduces a parallel and distributed extension to the alternating direction method of multipliers (ADMM) for solving convex problem: minimize ${\sum }_{i=1}^N{f}_i(x_i)$ subject to ${\sum }_{i=1}^N{A}_i{x}_i=c,x_i\in {\mathcal{X}}_i$. The algorithm decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This Jacobian-type algorithm is well suited for distributed computing and is particularly attractive for solving certain large-scale problems. This paper introduces a few novel results. Firstly, it shows that extending ADMM straightforwardly from the classic Gauss-Seidel setting to the Jacobian setting, from 2 blocks to N blocks, will preserve convergence if matrices $A_i$ are mutually near-orthogonal and have full column-rank. Secondly, for general matrices $A_i$, this paper proposes to add proximal terms of different kinds to the N subproblems so that the subproblems can be solved in flexible and efficient ways and the algorithm converges globally at a rate of o(1/k). Thirdly, a simple technique is introduced to improve some existing convergence rates from O(1/k) to o(1/k). In practice, some conditions in our convergence theorems are conservative. Therefore, we introduce a strategy for dynamically tuning the parameters in the algorithm, leading to substantial acceleration of the convergence in practice. Numerical results are presented to demonstrate the efficiency of the proposed method in comparison with several existing parallel algorithms. We implemented our algorithm on Amazon EC2, an on-demand public computing cloud, and report its performance on very large-scale basis pursuit problems with distributed data.

The second version has a new title

Cited by in corpus (19)

• Fog-Assisted Operational Cost Reduction for Cloud Data Centers
• Analysis of Distributed ADMM Algorithm for Consensus Optimization in Presence of Node Error
• Parallel Direction Method of Multipliers
• On the Sublinear Convergence Rate of Multi-Block ADMM
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• Randomized Primal-Dual Proximal Block Coordinate Updates
• On the Global Linear Convergence of the ADMM with Multi-Block Variables
• A general inertial proximal point method for mixed variational inequality problem
• Practical Algorithms for Learning Near-Isometric Linear Embeddings
• A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization
• Online Distributed ADMM on Networks
• A Decentralized Multi-block ADMM for Demand-side Primary Frequency Control using Local Frequency Measurements
• Auxiliary Problem Principle of augmented Lagrangian with Varying Core Functions for Large-Scale Structured Convex Problems
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems
• $L^0$-regularized Variational Methods for Sparse Phase Retrieval
• A primal-dual fixed point algorithm for multi-block convex minimization
• Per-Block-Convex Data Modeling by Accelerated Stochastic Approximation
• Convergence analysis of variants of the averaged alternating modified reflections method