Source-linked AI summary
Bregman Alternating Direction Method of Multipliers
Huahua Wang, Arindam Banerjee
TL;DR
The paper addresses whether ADMM’s quadratic penalty can be replaced while retaining a useful convergence framework. It introduces BADMM, establishes global convergence and O(1/T) iteration complexity, and reports faster performance than ADMM and Gurobi in supported cases.
Problem
ADMM uses quadratic penalty terms, and convergence for ADMM with nonquadratic penalties was previously unproved, despite Bregman methods’ ability to exploit problem structure.
Method
BADMM replaces ADMM’s quadratic penalty terms with selectable Bregman divergences and provides a generalized framework encompassing several ADMM variants.
Results
BADMM has global convergence and O(1/T) iteration complexity, is faster than ADMM in some cases, and is several times faster than Gurobi for mass transportation linear programs.
Takeaways & Limitations
BADMM supports structure-aware updates, unified treatment of ADMM variants, and GPU-parallel computation for large mass transportation problems.
Takeaways & Limitations
For p > 2, the convergence proof requires a sufficiently small step size τ, though this restriction may not be needed in practice.
Abstract
from arXiv · showhide
The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit the structure of problems. BADMM provides a unified framework for ADMM and its variants, including generalized ADMM, inexact ADMM and Bethe ADMM. We establish the global convergence and the $O(1/T)$ iteration complexity for BADMM. In some cases, BADMM can be faster than ADMM by a factor of $O(n/\log(n))$. In solving the linear program of mass transportation problem, BADMM leads to massive parallelism and can easily run on GPU. BADMM is several times faster than highly optimized commercial software Gurobi.
1 Introduction
ADMM splits composite constrained optimization problems into alternating updates, but existing convergence theory and implementations rely on quadratic penalty terms. BADMM replaces those terms with Bregman divergences to exploit problem structure, unify ADMM variants, and support efficient large-scale computation.
- ADMM motivation: ADMM separates composite objectives into alternating x and z updates under an equality constraint.The framework accommodates convex, potentially nonsmooth functions with different structures and constraints.
- ADMM motivation: ADMM’s computational burden lies mainly in proximal x and z updates using quadratic penalty terms.Inexact, generalized, online, and Bethe ADMM modify these updates, but existing ADMM methods still use quadratic penalties.
- Motivation for BADMM: Bregman divergences can exploit problem structure and improve gradient-type methods, motivating their use in ADMM.Prior work reports benefits in tomography, clustering, exponential-family distributions, and constrained optimization.
- Open problem: Before this work, it was unknown whether ADMM’s quadratic penalty could be replaced by Bregman divergence despite established ADMM convergence results.The cited literature had no convergence proof for ADMM with nonquadratic penalty terms.
- BADMM contribution: BADMM replaces ADMM quadratic penalties with Bregman divergences and unifies ADMM, generalized ADMM, inexact ADMM, and Bethe ADMM.Suitable divergences can make x and z updates efficient, including mirror-descent or proximal-style updates.
- Computational impact: BADMM enables massive parallelism for mass transportation and runs efficiently on GPUs, outperforming highly optimized Gurobi on large linear programs.Gurobi failed to terminate on larger instances even with 86G memory, while BADMM used a 5G-memory GPU.
2 Bregman Alternating Direction Method of Multipliers
BADMM replaces ADMM’s quadratic penalty with Bregman divergences and extends the updates with additional, variable-specific divergences to improve solvability. The framework supports linearization and structure-matched updates, including exponentiated-gradient and parallel forms.
- Bregman ADMM: Bregman divergences are not necessarily convex in their second argument, so BADMM updates cannot be obtained by directly alternating minimization of one augmented Lagrangian.This particularly affects the z update, where Bφ(c − A x^{t+1}, Bz) need not be convex in z.
- Bregman ADMM: BADMM replaces ADMM’s quadratic penalty in the x and z updates with a Bregman divergence.The same divergence Bφ is shared by both updates in the basic formulation.
- Special cases: When f is linear and X is the unit simplex, choosing KL divergence yields exponentiated-gradient updates; applying this to both variables gives alternating exponentiated gradients.The paper identifies mass transportation as an application of this scenario.
- Generalized BADMM: Generalized BADMM adds separate Bregman proximal terms for the x and z updates, allowing different divergences and step sizes to make updates efficient.The additional divergences are variable-specific and can be selected to support efficient or closed-form updates.
- Efficient updates: Linearizing selected terms can produce practical update rules: linearizing smooth f with a quadratic proximal term gives a simple closed-form x update.Other cases linearize the quadratic augmentation or both the function and augmentation; linearizing the quadratic term can also yield separable parallel updates.
- Special cases: Bethe-ADMM appears as a special case, where the resulting Bethe entropy problem can be solved exactly by sum-product in linear time on a tree.This illustrates how a suitable divergence can exploit graph structure.
3 Convergence Analysis of BADMM
BADMM is globally convergent under stated convexity, existence, divergence, and step-size assumptions, with an O(1/T) ergodic convergence rate. In a simplex case using KL divergence, it can outperform ADMM by O(n/ln(n)).
- Assumptions: The analysis assumes closed, proper, convex functions, existence of an optimal solution, and a Bregman divergence generated by an α-strongly convex function.These conditions are stated as Assumption 1.
- Step-size conditions: For 0 < p ≤ 2, the step-size condition includes Euclidean and KL divergences; for p > 2, the proof requires a sufficiently small step size τ.The paper notes that whether τ = O(ρ) suffices for every p > 0 remains open under other proof techniques.
- Global convergence: BADMM globally converges to a KKT point when Assumption 1 and the Lemma 2 conditions hold.The residual R(t + 1) converges to zero, and the generated sequence converges to a KKT point.
- Convergence rate: BADMM establishes an O(1/T) convergence rate for the objective and constraint residual in an ergodic sense.The rate theorem considers BADMM iterates with y0 = 0 and KKT points satisfying the stated conditions.
- Comparison with ADMM: With constant step size, BADMM outperforms ADMM by O(n/ln(n)) in an ergodic sense.This comparison is stated for the discussed special case and constant step size.
4 Experimental Results
The experiments apply BADMM to the mass transportation linear program and compare it with ADMM and Gurobi. BADMM converges faster than ADMM and, in parallel GPU runs, is several times faster than Gurobi on large-scale problems.
- Mass transportation problem: The mass transportation problem is formulated as a linear program minimizing ⟨C, X⟩ subject to Xe = a, X^T e = b, and X ≥ 0.The cost matrix C defines the objective, and the formulation is also called the assignment problem.
- BADMM formulation: BADMM reformulates the problem with split variables constrained to two simplices and linked by X = Z.This enables separate simplex-constrained updates for the split variables.
- Implementation: BADMM updates have closed-form exponentiated-gradient solutions with O(mn) computation and parallelizable elementwise operations.Apart from a sum operation requiring O(log(n)), the updates consist of elementwise operations.
- BADMM versus ADMM: BADMM converges faster than ADMM for dimensions n = {1000, 2000, 4000}, including when its initial point is farther from the optimum.The comparisons examine residuals over runtime and iterations, plus objective value against log runtime.
- BADMM versus Gurobi: BADMM running in parallel on a Tesla M2070 GPU is several times faster than Gurobi and remains efficient with 5G memory on larger problems.Gurobi did not terminate for larger n even on the 86G server.
5 Conclusions
BADMM extends ADMM into a unified Bregman-divergence framework, with established convergence guarantees and favorable performance in some cases, including mass-transportation linear programs.
- BADMM unifies ADMM with generalized ADMM, inexact ADMM, and Bethe ADMM.
- BADMM has global convergence and O(1/T) iteration complexity.
- In some cases, BADMM is faster than ADMM by a factor of O(n/log(n)).
- For mass-transportation linear programs, BADMM can outperform highly optimized commercial software Gurobi.
A Convergence of BADMM with Time Varying Step Size
The time-varying-step-size analysis establishes convergence of BADMM under bounded dual iterates and specified step-size conditions, with an ergodic convergence-rate result for the objective and constraint residual.
- Under bounded dual iterates, the convergence theorem requires a sufficiently large step size.
- With the stated assumptions and step-size choices, the residual measure R(t + 1) converges to zero.
- The analysis derives convergence rates for the objective and constraint residual in an ergodic sense.
- The proof uses telescoping sums followed by division by T and Jensen’s inequality to obtain the rate bounds.