Minibatch optimal transport distances; analysis and applications

Abstract

Optimal transport distances have become a classic tool to compare probability distributions and have found many applications in machine learning. Yet, despite recent algorithmic developments, their complexity prevents their direct use on large scale datasets. To overcome this challenge, a common workaround is to compute these distances on minibatches i.e. to average the outcome of several smaller optimal transport problems. We propose in this paper an extended analysis of this practice, which effects were previously studied in restricted cases. We first consider a large variety of Optimal Transport kernels. We notably argue that the minibatch strategy comes with appealing properties such as unbiased estimators, gradients and a concentration bound around the expectation, but also with limits: the minibatch OT is not a distance. To recover some of the lost distance axioms, we introduce a debiased minibatch OT function and study its statistical and optimisation properties. Along with this theoretical analysis, we also conduct empirical experiments on gradient flows, generative adversarial networks (GANs) or color transfer that highlight the practical interest of this strategy.

References in corpus (16)

• Scikit-learn: Machine Learning in Python
• Auto-Encoding Variational Bayes
• MMD GAN: Towards Deeper Understanding of Moment Matching Network
• DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation
• Learning with a Wasserstein Loss
• The Cramer Distance as a Solution to Biased Wasserstein Gradients
• Sample Complexity of Sinkhorn divergences
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Smooth and Sparse Optimal Transport
• Wasserstein Adversarial Examples via Projected Sinkhorn Iterations
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• Hierarchical Optimal Transport for Multimodal Distribution Alignment
• Sinkhorn AutoEncoders
• Multiscale Strategies for Computing Optimal Transport
• Analysis of nonsmooth stochastic approximation: the differential inclusion approach
• Stochastic Optimization for Regularized Wasserstein Estimators

Cited by in corpus (6)

• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• Multi-Source Domain Adaptation through Dataset Dictionary Learning in Wasserstein Space
• Improving Mini-batch Optimal Transport via Partial Transportation
• On Transportation of Mini-batches: A Hierarchical Approach
• Training Wasserstein GANs without gradient penalties
• Using Optimal Transport as Alignment Objective for fine-tuning Multilingual Contextualized Embeddings