Research map / Learning theory and algorithms / Optimal transport

Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation

NeurIPS 2026 · Learning theory and algorithms › Optimal transport · approach: Transport map estimation · 0 citations (OpenAlex)

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.

Proposes a solver-free Monte Carlo estimator of the one-sample OT discretization error (via closed-form semi-dual with optimal weights), uses its multi-scale decay to estimate intrinsic dimension, and a diagonal (n, epsilon-coupled) Richardson extrapolation of Sinkhorn divergence for debiased W2^2 estimation.

Problem

Wasserstein/OT estimation from samples is limited by discretization error whose rate depends on the unknown intrinsic dimension, and Sinkhorn-based estimates are biased by both entropic regularization and finite-sample error; calibrating these requires knowing the intrinsic dimension.

Approach

Shows that for the optimally weighted discrete measure on a fixed support, the semi-dual potential is zero, so OT cost equals the Monte Carlo average of nearest-neighbor distances (no OT solver). This error's multi-scale decay gives a linear-time intrinsic dimension estimator, and the intrinsic dimension calibrates a diagonal Richardson extrapolation that jointly couples the entropic parameter eps

Key results

• On CIFAR10 with n=1000, the n-Diag-Rich estimator reduces W2^2 error from 1.210 (Base Sinkhorn) to 0.089.
• On MNIST, n-Diag-Rich error is 0.219 vs 0.788 for Base and 0.706 for Eps-Rich.
• The solver-free intrinsic dimension estimator runs in under 0.1 s versus about 10 s on GPU for the discrete W1 estimator on synthetic mixtures with effective dimension 10.

Surprising findings

• The epsilon-only Richardson extrapolation with the estimated dimension yields errors comparable to the uncorrected Sinkhorn baseline on image datasets.

Limitations

• The diagonal Richardson bias cancellation relies on an unproven sharpness assumption for the statistical bias expansion.
• Results are limited to the scalar transport cost W2^2 and do not address Kantorovich potentials or gradients.
• Intrinsic dimension guarantees require sample sizes within a regime [n_min, n_max] and assume the dimension is stable across scales.

Experimental setup

Datasets: MNIST FashionMNIST CIFAR10

Benchmarks: MNIST FashionMNIST CIFAR10 scikit-dimension estimators (synthetic mixtures)

Metrics: absolute error of W2^2 estimate intrinsic dimension estimate accuracy runtime (s)

Baselines: Discrete W1 dimension estimator MLE CorrInt lPCA TwoNN Base Sinkhorn divergence Eps-Richardson extrapolation

Builds on: Sinkhorn divergence Richardson extrapolation (epsilon-only) semi-discrete optimal transport empirical Bernstein bound

Closest papers by meaning

• Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.88)
• Wasserstein Wormhole: Scalable Optimal Transport Distance with Transformer (ICML 2024 · similarity 0.88)
• Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.88)
• Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.88)
• Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.88)
• Estimation of Stochastic Optimal Transport Maps (NeurIPS 2025 · similarity 0.88)