An inexact Bregman proximal point method and its acceleration version for unbalanced optimal transport
This work addresses numerical stability and accuracy issues in UOT algorithms, which is incremental for applications in computational biology, imaging, and deep learning.
The paper tackles the Unbalanced Optimal Transport (UOT) problem, which is important in fields like computational biology and deep learning, by developing an inexact Bregman proximal point method and its accelerated version to improve accuracy and numerical stability compared to the Scaling algorithm, achieving comparable computational complexity in practice.
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.