Stability and statistical inference for semidiscrete optimal transport maps

Ritwik Sadhu, Ziv Goldfeld, Kengo Kato

TL;DR

This paper establishes the first rigorous framework for statistical inference on semidiscrete Optimal Transport (OT) maps. The authors derive limit distributions for estimation errors and linear functionals, prove the consistency of the bootstrap for constructing confidence intervals, and demonstrate that the empirical OT map is asymptotically efficient in a specific functional space.

What Problem Does This Paper Address?

Optimal Transport (OT) has become a cornerstone of modern machine learning and statistics, used for everything from domain adaptation to causal inference. A central object in OT is the Brenier map (or OT map), which describes the most efficient way to transform one probability distribution into another.

While researchers have spent years figuring out how fast we can estimate these maps (estimation rates), we have lacked a theory for statistical inference. If you estimate an OT map from data, how certain are you? How do you build a confidence interval around that map?

The challenge is particularly acute in the semidiscrete setting—where a continuous reference distribution (like a Gaussian) is mapped to a discrete target distribution (like a finite set of data points). In this case, the map is defined implicitly through a complex optimization problem, making its statistical properties difficult to track.

Methods

The authors tackle this by analyzing the stability of the OT map relative to its "dual potential vector." Their approach involves several sophisticated mathematical tools:

  • Hadamard Directional Differentiability: Because the $L^p$-error of the map is not a linear function, the authors use a generalized version of the derivative to describe how the map changes as the data changes.
  • Stability Estimates of Laguerre Cells: Semidiscrete OT maps are piecewise constant over regions called Laguerre cells. The authors provide a detailed analysis of how the boundaries (faces) of these cells shift when the target distribution is perturbed.
  • Extended Delta Method: This allows them to take the known Central Limit Theorem (CLT) for the dual potentials and "push" it through the map's functional to find the limit distribution of the map itself.
  • Dual Hölder Space: The authors prove that while the map doesn't behave well in standard $L^2$ space (it doesn't have a "weak limit"), it satisfies a CLT in the dual of an $\alpha$-Hölder space—a "weaker" space that can handle the map's discontinuities.

Datasets

As a theoretical statistics paper, the work does not introduce new large-scale benchmarks. Instead, it uses controlled synthetic environments to validate the derived theorems:

  • Reference Measures ($R$): Uniform distributions on a unit square $[0, 1]^2$ or a unit ball $B_1$.
  • Target Measures ($P$): Discrete distributions with support on 4 or 5 points chosen randomly or at specific coordinates.
  • Simulations: 10,000 Monte Carlo repetitions were used to generate histograms of sampling distributions and verify that bootstrap-based confidence intervals achieve the correct coverage.

Key Insights and Ideas

  • The "Super-Consistency" Paradox: At any fixed point inside a Laguerre cell, the empirical map will eventually exactly match the true map once you have enough data. This makes "pointwise" inference trivial and useless. However, the functionals (like total error) are driven by what happens at the boundaries of these cells, which is where the interesting statistical noise lives.
  • Non-Gaussian Limits: Surprisingly, the $L^p$-error of the OT map does not follow a Bell curve (Gaussian distribution) in the limit. The authors derive an explicit, non-Gaussian density for this error.
  • Bootstrap Validity: They prove that the nonparametric bootstrap—a common technique for estimating uncertainty by re-sampling data—is mathematically valid for these maps, even though the underlying derivatives are non-linear.
  • Efficiency: They show that the empirical OT map is "asymptotically efficient," meaning it makes the best possible use of the available data in the dual Hölder space.

Key Results

  • Limit Laws: The authors proved that linear functionals of the map (like the maximum tail correlation) are asymptotically normal (Gaussian), while the $L^p$-estimation error has a specific non-Gaussian limit.
  • Bootstrap Performance: In simulations, the bootstrap-based confidence intervals for $L^1$-error and tail correlation showed coverage probabilities that closely followed the theoretical 45-degree line, confirming the theory works in practice.
  • Risk Measure Inference: They successfully applied their theory to provide a method for statistical inference on the "maximum tail correlation," a risk measure used in finance for multivariate risky assets.

Limitations and Future Work

  • Semidiscrete Only: The results are specific to the semidiscrete case. Extending this to the "continuous-to-continuous" case remains a major open challenge because the map's regularity is much harder to control there.
  • Known Reference: The theory assumes the reference distribution $R$ is perfectly known. In some applications (like transfer learning), both distributions might be estimated from data, which would require further extensions.
  • Visualization: While they provide a method for confidence bands, visualizing uncertainty in high-dimensional OT maps remains difficult due to the complex geometry of Laguerre cells.

Summary updated

Abstract

We study statistical inference for the optimal transport (OT) map (also known as the Brenier map) from a known absolutely continuous reference distribution onto an unknown finitely discrete target distribution. We derive limit distributions for the Lp-error with arbitrary p∈[1,∞) and for linear functionals of the empirical OT map, together with their moment convergence. The former has a non-Gaussian limit, whose explicit density is derived, while the latter attains asymptotic normality. For both cases, we also establish consistency of the nonparametric bootstrap. The derivation of our limit theorems relies on new stability estimates of functionals of the OT map with respect to the dual potential vector, which may be of independent interest. We also discuss applications of our limit theorems to the construction of confidence sets for the OT map and inference for a maximum tail correlation. Finally, we show that, while the empirical OT map does not possess nontrivial weak limits in the L2 space, it satisfies a central limit theorem in a dual Hölder space, and the Gaussian limit law attains the asymptotic efficiency bound.
BibTeX
@article{sadhu2024stability,
  author = {Ritwik Sadhu and Ziv Goldfeld and Kengo Kato},
  title = {{Stability and statistical inference for semidiscrete optimal transport maps}},
  journal = {The Annals of Applied Probability},
  year = {2024},
  doi = {10.1214/24-aap2104},
}

Loading related content...

Figure