Semi-dual Regularized Optimal Transport

Abstract

Variational problems that involve Wasserstein distances and more generally optimal transport (OT) theory are playing an increasingly important role in data sciences. Such problems can be used to form an examplar measure out of various probability measures, as in the Wasserstein barycenter problem, or to carry out parametric inference and density fitting, where the loss is measured in terms of an optimal transport cost to the measure of observations. Despite being conceptually simple, such problems are computationally challenging because they involve minimizing over quantities (Wasserstein distances) that are themselves hard to compute. Entropic regularization has recently emerged as an efficient tool to approximate the solution of such variational Wasserstein problems. In this paper, we give a thorough duality tour of these regularization techniques. In particular, we show how important concepts from classical OT such as c-transforms and semi-discrete approaches translate into similar ideas in a regularized setting. These dual formulations lead to smooth variational problems, which can be solved using smooth, differentiable and convex optimization problems that are simpler to implement and numerically more stable that their un-regularized counterparts. We illustrate the versatility of this approach by applying it to the computation of Wasserstein barycenters and gradient flows of spatial regularization functionals.

References in corpus (8)

• Fast Computation of Wasserstein Barycenters
• Stochastic Optimization for Large-scale Optimal Transport
• Imaging with Kantorovich-Rubinstein discrepancy
• Computational Optimal Transport
• Robust and Scalable Bayes via a Median of Subset Posterior Measures
• Stochastic Wasserstein Barycenters
• On the symmetrical Kullback-Leibler Jeffreys centroids
• A numerical algorithm for $L_2$ semi-discrete optimal transport in 3D

Cited by in corpus (9)

• Entropic regularization of continuous optimal transport problems
• On the Complexity of Approximating Multimarginal Optimal Transport
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• Positive and free energy satisfying schemes for diffusion with interaction potentials
• Sinkhorn EM: An Expectation-Maximization algorithm based on entropic optimal transport
• A contribution to Optimal Transport on incomparable spaces
• Geometric Losses for Distributional Learning
• Randomized Stochastic Gradient Descent Ascent
• Variational Wasserstein Barycenters with c-Cyclical Monotonicity