Optimal Transport (OT) has emerged as a premier framework for comparing probability distributions because it respects the underlying geometry of the data. Unlike the Kullback-Leibler divergence or Total Variation distance, which compare distributions "pointwise," the Wasserstein distance (the core metric of OT) considers how much "work" is required to move mass from one configuration to another.
However, this geometric sensitivity comes at a steep statistical price. In high-dimensional spaces, the number of samples required to accurately estimate the Wasserstein distance grows exponentially with the dimension. This "curse of dimensionality" means that for a $d$-dimensional feature space, the estimation error typically scales as $O(n^{-1/d})$. As Marco Cuturi notes in Computational Optimal Transport, this makes standard OT unreliable for high-dimensional deep learning features without significant modification.
Recent research has focused on "breaking" this curse by introducing regularization, structural constraints, and algorithmic heuristics that trade off pure geometric precision for statistical stability.
Regularization as a Statistical Bridge
The most influential strategy for scaling OT is entropic regularization. By adding an entropy term to the transport objective, the problem becomes strongly convex and can be solved efficiently using the Sinkhorn algorithm.
Beyond computation, regularization provides a statistical lifeline. Alberto González-Sanz and Jonathan Weed demonstrate in An improved central limit theorem and fast convergence rates for entropic transportation costs that entropic OT behaves more like a kernel-based method, which often enjoys dimension-independent convergence rates. This allows practitioners to use Wasserstein-like distances in high dimensions without needing an astronomical number of samples.
However, regularization is not a free lunch. Aram-Alexandre Pooladian and Marco Cuturi warn in Debiaser Beware: Pitfalls of Centering Regularized Transport Maps that common "debiasing" techniques—intended to correct the smoothing effects of entropy—can actually inject noise and degrade the estimation of the transport map itself in finite-sample settings.
Structural Constraints and Smoothness
Another way to bypass the $O(n^{-1/d})$ bottleneck is to assume the transport map has specific structural properties. If we restrict the "search space" for how mass can move, we reduce the complexity of the estimation.
- Linearity: Rémi Flamary and colleagues show in Concentration bounds for linear Monge mapping estimation and optimal transport domain adaptation that by assuming a linear Monge mapping, one can achieve a dimension-free convergence rate of $O(n^{-1/2})$.
- Smoothness: Philippe Rigollet proves in Minimax estimation of smooth optimal transport maps that if the underlying transport map is sufficiently smooth, wavelet-based estimators can significantly outperform the standard empirical rates.
- Causality: In Designing Ambiguity Sets for Distributionally Robust Optimization Using Structural Causal Optimal Transport, Ahmad Reza Ehyaei and Samira Samadi incorporate structural causal equations to create tighter, less conservative models that effectively "break" the curse by leveraging known relationships between variables.
Minibatching and Stochastic Approximation
In practice, deep learning models rarely compute OT over the entire dataset. Instead, they use minibatches. While originally a computational necessity, minibatching has been found to have unique statistical properties.
Kilian Fatras and Nicolas Courty provide a rigorous analysis in Learning with minibatch Wasserstein : asymptotic and gradient properties, proving that minibatch Wasserstein distances yield unbiased gradients and concentration bounds that do not depend on the data's dimension. This explains why methods like Conditional Flow Matching, introduced by Alexander Tong in Improving and generalizing flow-based generative models with minibatch optimal transport, are so effective at training high-dimensional generative models: the minibatch heuristic acts as an implicit regularizer that sidesteps the sample complexity of the global transport plan.
Implications for Robustness and Generalization
The struggle against dimensionality isn't just a theoretical exercise; it determines the reliability of machine learning models. In Distributionally Robust Optimization (DRO), we seek to minimize the worst-case risk within a "Wasserstein ball" around our training data.
As Jaeho Lee and Maxim Raginsky explore in Minimax Statistical Learning and Domain Adaptation with Wasserstein Distances, if the Wasserstein distance is difficult to estimate, the resulting "robust" model might be overly conservative or fail to generalize. Similarly, Jose H. Blanchet notes in Sample Out-of-Sample Inference Based on Wasserstein Distance that standard statistical scaling laws (like the chi-squared distribution) break down in high dimensions, requiring new "Sample Out-of-Sample" (SOS) inference techniques to calibrate uncertainty.
By understanding these statistical bottlenecks, researchers are moving from "pure" Optimal Transport toward a more pragmatic, "computationally-aware" geometry that remains robust even as the number of features grows.