Statistical Optimal Transport posed as Learning Kernel Embedding

• URL: http://arxiv.org/abs/2002.03179v6
• Date: Tue, 10 Nov 2020 08:41:48 GMT
• Title: Statistical Optimal Transport posed as Learning Kernel Embedding
• Authors: J. Saketha Nath (IIT Hyderabad, INDIA) and Pratik Jawanpuria (Microsoft IDC, INDIA)
• Abstract summary: This work takes the novel approach of posing statistical Optimal Transport (OT) as that of learning the transport plan's kernel mean embedding from sample based estimates of marginal embeddings. A key result is that, under very mild conditions, $epsilon$-optimal recovery of the transport plan as well as the Barycentric-projection based transport map is possible with a sample complexity that is completely dimension-free.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The objective in statistical Optimal Transport (OT) is to consistently estimate the optimal transport plan/map solely using samples from the given source and target marginal distributions. This work takes the novel approach of posing statistical OT as that of learning the transport plan's kernel mean embedding from sample based estimates of marginal embeddings. The proposed estimator controls overfitting by employing maximum mean discrepancy based regularization, which is complementary to $\phi$-divergence (entropy) based regularization popularly employed in existing estimators. A key result is that, under very mild conditions, $\epsilon$-optimal recovery of the transport plan as well as the Barycentric-projection based transport map is possible with a sample complexity that is completely dimension-free. Moreover, the implicit smoothing in the kernel mean embeddings enables out-of-sample estimation. An appropriate representer theorem is proved leading to a kernelized convex formulation for the estimator, which can then be potentially used to perform OT even in non-standard domains. Empirical results illustrate the efficacy of the proposed approach.

Related papers

• Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
  We tackle the task of sampling from a probability density as transporting a tractable density function to the target. We employ physics-informed neural networks (PINNs) to approximate the respective partial differential equations (PDEs) solutions. PINNs allow for simulation- and discretization-free optimization and can be trained very efficiently.
  arXiv  Detail & Related papers  (2024-07-10T17:39:50Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Minimax estimation of discontinuous optimal transport maps: The semi-discrete case [14.333765302506658]
  We consider the problem of estimating the optimal transport map between two probability distributions, $P$ and $Q$ in $mathbb Rd$. We show that an estimator based on entropic optimal transport converges at the minimax-optimal rate $n-1/2$, independent of dimension.
  arXiv  Detail & Related papers  (2023-01-26T18:41:38Z)
• Learning Optimal Flows for Non-Equilibrium Importance Sampling [13.469239537683299]
  We develop a method to perform calculations based on generating samples from a simple base distribution, transporting them along the flow generated by a velocity field, and performing averages along these flowlines. On the theory side we discuss how to tailor the velocity field to the target and establish general conditions under which the proposed estimator is a perfect estimator. On the computational side we show how to use deep learning to represent the velocity field by a neural network and train it towards the zero variance optimum.
  arXiv  Detail & Related papers  (2022-06-20T17:25:26Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  We build upon the diffeomorphic properties of normalizing flows to estimate the cumulative distribution function (CDF) over a closed region. Our experiments on popular flow architectures and UCI datasets show a marked improvement in sample efficiency as compared to traditional estimators.
  arXiv  Detail & Related papers  (2022-02-23T06:11:49Z)
• GAN Estimation of Lipschitz Optimal Transport Maps [0.0]
  This paper introduces the first statistically consistent estimator of the optimal transport map between two probability distributions, based on neural networks. We demonstrate that, under regularity assumptions, the obtained generator converges uniformly to the optimal transport map as the sample size increases to infinity. In contrast to previous work tackling either statistical guarantees or practicality, we provide an expressive and feasible estimator which paves way for optimal transport applications.
  arXiv  Detail & Related papers  (2022-02-16T10:15:56Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Entropic estimation of optimal transport maps [15.685006881635209]
  We develop a method for estimating the optimal map between two distributions over $mathbbRd$ with rigorous finite-sample guarantees. We show that our estimator is easy to compute using Sinkhorn's algorithm.
  arXiv  Detail & Related papers  (2021-09-24T14:57:26Z)
• Comparing Probability Distributions with Conditional Transport [63.11403041984197]
  We propose conditional transport (CT) as a new divergence and approximate it with the amortized CT (ACT) cost. ACT amortizes the computation of its conditional transport plans and comes with unbiased sample gradients that are straightforward to compute. On a wide variety of benchmark datasets generative modeling, substituting the default statistical distance of an existing generative adversarial network with ACT is shown to consistently improve the performance.
  arXiv  Detail & Related papers  (2020-12-28T05:14:22Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

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.