Minibatch optimal transport distances; analysis and applications

• URL: http://arxiv.org/abs/2101.01792v1
• Date: Tue, 5 Jan 2021 21:29:31 GMT
• Title: Minibatch optimal transport distances; analysis and applications
• Authors: Kilian Fatras, Younes Zine, Szymon Majewski, R\'emi Flamary, R\'emi Gribonval, Nicolas Courty
• Abstract summary: Optimal transport distances have become a classic tool to compare probability distributions and have found many applications in machine learning. A common workaround is to compute these distances on minibatches 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.
• Score: 9.574645423576932
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
  We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions. Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
  arXiv  Detail & Related papers  (2023-10-02T11:24:36Z)
• Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport [35.440243358517066]
  We introduce novel families of upper and lower bounds for the Optimal Transport problem constructed by aggregating solutions of mini-batch OT problems. The upper bound family contains traditional mini-batch averaging at one extreme and a tight bound found by optimal coupling of mini-batches at the other. Through various experiments, we explore the trade-off between computational budget and bound tightness and show the usefulness of these bounds in computer vision applications.
  arXiv  Detail & Related papers  (2022-10-24T22:12:17Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOT is an information-theoretic extension of optimal transport. It maximizes the mutual information between domains while minimizing geometric distances. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples.
  arXiv  Detail & Related papers  (2022-10-06T18:55:41Z)
• Learning Optimal Transport Between two Empirical Distributions with Normalizing Flows [12.91637880428221]
  We propose to leverage the flexibility of neural networks to learn an approximate optimal transport map. We show that a particular instance of invertible neural networks, namely the normalizing flows, can be used to approximate the solution of this OT problem.
  arXiv  Detail & Related papers  (2022-07-04T08:08:47Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  Three simple ideas allow us to train models with DRO using a broader class of parametric likelihood ratios. We find that models trained with the resulting parametric adversaries are consistently more robust to subpopulation shifts when compared to other DRO approaches.
  arXiv  Detail & Related papers  (2022-04-13T12:43:12Z)
• An Efficient Mini-batch Method via Partial Transportation [10.127116789814488]
  Mini-batch optimal transport (m-OT) has been widely used to deal with the memory issue of OT in large-scale applications. We propose a novel mini-batch method by using partial optimal transport (POT) between mini-batch empirical measures. We show that m-POT is better than m-OT deep domain adaptation applications while having comparable performance with m-UOT.
  arXiv  Detail & Related papers  (2021-08-22T05:45:48Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation [8.889304968879163]
  Optimal transport distances have found many applications in machine learning for their capacity to compare non-parametric probability distributions. We argue that the same minibatch strategy coupled with unbalanced optimal transport can yield more robust behavior. Our experimental study shows that in challenging problems associated to domain adaptation, the use of unbalanced optimal transport leads to significantly better results, competing with or surpassing recent baselines.
  arXiv  Detail & Related papers  (2021-03-05T11:15:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.