Linear Time Sinkhorn Divergences using Positive Features

Abstract

Although Sinkhorn divergences are now routinely used in data sciences to compare probability distributions, the computational effort required to compute them remains expensive, growing in general quadratically in the size $n$ of the support of these distributions. Indeed, solving optimal transport (OT) with an entropic regularization requires computing a $n\times n$ kernel matrix (the neg-exponential of a $n\times n$ pairwise ground cost matrix) that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-\log\dotp{φ(x)}{φ(y)}$ where $\phi$ is a map from the ground space onto the positive orthant $\RR^r_+$, with $r\ll n$. This choice yields, equivalently, a kernel $k(x,y)=\dotp{φ(x)}{φ(y)}$, and ensures that the cost of Sinkhorn iterations scales as $O(nr)$. We show that usual cost functions can be approximated using this form. Additionaly, we take advantage of the fact that our approach yields approximation that remain fully differentiable with respect to input distributions, as opposed to previously proposed adaptive low-rank approximations of the kernel matrix, to train a faster variant of OT-GAN \cite{salimans2018improving}.

References in corpus (12)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• Fast Computation of Wasserstein Barycenters
• MMD GAN: Towards Deeper Understanding of Moment Matching Network
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Convolutional Kernel Networks
• Sample Complexity of Sinkhorn divergences
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Unsupervised Hyperalignment for Multilingual Word Embeddings
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• GAN and VAE from an Optimal Transport Point of View
• Massively scalable Sinkhorn distances via the Nyström method

Cited by in corpus (5)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Differentiable Particle Filtering via Entropy-Regularized Optimal Transport
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Equitable and Optimal Transport with Multiple Agents
• Approximating Optimal Transport via Low-rank and Sparse Factorization