  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.
