# An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Scalable Unbalanced Optimal Transport using Generative Adversarial Networks](https://mlsanity.com/paper/1810.11447/) (2018)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization](https://mlsanity.com/paper/1808.03045/) (2018)
- [Spatio-Temporal Alignments: Optimal transport through space and time](https://mlsanity.com/paper/1910.03860/) (2019)
- [Parallel Unbalanced Optimal Transport Regularization for Large Scale Imaging Problems](https://mlsanity.com/paper/1909.00149/) (2019)
- [Bregman Proximal Point Algorithm Revisited: A New Inexact Version and its Inertial Variant](https://mlsanity.com/paper/2105.10370/) (2021)
- [Convex Color Image Segmentation with Optimal Transport Distances](https://mlsanity.com/paper/1503.01986/) (2015)
- [An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems](https://mlsanity.com/paper/2011.14312/) (2020)
- [Bregman Augmented Lagrangian and Its Acceleration](https://mlsanity.com/paper/2002.06315/) (2020)

## Abstract (arXiv)

The Unbalanced Optimal Transport (UOT) problem plays increasingly important roles in computational biology, computational imaging and deep learning. Scaling algorithm is widely used to solve UOT due to its convenience and good convergence properties. However, this algorithm has lower accuracy for large regularization parameters, and due to stability issues, small regularization parameters can easily lead to numerical overflow. We address this challenge by developing an inexact Bregman proximal point method for solving UOT. This algorithm approximates the proximal operator using the Scaling algorithm at each iteration. The algorithm (1) converges to the true solution of UOT, (2) has theoretical guarantees and robust regularization parameter selection, (3) mitigates numerical stability issues, and (4) can achieve comparable computational complexity to the Scaling algorithm in specific practice. Building upon this, we develop an accelerated version of inexact Bregman proximal point method for solving UOT by using acceleration techniques of Bregman proximal point method and provide theoretical guarantees and experimental validation of convergence and acceleration.