The Fundamental Limits of Valid Transport Map Estimation

Source: arXiv:2606.30574 · Published 2026-06-29 · By Sivaraman Balakrishnan

TL;DR

This paper addresses the fundamental statistical difficulty of estimating valid transport maps between probability distributions, motivated by modern generative modeling methods such as diffusion models, normalizing flows, and flow matching. These generative methods often learn transport maps or plans that are not necessarily optimal in the classical optimal transport (OT) sense, raising the question: is estimating any valid transport map statistically easier than estimating the OT map? The author formalizes the problem in a minimax framework to analyze the sample complexity of estimating general valid transport maps, rather than restricting to the OT map. The key insight is that estimating any valid transport map remains at least as statistically hard as the Wasserstein distance estimation problem between distributions, which also lower bounds OT map estimation. However, this equivalence breaks down when the standard stability assumptions for OT maps do not hold. The paper provides explicit constructions showing that in unstable regimes, alternative valid (suboptimal) transport maps can be learned with significantly lower sample complexity than OT maps, with polynomial or even exponential separations. This establishes a rigorous foundation to understand when targeting suboptimal transport maps can yield improved statistical performance and explains the empirical success of generative models that do not explicitly optimize OT costs. The results unify and extend prior work on OT map estimation and provide new minimax lower bounds for flow matching and diffusion-based generative models.

Key findings

• Under classical stability assumptions (e.g. strong convexity and smoothness of Brenier potential), the minimax risk of estimating any valid transport map equals that of estimating the OT map up to a stability constant (Proposition 1).
• The valid transport map estimation risk is always lower bounded by the minimax squared Wasserstein distribution estimation risk (Lemma 3), implying no suboptimal map can be statistically easier in stable regimes.
• In a constructed two-component example on a benign source distribution (uniform on unit disk), the OT map estimation risk scales as ~1/n while the valid map estimation risk can scale as ~1/n^2, yielding a polynomial separation between these tasks (Theorem 1).
• In an adversarial source-target construction with many tiny components and exponentially small perturbations, the valid map risk scales as exp(-2n) while the OT map risk stays bounded away from zero, yielding an exponential separation (Theorem 2).
• The classical Hölder stability of OT maps (with exponent 1/6) prevents extreme instability on regular sources but does not rule out polynomial separations (Section 3.3.1).
• The framework yields new sample complexity lower bounds for generative model estimators whose outputs are maps or plans, including flow matching and diffusion models (Section 3.2).
• For distributions with densities in Besov balls on [0,1]^d, valid map estimation suffers from the curse of dimensionality with minimax lower bound of order n^{-2(1+s)/(d+2s)} for d≥2 (Corollary 1).
• Targeting a suboptimal transport map cannot improve minimax rates over OT map estimation in stable regimes, but can yield substantial gains in unstable regimes.

Threat model

The adversary is treated as nature choosing an unknown target distribution ν from a known regularity class, with the source distribution µ given and fixed. The adversary's capability is limited to selecting ν to maximize estimation risk, but does not control the samples beyond standard i.i.d. draws. The estimator observes n i.i.d. samples from ν and aims to learn a map pushing µ to ν. The adversary cannot corrupt data or provide non-i.i.d. samples. Stability assumptions limit how much small changes in ν perturb the OT map. No computational adversary or active attack is considered.

Methodology — deep read

The paper introduces a minimax statistical framework to study the estimation of valid transport maps between a known source distribution µ and unknown target distribution ν from n i.i.d. samples. The key steps are:

1. Threat Model & Assumptions: The adversary is nature providing target distributions ν from a regularity class. The estimator observes n samples from ν and knows µ. The goal is to estimate a measurable transport map T: Rd->Rd with T#µ=ν, that pushes µ to ν. Stability assumptions refer to the smoothness and strong convexity of Brenier potentials associated with the OT maps.

2. Data: The target distributions ν come from classes defined by smoothness conditions (e.g., Besov balls), with support in Rd or [0,1]^d. Samples Y_1,...,Y_n ~ i.i.d. ν are used to construct estimators.

3. Architecture/Algorithm: The paper is primarily theoretical and does not propose a new algorithm. Instead, it analyzes abstract estimators bT of transport maps and characterizes minimax risks. This includes deterministic transport maps and stochastic couplings.

4. Training Regime: Training details are not relevant here since the study is theoretical. The focus is on sample complexity (number of i.i.d. samples n) and minimax error rates.

5. Evaluation Protocol: The loss is defined as L_valid(bT) = inf_{T:#µ=ν} E[||bT(X) - T(X)||^2], measuring L2-distance from the estimator bT to the set of valid transport maps. This contrasts with the OT map loss L_OT comparing to a specific OT map T0. Risks are defined as expectations over sample randomness and distributions. Lower bounds are derived using classical minimax tools including two-point testing reductions and Assouad's lemma. The author analyzes stability inequalities linking OT map estimation risk and Wasserstein distribution estimation risk.

6. Reproducibility: The theoretical nature means no code/data release is relevant. The paper provides explicit constructions of source-target pairs to demonstrate statistical separations.

Example: For the two-component disk rotation example, the source µ is uniform on the unit disk in R^2. Two target distributions ν_0 and ν_θ are constructed by pushing µ via OT maps that rotate a separation hyperplane by a small angle θ. For θ ≈ κ/n, the author shows the OT map estimation error scales as 1/n while a certain valid transport map can be learned with risk ~1/n^2, demonstrating a polynomial advantage of non-OT maps in this setting. This derivation uses explicit geometric constructions and known stability estimates for OT maps.

Overall, the methodology applies classical statistical minimax theory combined with modern optimal transport regularity results to characterize the fundamental limits of valid transport map estimation.

Technical innovations

• Formulating the problem of estimating any valid transport map (not necessarily OT) in a minimax statistical framework with an appropriate projection loss.
• Showing under classical stability assumptions that estimating any valid transport map is statistically as hard as estimating the OT map, linking the two via Wasserstein distribution estimation risk.
• Constructing explicit source-target distribution pairs exhibiting polynomial and exponential separations between OT map and valid map estimation minimax risks to demonstrate when suboptimal maps can be learned substantially more efficiently.
• Deriving distribution estimation lower bounds that are applicable to contemporary generative modeling methods like flow matching and diffusion models by mapping their output to the valid transport map estimation framework.

Baselines vs proposed

• Under smoothness/convexity stability: Mvalid(N) ≍ MOT(N) up to stability constant (Proposition 1)
• Two-component uniform disk example: MOT(N_n) ≳ 1/n vs Mvalid(N_n) ≲ 1/n^2 (Theorem 1)
• Adversarial multi-block example: MOT(N_n) ≳ 1 vs Mvalid(N_n) ≲ exp(-2n), separation ≳ exp(2n) (Theorem 2)
• Smooth-density Besov class: Mvalid(N_s) ≳ n^{-2(1+s)/(d + 2s)} for d ≥ 2 (Corollary 1)

Limitations

• The main results rely on classical strong stability assumptions for equivalences; these assumptions often do not hold for real-world data distributions.
• The constructed separations use adversarial or artificial source-target distributions, which may not reflect typical data geometries in practice.
• Results focus on statistical limits and do not address computational complexity or practical algorithmic implementations or optimization issues.
• The framework emphasizes the metric of proximity to valid transport maps, which may not capture all relevant notions of quality in generative modeling (e.g., sample fidelity or likelihood).
• Extension to stochastic transport plans (as opposed to maps) is briefly considered but not analyzed in depth.
• One-dimensional cases are deferred to appendix, leaving multidimensional insights primary but some simplified cases less explored.

Open questions / follow-ons

• Can practical data-driven diagnostics be developed to characterize when optimal transport maps are stable or unstable for real-world datasets?
• What are the computational complexity trade-offs for finding valid suboptimal transport maps versus OT maps in high dimensions?
• How do design choices in diffusion and flow-based models implicitly regularize the learned transport maps to gain statistical advantages in unstable regimes?
• Can alternative loss functions better aligned with generative modeling goals (sample quality/diversity) be rigorously analyzed within this framework?

Why it matters for bot defense

For bot-defense practitioners focusing on CAPTCHA and bot-detection, this paper provides foundational insights into the statistical limits of learning transport maps used in generative modeling. Many CAPTCHA-breaking or bot-imitating approaches might rely on generating samples or transformations captured by transport maps or couplings. Understanding when estimating a valid transport map is as hard as the OT map, and when suboptimal maps can be learned with fewer samples, can inform defenses by assessing how difficult it is for adversaries to learn certain image or behavior transformations. Moreover, since diffusion models and flow matching methods implicitly learn transport maps, the lower bounds established here imply inherent sample complexity limitations that may translate to attack complexity. Recognizing regimes of instability where suboptimal estimators outperform optimal ones could guide the design of obfuscations or puzzles that exploit such instability to heighten attack difficulty. Overall, while the paper is theoretical and statistical, it offers a rigorous grounding for evaluating the feasibility and limits of transformation-based attack generative models relevant in bot-defense.

Cite

@article{arxiv2606_30574,
  title={ The Fundamental Limits of Valid Transport Map Estimation },
  author={ Sivaraman Balakrishnan },
  journal={arXiv preprint arXiv:2606.30574},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.30574}
}

Read the full paper

• arXiv:2606.30574 (abstract)
• arXiv:2606.30574 (PDF)