Source-linked AI summary
Convergence of multi-block Bregman ADMM for nonconvex composite problems
Fenghui Wang, Wenfei Cao, Zongben Xu
TL;DR
Nonconvex multi-block ADMM lacks a sufficiently general convergence theory despite its broad use. This paper introduces a Bregman 3-block ADMM, extends the analysis to N ≥ 3 blocks, and proves convergence under structured assumptions, including subanalyticity and full-row-rank conditions.
Problem
Nonconvex multi-block ADMM is widely used, but its convergence analysis is difficult because Fejér monotonicity of iterates can fail.
Method
The paper proposes a Bregman modification of 3-block ADMM and extends the convergence analysis to N-block problems.
Results
The generated sequence converges to a stationary point of the augmented Lagrangian under the stated assumptions.
Takeaways & Limitations
The results support convergence of Bregman multi-block ADMM for a family of nonconvex problems under the paper’s assumptions.
Takeaways & Limitations
The convergence guarantee depends on assumptions including strong convexity, Lipschitz continuity, subanalyticity, and full-row-rank structure.
Abstract
from arXiv · showhide
The alternating direction method with multipliers (ADMM) has been one of most powerful and successful methods for solving various composite problems. The convergence of the conventional ADMM (i.e., 2-block) for convex objective functions has been justified for a long time, and its convergence for nonconvex objective functions has, however, been established very recently. The multi-block ADMM, a natural extension of ADMM, is a widely used scheme and has also been found very useful in solving various nonconvex optimization problems. It is thus expected to establish convergence theory of the multi-block ADMM under nonconvex frameworks. In this paper we present a Bregman modification of 3-block ADMM and establish its convergence for a large family of nonconvex functions. We further extend the convergence results to the $N$-block case ($N \geq 3$), which underlines the feasibility of multi-block ADMM applications in nonconvex settings. Finally, we present a simulation study and a real-world application to support the correctness of the obtained theoretical assertions.
1. Introduction
The paper studies convergence of multi-block ADMM for nonconvex composite optimization, focusing on a Bregman modification of the 3-block method and its extension to N blocks. It addresses the difficulty that 3-block ADMM can fail to converge without restrictive conditions.
- Multi-block composite problems arise in signal and image processing and machine learning under linear equality constraints.
- The study begins with three blocks and generalizes the convergence results to multiple blocks.
- Unlike 2-block ADMM, 3-block ADMM is not necessarily convergent even for convex objectives.
- Existing semi-proximal 3-block ADMM convergence requires convex objectives and at least one strongly convex function.
- The proposed 3-block Bregman ADMM adds Bregman distances to the block updates and targets nonconvex optimization.
- Under subanalytic objectives and full-row-rank matrix C, the 3-block Bregman ADMM is shown to converge.
2. Preliminaries
The preliminaries define the nonsmooth analysis, K-L framework, subanalytic functions, and Bregman distances used in the convergence theory. They also state assumptions linking strong convexity, Lipschitz continuity, full-row rank, and subanalyticity to descent and global convergence.
- Subdifferentials: The limiting subdifferential supports the paper’s stationarity notion, with stationary points satisfying 0 ∈ ∂f(x).
- Subdifferentials: A stationary point of the augmented Lagrangian satisfies blockwise subdifferential or gradient conditions together with primal feasibility.
- Kurdyka-Łojasiewicz inequality: The K-L inequality is introduced for proper lower semicontinuous functions and extended through a compact-subset formulation.
- Kurdyka-Łojasiewicz inequality: Strongly convex, real analytic, semi-algebraic, and subanalytic functions are identified as typical K-L functions.
- Bregman distance: Bregman distance generalizes squared Euclidean distance but need not satisfy symmetry or the triangle inequality.
- Basic assumptions: The assumptions require Lipschitz gradients, paired strong convexity across objectives or Bregman generators, full-row-rank C, and subanalytic f + g + h.
3. Convergence Analysis
The paper establishes convergence of a 3-block Bregman ADMM under nonconvex assumptions and extends the result to N-block problems. The analysis uses boundedness, descent, asymptotic regularity, and the KŁ framework to show convergence to stationary points.
- 3. Convergence Analysis: The analysis first establishes descent and boundedness properties for the 3-block BADMM iterates under stated assumptions.The proof introduces an augmented function and derives boundedness of the primal, multiplier, and auxiliary sequences.
- 3. Convergence Analysis: The BADMM sequence is asymptotically regular, with successive-iterate differences tending to zero, and every cluster point is stationary.These properties follow from the boundedness assumption and the auxiliary lemmas used in the convergence proof.
- 3. Convergence Analysis: Under conditions including lower-bounded objectives, coercivity, and a sufficiently large penalty parameter, the auxiliary sequence is bounded.The listed conditions include either coercivity of a modified third-block objective or a square constraint matrix.
- 3. Convergence Analysis: The resulting 3-block BADMM sequence converges to a stationary point of the augmented Lagrangian.This conclusion combines the boundedness result with the preceding convergence theorem.
- N-block extension: The convergence result is extended to N-block BADMM, with a corresponding theorem covering the multi-block procedure and a two-block specialization.The N-block theorem states convergence to a stationary point under its stated assumptions; the two-block case reduces to conventional BADMM.
4. Demonstration examples
The paper applies 3-block Bregman ADMM to a nonconvex matrix-decomposition model, then evaluates convergence through simulations and background-subtraction video experiments.
- Model and algorithm: The model decomposes an observed matrix into low-rank, sparse, and ideal-observation components while incorporating a noise-level parameter.The spectral sparsity, elementwise sparsity, and noise terms are controlled by λ and µ.
- Model and algorithm: The authors derive closed-form BADMM iterations using singular-value soft shrinkage and entrywise half shrinkage.These operations specify the BADMM procedure for the matrix-decomposition problem.
- Theoretical basis: The model satisfies the assumptions of Theorem 3.8, which predicts convergence of the proposed procedure.The paper then uses simulations and an application to support this theoretical assertion.
- Simulation study: The simulation generates observations as M = L + S + N and measures recovery using relative error and relative change.The experiments include both noiseless and Gaussian-noise settings.
- Simulation study: The relative-error and relative-change curves indicate that procedure (46) converges under the stated initialization, with and without Gaussian noise.The noisy case uses Gaussian noise with variance σ2 = 0.22.
- Application example: In background subtraction, BADMM produces a clean video background while detecting a satisfactory foreground across four video clips.The application uses 600 frames from each of Lobby, Bootstrap, Hall, and ShoppingMall.