September 28, 2021 Machine Learning
On robust optimal transport: Computational complexity and barycenter computation
44 minutes
Huy Nguyen, Khang Le, Quang Nguyen, Nhat Ho, Tung Pham, Hung Bui
NeurIPS 2021
Abstract
We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibler divergence. We show that Sinkhorn-based algorithms can approximate the optimal cost of robust optimal transport in O(n2/epsilon) time, in which n is the number of supports of the probability distributions and epsilon is the desired error. Furthermore, we investigate a fixed-support robust barycenter problem between m discrete probability distributions with at most n number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case m = 2, we show that this algorithm can approximate the optimal barycenter value in O(mn2/epsilon) time, thus being better than the previous complexity O(mn2/epsilon2) of the IBP algorithm for approximating the Wasserstein barycenter.
44 minutes
Huy Nguyen, Khang Le, Quang Nguyen, Nhat Ho, Tung Pham, Hung Bui
NeurIPS 2021