# A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

arXiv: https://arxiv.org/abs/2101.05380 · HTML: https://mlsanity.com/paper/2101.05380/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2021.

## Built on by (most cited first, 17 of 17)

- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Measuring Generalization with Optimal Transport](https://mlsanity.com/paper/2106.03314/) (2021)
- [Near-optimal estimation of smooth transport maps with kernel sums-of-squares](https://mlsanity.com/paper/2112.01907/) (2021)
- [Learning PSD-valued functions using kernel sums-of-squares](https://mlsanity.com/paper/2111.11306/) (2021)
- [Analysis of Kernel Mirror Prox for Measure Optimization](https://mlsanity.com/paper/2403.00147/) (2024)
- [Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems](https://mlsanity.com/paper/2103.12624/) (2021)
- [Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares](https://mlsanity.com/paper/2204.04970/) (2022)
- [Approximation of optimization problems with constraints through kernel Sum-Of-Squares](https://mlsanity.com/paper/2301.06339/) (2023)
- [Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models](https://mlsanity.com/paper/2303.17109/) (2023)
- [A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport](https://mlsanity.com/paper/2310.14087/) (2023)
- [Scalable and adaptive prediction bands with kernel sum-of-squares](https://mlsanity.com/paper/2505.21039/) (2025)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Geometrically Constrained Stenosis Editing in Coronary Angiography via Entropic Optimal Transport](https://mlsanity.com/paper/2605.08851/) (2026)
- [Measuring dissimilarity with diffeomorphism invariance](https://mlsanity.com/paper/2202.05614/) (2022)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)

## Abstract (arXiv)

It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexity of these recently proposed methods still degrades exponentially with the dimension. In this paper, thanks to an infinite-dimensional sum-of-squares representation, we derive a statistical estimator of smooth optimal transport which achieves a precision varepsilon from tildeO(varepsilon-2) independent and identically distributed samples from the distributions, for a computational cost of tildeO(varepsilon-4) when the smoothness increases, hence yielding dimension-free statistical and computational rates, with potentially exponentially dimension-dependent constants.