Near-optimal estimation of smooth transport maps with kernel sums-of-squares

• URL: http://arxiv.org/abs/2112.01907v1
• Date: Fri, 3 Dec 2021 13:45:36 GMT
• Title: Near-optimal estimation of smooth transport maps with kernel sums-of-squares
• Authors: Boris Muzellec, Adrien Vacher, Francis Bach, Fran\c{c}ois-Xavier Vialard, Alessandro Rudi
• Abstract summary: 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.
• Score: 81.02564078640275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It was recently shown that under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. However, rather than the distance itself, the object of interest for applications such as generative modeling is the underlying optimal transport map. Hence, computational and statistical guarantees need to be obtained for the estimated maps themselves. In this paper, we propose the first tractable algorithm for which the statistical $L^2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation. Our method is based on solving the semi-dual formulation of optimal transport with an infinite-dimensional sum-of-squares reformulation, and leads to an algorithm which has dimension-free polynomial rates in the number of samples, with potentially exponentially dimension-dependent constants.

Related papers

• Conditional simulation via entropic optimal transport: Toward non-parametric estimation of conditional Brenier maps [13.355769319031184]
  Conditional simulation is a fundamental task in statistical modeling. One promising approach is to construct conditional Brenier maps, where the components of the map pushforward a reference distribution to conditionals of the target. We propose a non-parametric estimator for conditional Brenier maps based on the computational scalability of emphentropic optimal transport.
  arXiv  Detail & Related papers  (2024-11-11T17:32:47Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• 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)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  We present a model inversion algorithm, CKLEMAP, for data assimilation and parameter estimation in partial differential equation models. The CKLEMAP method provides better scalability compared to the standard MAP method.
  arXiv  Detail & Related papers  (2023-01-26T18:14:12Z)
• 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)
• 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)
• Scalable Computation of Monge Maps with General Costs [12.273462158073302]
  Monge map refers to the optimal transport map between two probability distributions. We present a scalable algorithm for computing the Monge map between two probability distributions.
  arXiv  Detail & Related papers  (2021-06-07T17:23:24Z)
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization [106.70006655990176]
  A distributional optimization problem arises widely in machine learning and statistics. We propose a novel particle-based algorithm, dubbed as variational transport, which approximately performs Wasserstein gradient descent. We prove that when the objective function satisfies a functional version of the Polyak-Lojasiewicz (PL) (Polyak, 1963) and smoothness conditions, variational transport converges linearly.
  arXiv  Detail & Related papers  (2020-12-21T18:33:13Z)
• 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)

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.