Smooth and Sparse Optimal Transport

Abstract

Entropic regularization is quickly emerging as a new standard in optimal transport (OT). It enables to cast the OT computation as a differentiable and unconstrained convex optimization problem, which can be efficiently solved using the Sinkhorn algorithm. However, entropy keeps the transportation plan strictly positive and therefore completely dense, unlike unregularized OT. This lack of sparsity can be problematic in applications where the transportation plan itself is of interest. In this paper, we explore regularizing the primal and dual OT formulations with a strongly convex term, which corresponds to relaxing the dual and primal constraints with smooth approximations. We show how to incorporate squared $2$-norm and group lasso regularizations within that framework, leading to sparse and group-sparse transportation plans. On the theoretical side, we bound the approximation error introduced by regularizing the primal and dual formulations. Our results suggest that, for the regularized primal, the approximation error can often be smaller with squared $2$-norm than with entropic regularization. We showcase our proposed framework on the task of color transfer.

Accepted to AISTATS 2018

Cited by in corpus (32)

• On the regularization of Wasserstein GANs
• Large-Scale Optimal Transport and Mapping Estimation
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Efficient and Modular Implicit Differentiation
• Wasserstein Adversarial Imitation Learning
• 2-Wasserstein Approximation via Restricted Convex Potentials with Application to Improved Training for GANs
• Screening Sinkhorn Algorithm for Regularized Optimal Transport
• Learning with minibatch Wasserstein : asymptotic and gradient properties
• Minibatch optimal transport distances; analysis and applications
• Doubly Stochastic Subspace Clustering
• Adversarial Computation of Optimal Transport Maps
• Blind Source Separation with Optimal Transport Non-negative Matrix Factorization
• Debiased Sinkhorn barycenters
• Scalable Unbalanced Optimal Transport using Generative Adversarial Networks
• An explicit analysis of the entropic penalty in linear programming
• Orlicz space regularization of continuous optimal transport problems
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Learning with Fenchel-Young Losses
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Score-based Generative Neural Networks for Large-Scale Optimal Transport
• Feature Robust Optimal Transport for High-dimensional Data
• Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
• Orlicz-space regularization for optimal transport and algorithms for quadratic regularization
• Sinkhorn Divergence of Topological Signature Estimates for Time Series Classification
• Learning Generalized Gumbel-max Causal Mechanisms
• Order Constraints in Optimal Transport
• Approximation of Wasserstein distance with Transshipment
• Dual Regularized Optimal Transport
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm
• Optimal transport weights for causal inference
• Entropy-regularized optimal transport on multivariate normal and q-normal distributions