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.
Introduction
Optimal Transport (OT) has emerged as a powerful framework for comparing probability distributions, finding applications in diverse fields such as generative modeling, domain adaptation, and cell trajectory prediction. While much research has focused on estimating the Wasserstein distance—a scalar value representing the cost of transport—many practical applications require the transport map itself. This map defines the functional transformation that pushes one distribution onto another.
Estimating these maps is significantly more challenging than estimating distances. Standard "plugin" estimators, which rely directly on empirical samples, often suffer from the "curse of dimensionality," where the required sample size grows exponentially with the data dimension. To mitigate this, researchers often assume the underlying map is smooth. However, enforcing both smoothness and the necessary convexity constraints typically leads to NP-hard optimization problems. This paper addresses this gap by introducing a computationally tractable algorithm that achieves near-optimal statistical error rates for smooth map estimation.
Methodology
The proposed approach leverages a Kernel Sum-of-Squares (SoS) framework to handle the complex constraints inherent in smooth optimal transport.
Semi-Dual Reformulation
The authors solve the problem in the semi-dual space. This formulation provides stronger convexity properties compared to the standard dual, which simplifies the error analysis and improves the stability of the optimization process.
Infinite-Dimensional Sum-of-Squares
A key technical innovation is replacing the hard, infinite-dimensional inequality constraints of the dual problem with an equality constraint involving a Sum-of-Squares term within a Reproducing Kernel Hilbert Space (RKHS). This reformulation transforms a potentially intractable problem into one that can be solved using standard optimization techniques.
Algorithmic Scalability
To ensure the method is practical for real-world datasets, several enhancements were implemented:
- Strongly Convex Relaxation: By replacing trace penalties with square norm penalties, the authors enable the use of efficient first-order optimization methods, such as Accelerated Gradient Descent.
- Nyström Approximation: This low-rank technique significantly reduces the computational burden of handling large kernel matrices, lowering the cost per iteration.
- MMD-based Hyperparameter Selection: The Maximum Mean Discrepancy (MMD) is used as a proxy for the $L^2$ error, allowing for effective hyperparameter tuning without requiring knowledge of the ground-truth map.
Experimental Evaluation
The algorithm was evaluated using synthetic datasets where ground-truth Brenier maps are analytically known. Specifically, the authors tested the method on Gaussian distributions in 2, 4, and 8 dimensions, with covariances generated via Wishart distributions to ensure a variety of test cases.
Key Results
- Near-Optimal Statistical Rates: The algorithm's $L^2$ error rate nearly matches the theoretical minimax lower bounds, representing the "speed limit" for smooth map estimators.
- Dimension-Free Exponents: The statistical error rate is "dimension-free" in its dependence on the number of samples ($n$), meaning the exponent of $n$ does not degrade as dimension increases, although the constant factors might.
- Empirical Performance: In higher-dimensional tests (4D and 8D), the SoS-OT approach significantly outperformed traditional plugin estimators. The performance gap widened as the dimensionality increased, demonstrating the method's robustness.
Discussion and Limitations
While the method achieves near-optimal rates, a few challenges remain. The constant factor in the error bound can be exponentially large relative to the dimension, implying that very high-dimensional data may still require a substantial number of samples to reach the optimal regime. Furthermore, the current SoS reformulation requires high levels of smoothness ($m > 2d$). Future work may explore extending these guarantees to maps with lower regularity and closing the theoretical gap between the strongly convex relaxation used in practice and the hard-constraint version analyzed in the proofs.
Conclusion
This paper presents the first tractable algorithm for smooth optimal transport map estimation that bridges the gap between theoretical minimax limits and practical implementation. By combining SoS reformulations with modern optimization techniques, the authors provide a scalable path forward for high-dimensional generative modeling and distribution alignment tasks.
Summary updated