Bregman Alternating Direction Method of Multipliers

Abstract

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.

References in corpus (3)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
• Agglomerative Bregman Clustering

Cited by in corpus (38)

• End-to-End Training of Deep Visuomotor Policies
• Collective Robot Reinforcement Learning with Distributed Asynchronous Guided Policy Search
• Deep Reinforcement Learning based Optimal Control of Hot Water Systems
• Measuring Road Network Topology Vulnerability by Ricci Curvature
• Robust Linear Regression Analysis - A Greedy Approach
• Parallel Direction Method of Multipliers
• Generalized Dantzig Selector: Application to the k-support norm
• Robust Non-linear Regression: A Greedy Approach Employing Kernels with Application to Image Denoising
• Deep Learning for Learning Graph Representations
• New Bregman proximal type algorithms for solving DC optimization problems
• A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
• Gromov-Wasserstein Factorization Models for Graph Clustering
• Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support
• Bregman Augmented Lagrangian and Its Acceleration
• Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem
• D-MFVI: Distributed Mean Field Variational Inference using Bregman ADMM
• Improved Hierarchical ADMM for Nonconvex Cooperative Distributed Model Predictive Control
• Convergence for nonconvex ADMM, with applications to CT imaging
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Hyperspectral-Multispectral Image Fusion with Weighted LASSO
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• MOCCA: mirrored convex/concave optimization for nonconvex composite functions
• Wasserstein Autoencoders for Collaborative Filtering
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• Latent variable model selection for Gaussian conditional random fields
• Bregman Parallel Direction Method of Multipliers for Distributed Optimization via Mirror Averaging
• Mass-spring-damper Networks for Distributed Optimization in Non-Euclidean Spaces
• A Provably Convergent Information Bottleneck Solution via ADMM
• An inexact PAM method for computing Wasserstein barycenter with unknown supports
• Visualization of topology optimization designs with representative subset selection
• Optimal Sequence and Performance for Desired User in Asynchronous CDMA System
• Analysis Co-Sparse Coding for Energy Disaggregation
• Hawkes Processes on Graphons
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex Infimal Convolutions
• Privacy of Agents' Costs in Peer-to-Peer Distributed Optimization
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths
• Beyond Gradient Descent for Regularized Segmentation Losses