Bregman Alternating Direction Method of Multipliers
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.
Code (0)
등록된 구현이 없습니다.
Tasks
GPUMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Bregman Douglas-Rachford Splitting Method
In this paper, we propose the Bregman Douglas-Rachford splitting (BDRS) method and its variant Bregman Peaceman-Rachford splitting method for solving maximal monotone inclusion problem. We show that BDRS is equivalent to…
Adaptive Stochastic Alternating Direction Method of Multipliers
The Alternating Direction Method of Multipliers (ADMM) has been studied for years. The traditional ADMM algorithm needs to compute, at each iteration, an (empirical) expected loss function on all training examples, resul…
D-MFVI: Distributed Mean Field Variational Inference using Bregman ADMM
Bayesian models provide a framework for probabilistic modelling of complex datasets. However, many of such models are computationally demanding especially in the presence of large datasets. On the other hand, in sensor n…
parameter estimationVariational InferenceDistributed Pose Graph Optimization using the Splitting Method based on the Alternating Direction Method of Multipliers
Distributed optimization aims to leverage the local computation and communication capabilities of each agent to achieve a desired global objective. This paper addresses the distributed pose graph optimization (PGO) probl…
Distributed OptimizationIteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounte…