# Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems

arXiv: https://arxiv.org/abs/2203.00802 · HTML: https://mlsanity.com/paper/2203.00802/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2022.

## Built on by (most cited first, 7 of 7)

- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems](https://mlsanity.com/paper/2212.07844/) (2022)
- [A Survey on Algorithmic Developments in Optimal Transport Problem with Applications](https://mlsanity.com/paper/2501.06247/) (2025)
- [Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm](https://mlsanity.com/paper/2210.16645/) (2022)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Decentralized and Equitable Optimal Transport](https://mlsanity.com/paper/2403.04259/) (2024)

## Abstract (arXiv)

This paper discusses the efficiency of Hybrid Primal-Dual (HPD) type algorithms to approximate solve discrete Optimal Transport (OT) and Wasserstein Barycenter (WB) problems, with and without entropic regularization. Our first contribution is an analysis showing that these methods yield state-of-the-art convergence rates, both theoretically and practically. Next, we extend the HPD algorithm with linesearch proposed by Malitsky and Pock in 2018 to the setting where the dual space has a Bregman divergence, and the dual function is relatively strongly convex to the Bregman's kernel. This extension yields a new method for OT and WB problems based on smoothing of the objective that also achieves state-of-the-art convergence rates. Finally, we introduce a new Bregman divergence based on a scaled entropy function that makes the algorithm numerically stable and reduces the smoothing, leading to sparse solutions of OT and WB problems. We complement our findings with numerical experiments and comparisons.