Regularity as Regularization: Smooth and Strongly Convex Brenier
  Potentials in Optimal Transport
  Estimating Wasserstein distances between two high-dimensional densities
suffers from the curse of dimensionality: one needs an exponential (wrt
dimension) number of samples to ensure that the distance between two empirical
measures is comparable to the distance between the original densities.
Therefore, optimal transport (OT) can only be used in machine learning if it is
substantially regularized. On the other hand, one of the greatest achievements
of the OT literature in recent years lies in regularity theory: Caffarelli
showed that the OT map between two well behaved measures is Lipschitz, or
equivalently when considering 2-Wasserstein distances, that Brenier convex
potentials (whose gradient yields an optimal map) are smooth. We propose in
this work to draw inspiration from this theory and use regularity as a
regularization tool. We give algorithms operating on two discrete measures that
can recover nearly optimal transport maps with small distortion, or
equivalently, nearly optimal Brenier potentials that are strongly convex and
smooth. The problem boils down to solving alternatively a convex QCQP and a
discrete OT problem, granting access to the values and gradients of the Brenier
potential not only on sampled points, but also out of sample at the cost of
solving a simpler QCQP for each evaluation. We propose algorithms to estimate
and evaluate transport maps with desired regularity properties, benchmark their
statistical performance, apply them to domain adaptation and visualize their
action on a color transfer task.
