Timezone: »

 
Poster
On Robust Optimal Transport: Computational Complexity and Barycenter Computation
Khang Le · Huy Nguyen · Quang M Nguyen · Tung Pham · Hung Bui · Nhat Ho

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
in Poster Session 3 »
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 $\widetilde{\mathcal{O}}(\frac{n^2}{\varepsilon})$ time, in which $n$ is the number of supports of the probability distributions and $\varepsilon$ 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 $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon})$ time, thus being better than the previous complexity $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon^2})$ of the IBP algorithm for approximating the Wasserstein barycenter.
Keywords: Optimization · Robustness · Optimal Transport

Author Information

Khang Le (VinAI Research, Vietnam)
Huy Nguyen (Vinai Artificial Intelligence Application and Research JSC)
Quang M Nguyen (Massachusetts Institute of Technology)
Tung Pham (Vietnam National University)
Hung Bui (Google DeepMind)
Nhat Ho (University of Texas at Austin)

More from the Same Authors