Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport

Estimating the Wasserstein distance between two measures living in high-dimensional spaces is a challenging task. Indeed, that problem suffers from the curse of dimensionality: a number of samples that is exponential in the dimension of the ambient space is required to obtain good approximations. Regularizing the optimal transport (OT) problem is therefore crucial to use Wasserstein distances in data sciences. One of the greatest achievements of the OT literature in recent years lies in regularity theory: one can prove under suitable hypothesis that the OT map between two measures is Lipschitz, or, equivalently when studying 2-Wasserstein distances, that the Brenier convex potential (whose gradient is the optimal map) is a smooth function. We work backwards, and adopt regularity as a regularization tool, to propose algorithms working on discrete measures that can recover nearly optimal transport maps that have small distortion, or, equivalently, nearly optimal Brenier potential that are strongly convex and smooth. These potentials and their gradient can be evaluated on the measures themselves, but, more generally, everywhere in the space by solving a QP at each evaluation. For univariate measures, we show that computing these potentials is equivalent to solving an isotonic regression problem under Lipschitz and strong monotonicity constraints. For multivariate measures the problem boils down to a non-convex QCQP problem. We show that this QCQP can be lifted a semidefinite program that is tight when the number of points is not large w.r.t. the dimension. Building on these two formulations we propose practical algorithms to estimate and evaluate these transport maps.

• Machine Intelligence