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

May 19, 2026

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

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

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

Ask PDF

Mar 30, 2026

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

We study training-free flow matching between two Gaussian mixture models (GMMs) using explicit velocity fields that transport one mixture into the other over time. Our baseline approach constructs component-wise Gaussian paths with affine velocity fields satisfying the continuity equation, which yields to a closed-form surrogate for the pairwise kinetic transport cost. In contrast to the exact Gaussian Wasserstein cost, which relies on matrix square-root computations, the surrogate admits a simple analytic expression derived from the kinetic energy of the induced flow. We then analyze how closely this surrogate approximates the exact cost. We prove second-order agreement in a local commuting regime and derive an explicit cubic error bound in the local commuting regime. To handle nonlocal regimes, we introduce a path-splitting strategy that localizes the covariance evolution and enables piecewise application of the bound. We finally compare the surrogate with an exact construction based on the Gaussian Wasserstein geodesic and summarize the results in a practical regime map showing when the surrogate is accurate and the exact method is preferable.

Elham Rostami, Taous-Meriem Laleg-Kirati, Hamidou Tembine

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

Flow Matching Optimal Transport Surrogate Modeling Wasserstein Distance Gaussian Mixture Models

Ask PDF

Feb 11, 2026

Convergence Rates for Distribution Matching with Sliced Optimal Transport

We study the slice-matching scheme, an efficient iterative method for distribution matching based on sliced optimal transport. We investigate convergence to the target distribution and derive quantitative non-asymptotic rates. To this end, we establish Lojasiewicz-type inequalities for the Sliced-Wasserstein objective. A key challenge is to control along the trajectory the constants in these inequalities. We show that this becomes tractable for Gaussian distributions. Specifically, eigenvalues are controlled when matching along random orthonormal bases at each iteration. We complement our theory with numerical experiments and illustrate the predicted dependence on dimension and step-size, as well as the stabilizing effect of orthonormal-basis sampling.

Gauthier Thurin, Claire Boyer, Kimia Nadjahi

ENS-PSL · CNRS, ENS Paris, France · LMO, IUF, CELESTE +2

Distribution Matching Sliced Wasserstein Distance Optimal Transport

Ask PDF

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