Tree-Sliced Variants of Wasserstein Distances

Optimal transport (OT) theory provides a useful set of tools to compare probability distributions. As a consequence, the field of OT is gaining traction and interest within the machine learning community. A few deficiencies usually associated with OT include its high computational complexity when comparing discrete measures, which is quadratic when approximating it through entropic regularization; or supercubic when solving it exactly. For some applications, the fact that OT distances are not usually negative definite also means that they cannot be used with usual Hilbertian tools. In this work, we consider a particular family of ground metrics, namely tree metrics, which yield negative definite OT metrics that can be computed in linear time. By averaging over randomly sampled tree metrics, we obtain a tree-sliced-Wasserstein distance. We illustrate that the proposed tree-sliced-Wasserstein distances compare favorably with other baselines on various benchmark datasets.

• Algorithms and Theory

• Machine Intelligence