SRRM: Improving Recursive Transport Surrogates in the Small-Discrepancy Regime

Yufei Zhang; Tao Wang; Jingyi Zhang

stat.MLMar 19, 2026

SRRM: Improving Recursive Transport Surrogates in the Small-Discrepancy Regime

Authors: Yufei Zhang, Tao Wang, Jingyi Zhang

Organizations: School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China · Institute of Statistics and Big Data, Renmin University of China, Beijing, China · Key Laboratory of Mathematics and Information Networks (Beijing University of Posts and Telecommunications), Ministry of Education, Beijing, China

Abstract

Recursive partitioning methods provide computationally efficient surrogates for the Wasserstein distance, yet their statistical behavior and their resolution in the small-discrepancy regime remain insufficiently understood. We study Recursive Rank Matching (RRM) as a representative instance of this class under a population-anchored reference. In this setting, we establish consistency and an explicit convergence rate for the anchored empirical RRM under the quadratic cost. We then identify a dominant mismatch mechanism responsible for the loss of resolution in the small-discrepancy regime. Based on this analysis, we introduce Selective Recursive Rank Matching (SRRM), which suppresses the resulting dominant mismatches and yields a higher-fidelity practical surrogate for the Wasserstein distance at moderate additional computational cost.

Figures & tables

Panel of Figure 1 — Figure 1.1 : The last-mile phenomenon of recursive partitioning methods.

Figure 2.1 : (a) Samples of the source and target distributions. (b) Illustrations of how various distance metrics change as $\alpha$ increases. (c) Comparisons of different distance metrics in terms of runtime.

Figure 2.2 : Hilbert space-filling curve Visualization.

Figure 2.3 : Samples of the distributions and illustrations of how various distance metrics change.

Figure 2.4 : Samples of the last-mile problem.

Panel of Figure 4 — Figure 4.1 : An illustration of Alg. 1 when $d=2$ . (a) Source data points (blue) and target data points (red). (b) axis-aligned recursive partitioning. (c) connect corresponding points.

Panel of Figure 5 — Figure 5.1 : When the absolute slope $|m|$ of the red and blue lines tends to zero or infinity, almost all sampled points become bad indices. However, the severity of the resulting mismatches differs between the two regimes.

$t$	$\\|m_{1}-m_{2}\\|$	Metric	iter00	iter01	iter02	iter03	iter04	iter05	iter06	iter07	iter08	iter09	iter10
0.000	0.8485	$\|I_{+}\|$	$1498.50\pm 12.28$	$1123.80\pm 8.15$	$847.80\pm 9.02$	$637.60\pm 13.53$	$477.10\pm 10.52$	$358.40\pm 9.32$	$268.50\pm 8.40$	$204.80\pm 7.24$	$156.20\pm 3.16$	$119.00\pm 4.32$	$119.00\pm 4.32$
0.111	0.7542	$\|I_{+}\|$	$1498.10\pm 9.33$	$1118.10\pm 6.14$	$844.10\pm 9.77$	$632.00\pm 10.26$	$472.00\pm 11.38$	$354.20\pm 14.61$	$268.10\pm 11.24$	$203.40\pm 9.80$	$154.00\pm 8.73$	$117.80\pm 7.60$	$117.80\pm 7.60$
0.222	0.6600	$\|I_{+}\|$	$1495.80\pm 12.42$	$1118.10\pm 13.28$	$843.60\pm 17.55$	$631.40\pm 15.01$	$476.00\pm 6.85$	$359.00\pm 6.60$	$266.70\pm 6.95$	$198.10\pm 5.59$	$149.00\pm 4.90$	$112.20\pm 4.94$	$112.20\pm 4.94$
0.333	0.5657	$\|I_{+}\|$	$1498.50\pm 16.95$	$1119.40\pm 14.86$	$842.20\pm 11.43$	$630.00\pm 10.30$	$469.20\pm 6.89$	$351.30\pm 6.45$	$263.70\pm 4.88$	$194.60\pm 6.42$	$147.00\pm 7.85$	$109.80\pm 8.39$	$109.80\pm 8.39$
0.444	0.4714	$\|I_{+}\|$	$1494.20\pm 11.56$	$1119.30\pm 13.95$	$850.00\pm 15.38$	$634.10\pm 10.79$	$477.40\pm 10.67$	$358.40\pm 8.40$	$268.30\pm 9.07$	$202.60\pm 9.73$	$151.90\pm 7.37$	$115.80\pm 5.65$	$115.80\pm 5.65$
0.556	0.3771	$\|I_{+}\|$	$1498.50\pm 12.58$	$1123.30\pm 14.86$	$843.30\pm 16.85$	$630.10\pm 12.36$	$467.70\pm 11.44$	$352.10\pm 10.68$	$264.10\pm 8.40$	$197.30\pm 8.62$	$145.40\pm 7.03$	$108.40\pm 7.34$	$108.40\pm 7.34$

Table 5.1 : Statistics of

|I_{+}|

over iterations.

Panel of Figure 6 — Figure 6.1 : Robustness analysis of SRRM under different parameter settings.

Method	n=100	n=200	n=500	n=1000	n=2000	n=100	n=200	n=500	n=1000	n=2000
	Accuracy (%)					CPU time(s)
SRRM	80.4 $\pm$ 3.7	82.6 $\pm$ 2.9	84.7 $\pm$ 2.7	85.7 $\pm$ 2.6	85.5 $\pm$ 2.6	41.6	92.9	250.9	545.8	1181.5
BSP	78.9 $\pm$ 3.6	82.9 $\pm$ 2.6	84.8 $\pm$ 2.6	84.6 $\pm$ 3.2	85.2 $\pm$ 2.8	83.8	184.8	512.7	1102.7	2427.5
HCP	73.6 $\pm$ 2.9	78.8 $\pm$ 2.9	81.8 $\pm$ 3.3	82.0 $\pm$ 2.9	82.6 $\pm$ 2.8	10.2	17.9	51.9	120.6	240.3
SW	70.3 $\pm$ 4.1	73.1 $\pm$ 3.6	76.2 $\pm$ 4.4	76.7 $\pm$ 4.1	77.4 $\pm$ 3.9	94.9	159.7	365.0	764.5	1653.4
GSW(Poly5)	70.1 $\pm$ 3.3	72.9 $\pm$ 3.9	75.9 $\pm$ 4.4	77.0 $\pm$ 3.5	/	782.8	986.2	1541.9	2334.6	/

Table 6.1 : Comparisons on 3D Point Cloud Classification

Surrogate Modeling

Surrogate modeling builds faster or more interpretable approximations of expensive simulations and black-box models.

See all 226 papers

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized Sketching Approximation Algorithms
Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101
An Explicit Surrogate for Gaussian Mixture Flow Matching with Wasserstein Gap Bounds
Mar 30, 2026Elham Rostami, Taous-Meriem Laleg-Kirati, Hamidou TembineFlow Matching Optimal Transport
Université Paris-Saclay, Inria, CIAMS, Gif-sur-Yvette, 91190, France · Department of Electrical Engineering and Computer Science, University of Quebec in Trois-Rivieres (UQTR), Quebec, Canada
Convergence Rates for Distribution Matching with Sliced Optimal Transport
Feb 11, 2026Gauthier Thurin, Claire Boyer, Kimia NadjahiDistribution Matching Sliced Wasserstein Distance
ENS-PSL · CNRS, ENS Paris, France · LMO, IUF, CELESTE +2

May 19, 2026J/K move · Enter open · S save

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Peter Matthew Jacobs, Jeff M. Phillips

Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

Randomized Sketching Approximation Algorithms Optimal Transport Wasserstein Distance

Open paper AskPDF arXiv

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size

n

from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems

\left( d \in \{2,3\} \right)

, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of

n

and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to

ε

-additive error in expectation with respect to the sampling; we allow

O(1)

computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under

α

-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate

W_2^2(P,Q)

within

ε

error in

ε^{-\max(2,\frac{d+1+o(1)}{1+α})}

time for

0 < α< 1

Hölder smooth distributions

P,Q

(0,1)^{d}

; an optimal

Θ(ε^{-2})

for

α> 1/2

when

d=2

and nearly optimal as

α\to 1

when

d = 3

Abstract

Surrogate Modeling

Explore similar work

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

An Explicit Surrogate for Gaussian Mixture Flow Matching with Wasserstein Gap Bounds

Convergence Rates for Distribution Matching with Sliced Optimal Transport