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

arXiv: https://arxiv.org/abs/1312.3040 · HTML: https://mlsanity.com/paper/1312.3040/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2013.

## Built on by (most cited first, 12 of 12)

- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [Multimodal Remote Sensing Benchmark Datasets for Land Cover Classification with A Shared and Specific Feature Learning Model](https://mlsanity.com/paper/2105.10196/) (2021)
- [Graph Denoising with Framelet Regularizer](https://mlsanity.com/paper/2111.03264/) (2021)
- [Sign-regularized Multi-task Learning](https://mlsanity.com/paper/2102.11191/) (2021)
- [Communication Efficient Federated Learning via Ordered ADMM in a Fully Decentralized Setting](https://mlsanity.com/paper/2202.02580/) (2022)
- [GenCP: Towards Generative Modeling Paradigm of Coupled Physics](https://mlsanity.com/paper/2601.19541/) (2026)
- [A Convergent ADMM Framework for Efficient Neural Network Training](https://mlsanity.com/paper/2112.11619/) (2021)
- [FDR-SVM: A Federated Distributionally Robust Support Vector Machine via a Mixture of Wasserstein Balls Ambiguity Set](https://mlsanity.com/paper/2410.03877/) (2024)
- [Towards Quantized Model Parallelism for Graph-Augmented MLPs Based on Gradient-Free ADMM Framework](https://mlsanity.com/paper/2105.09837/) (2021)
- [Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems](https://mlsanity.com/paper/2408.15969/) (2024)
- [On the Relationship Between CoCoA and ADMM for Distributed Empirical Risk Minimization](https://mlsanity.com/paper/2502.00470/) (2025)
- [Parallel Algorithms for Structured Sparse Support Vector Machines: Application in Music Genre Classification](https://mlsanity.com/paper/2512.07463/) (2025)

## Abstract (arXiv)

This paper introduces a parallel and distributed extension to the alternating direction method of multipliers (ADMM) for solving convex problem: minimize sumi=1N fi(xi) subject to sumi=1N Ai xi=c, xi∈ Xi. 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 Ai are mutually near-orthogonal and have full column-rank. Secondly, for general matrices Ai, 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.