# Minimax estimation of discontinuous optimal transport maps: The semi-discrete case

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 86 references that are in the map.
- First posted on arXiv 26 Jan 2023.

## Builds on (most cited first, 26 of 26)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Supervised Training of Conditional Monge Maps](https://mlsanity.com/paper/2206.14262/) (2022)
- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [Optimal Transport for Diffeomorphic Registration](https://mlsanity.com/paper/1706.05218/) (2017)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Entropic Optimal Transport: Convergence of Potentials](https://mlsanity.com/paper/2104.11720/) (2021)
- [Stability of Entropic Optimal Transport and Schr"odinger Bridges](https://mlsanity.com/paper/2106.03670/) (2021)
- [Entropic Optimal Transport: Geometry and Large Deviations](https://mlsanity.com/paper/2102.04397/) (2021)
- [Optimal transport map estimation in general function spaces](https://mlsanity.com/paper/2212.03722/) (2022)
- [Learning normalizing flows from Entropy-Kantorovich potentials](https://mlsanity.com/paper/2006.06033/) (2020)
- [An improved central limit theorem and fast convergence rates for entropic transportation costs](https://mlsanity.com/paper/2204.09105/) (2022)
- [Neural Unbalanced Optimal Transport via Cycle-Consistent Semi-Couplings](https://mlsanity.com/paper/2209.15621/) (2022)
- [Asymptotics for semi-discrete entropic optimal transport](https://mlsanity.com/paper/2106.11862/) (2021)
- [Near-optimal estimation of smooth transport maps with kernel sums-of-squares](https://mlsanity.com/paper/2112.01907/) (2021)
- [Semi-Discrete Normalizing Flows through Differentiable Tessellation](https://mlsanity.com/paper/2203.06832/) (2022)
- [Non-asymptotic convergence bounds for Wasserstein approximation using point clouds](https://mlsanity.com/paper/2106.07911/) (2021)
- [Debiaser Beware: Pitfalls of Centering Regularized Transport Maps](https://mlsanity.com/paper/2202.08919/) (2022)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)

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

- [Wasserstein Flow Matching: Generative modeling over families of distributions](https://mlsanity.com/paper/2411.00698/) (2024)
- [Minimum intrinsic dimension scaling for entropic optimal transport](https://mlsanity.com/paper/2306.03398/) (2023)
- [Conditional simulation via entropic optimal transport: Toward non-parametric estimation of conditional Brenier maps](https://mlsanity.com/paper/2411.07154/) (2024)
- [Plug-in estimation of Schr"odinger bridges](https://mlsanity.com/paper/2408.11686/) (2024)
- [Learning Elastic Costs to Shape Monge Displacements](https://mlsanity.com/paper/2306.11895/) (2023)
- [Diffeomorphic Measure Matching with Kernels for Generative Modeling](https://mlsanity.com/paper/2402.08077/) (2024)
- [Estimation of entropy-regularized optimal transport maps between non-compactly supported measures](https://mlsanity.com/paper/2311.11934/) (2023)
- [Meta Optimality for Demographic Parity Constrained Regression via Post-Processing](https://mlsanity.com/paper/2506.13947/) (2025)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Stability of the Kim--Milman flow map](https://mlsanity.com/paper/2511.01154/) (2025)
- [Estimation of Stochastic Optimal Transport Maps](https://mlsanity.com/paper/2512.09499/) (2025)
- [Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations](https://mlsanity.com/paper/2307.13370/) (2023)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)
- [Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps](https://mlsanity.com/paper/2412.13372/) (2024)
- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)
- [PCA of probability measures: Sparse and Dense sampling regimes](https://mlsanity.com/paper/2602.02190/) (2026)
- [Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation](https://mlsanity.com/paper/2602.04335/) (2026)
- [Near-Lipschitz stability of the Kim--Milman flow map](https://mlsanity.com/paper/2606.23383/) (2026)
- [Deep Barycentric Regression for Optimal Transport Map Estimation and its Statistical Optimality](https://mlsanity.com/paper/2609.06598/) (2026)

## Abstract (arXiv)

We consider the problem of estimating the optimal transport map between two probability distributions, P and Q in mathbb Rd, 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 Rd. 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.