Research map / Learning theory and algorithms / Optimal transport
Estimation of Stochastic Optimal Transport Maps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the transportation error E_p for stochastic (kernel-valued) optimal transport maps and gives finite-sample rounding, entropic, and robust (Gaussian-convolution) kernel estimators with near-optimal rates under minimal assumptions.
Problem
Estimating optimal transport maps when Brenier's theorem fails (no deterministic optimal map exists, or source not absolutely continuous), so optimal transport must be stochastic; existing map estimation theory requires uniqueness and strong regularity assumptions.
Approach
Defines a transportation error E_p(kappa; mu, nu) for Markov kernels combining an optimality gap and a feasibility gap in Wasserstein distance, which vanishes for any optimal kernel and needs no uniqueness or existence of a deterministic map; builds rounding, entropic, WDRO, and convolution-based estimators with stability lemmas for E_p.
Key results
- Rounding estimator achieves E_p error of order n^{-1/(d+2p)} (up to logs) with sub-Gaussian assumptions, near-optimal against an n^{-1/(d∨2p)} minimax lower bound.
- Under a Lipschitz optimal kernel, WDRO estimator achieves E_p rate of order n^{-1/(d∨2p)} (minimax optimal up to logs).
- In experiments on synthetic settings, NN estimator's L^1 error exceeds 1 in Setting A while its E_1 error is small, and NN outperforms rounding estimator under E_1, with gap shrinking in high dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the rounding kernel estimator instead of the nearest-neighbor estimator | OT map estimation in Setting A · Setting A | E_1 error | Hurt |
| Use the rounding kernel estimator instead of the nearest-neighbor estimator | OT map estimation in Setting B · Setting B | E_1 error | Hurt |
| Evaluate the nearest-neighbor estimator with E_1 rather than L^1 | Nearest-neighbor map estimator · Setting A | estimation error | Helped |
| Increase the dimension | Nearest-neighbor map estimator · Setting A | E_1 error | Hurt |
| Set the rounding partition side length to n^{-1/(d+2)} | Rounding kernel estimator · Setting A and Setting B | E_1 error | Mixed |
| Replace the uniform cubic partition with a non-uniform partition (ablation) | Rounding estimator · Distributions where μ has bounded 2p-th moments | expected transportation error (E_p): \widetilde{O}_{p,d}\bigl(n^{-1/(d+2p)}\bigr) | Helped |
| Use the Kolmogorov-Smirnov metric for stability in one dimension (ablation) | Rounding estimator · d=1 | transportation error (E_p): n^{-1/2} | Helped |
| Train with the Monge gap objective rather than E_p | Neural map estimation · Preliminary tests | training stability | Helped |
Surprising findings
- In Setting A, the nearest-neighbor map has L^1 error always above 1 despite strong E_1 performance, showing L^p loss can be misleading for stochastic optimal maps.
- Monge gap objective gave more stable neural training than the E_p objective in preliminary tests, so the authors recommend E_p as an evaluation metric rather than a training loss.
Limitations
- The minimax rate for general mu, nu on [0,1]^d is not closed: lies between n^{-1/(d∨2p)} and n^{-1/(d+2p)}.
- Computationally efficient estimator achieving optimal rate under Lipschitz kernel is open; the NN estimator lacks formal guarantees.
- Experiments are small synthetic settings (N up to 100 samples on an M1 MacBook Air).
Experimental setup
Datasets: synthetic discrete distributions (Setting A and Setting B)
Benchmarks: synthetic Setting A synthetic Setting B
Metrics: E_1 transportation error L^1 error bootstrapped quantiles
Baselines: nearest-neighbor map estimator L^p loss
Builds on: Brenier map estimation entropic optimal transport Monge gap Wasserstein distributionally robust optimization
Closest papers by meaning
- Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate (NeurIPS 2025 · similarity 0.88)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.88)
- On the Private Estimation of Smooth Transport Maps (ICML 2025 · similarity 0.87)
- Minimax Private Estimation of Smooth Optimal-Transport Maps (NeurIPS 2026 · similarity 0.87)
- Improving Neural Optimal Transport via Displacement Interpolation (ICLR 2025 · similarity 0.87)
- Analyzing and Improving Optimal-Transport-based Adversarial Networks (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.