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/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.

• Publication year

  2013

• Venue

  Neural Information Processing Systems

• Publication date

  2013-06-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1306.3203
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

  2016influential reference
• Fast Alternating Direction Optimization Methods

  2014cited by this paper
• Bethe-ADMM for Tree Decomposition based Parallel MAP Inference

  2013influential reference
• Agglomerative Bregman Clustering

  2012cited by this paper
• On the linear convergence of the alternating direction method of multipliers

  2012cited by this paper
• Online Alternating Direction Method

  2012cited by this paper
• On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method

  2012cited by this paper
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

  2011cited by this paper
• Composite objective mirror descent

  2010influential reference
• Sparse Inverse Covariance Selection via Alternating Linearization Methods

  2010cited by this paper
• Restoration of Poissonian Images Using Alternating Direction Optimization

  2010cited by this paper
• Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction

  2010cited by this paper
• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

  2010cited by this paper
• Proximal Splitting Methods in Signal Processing

  2009cited by this paper
• Alternating Direction Algorithms for 1-Problems in Compressive Sensing

  2009cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition by Trevor Hastie, Robert Tibshirani, Jerome Friedman

  2009cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• Efficient projections onto the l1-ball for learning in high dimensions

  2008influential reference
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• Learning Permutations with Exponential Weights

  2007cited by this paper
• Doubly Stochastic Normalization for Spectral Clustering

  2006cited by this paper
• Clustering with Bregman Divergences

  2005cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2004cited by this paper
• Mirror descent and nonlinear projected subgradient methods for convex optimization

  2003cited by this paper
• The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography

  2001cited by this paper
• Parallel Optimization: Theory, Algorithms and Applications

  2000cited by this paper
• Exponentiated Gradient Versus Gradient Descent for Linear Predictors

  1997cited by this paper
• Parallel Optimization:theory

  1997cited by this paper
• Proximal Minimization Methods with Generalized Bregman Functions

  1997cited by this paper
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions

  1993cited by this paper
• Applications of the method of multipliers to variational inequalities

  1983cited by this paper
• Problem Complexity and Method Efficiency in Optimization

  1983cited by this paper
• Concerning nonnegative matrices and doubly stochastic matrices

  1967cited by this paper
• The Hungarian method for the assignment problem

  1955cited by this paper
• The Distribution of a Product from Several Sources to Numerous Localities

  1941cited by this paper

• A Proximal-Perturbed Bregman ADMM for Solving Nonsmooth and Nonconvex Composite Optimization

  2026influential citation
• Synthesis of model predictive control and reinforcement learning: Survey and classification

  2026cites this paper
• QoS-Oriented Joint Resource and Trajectory Optimization in NOMA-Enhanced AAV-MEC Systems

  2025cites this paper
• An ADMM-inspired Algorithm for Sensor Selection and Scheduling with Routing Constraints

  2025cites this paper
• Capacity Optimizing Resource Allocation in Joint Source-Channel Coding Systems With QoS Constraints

  2025cites this paper
• Structure-Preserving Counterfactual Regression for Personalized Consumer-Electronics Service Networks

  2025cites this paper
• Perturbed Proximal Gradient ADMM for Nonconvex Composite Optimization

  2025cites this paper
• Bregman ADMM: A new algorithm for nonconvex optimization with linear constraints

  2025cites this paper
• Bregman Douglas-Rachford Splitting Method

  2025influential citation
• LAGO: Few-shot Crosslingual Embedding Inversion Attacks via Language Similarity-Aware Graph Optimization

  2025cites this paper
• FedGF: Enhancing Structural Knowledge via Graph Factorization for Federated Graph Learning

  2025cites this paper
• A Partially Feasible Jacobi-Type Distributed SQO Method for Two-Block General Linearly Constrained Smooth Optimization

  2025influential citation
• An Unbalanced Optimal Transport-Based Approach for Robust Dictionary Learning

  2025cites this paper
• Synthesis of Model Predictive Control and Reinforcement Learning: Survey and Classification

  2025cites this paper
• Federated ADMM from Bayesian Duality

  2025influential citation
• A single-loop proximal-conditional-gradient penalty method

  2024influential citation
• Operator Splitting Covariance Steering for Safe Stochastic Nonlinear Control

  2024cites this paper
• Speckle Noise Removal: A Local Structure Preserving Approach

  2024influential citation
• Low-tubal-rank tensor completion via local and nonlocal knowledge

  2024cites this paper
• An Inverse Partial Optimal Transport Framework for Music-guided Trailer Generation

  2024cites this paper
• Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by a Difference of Functions

  2024influential citation
• Consensus Planning with Primal, Dual, and Proximal Agents

  2024cites this paper
• Self-supervised Video Summarization Guided by Semantic Inverse Optimal Transport

  2023cites this paper
• Group Sparse Optimal Transport for Sparse Process Flexibility Design

  2023cites this paper
• Computing Wasserstein Barycenter via operator splitting: the method of averaged marginals

  2023cites this paper
• Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications

  2023cites this paper
• Machine Learning Meets Advanced Robotic Manipulation

  2023cites this paper
• Decentralized Entropic Optimal Transport for Privacy-preserving Distributed Distribution Comparison

  2023influential citation
• Efficient MP Decoding via Fast G-BADMM Approach for Binary LDPC Codes

  2023cites this paper
• A Bregman-style Partially Symmetric Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization

  2023cites this paper
• Joint Internal Multi-Interest Exploration and External Domain Alignment for Cross Domain Sequential Recommendation

  2023cites this paper
• A Quasi-Wasserstein Loss for Learning Graph Neural Networks

  2023influential citation
• A Linearly Convergent Douglas-Rachford Splitting Solver for Markovian Information-Theoretic Optimization Problems

  2022cites this paper
• EVM Mitigation With PAPR and ACLR Constraints in Large-Scale MIMO-OFDM Using TOP-ADMM

  2022influential citation
• Multisource single‐cell data integration by MAW barycenter for Gaussian mixture models

  2022cites this paper
• Hilbert Curve Projection Distance for Distribution Comparison

  2022cites this paper
• Towards Compositional Adversarial Robustness: Generalizing Adversarial Training to Composite Semantic Perturbations

  2022cites this paper
• An Energy Management System for microgrids including costs, exergy, and stress indexes

  2022cites this paper
• A semismooth Newton-proximal method of multipliers for 𝓁1-regularized convex quadratic programming

  2022cites this paper
• Spectral Ranking Regression

  2022cites this paper
• A Practical Distributed ADMM Solver for Billion-Scale Generalized Assignment Problems

  2022influential citation
• Revisiting Pooling through the Lens of Optimal Transport

  2022influential citation
• Deep Whole-Body Control: Learning a Unified Policy for Manipulation and Locomotion

  2022cites this paper
• Federated Learning Using Three-Operator ADMM

  2022cites this paper
• Differentiable Hierarchical Optimal Transport for Robust Multi-View Learning

  2022cites this paper
• Revisiting Global Pooling through the Lens of Optimal Transport

  2022influential citation
• Weakly-Supervised Temporal Action Alignment Driven by Unbalanced Spectral Fused Gromov-Wasserstein Distance

  2022influential citation
• Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing

  2022cites this paper
• Gromov-Wasserstein Multi-modal Alignment and Clustering

  2022cites this paper
• Stochastic Mirror Descent for Convex Optimization with Consensus Constraints

  2022cites this paper
• Convergence of Bregman Peaceman–Rachford Splitting Method for Nonconvex Nonseparable Optimization

  2022cites this paper
• Regularized Optimal Transport Layers for Generalized Global Pooling Operations

  2022influential citation
• Representing Graphs via Gromov-Wasserstein Factorization

  2022influential citation
• Hawkes Processes on Graphons

  2021cites this paper
• A Provably Convergent Information Bottleneck Solution via ADMM

  2021cites this paper
• New Bregman proximal type algorithms for solving DC optimization problems

  2021cites this paper
• Deep Spectral Ranking

  2021cites this paper
• Proportional-Integral Projected Gradient Method for Conic Optimization

  2021cites this paper
• Bregman Methods for Large-Scale Optimisation with Applications in Imaging

  2021cites this paper
• Efficient Robot Skills Learning with Weighted Near-Optimal Experiences Policy Optimization

  2021cites this paper
• Rate-optimal robust estimation of high-dimensional vector autoregressive models

  2021cites this paper
• Guided Policy Search Methods: A Review

  2021cites this paper
• An inexact PAM method for computing Wasserstein barycenter with unknown supports

  2021influential citation
• Denoising Score-Matching for Uncertainty Quantification in Inverse Problems

  2020cites this paper
• Bregman Augmented Lagrangian and Its Acceleration.

  2020cites this paper
• On the Convergence of Bregman ADMM With Variational Inequality

  2020cites this paper
• Learning Latent Features With Pairwise Penalties in Low-Rank Matrix Completion

  2020cites this paper
• Consensus reaching with heterogeneous user preferences, private input and privacy-preservation output

  2020cites this paper
• Graph-Based Non-Convex Low-Rank Regularization for Image Compression Artifact Reduction

  2020cites this paper
• Joint Estimation of Multiple Granger Graphical Models using Non-convex Penalties

  2020cites this paper
• Accelerated Hierarchical ADMM for Nonconvex Optimization in Multi-Agent Decision Making

  2020cites this paper
• Stochastic Optimal Control for Multivariable Dynamical Systems Using Expectation Maximization

  2020influential citation
• Deep Trajectory Prediction for Robotic Manipulation Under Unreliable Sensor Data

  2020cites this paper
• Integrated vehicle assignment and routing for system-optimal shared mobility planning with endogenous road congestion

  2020cites this paper
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths

  2020cites this paper
• Convergence for nonconvex ADMM, with applications to CT imaging

  2020cites this paper
• Improved Hierarchical ADMM for Nonconvex Cooperative Distributed Model Predictive Control

  2020cites this paper
• Hyperspectral-Multispectral Image Fusion with Weighted LASSO

  2020cites this paper
• Image Restoration Via Data-Dependent Proximal Averaged Optimization

  2020cites this paper
• Monotone Splitting Sequential Quadratic Optimization Algorithm with Applications in Electric Power Systems

  2020influential citation
• Heterogeneous Few-Shot Model Rectification With Semantic Mapping

  2020cites this paper
• Monotone Splitting Sequential Quadratic Optimization Algorithm with Applications in Electric Power Systems

  2020cites this paper
• Robust Stochastic Optimal Control for Multivariable Dynamical Systems Using Expectation Maximization

  2020cites this paper
• Alternating Direction Method of Multipliers for Quantization

  2020cites this paper
• Effects of underlying gene-regulation network structure on prediction accuracy in high-dimensional regression

  2020cites this paper
• Convergence and Applications of ADMM on the Multi-convex Problems

  2019cites this paper
• Many-isocenter optimization for robotic radiotherapy

  2019cites this paper
• GPU-based contact-aware trajectory optimization using a smooth force model

  2019cites this paper
• Spatial Homogeneity Pursuit of Regression Coefficients for Large Datasets

  2019cites this paper
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence

  2019influential citation
• Exploring Structural Sparsity of Deep Networks Via Inverse Scale Spaces

  2019cites this paper
• Stochastic Bregman Parallel Direction Method of Multipliers for Distributed Optimization

  2019influential citation
• Multi-convex Inequality-constrained Alternating Direction Method of Multipliers

  2019cites this paper
• Deep Learning for Learning Graph Representations

  2019influential citation
• A Submodular Feature-Aware Framework for Label Subset Selection in Extreme Classification Problems

  2019cites this paper
• Siamese Deep Dictionary Learning

  2019cites this paper
• Optimal Sequence and Performance for Desired User in Asynchronous CDMA System

  2019cites this paper
• O C ] 2 1 A ug 2 01 9 Mass-spring-damperNetworks for DistributedOptimization inNon-EuclideanSpaces

  2019cites this paper
• Fast Numerical Methods for Convex Problems with Optimal Transport Regularization

  2019cites this paper
• Gromov-Wasserstein Factorization Models for Graph Clustering

  2019influential citation