Honest Confidence Bounds on Wasserstein Distance via Mollification

Wasserstein distance measures how far one probability distribution must be moved, mass by mass, to become another. It is widely used in machine learning, but it is hard to do statistics with it. Estimated from samples in dimension $d$, it converges at the slow rate $n^{-1/d}$. Its systematic error (bias) shrinks more slowly than its random fluctuations, so a confidence interval built naively around the sample estimate misses the true distance in high dimensions. Smoothing both distributions with the same small blurring kernel, called a mollifier, fixes the rate: Gaussian-smoothed OT and the smooth p-Wasserstein distance converge at $n^{-1/2}$ in any dimension, and limit distribution theory for smooth p-Wasserstein distances gives Gaussian limits and a valid bootstrap. The cost is that these results describe a different quantity, the distance between the blurred distributions. The step from that quantity back to the true distance, which needs a bandwidth that shrinks with $n$, is listed there as open.

This proposal does not attack that shrinking-bandwidth problem head on. It relies on a simple fact: blurring two distributions with the same kernel can only bring them closer. The smoothed distance at any fixed bandwidth is therefore a lower bound on the true Wasserstein distance. It can be estimated at the parametric rate, and it comes with the existing bootstrap theory. We turn this into a one-sided confidence bound on the unsmoothed distance that holds in every dimension. We then tighten it by searching over many bandwidths at once with a joint bootstrap. Finally, we close it from above with an entropic upper bound, which gives a two-sided interval that needs no bias correction.

Core Claim

Let $P,Q$ be distributions on $\mathbb{R}^d$ and let $\eta_\sigma$ be any mollifier of width $\sigma$. Couple $X\sim P$ and $Y\sim Q$ optimally, then add the same noise draw $Z\sim\eta_\sigma$ to both. This shows

$$W_p(P*\eta_\sigma,\,Q*\eta_\sigma)\;\le\;W_p(P,Q)\quad\text{for all }\sigma>0,\ p\ge 1.$$

For the Gaussian family the bound is also nonincreasing in $\sigma$, because $\mathcal{N}_{\sigma_2}=\mathcal{N}_{\sigma_1}*\mathcal{N}_{\sqrt{\sigma_2^2-\sigma_1^2}}$. The inequality is about population quantities, so it carries no sampling bias.

The claim is that combining this inequality with fixed-bandwidth limit theory gives a lower confidence bound on $W_p(P,Q)$ with the following properties:

  • It is asymptotically valid at the parametric rate in any dimension.
  • It can be tightened adaptively by maximizing over a grid of bandwidths.
  • It becomes a two-sided interval when paired with an upper bound from entropic OT. Entropic OT regularizes the transport plan rather than the distributions. The transport cost of the entropic plan $\pi_\epsilon$, written $\langle c,\pi_\epsilon\rangle$ (the cost function $c$ integrated against $\pi_\epsilon$), can never fall below the unregularized optimum $W_2^2(P,Q)$, because $\pi_\epsilon$ is just one feasible plan.

As far as the research file shows, prior smoothed-OT inference only targets the blurred distance at one fixed $\sigma$. This proposal instead targets the unblurred distance, using monotonicity as the bridge.

Research Program

Multi-bandwidth lower bound. The first theoretical step extends the delta-method argument of Goldfeld, Kato, Nietert and Rioux from one bandwidth to a finite grid $\sigma_1<\dots<\sigma_K$. That paper proves the smoothed distance is Hadamard directionally differentiable along the dual Sobolev space matched to Gaussian smoothing, and that the bootstrap is consistent. Stacking $K$ such functionals should give a joint Gaussian limit under the alternative $P\neq Q$.

The statistic is

$$L_n=\max_{k\le K}\Big(\widehat W^{(\sigma_k)}_p-\hat c_{k}\,n^{-1/2}\Big).$$

Here $\widehat W^{(\sigma_k)}_p$ is the empirical smoothed distance at bandwidth $\sigma_k$. The offsets $\hat c_k$ are set from the joint bootstrap so that all $K$ lower bounds hold at once with probability $1-\alpha$. This is the same simultaneous-calibration idea that MMDAgg uses across kernel bandwidths, carried over from testing to estimation. Small $\sigma$ gives a tight but noisy bound, and large $\sigma$ gives a loose but stable one. The maximum picks the best trade-off from the data, with no tuning.

We will also study a slowly growing grid ($K_n\to\infty$ with $\sigma_1\to 0$). This connects to the open shrinking-bandwidth question without having to resolve it: the procedure stays valid whatever the grid, and only its tightness depends on how fast $\sigma_1$ can shrink. That in turn depends on the dimension-exponential Sobolev constants noted by Nietert, Goldfeld and Kato.

Upper bound and sandwich. For $p=2$ we pair the lower bound with an upper confidence bound on the entropic plan cost $\langle c,\pi_\epsilon\rangle$. Limit theorems for entropic OT maps and Sinkhorn divergence supply Hadamard differentiability of the entropic potentials. Mena and Weed supply dimension-free $n^{-1/2}$ rates for sub-Gaussian distributions. Together they should yield a CLT for the plan cost, which is a smooth functional of the potentials. That derivation is new work, not a citation. The resulting interval is $[L_n, U_n]$. Its width shrinks only as far as the gap between the two regularizations allows, and measuring that gap empirically is part of the study.

Other mollifiers. Gaussian smoothing leaks mass past the boundary on compact domains (gap 4 in the file). The contraction inequality holds for any mollifier, so we will also test compactly supported blob kernels of the kind used by Craig et al.. The inequality carries over unchanged for them; the delta-method step does not, and whether it can be redone for compact kernels is an open question.

Computation. Estimating the smoothed distance requires drawing noise copies of each sample and then solving a discrete OT problem. Finite noise draws push the estimate upward, which could break the lower-bound direction. To guard against this, we refresh the noise draws inside every bootstrap replicate, so that computational error is folded into the reported uncertainty. We will measure how many copies per point are needed before this effect is negligible next to $n^{-1/2}$.

Baselines

Naive reference. The first baseline is the plug-in empirical $W_2(P_n,Q_n)$ with a percentile bootstrap interval. Most practitioners do this, and it is exactly what the del Barrio–Loubes theory warns against in $d\ge 4$: the fluctuations are asymptotically normal, but they are centered at a biased mean. It is run on the same samples with the same number of bootstrap replicates. We beat it if our lower bound holds its nominal coverage while the naive interval's coverage of the true $W_2$ collapses as $d$ grows.

Strongest existing method. The single fixed-$\sigma$ smoothed distance with the bootstrap of Goldfeld et al., read as a lower bound. It is the natural competitor because it already has everything except bandwidth adaptivity. We give it its best case: $\sigma$ is chosen by an oracle, meaning the grid value that is tightest in hindsight, with the same solver and noise budget. Beating it means that our data-driven maximum comes within a small margin of the oracle single $\sigma$, and is clearly tighter than any $\sigma$ fixed in advance. The file contains no reported coverage or tightness numbers for this method (no reported result found on Lacuna for smoothed-OT confidence-interval coverage).

Competing lower bound. Sliced Wasserstein is also a lower bound on $W_p$. Its process-level limit theory makes calibrated lower bounds cheap to build. We compute both the average-over-directions and the max-over-directions versions under the same bootstrap. Beating it means a larger valid lower bound on the same data.

Ablation. The multi-bandwidth maximum is compared with a Bonferroni-corrected maximum and with each single $\sigma$. This isolates the value of joint calibration. Separately, the sandwich is compared with the lower bound alone, which isolates what the entropic side adds.

For the secondary testing experiment on MNIST digit abundance shifts at $n=500$, the strongest reported number is test power 1.000 for the kernel projected Wasserstein test, against 0.782 for linear projected Wasserstein (Two-Sample Test with Kernel Projected Wasserstein Distance). Testing is not our main target, and we expect at most to match these figures.

Why not just…?

Why not just use the fixed-bandwidth smoothed distance and stop? If the goal is only to test whether $P=Q$, this is enough, and we say so: every $W_p^{(\sigma)}$ is already a metric. The difference arises when the quantity of interest is the unsmoothed distance itself, for example a transport cost with physical units, or a fairness or drift threshold defined in $W_2$. Then a single fixed $\sigma$ gives a bound whose looseness is unknown and chosen arbitrarily. The oracle-$\sigma$ baseline measures exactly how much the adaptive maximum gains.

Why not just use entropic OT and extrapolate the regularization to zero? This is the real threat. Debiased Sinkhorn divergence has mature limit theory (Goldfeld et al.), and extrapolating to $\epsilon\to 0$ may give point estimates with small bias. However, the extrapolation rests on smoothness assumptions and gives no guaranteed direction of error. The semidiscrete analysis in Approximation rates of entropic maps shows that the $\epsilon\to 0$ behavior depends delicately on the geometry. Our proposal therefore uses entropic OT for the one-sided guarantee it does give, an upper bound, rather than competing with it. We will run $\epsilon$-extrapolated intervals as an extra baseline. If they reach nominal coverage with narrower width on the non-smooth cases (the uniform hypercubes), the sandwich's value reduces to its assumption-free guarantee, and we will report that.

Why not just use sliced Wasserstein as the lower bound? It is cheaper and equally valid. However, a projection onto one line discards any difference that no single direction reveals. The 0.782 power of linear projection on MNIST (KPW paper) is indirect evidence of how much such projections miss. Smoothing keeps the full geometry. The decisive check is the ratio of each lower bound to the true $W_2$ on anisotropic Gaussians and mixtures. If max-sliced matches the smoothed bound, the mollifier adds nothing for this purpose.

Why not just use MMD? An MMD gives no bound on $W_2$ in the needed direction. The Sobolev MMD proxy of Nietert et al. lies above $W_2^{(\sigma)}$, and the authors themselves report that it is loose.

Proposed Experiments

The primary testbed uses Gaussian pairs with random means and covariances in $d\in\{5,10,50,100\}$. For these, $W_2$ has a closed form, so coverage and tightness can be measured exactly. We then add two families from the literature: uniform distributions on hypercubes at $d=5,10,100$ as in Goldfeld and Greenewald, and Gaussian mixtures as in Nietert et al.. For these the true distance is approximated by exact OT on very large samples in low $d$. In high $d$ we check only the lower-bound property against a certified upper bound from a known coupling.

The metrics are:

  • empirical coverage of the lower bound, $L_n$, and of the interval $[L_n, U_n]$ at the 95% nominal level, over 500 repetitions;
  • tightness, measured as $L_n/W_2$ and as interval width;
  • runtime, compared at matched noise and bootstrap budgets.

The results that would refute or confirm the proposal are three. First, whether coverage holds at $d=100$, where the naive interval should fail. Second, whether the adaptive maximum comes within 10% of the oracle single-$\sigma$ bound. Third, whether it exceeds max-sliced Wasserstein on the anisotropic cases. The MNIST abundance-shift test is a secondary sanity check.