Optimal transport finds the cheapest way to move one probability distribution onto another. Under squared-distance cost, the answer is the gradient of a single convex function, the Brenier potential. Neural estimators learn this potential from samples. Each training step needs the potential's convex conjugate, $\phi^*(y)=\sup_x\{\langle x,y\rangle-\phi(x)\}$, an inner maximization over every point $x$. When the data are unbounded, as with Gaussian or heavy-tailed noise, that maximization ranges over all of $\mathbb{R}^d$ and becomes unstable. The current best answer, Stability and Oracle Inequalities for Optimal Transport Maps between General Distributions, restricts the maximization to a ball of radius $R$ that grows with the sample size. This works, but it adds a "sieve bias" term to the error bound and leaves $R$ to heuristics. Their analysis also needs $C^2$ activations such as tanh, and they state that ReLU-type networks are out of reach.
We propose to remove the sieve rather than tune it. The potential is parameterized as an explicit quadratic plus a two-layer network with the rectified quadratic unit $\mathrm{ReQU}(t)=\max(0,t)^2$. This class grows exactly as fast as Brenier potentials do, so it can be studied in the weighted function spaces of Global Universality of the Two-Layer Neural Network with the k-Rectified Linear Unit rather than on growing balls. The class has a global gradient-Lipschitz constant that can be read off the weights. And when a simple weight constraint holds, the maximizer of the conjugate provably lies in a ball whose radius is computed from the parameters and $y$. Inside that ball, the truncated conjugate equals the true conjugate, so the sieve bias is zero by construction rather than shrinking asymptotically.
Core Claim
Write the potential as $$\phi_\theta(x)=\tfrac{\lambda}{2}\|x\|^2+b^\top x+\sum_{j=1}^m a_j\,\mathrm{ReQU}(w_j^\top x+c_j).$$ Here $\lambda>0$ is a learned curvature floor, $b$ a linear term, and $(a_j,w_j,c_j)$ the hidden-unit weights. Each ReQU unit has a Hessian bounded by $2|a_j|\|w_j\|^2$. This gives two certificates. Strong convexity at infinity holds with modulus $\lambda_- = \lambda-2\sum_{a_j<0}|a_j|\|w_j\|^2$. Global smoothness holds with constant $\beta=\lambda+2\sum_j|a_j|\|w_j\|^2$.
Whenever $\lambda_->0$, every maximizer of $\langle x,y\rangle-\phi_\theta(x)$ lies in a ball of radius $r(y)=(\|y-b\|+C_\theta)/\lambda_-$, where $C_\theta$ is explicit in the bias terms. So computing the conjugate on that ball is exact, not an approximation.
We claim three things. First, the semi-dual objective computed this way has no sieve term. The oracle inequality then reduces to statistical error plus approximation error, with the approximation error measured in the weighted norm $\|f\|_{Y_2}=\sup_x |f(x)|/(1+\|x\|^2)$. Second, that weighted error converts to an error in expectation at the cost of only second moments of the data, because $\int|f-g|\,d\mu\le \|f-g\|_{Y_2}\int(1+\|x\|^2)d\mu$. This is weaker than the tail conditions behind the ball-sieve analysis. Third, the certified constant $\beta$ yields the standard map-stability inequality from smoothness, namely excess semi-dual risk $\ge \tfrac{1}{2\beta}\|\nabla\phi_\theta-\nabla\phi_0\|^2_{L^2(\mu)}$. This needs the gradient to be Lipschitz, which ReQU provides, and not $C^\infty$ activations. That answers the activation restriction Li et al. flag.
The estimated map is globally Lipschitz with constant $\beta$. It therefore has no singular set, and pushing perturbed inputs through it is Lipschitz-stable. This sidesteps the Hölder-1/3 barrier that Quantitative Stability of the Pushforward Operation by an Optimal Transport Map proves for non-smooth potentials on compact domains. It holds for the estimator, not for arbitrary convex potentials.
Relation to Prior Work
Li et al. supply the semi-dual estimation setup and the error decomposition we reuse. We differ in removing the truncation term and in replacing tanh with a growth-matched, piecewise-polynomial unit. Hatano et al. prove that ReLU$^k$ spans are dense in $Y_k(\mathbb{R})$ in one dimension through the isometry $f\mapsto f/(1+|x|^k)$. We need a $d$-dimensional version for ridge sums plus a quadratic, together with control of the gradient in a weighted norm. Extending their result is one theoretical deliverable and the place we expect the most difficulty.
An Approximation Theory Framework for Measure-Transport Sampling Algorithms motivates the project. It shows that ReLU networks and Hermite expansions approximate transport maps on all of $\mathbb{R}^d$ under Gaussian reference measures, but it has no finite-sample statistics. Our oracle inequality is an attempt at that missing statistical half for the potential-based estimator.
Quantitative stability of optimal transport maps under variations of the target measure acts as a constraint. Its Hölder bounds need a source density bounded below on a compact convex set, so we do not inherit them for Gaussian sources. We only claim stability of the estimator class, not of the true map.
Research Program
The theory has three parts, in order of confidence. The first is the localization lemma and the exact-conjugate statement; this is elementary, and we expect it to hold cleanly. The second is the sieve-free oracle inequality under finite second moments plus a moment condition for the empirical-process term. Here we reuse Li et al.'s statistical machinery with weighted covering numbers of the ReQU class. The third is weighted density and, for targets whose residual potential has a finite Barron-type spectral norm, an approximation rate in $Y_2(\mathbb{R}^d)$. We will report honestly if the rate degrades with dimension.
The algorithm computes the conjugate by projected gradient ascent on the certified ball. Because the inner problem is strongly concave once $\lambda_->0$, it converges linearly. A barrier on $\lambda_-$ keeps the certificate valid during training.
There is one real expressivity limit. A potential with quadratic growth gives a map that grows at most linearly. Maps from a Gaussian source to a heavy-tailed target grow superlinearly, and neither this class nor quadratic-plus-tanh captures them. We restrict the claims to targets whose maps are asymptotically linear in each direction, where the true potential is in $Y_2$. We also test $k=3$ separately as an exploratory extension, without a certificate.
Baselines
The naive reference point is the closed-form Gaussian (Bures) map: the affine map between the empirical means and covariances. It costs nothing, is exact for Gaussian pairs, and is linear at infinity. Any learned method that fails to beat it on tail-stratified error has learned nothing about the tails.
The strongest existing method on this exact question is Li et al.'s sieved tanh estimator. It is the only method in the file with finite-sample guarantees for unbounded, heavy-tailed OT, and it is reported to beat standard dual estimators on Student's $t_6$ in up to 20 dimensions. The file gives no numerical error values for that experiment; no reported result was found on Lacuna for the sieved estimator's error on the $t_6$ benchmark. We will therefore rerun it ourselves. It gets the same samples, the same parameter count, the same number of inner conjugate steps, and an equal hyperparameter search budget, with its radius $R$ given its own grid of values. We beat it if tail-stratified map error is lower, at equal or lower total compute, across sample sizes, with non-overlapping seed intervals.
For the broader neural-solver field we use input-convex neural network solvers as evaluated in Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark. That paper reports $L^2$ unexplained variance above 70% for many popular solvers in dimension 64. Exact per-solver values are not in the file, so we will rerun the input-convex solvers under our protocol.
Two ablations isolate the key ingredients. The first keeps the ReQU parameterization but replaces the certified ball with a fixed heuristic radius. This tests whether exactness of the conjugate matters, or whether the activation does all the work. The second keeps the certified quadratic floor but swaps ReQU for tanh residuals. This tests whether growth-matched, direction-dependent asymptotics matter.
Why not just…?
Why not just keep the sieve and tune $R$ by validation? This is a real competitor. In Gaussian-tailed problems a well-tuned radius may match us, because the mass outside a large ball is negligible. Li et al. show that the radius trades bias against variance and has no principled rule. Our first ablation separates the two cases directly. If a validation-tuned $R$ matches the certified ball at equal compute on heavy-tailed sources, we will report the contribution as theoretical, namely a cleaner bound, rather than practical.
Why not just add a quadratic to a tanh network? This is the most serious threat. It already provides quadratic growth, a bounded Hessian, and the same localization certificate. What it cannot do is produce maps whose asymptotic slope differs by direction, because a tanh residual has bounded gradient. Consider the map from $\mathcal{N}(0,1)$ to an asymmetric split-normal target, which has different scales on each side. That map is exactly piecewise linear with two slopes: one quadratic plus one ReQU unit represents it exactly, while quadratic plus tanh can only match it on a bounded region. Under a Gaussian source the tail mass is tiny, so this advantage may not show in $L^2(\mu)$. We therefore predict the gap appears mainly under heavy-tailed sources and in extrapolation beyond the training range. If it does not appear there, the ReQU choice is unjustified and we will say so.
Why not just use an input-convex network with a smooth activation? Convexity by design is attractive, but Korotin et al. report the map-recovery failures above in 64 dimensions. These networks also give no explicit control of growth or of the localization radius. We include them to measure whether certified localization improves on convexity alone.
Proposed Experiments
Pairs with known optimal maps. Following the construction of Korotin et al., we create pairs with known ground-truth maps. We pick a source $P$, either $\mathcal{N}(0,I_d)$ or a Student's $t_6$, and a known convex potential $\psi$ with direction-dependent quadratic growth, built as a quadratic plus a few nonnegative ReQU ridges plus a softplus term. We then set $Q=(\nabla\psi)_\#P$ for $d\in\{2,8,20,64\}$. We also run Li et al.'s $t_6$-to-$t_6$ setup up to $d=20$ and the Gaussian-mixture pairs of the Wasserstein-2 benchmark, where the tails are mild, as a check that nothing regresses.
Metrics. We report $L^2$ unexplained variance overall and stratified by shells of $\|x\|$ at the 90th, 99th and 99.9th source quantiles. We also report the weighted sup error of the potential on held-out points, the gap between the computed and true conjugate, and wall-clock time.
Decisive checks. Three results decide the project. The first is that the certified ball's conjugate gap is at numerical precision, while the fixed-radius ablation shows a gap that grows with the tail index. The second is that, on heavy-tailed sources and asymmetric targets, quadratic-plus-ReQU beats both the sieved tanh estimator and quadratic-plus-tanh on outer-shell error, with the advantage growing with sample size. The third is that error versus sample size, on a log-log plot, falls with a slope consistent with the oracle inequality's statistical-plus-approximation rate, showing no plateau from a truncation term.
If the second check fails while the first holds, the paper becomes a result about exact conjugates. If both fail, sieving is adequate in practice, and that is worth knowing too.
References
- Stability and Oracle Inequalities for Optimal Transport Maps between General Distributions
- Global Universality of the Two-Layer Neural Network with the<a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"><a:mi>k</a:mi></a:math>-Rectified Linear Unit
- Quantitative Stability of the Pushforward Operation by an Optimal Transport Map
- An approximation theory framework for measure-transport sampling algorithms
- Quantitative stability of optimal transport maps under variations of the target measure
- Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark