Timezone: »

 
Poster
On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
Khiem Pham · Khang Le · Nhat Ho · Tung Pham · Hung Bui

Wed Jul 15 05:00 AM -- 05:45 AM & Wed Jul 15 07:00 PM -- 07:45 PM (PDT) @
in Poster Session 21 »
We provide a computational complexity analysis for the Sinkhorn algorithm that solves the entropic regularized Unbalanced Optimal Transport (UOT) problem between two measures of possibly different masses with at most $n$ components. We show that the complexity of the Sinkhorn algorithm for finding an $\varepsilon$-approximate solution to the UOT problem is of order $\widetilde{\mathcal{O}}(n^2/ \varepsilon)$. To the best of our knowledge, this complexity is better than the best known complexity upper bound of the Sinkhorn algorithm for solving the Optimal Transport (OT) problem, which is of order $\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$. Our proof technique is based on the geometric convergence rate of the Sinkhorn updates to the optimal dual solution of the entropic regularized UOT problem and scaling properties of the primal solution. It is also different from the proof technique used to establish the complexity of the Sinkhorn algorithm for approximating the OT problem since the UOT solution does not need to meet the marginal constraints of the measures.
Keywords: Computational Learning Theory · Learning Theory

Author Information

Khiem Pham (VinAI Research, Vietnam)

Research Resident at Vinai Research, Vietnam. Looking for PhD positions Fall 2020.

Khang Le (VinAI Research, Vietnam)
Nhat Ho (University of California, Berkeley)
Tung Pham (VinAI Research; Vietnam National University, Hanoi)
Hung Bui (VinAI Research)

More from the Same Authors