Minimax estimation of discontinuous optimal transport maps: The
semi-discrete case
- URL: http://arxiv.org/abs/2301.11302v2
- Date: Wed, 24 May 2023 18:24:19 GMT
- Title: Minimax estimation of discontinuous optimal transport maps: The
semi-discrete case
- Authors: Aram-Alexandre Pooladian, Vincent Divol, Jonathan Niles-Weed
- Abstract summary: 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.
- Score: 14.333765302506658
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of estimating the optimal transport map between two
probability distributions, $P$ and $Q$ in $\mathbb R^d$, on the basis of i.i.d.
samples. All existing statistical analyses of this problem require the
assumption that the transport map is Lipschitz, a strong requirement that, in
particular, excludes any examples where the transport map is discontinuous. As
a first step towards developing estimation procedures for discontinuous maps,
we consider the important special case where the data distribution $Q$ is a
discrete measure supported on a finite number of points in $\mathbb R^d$. We
study a computationally efficient estimator initially proposed by Pooladian and
Niles-Weed (2021), based on entropic optimal transport, and show in the
semi-discrete setting that it converges at the minimax-optimal rate $n^{-1/2}$,
independent of dimension. Other standard map estimation techniques both lack
finite-sample guarantees in this setting and provably suffer from the curse of
dimensionality. We confirm these results in numerical experiments, and provide
experiments for other settings, not covered by our theory, which indicate that
the entropic estimator is a promising methodology for other discontinuous
transport map estimation problems.
Related papers
- Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs [49.1574468325115]
"Normalizing Flows" is related to the task of constructing invertible transport maps between probability measures by means of deep neural networks.
We consider the problem of recovering the $Wamma$-optimal transport map $T$ between absolutely continuous measures $mu,nuinmathcalP(mathbbRn)$ as the flow of a linear-control neural ODE.
arXiv Detail & Related papers (2023-11-02T17:17:03Z) - On minimax density estimation via measure transport [0.0]
We study the convergence properties of nonparametric density estimators based on measure transport.
We show that penalized and unpenalized versions of such estimators achieve minimax optimal convergence rates over H"older classes of densities.
arXiv Detail & Related papers (2022-07-20T23:56:00Z) - 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) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process.
We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator.
We prove minimax lower bounds over sub-classes of MRPs.
arXiv Detail & Related papers (2021-09-24T14:48:20Z) - Plugin Estimation of Smooth Optimal Transport Maps [25.23336043463205]
We show that a number of natural estimators for the optimal transport map between two distributions are minimax optimal.
Our work provides new bounds on the risk of corresponding plugin estimators for the quadratic Wasserstein distance.
arXiv Detail & Related papers (2021-07-26T17:58:48Z) - Rates of Estimation of Optimal Transport Maps using Plug-in Estimators
via Barycentric Projections [0.0]
We provide a comprehensive analysis of the rates of convergences for general plug-in estimators defined via barycentric projections.
Our main contribution is a new stability estimate for barycentric projections which proceeds under minimal smoothness assumptions.
We illustrate the usefulness of this stability estimate by first providing rates of convergence for the natural discrete-discrete and semi-discrete estimators of optimal transport maps.
arXiv Detail & Related papers (2021-07-04T19:50:20Z) - Continuous Wasserstein-2 Barycenter Estimation without Minimax
Optimization [94.18714844247766]
Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport.
We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
arXiv Detail & Related papers (2021-02-02T21:01:13Z) - Linear Optimal Transport Embedding: Provable Wasserstein classification
for certain rigid transformations and perturbations [79.23797234241471]
Discriminating between distributions is an important problem in a number of scientific fields.
The Linear Optimal Transportation (LOT) embeds the space of distributions into an $L2$-space.
We demonstrate the benefits of LOT on a number of distribution classification problems.
arXiv Detail & Related papers (2020-08-20T19:09:33Z) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected.
Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances.
Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
arXiv Detail & Related papers (2020-06-22T14:35:33Z) - Statistical Optimal Transport posed as Learning Kernel Embedding [0.0]
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.
arXiv Detail & Related papers (2020-02-08T14:58:53Z)
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.