Bregman Alternating Direction Method of Multipliers

By Huahua Wang, Arindam Banerjee. 2013

222 citations recorded by the source corpus.

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/ln n) where n is the dimensionality. 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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Learning to Optimize Neural Nets (2017, positive): “The transition probability density p is the density of the random variable( x(t) + ∆x,Φ ({ x(i),∇f̂(x(i)), f̂(x(i)) }t+1 i=0 ))T given x(t), Φ ({ x(i),∇f̂(x(i)), f̂(x(i)) }t i=0 ) and ∆x, where f ∼ F .”
End-to-End Training of Deep Visuomotor Policies (2015, methodology): “We use BADMM [41] to adapt the trajectories to the policy, alternating between optimizing the policy to match the trajectories, and optimizing the trajectories to minimize cost and match the policy, such that at convergence, they have the same state distribution.”
Collective robot reinforcement learning with distributed asynchronous guided policy search (2016, methodology): “The constrained optimization is then solved using the Bregman ADMM algorithm [22], which augments the objective for both the local and global policies with Lagrange multipliers that keep them similar in terms of KL-divergence.”
Scaling Algorithms for Unbalanced Transport Problems (2016, methodology): “The most simple one is the proximal point algorithm [31], but most proximal splitting schemes have been extended to this setting, such as for instance ADMM [78], primal-dual schemes [23] and forward-backward [54].”
Rectify Heterogeneous Models with Semantic Mapping (2018, methodology): “Introducing an auxiliary variable Z and let Z = T , BADMM decomposes the complex constraint domain T into two parts, i.e., T ∈ T1 = {T1 = 1d21, T ≥ 0} and Z ∈ T2 = {Z>1 = 1d11, Z ≥ 0}.”
Parallel Direction Method of Multipliers (2014, background): “In the xjt -update (5), a Bregman divergence is addded so that exact PDMM and its inexact variants can be analyzed in an unified framework [23, 11].”
Generalized Dantzig Selector: Application to the k-support norm (2014, methodology): “In order to converge, the algorithm requires μ 2 to be larger than the spectral radius of AA, and the convergence rate is O(1/T ) according to Theorem 2 in [20].”
Kullback-Leibler Proximal Variational Inference (2015, methodology): “In addition, our proximal framework can also be used for distributed optimization in variational inference [26, 11].”
Heterogeneous Few-Shot Model Rectification With Semantic Mapping (2020, methodology): “Equipped with types of optimization strategy [27], [28], [54], OT aligns distributions between sets [16], [55], and has been successfully applied in various machine learning ﬁelds with both its objective measure or the learned transportation plan.”