Published on Sun Jul 04 2021

Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections

Nabarun Deb, Promit Ghosal, Bodhisattva Sen

In this paper, we provide a comprehensive analysis of the rates of convergences for general plug-in estimators defined via barycentric projections. We illustrate the usefulness of this stability estimate by providing rates of convergence for the natural discrete-discrete and semi-discret estimators of optimal transport maps.

3
1
0
Abstract

Optimal transport maps between two probability distributions and on have found extensive applications in both machine learning and statistics. In practice, these maps need to be estimated from data sampled according to and . Plug-in estimators are perhaps most popular in estimating transport maps in the field of computational optimal transport. In this paper, 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 and can be used to analyze general plug-in estimators. 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. We then use the same stability estimate to show that, under additional smoothness assumptions of Besov type or Sobolev type, wavelet based or kernel smoothed plug-in estimators respectively speed up the rates of convergence and significantly mitigate the curse of dimensionality suffered by the natural discrete-discrete/semi-discrete estimators. As a by-product of our analysis, we also obtain faster rates of convergence for plug-in estimators of , the Wasserstein distance between and , under the aforementioned smoothness assumptions, thereby complementing recent results in Chizat et al. (2020). Finally, we illustrate the applicability of our results in obtaining rates of convergence for Wasserstein barycenters between two probability distributions and obtaining asymptotic detection thresholds for some recent optimal-transport based tests of independence.

Mon Jul 26 2021
Machine Learning
Plugin Estimation of Smooth Optimal Transport Maps
We analyze a number of natural estimators for the optimal transport map. We show that they are minimax optimal. Our work also provides new bounds on the risk of misinterpreting Wasserstein distances.
8
0
0
Sun Feb 28 2021
Machine Learning
Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples
The Gaussian-smoothed optimal transport (GOT) framework, recently proposed by Goldfeld et al., scales to high dimensions in estimation. This paper provides convergence assurances for estimating the GOT distance under more general settings.
0
0
0
Mon Jun 22 2020
Machine Learning
On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification
Optimal transport (OT) distances are increasingly used as loss functions foristical inference. Yet, the behavior of minimum Wasserstein estimators is poorly understood, notably in high-dimensional regimes or under model misspecification. We establish several fundamental statistical properties of PR Wasserstein distances.
1
0
1
Fri May 27 2016
Machine Learning
Stochastic Optimization for Large-scale Optimal Transport
Optimal transport (OT) defines a powerful framework to compare probability distributions in a geometrically faithful way. However, the practical impact of OT is still limited because of its computational burden. We propose a new class of stochastic optimization algorithms to cope with large-scale problems.
0
0
0
Wed Nov 07 2018
Machine Learning
Wasserstein variational gradient descent: From semi-discrete optimal transport to ensemble variational inference
Particle-based variational inference offers a flexible way of approximating complex posterior distributions with a set of particles. We approximate these transportation densities by minimizing the KL divergence between a truncated distribution and the optimal transport solution.
0
0
0
Fri Oct 30 2020
Machine Learning
Efficient constrained sampling via the mirror-Langevin algorithm
We propose a new discretization of the mirror-Langevin diffusion. Our analysis uses relative convexity/smoothness and self-concordance. Unlike prior works, our result both (1) requires much weaker assumptions on the mirror map and the target distribution.
0
0
0
Tue Jun 10 2014
Machine Learning
Generative Adversarial Networks
We propose a new framework for estimating generative models via an adversarial process. We simultaneously train two models: a generative model G that captures the data distribution, and a discriminative model D. The training procedure for G is to maximize the probability of D making a mistake.
9
3,421
23,915
Tue Oct 11 2016
Machine Learning
Learning in Implicit Generative Models
Generative adversarial networks (GANs) provide an algorithmic framework for constructing generative models. We develop likelihood-free inference methods and highlight hypothesis testing as a principle for learning in implicit GANs.
0
0
0
Wed Jun 17 2015
Machine Learning
Learning with a Wasserstein Loss
Wasserstein loss can encourage smoothness of the predictions with respect to a chosen metric on the output space. We demonstrate this property on a real-data tag prediction problem, using the Yahoo Flickr Creative Commons dataset.
0
0
0
Fri Nov 17 2017
Machine Learning
Nonparametric independence testing via mutual information
We propose a test of independence of two multivariate random vectors. Our approach is based on the estimation of mutual information. The theory is supported by numerical studies on both simulated and real data.
0
0
0
Thu Mar 15 2018
Machine Learning
Improving GANs Using Optimal Transport
We present Optimal Transport GAN (OT-GAN), a variant of generative adversarial nets. It combines optimal transport in primal form with an adversarially learned feature space. The result is a highly discriminative distance function with unbiased mini-batch gradients.
0
0
0
Thu Feb 15 2018
Machine Learning
Stochastic Wasserstein Barycenters
We present a stochastic algorithm to compute the barycenter of a set of probabilities. We tackle the problem without regularization, allowing us to recover a sharp output. Our method is versatile and can be extended to generate super samples.
0
0
0