Handling Multiple Costs in Optimal Transport: Strong Duality and Efficient Computation.

We introduce an extension of the optimal transportation (OT) problem when multiple costs are involved. We consider a linear optimization problem which allows to choose locally among $N\geq 1$ cost functions in order to minimize the cost of transport, while making them contribute equally. When $N=1$, we recover the classical OT problem; for $N=2$ we are able to recover integral probability metrics defined by $\alpha$-H\"older functions, which includes the Dudley metric. We derive the dual formulation of the problem and show that strong duality holds under some mild assumptions. In the discrete case, as with regular OT, the problem can be solved with a linear program. We provide a faster, entropic regularized formulation of that problem. We validate our proposed approximation with experiments on real and synthetic datasets.