# Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2015.

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

- [Preconditioners for the Stochastic Training of Neural Fields](https://mlsanity.com/paper/2402.08784/) (2024)
- [Adapting to Dynamic LEO-B5G Systems: Meta-Critic Learning Based Efficient Resource Scheduling](https://mlsanity.com/paper/2110.06787/) (2021)
- [Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems](https://mlsanity.com/paper/2408.15969/) (2024)

## Abstract (arXiv)

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of N (N≥ 3) convex functions with N block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we present convergence and convergence rate results for the multi-block ADMM applied to solve certain N-block (N≥ 3) convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an ε-optimal solution within O(1/ε2) iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an ε-optimal solution within O(1/ε) iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz property, which essentially covers most convex optimization models except for some pathological cases.