Source-linked AI summary
Parallel Multi-Block ADMM with o(1/k) Convergence
Wei Deng, Ming-Jun Lai, Zhimin Peng, Wotao Yin
TL;DR
The paper addresses parallelization of ADMM for problems with separable structures, where schemes may diverge or need further improvement. It proposes a simpler parallel and distributed method and establishes convergence at an o(1/k) rate, with competitive performance reported.
Problem
Parallelization of ADMM for N-block problems needs further investigation because the algorithm may not converge for N ≥3 and parallel schemes are more likely to diverge.
Method
The paper proposes a simpler parallel and distributed ADMM for separable problems, using proximal terms such as Pi = τiI with τi > 0 for the xi-subproblems.
Results
The proposed algorithm achieves global convergence at a rate of o(1/k) and competitive performance in comparison with existing parallel algorithms.
Takeaways & Limitations
The method offers a parallel and distributed approach with easy coding, fast computation, and an established o(1/k) convergence rate.
Takeaways & Limitations
Convergence remains a concern for some parallel schemes, particularly when N ≥3, and parallelization can make divergence more likely.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper targets separable convex optimization with parallel and distributed ADMM, addressing limitations of sequential and variable-splitting approaches. It proposes Jacobian variants with convergence guarantees, flexible proximal subproblems, and improved convergence rates.
- Problem setting: Separable objectives and constraints decompose the problem into N smaller subproblems solvable in parallel and distributed fashion.
- Jacobian scheme: Jacobian ADMM updates all N blocks in parallel, but can diverge even in the two-block case without additional assumptions or modifications.
- Existing approaches: Variable-splitting ADMM enables parallel x_i updates but substantially increases variables and constraints, especially when N is large.
- Existing approaches: Gauss-Seidel ADMM updates blocks sequentially, limiting parallelization, and may fail to converge for N ≥3.
- Convergence guarantees: If the matrices A_i are mutually near-orthogonal and full column-rank, Jacobian ADMM converges globally; general cases require proximal variants.
- Proximal Jacobian ADMM: Proximal Jacobian ADMM achieves global convergence at o(1/k), stabilizes non-strictly convex subproblems, and permits multiple easier-to-solve proximal designs.
2. Convergence Analysis of the Proximal Jacobian ADMM.
The analysis establishes convergence of Proximal Jacobian ADMM under parameter conditions and derives an o(1/k) rate. It also proves convergence for adaptive parameter tuning and motivates practical adjustments that can accelerate convergence.
- Rate of Convergence: The method achieves an o(1/k) convergence rate, including o(1/k) decay for G′x and successive dual-variable differences.
- Parameter Conditions: Standard proximal and prox-linear choices impose different sufficient parameter conditions, including τ_i > ρ and τ_i > ρN, respectively.
- Convergence: The iterative sequence is strictly contractive, while the associated quantity G is monotonically non-increasing and convergent.
- Convergence: Proximal Jacobian ADMM converges to a solution of problem (1.1) when its parameters satisfy condition (2.8).
- Adaptive Parameter Tuning: The adaptive strategy can use the exactly computed h(u^k,u^{k+1}), typically produces smaller proximal matrices, and leads to substantially faster practical convergence.
- Adaptive Parameter Tuning: Adaptive tuning adjusts proximal matrices until the convergence condition holds, after which the matrices remain constant and convergence follows.
3. Numerical Experiments.
The experiments compare Prox-JADMM with VSADMM, Corr-JADMM, and YALL1 on exchange and ℓ1-minimization problems, including distributed large-scale instances. Prox-JADMM is fastest in the exchange test, while Prox-JADMM and Corr-JADMM are fastest on the ℓ1 test and Jacobian ADMM is efficient at low accuracy on very large problems.
- Experimental setup: Prox-JADMM adds a proximal term and uses P_i = τ_iI, making each x_i-subproblem a efficiently computable quadratic program.The proximal parameters are adaptively updated during the experiments.
- Exchange problem: Prox-JADMM is clearly the fastest algorithm in the exchange-problem comparison averaged over 100 random trials.The test uses n = 100, N = 100, p = 80 and runs all algorithms for 200 iterations.
- ℓ1-minimization: Prox-JADMM and Corr-JADMM achieve very close performance and are the fastest compared algorithms on the ℓ1-problem experiments.The results average 100 random trials with n = 1000, m = 300, k = 60, and noise standard deviations σ = 0 and 10^-3; YALL1 is also competitive.
- ℓ1-minimization: VSADMM is far slower than the other methods, probably because of inexact subproblem minimization and conservative proximal parameters.The experiments use prox-linear subproblem solutions for VSADMM, whereas Corr-JADMM computes scalar subproblems exactly.
- Distributed large-scale ℓ1-minimization: Jacobian ADMM is very efficient for obtaining relatively low accuracy, which is usually sufficient for large-scale problems.The paper reports distributed C/MPI experiments on Amazon EC2 for very large ℓ1-minimization instances that exceed single-workstation capacity.
4. A Sufficient Condition for Convergence of Jacobian ADMM.
This section establishes sufficient convergence conditions for Jacobian ADMM and Proximal Jacobian ADMM. The conditions rely on properties of the coefficient matrices, especially mutual near-orthogonality, and Proximal Jacobian ADMM converges under the stated condition.
- Jacobian ADMM: A sufficient condition guarantees convergence of the sequence generated by Jacobian ADMM to a solution of problem (1.1).The proof analyzes contraction under a suitable G-norm.
- Jacobian ADMM: The condition depends only on the coefficient matrices A_i and imposes no further assumptions on the objective functions f_i or penalty parameter ρ.The convergence proof establishes primal convergence and then verifies the KKT conditions for a limit point.
- Jacobian ADMM: The proposed condition assumes that the matrices A_i are mutually near-orthogonal rather than exactly orthogonal.This extends a special N = 3 result that assumed exact orthogonality for two coefficient matrices.
- Proximal Jacobian ADMM: Under a similar near-orthogonality assumption, Proximal Jacobian ADMM converges to a solution of problem (1.1).The result applies to Algorithm 4 with proximal terms satisfying the stated sufficient inequalities.
5. On o(1/k) Convergence Rate of ADMM.
The section revisits the standard two-block ADMM convergence analysis and improves the established O(1/k) rate to o(1/k). The same elementary technique can also improve some other existing ADMM rates.
- Optimality measure: The quantity ∥w^k − w^{k+1}∥_H measures the distance between an ADMM iteration and the solution set.The paper relates this quantity to the optimality conditions and the variational characterization of ADMM iterations.
- Rate improvement: The H-based optimality measure for standard ADMM converges to zero at rate O(1/k).This rate is the starting point for the section's rate improvement.
- Two-block ADMM: The sequence generated by two-block ADMM converges to a solution in the H-norm.The proof uses the sequence's contractive property and standard contraction-method analysis.
- Rate improvement: The same technique can improve some other existing O(1/k) convergence rates to o(1/k).The paper specifically identifies rates associated with prior results.
6. Conclusion.
The paper addresses the need for improved parallelization of ADMM by proposing a simpler parallel and distributed framework for separable problems. It establishes global convergence and an o(1/k) rate, with numerical evidence of efficiency and faster practical convergence through parameter tuning.
- Motivation: The paper targets further investigation and improvement of ADMM parallelization for large-scale distributed computing.ADMM is described as effective for large-scale problems and well suited for distributed computing.
- Contributions: The proposed framework is a simpler parallel and distributed ADMM for problems with separable structures.Its subproblem computation is made more flexible through appropriately chosen proximal matrices P_i.
- Theoretical results: The framework has established global convergence and an o(1/k) convergence rate.The conclusion also reports a simple improvement from standard ADMM's O(1/k) rate to o(1/k).
- Numerical results: Numerical results demonstrate the proposed method's efficiency compared with several existing parallel algorithms.The experiments include exchange and ℓ1-minimization problems.