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
Share

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.

Back to Research
  • 44 minutes
  • Huy Nguyen, Khang Le, Quang Nguyen, Nhat Ho, Tung Pham, Hung Bui

  • NeurIPS 2021
Share

Related publications