Computational and Statistical Guarantees of the \textit{c}-Rectified flow

COMPUTATIONAL AND STATISTICAL GUARANTEES OF THE C-RECTIFIED FLOW B Y L EDA WANG1,a , Z HEHAO X U1,b , Q IANG L IU2,d AND H ARRISON H. Z HOU1,c 1 Department of Statistics and Data Science, Yale University, a leda.wang@yale.edu; b zhehao.xu@yale.edu; c huibin.zhou@yale.edu

arXiv:2608.02487v1 [stat.ML] 3 Aug 2026

2 Department of Computer Science, University of Texas at Austin, d qiang.liu.research@gmail.com

Recently, rectified flow has emerged as a fundamental framework for large-scale image generation, powering state-of-the-art systems such as FLUX.1 and Stable Diffusion 3. Despite its remarkable empirical success, the computational and statistical guarantees of iterative rectified flow have remained largely unexplored. We address this problem by studying c-rectified flow, a cost-aware class of rectified flow that projects velocity fields onto a gradient class while preserving endpoint marginals. The ordinary rectified flow can fail to recover the optimal transport coupling: in a Gaussian case study, the iteration converges to the optimal coupling if and only if the source and target covariance matrices commute. In contrast, under suitable compactness and uniform-integrability assumptions, iterative c-rectified flow always converges to the optimal transport coupling. We further establish quantitative one-step contraction and exponential convergence guarantees under projection-stability assumptions for both quadratic and strongly convex displacement costs. Finally, under a Hölder ball assumption, we develop new minimax-optimal score estimation rates and show that, when combined with iterative c-rectified flow, they yield a rate-optimal estimator of the optimal transport for the dimension d ≥ 3 and a nearly parametric rate for d = 1, 2.

CONTENTS 1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Optimal Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Statistical Property for Optimal Transport . . . . . . . . . . . . . . . . . . . 2.3 Rectified Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 c-Rectified Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 The Convergence of c-Rectified Flow . . . . . . . . . . . . . . . . . . . . . 2.5.1 Quadratic Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Computational Guarantee of c-Rectified Flow . . . . . . . . . . . . . . . . . . . . 3.1 The Failure of Rectified Flow: Gaussian Case Study . . . . . . . . . . . . . . 3.2 Convergence Rates for c-Rectified Flow with Gaussian Marginals . . . . . . 3.2.1 One Step Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Iterating the One-step Contraction . . . . . . . . . . . . . . . . . . . 3.3 A General Contraction Criterion for c-Rectified Flow . . . . . . . . . . . . . 3.3.1 Assumptions and Main Results . . . . . . . . . . . . . . . . . . . . MSC2020 subject classifications. Primary 49Q22, 62G05; secondary 68T07. Keywords and phrases. optimal transport, rectified flow, statistical estimation, convergence rates.

1

3 4 4 6 6 6 6 7 7 8 8 8 9 9 10 11 11 12 12

2

3.3.2 Local Validity of the Projection Bound . . . . . . . . . . . . . . . . 3.3.3 Iterating the One-step Contraction . . . . . . . . . . . . . . . . . . . 4 Statistical Guarantee of c-Rectified Flow . . . . . . . . . . . . . . . . . . . . . . . 4.1 Score Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Setup and main statistical results . . . . . . . . . . . . . . . . . . . . 4.2 Application: Optimal Estimation of Optimal Transport . . . . . . . . . . . . 5 General Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Convergence of c-Rectified Flow under General Cost . . . . . . . . . . . . . 5.2 Contraction Beyond Quadratic Loss . . . . . . . . . . . . . . . . . . . . . . 5.3 Estimation for General Cost . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Additional Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.0.0.1 Flow-based estimation and bridge methods. . . . . . . . . A.0.0.2 Score-based estimation and sampling. . . . . . . . . . . . A.0.0.3 Entropic statistical optimal transport. . . . . . . . . . . . . B Additional Details for Section 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1 Additional optimal-transport facts . . . . . . . . . . . . . . . . . . . . . . . B.2 Statistical OT background . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Statistical Property for Optimal Transport . . . . . . . . . . . . . . . . . . . B.4 Additional rectified-flow facts . . . . . . . . . . . . . . . . . . . . . . . . . B.5 Additional c-rectified-flow facts . . . . . . . . . . . . . . . . . . . . . . . . B.5.0.1 Marginal-preserving vector fields. . . . . . . . . . . . . . B.5.0.2 c-Rectified duality formulation. . . . . . . . . . . . . . . . B.5.0.3 Stationary points of c-rectified flow. . . . . . . . . . . . . B.5.0.4 Decrease of transport cost. . . . . . . . . . . . . . . . . . C Proof of Section 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D Proof of Section 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.1 Proof of Section 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E Proof of Section 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.0.1 Technical Preparation . . . . . . . . . . . . . . . . . . . . . . . . . E.0.1.1 Factorization of linear transports. . . . . . . . . . . . . . . E.0.1.2 Projection of linear fields. . . . . . . . . . . . . . . . . . E.0.2 Explicit c-Rectified Flow Framework in the Gaussian Case . . . . . . E.0.3 Quantitative Variational Lower Bound for One-step c-Rectified Flow E.0.4 Spectral Criterion for the Projection Bound. . . . . . . . . . . . . . . E.0.4.1 Verification under a spectral gap. . . . . . . . . . . . . . . E.0.5 Cost-difference Lemma and Contraction. . . . . . . . . . . . . . . . F Proof of Section 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.1 Projection Estimates Along the Interpolation . . . . . . . . . . . . . . . . . F.2 Proof of the Contraction Criterion . . . . . . . . . . . . . . . . . . . . . . . G Proof of Section 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H Proof of Section 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.1 Smoothing identities and score reduction . . . . . . . . . . . . . . . . . . . . H.2 Upper bound for Theorem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . H.3 Lower bound for Theorem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . H.3.0.1 Low noise . . . . . . . . . . . . . . . . . . . . . . . . . . H.3.0.2 Intermediate noise . . . . . . . . . . . . . . . . . . . . . . H.3.0.3 Large noise . . . . . . . . . . . . . . . . . . . . . . . . . H.4 Projection and the resulting sampler rate . . . . . . . . . . . . . . . . . . . . I Proof of Section 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 14 14 14 15 16 18 18 19 21 21 22 22 22 22 23 23 24 24 25 26 26 26 27 27 27 29 32 33 33 33 33 35 36 37 38 39 41 41 43 45 47 47 47 52 52 53 55 55 58 59

COMP & STAT GUARANTEES OF C-RECT FLOW

3

1. Introduction. Rectified flow, introduced by Liu, Gong and Liu (2022), is a simple and effective framework for learning continuous-time transports between distributions. Its least-squares training objective is readily implemented with neural networks, while iterative reflow straightens transport trajectories and enables accurate generation with few discretization steps. Closely related formulations such as flow matching Lipman et al. (2023) and stochastic interpolants Albergo, Boffi and Vanden-Eijnden (2023) have further established regression-based probability flows as a general framework for generative modeling. The original rectified-flow experiments demonstrated strong performance in image generation, image-to-image translation, and domain adaptation Liu, Gong and Liu (2022); InstaFlow subsequently used reflow to construct a one-step text-to-image generator Liu et al. (2024). At a much larger scale, rectified-flow transformers have become a practical foundation for high-resolution image synthesis: Stable Diffusion 3 scales this architecture with a multimodal transformer Esser et al. (2024), while the FLUX.1 family places flow matching at the core of large text-to-image and in-context image-generation systems Black Forest Labs (2025). These developments make rectification more than a device for simplifying simulation and motivate a deeper understanding of the transport coupling from the procedure. Yet the computational and statistical guarantees of iterative rectified flow have remained largely unexplored. We study this question in the following statistical setting. Suppose that we observe two independent samples i.i.d.

X1 , . . . , Xn ∼ P,

i.i.d.

Y1 , . . . , Yn ∼ Q,

where the endpoint distributions P and Q are unknown. Our goal is to estimate the optimal transport map T ∗ from P to Q, namely the cost-minimizing measurable map satisfying T# P = Q. The statistical objective is to construct an estimator Tbn whose L2 (P )-risk relative to T ∗ attains the optimal rate over the distribution classes specified later. In the one-dimensional setting, the connection between rectified flow and optimal transport is particularly interesting. Under rectifiability assumptions that guarantee uniqueness of the defining ODE, trajectories issued from two ordered initial points cannot cross at a common time: otherwise two ODE solutions would pass through the same space–time point, contradicting uniqueness. The endpoint flow map is therefore monotone, which immediately implies that it is the one-dimensional optimal transport map. This noncrossing argument underlies one-step recovery results for one-dimensional rectified flow Bansal et al. (2025); Hertrich, Chambolle and Delon (2025); in particular, Hertrich, Chambolle and Delon (2025) shows that every rectifiable one-dimensional coupling is mapped to the optimal coupling by a single rectification step. The conclusion is intrinsically one-dimensional: in higher dimensions, the nonintersection of ODE trajectories does not by itself impose the cyclic monotonicity, or equivalently the cost-dependent gradient structure, that characterizes optimal transport. The statistical analysis of rectified flow can be challenging. The analysis in Mena, Kuchibhotla and Wasserman (2025) studies empirical rectified-flow estimators and, under some regularity and Hölder smoothness assumptions, establishes a convergence rate that is slower than the minimax-optimal rate for optimal transport estimation but faster than the standard nonparametric rate. This naturally raises the question of whether rectified flow is statistically optimal for estimate the optimal transport. These computational and statistical results leave three closely related questions. Is a single step of rectified flow, or its cost-aware analogue, sufficient beyond the one-dimensional setting? If repeated rectification is necessary, does the iteration converge to optimal transport, and how fast? Finally, can an iterative construction attain the minimax rate for optimal transport map estimation? We answer these questions through the c-rectified flow of Liu (2022),

4

which projects each velocity onto the appropriate cost-dependent gradient class. Under suitable conditions, iterative c-rectified flow converges to optimal transport. Moreover, under additional structural assumptions, we establish quantitative one-step contraction and exponential convergence guarantees. Finally, when combined with score-based estimation of the endpoint marginals, it can yield a rate-optimal estimator of the optimal transport map. 1.1. Our Contributions. The main contributions of the paper are as follows. • Vanilla rectified flow can fail to select optimal transport. In a centered Gaussian example, ordinary rectified flow initialized from the independent coupling produces after one step a deterministic linear coupling that is fixed by all subsequent reflows. This fixed point is the Gaussian optimal transport map if and only if the source and target covariance matrices commute. Thus cost decrease and marginal preservation alone do not guarantee convergence to optimal transport. • c-rectified flow converges qualitatively to optimal transport. The cost-aware gradient structure in c-rectified flow rules out the non-optimal fixed points above under compactness and uniform-integrability assumptions. For quadratic cost, the transport cost along the iterates converges to the optimal value, and uniqueness of the optimal coupling gives weak convergence of the couplings. We also prove the analogous qualitative convergence statement for more general displacement costs. • The convergence can be quantitative. We establish one-step decrease and exponential convergence guarantees. In the Gaussian setting, the relevant projection mechanism can be computed explicitly. In a general quadratic setting, Lipschitz regularity, strong convexity of the Brenier map, and a projection-stability condition imply geometric decay of the excess transport cost. The same contraction framework extends beyond quadratic loss to strongly convex displacement costs. • New minimax score rates yield a rate-optimal map estimator. For the multivariate Gaussian-ratio model, we construct an aggregate score estimator and prove matching upper and lower bounds rn,d (t) across the low-, intermediate-, and large-noise regimes. These new minimax-optimal score-estimation rates lead to score-based marginal estimators with explicit Wasserstein rates ϵn,d . Combining these marginal estimators with iterative c-rectified flow yields a rate-optimal estimator of the optimal transport map. Conceptually, the paper connects three viewpoints that are often studied separately: classical optimal transport, iterative flow-based transport algorithms, and statistical estimation from data. The main message is that c-rectified flow is not merely a heuristic cost-reduction procedure: with the right cost-aware gradient structure, it can serve as a principled algorithmic bridge from estimated marginals to optimal transport maps. 1.2. Related Works. Recent work on rectified flow and flow matching provides the conceptual starting point for our analysis. The original rectified flow formulation Liu, Gong and Liu (2022), together with the marginal-preserving c-rectified flow variant in Liu (2022), shows that iterative rectification can decrease transport costs while preserving endpoint marginals. Closely related frameworks, including flow matching Lipman et al. (2023) and stochastic interpolants Albergo, Boffi and Vanden-Eijnden (2023), place these methods in a broader regression-based framework for learning transport dynamics between distributions. Our work focuses instead on the limiting coupling generated by rectification and on conditions under which this coupling converges to classical optimal transport. The closest strand of prior work examines when vanilla rectified flow recovers optimal transport. The analysis in Bansal et al. (2025) gives Wasserstein error bounds for the sampling distribution of rectified flow and relates discretization error to a stronger notion of

COMP & STAT GUARANTEES OF C-RECT FLOW

5

straightness; in one dimension with a Gaussian source, it also identifies regimes in which one-step rectified flow recovers the Monge map. A complementary statistical analysis is given in Mena, Kuchibhotla and Wasserman (2025), which studies existence, uniqueness, regularity, and limit distributions for empirical rectified-flow estimators. In the Gaussian setting, that work shows that the rectified map agrees with the optimal transport map in one step precisely when the source and target covariance matrices commute. These results identify special cases in which rectified flow is compatible with optimal transport. Our focus is on iterative convergence guarantees and contraction mechanisms for c-rectified flow. A sharper structural characterization of the relation between rectified flow and optimal transport is developed in Hertrich, Chambolle and Delon (2025). That work derives explicit formulas in Gaussian and Gaussian-mixture settings and proves that every rectifiable onedimensional coupling is mapped to the optimal transport coupling after a single rectification step. It also shows that several previously claimed rectifiability statements require stronger regularity assumptions than had been emphasized. Rather than assuming rectifiability of the initial coupling, we study the behavior of the iterative procedure and identify conditions under which its cost decreases toward the optimal value. Another neighboring line improves the coupling or path geometry without directly proving convergence to the globally optimal transport plan. Minibatch optimal transport and multisample flow-matching methods Tong et al. (2024); Pooladian et al. (2023) use nontrivial couplings to obtain straighter flows, lower transport cost, and lower training variance. These methods are useful for constructing improved training couplings, but they typically rely on batch-level approximations and do not by themselves identify the population limit as the optimal coupling. Direct neural optimal transport solvers take a different route by parameterizing Brenier potentials Makkuva et al. (2020), while plug-in methods recover the map from estimated marginals Manole et al. (2024). Our focus is complementary: we analyze whether rectification itself is a convergent algorithm for classical optimal transport. The statistical estimation of optimal transport has been studied from several complementary perspectives. A foundational line of work analyzes convergence of empirical measures in Wasserstein distance. Nonasymptotic rates under moment conditions were established by Fournier and Guillin (2015), and sharp asymptotic and finite-sample rates were further developed by Weed and Bach (2019). These results clarify the dimension dependence of empirical optimal transport estimation and show that the empirical plug-in estimator can exhibit the curse of dimensionality. In high-dimensional regimes, the empirical Wasserstein distance typically converges much more slowly than parametric rates unless additional structure or smoothing is imposed. A related inferential literature studies optimal transport costs as statistical functionals, including discrete settings Sommerfeld and Munk (2018) and continuous settings del Barrio and Loubes (2019). These works show that transport costs can be used for statistical inference, but their limiting behavior is more delicate than that of smooth integral functionals. Our statistical estimation results use Wasserstein control of the marginals as an input to transport-map estimation, rather than studying inference for the optimal transport cost itself. Minimax and plug-in estimation form another important part of the statistical optimal transport literature. For density estimation under Wasserstein loss, Niles-Weed and Berthet (2022) shows that minimax rates over smooth density classes depend crucially on whether the density is bounded away from zero. For optimal transport maps, Manole et al. (2024) studies plug-in estimators under smoothness and regularity assumptions on the Brenier map and establishes minimax optimal rates. Those results also give central limit theorems for plugin estimators of W22 (µ, ν) in sufficiently smooth regimes. The work Divol, Niles-Weed and Pooladian (2025a) develops rates for optimal transport map estimation in general function spaces under assumptions expressed through metric entropy, thereby moving beyond classical Hölder-type smoothness classes. These results show that optimal transport maps can be

6

estimated at nontrivial rates under suitable structural assumptions on the underlying measures and maps. Our plug-in analysis is complementary: it combines marginal estimation with the c-rectified-flow convergence theory developed in this paper. Additional related work on flow-based distribution estimation, Schrödinger bridges, scorebased sampling, and entropic regularization is collected in Appendix A. 1.3. Organization. The remainder of the paper is organized as follows. Section 1.2 reviews related work on rectified flow and statistical optimal transport, with additional adjacent literature collected in Appendix A. Section 2 introduces the background on optimal transport, rectified flow, and c-rectified flow. Section 3.1 gives the Gaussian counterexample showing that ordinary rectified flow can stabilize at a non-optimal coupling. Section 2.5 proves qualitative convergence of iterative c-rectified flow. Section 3.2 studies convergence speed for Gaussian couplings, and Section 3.3 develops a general contraction criterion for the quadratic cost. Section 5.2 extends the contraction analysis beyond quadratic loss. Section 4.1 constructs the score-based marginal estimator and derives its Wasserstein risk. Finally, Section 4.2 combines marginal estimation with c-rectified flow to obtain a rate-optimal estimator of the optimal transport map. 1.4. Notations. Let Rd denote the d-dimensional Euclidean space. For a set A, let P(A) denote the set of probability measures supported on A. For an integer m and two distributions P and Q, let Wm (P, Q) denote the m-Wasserstein distance between P and Q. For a random variable X , let L(X) denote its law. Let ∥ · ∥2 and ⟨·, ·⟩ denote the Euclidean norm and inner product, respectively, and write | · | = ∥ · ∥2 for brevity. If P ∈ P(A) and T : A → B , then T# P denotes the pushforward of P under T . For a probability measure P , let spt(P ) denote its support. For distributions P and Q, we say that a random vector (X, Y ) is a coupling of P and Q if L(X) = P and L(Y ) = Q. For two sequences {an } and {bn }, we write an = O(bn ) if an ≤ Cbn for a universal positive constant C and all sufficiently large n. For a scalar function T : Rd → R, let ∇T denote the gradient and ∇ · T the divergence. For a vector-valued map T = (T1 , . . . , Td )⊤ : d Rd → Rd , let JT = (∇T 1 , . . . , ∇Td ). For a probability density ρ on R and a function f : R Rd → R, write ρ(f ) = Rd ρ(x)f (x) dx. For a closed set Ω ⊂ Rd with nonempty interior, let ∥ · ∥C α (Ω) denote the Hölder norm P on Ω. For a vector-valued map T = (T1 , . . . , Td )⊤ , define ∥T ∥C α (Ω) = di=1 ∥Ti ∥C α (Ω) . On space-time domains ΩT = Ω × [0, T ], we write f ∈ C α,β (ΩT ) to denote functions that are α-Hölder continuous in space and β -Hölder continuous in time for α, β ∈ (0, 1), and C k+α,l+β (ΩT ) for the corresponding spaces of higher Hölder-continuous derivatives for every k, l ∈ N. Finally, for a Euclidean space Rd , we write h ∈ Cck (Rd ) if h : Rd → R is compactly supported and continuously differentiable up to order k . Let O(d) be the ddimensional orthogonal group, defined by O(d) := {U ∈ Rd×d : ⊤ U U = U U ⊤ = Id }. For a matrix A ∈ Rd×d , we denote Spec(A) to be the set of all eigenvalues of A. Specifically, Spec(A) = {λ ∈ C | det(A − λId ) = 0}. and we define dist(Spec(A), Spec(B)) = inf{|λ − µ| : λ ∈ Spec(A), µ ∈ Spec(B)}. 2. Background. 2.1. Optimal Transport. For P, Q ∈ P2 (Rd ), let n o d d d d Π(P, Q) := π ∈ P(R × R ) : π(A × R ) = P (A), π(R × A) = Q(A)

COMP & STAT GUARANTEES OF C-RECT FLOW

7

be the set of couplings between P and Q. The quadratic optimal transport cost is Z 1 2 1 (1) W2 (P, Q) := inf ∥x − y∥2 dπ(x, y). 2 π∈Π(P,Q) Rd ×Rd 2 We call any minimizer an optimal coupling. When a coupling is induced by a map, we use the Monge formulation Z 1 ∗ (2) T ∈ argmin ∥x − T (x)∥2 dP (x). T : T# P =Q Rd 2 Under the usual absolute-continuity assumption on the source, Brenier’s theorem identifies the unique optimal map as T ∗ = ∇φ0 for a convex potential φ0 , and the optimal coupling is (id, T ∗ )# P . For a general displacement cost c(y − x), write (3)  Z Z Z φ dP + ψ dQ : φ(x) + ψ(y) ≤ c(y − x) . Wc (P, Q) = inf c(y −x) dπ(x, y) = sup π∈Π(P,Q) Rd ×Rd

φ,ψ

When the dual optimum is attained by (φ, ψ) and the c-optimal map is denoted by T ∗ , we use the slack function D(x, y) := c(y − x) − ψ(y) − φ(x).

Then D(x, y) ≥ 0 and D(x, T ∗ (x)) = 0 for P -a.e. x; in particular, T ∗ (x) is a minimizer of D(x, ·) and ∇y D(x, T ∗ (x)) = 0 whenever the derivatives exist. 2.2. Statistical Property for Optimal Transport. The statistical problem considered later is to estimate the marginals and then transport between the estimated distributions. Given b n and samples from unknown marginals P and Q, we will construct estimators Pbn and Q measure their quality in Wasserstein distance. These marginal errors are then propagated to optimal-transport map error through stability estimates. Detailed background on empirical OT rates and minimax OT map estimation is deferred to Appendix B. 2.3. Rectified Flow. Rectified flow starts from a coupling (X0 , X1 ) of P and Q and the linear interpolation Xt = (1 − t)X0 + tX1 . It fits the conditional velocity field by Z 1 (4) min E∥X1 − X0 − vt (Xt )∥2 dt, v

0

whose minimizer is vtX (z) = E[X1 − X0 | Xt = z]

for PXt -a.e. z . The rectified flow associated with X is the ODE (5)

dZt = vtX (Zt )dt,

Z0 ∼ P.

A process is rectifiable when this velocity exists, is locally bounded, and the ODE is well posed. We write (Z0 , Z1 ) = Rectify((X0 , X1 )) for the endpoint coupling produced by one rectification step.

8

2.4. c-Rectified Flow. Rectified flow is not tied to a prescribed transport cost. The cost-dependent variant studied in this paper replaces arbitrary velocity fields by the costcompatible gradient field generated by the convex conjugate of c. Throughout, c : Rd → R is differentiable and strictly convex, c∗ denotes its convex conjugate, and mc (x, y) = c(x) + c∗ (y) − ⟨x, y⟩ = bc (x; ∇c∗ (y)),

where bc is the Bregman divergence of c. For a time-differentiable process X , define Z 1 h i LX,c (f ) := E mc (Ẋs , ∇fs (Xs )) ds. 0

The c-rectified flow is the process Z = c-Rectify(X) solving dZs = ∇c∗ (∇fsX,c (Zs ))ds,

s ∈ [0, 1], Z0 = X0 , X,c where f minimizes LX,c . A process is c-rectifiable if the velocity v X exists, the miniX,c mizer f exists and is locally bounded, and (6) admits a unique solution.

(6)

Given an endpoint coupling (X0 , X1 ), we apply this construction to its linear interpolation and write (Z0 , Z1 ) = c-Rectify(X0 , X1 ). Iterating this map gives the coupling sequence used throughout the paper. Algorithm 1 c-rectified Coupling (0)

(0)

(0)

(0)

1: Initialize (Z0 , Z1 ) such that L(Z0 ) = P , L(Z1 ) = Q. 2: for k = 1, 2, . . . , K do (k)

(k)

(k−1)

3: (Z0 , Z1 ) = c-Rectify(Z0 4: end for (K) (K) 5: return (Z0 , Z1 ).

(k−1)

, Z1

).

Additional background facts and earlier results used in this section are collected in Appendix B. With the basic objects now fixed, we turn to the population behavior of the iteration. The first question is qualitative: if the marginals are known and the c-rectified update is applied repeatedly, does the resulting coupling approach the optimal transport coupling? 2.5. The Convergence of c-Rectified Flow. This subsection records the basic convergence guarantee for c-rectified flow. The main point is that the additional gradient structure imposed by the c-rectified objective rules out non-optimal limiting couplings under suitable compactness and integrability assumptions. We first present the quadratic cost, where the connection with classical optimal transport is most transparent. 2

2.5.1. Quadratic Loss. We first specialize to the quadratic cost c(x) = ∥x∥ 2 . Below we d d always assume P, Q ∈ P2 (R ). In this case, for all x, y ∈ R , ∥x∥2 ∥x − y∥2 , ∇c∗ (x) = ∇c(x) = id, mc (x, y) = . 2 2 Thus, in the quadratic case, the c-rectified objective measures the squared deviation between the displacement Z1 − Z0 and a gradient velocity field along the straight interpolation. This should be compared with ordinary rectified flow, where the minimizing velocity is an arbitrary conditional expectation. The restriction to gradient fields is precisely the structure compatible with Brenier’s theorem, and it is this restriction that allows the iteration to select the optimal coupling. The following theorem makes this intuition precise. c∗ (x) = c(x) =

9

COMP & STAT GUARANTEES OF C-RECT FLOW (0)

(0)

T HEOREM 1 (Convergence of c-rectified flow). Let (Z0 , Z1 ) = (X0 , X1 ) be an initial (k) (k) coupling of P and Q, and {Z (k) = (Z0 , Z1 )}∞ k=1 be a sequence of couplings of (P, Q) (k) (k) (k−1) (k−1) defined recursively by (Z0 , Z1 ) = c-Rectify(Z0 , Z1 ). For each k ≥ 1, define (k) (k) (k) (k) (k) Z Zt = tZ1 + (1 − t)Z0 , t ∈ [0, 1], and let f· (·) : (x, t) 7→ ftZ (x) be a minimizer of  Z 1 
2 (k) (k) (k) LZ (k) (f ) = E Z1 − Z0 − ∇fs Zs ds. 0

Suppose moreover that the following hold. • There exists an α > 0, such that for every R > 0, there exists a constant CR > 0, for all k ≥ 1, (k)

∥f Z ∥C 2+α,1+α (B(0,R)×[0,1]) ≤ CR ;

• There exist a constant C > 0 and a nonnegative measurable function g : Rd → [0, ∞) Z (k) d such t o (x)∥ ≤ Cg(x) for all (x, t) ∈ R × [0, 1] and all k ≥ 1, and the family nR that ∥∇f ∞
2 (k) 1 is uniformly integrable. dt 0 g Zt

k=1 ∗ ∗ Denote (Z0 , Z1 ) as the unique optimal coupling of (P, Q), then (k)

(k)

lim E∥Z1 − Z0 ∥2 = E∥Z0∗ − Z1∗ ∥2 = W22 (P, Q),

k→∞

(k)

(k)

(Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ).

The proof of Theorem 1 is given in Appendix D. The theorem identifies the population target of the iteration: under the stated regularity assumptions, repeated c-rectification drives the quadratic transport cost down to W22 (P, Q) and the couplings converge weakly to the Brenier coupling. This qualitative result does not yet give a rate, nor does it explain why the gradient restriction is essential. The next section addresses both points by contrasting ordinary rectified flow with the c-rectified update. 3. Computational Guarantee of c-Rectified Flow. The convergence theorem above describes the limiting population behavior of c-rectified flow. We now study finite-iteration behavior. We first show that ordinary rectified flow can fail even in a centered Gaussian model, and then prove quantitative contraction estimates for the c-rectified update. 3.1. The Failure of Rectified Flow: Gaussian Case Study. For centered Gaussian marginals, ordinary rectified flow recovers the optimal transport coupling if and only if the two covariance matrices commute. Indeed, commuting covariances yield the optimal map after one rectification step, as shown in Hertrich, Chambolle and Delon (2025); when the covariances do not commute, the first step produces a non-optimal deterministic coupling that is fixed by all subsequent reflow steps. The following statements make this obstruction explicit: the first two record the Gaussian reflow dynamics, while the proposition gives the resulting non-convergence conclusion. P ROPOSITION 1 (Jointly Gaussian Coupling Velocity). Let (X0 , X1 ) be a centered jointly Gaussian coupling in Rd × Rd , with X0 ∼ N (0, Σ1 ), X1 ∼ N (0, Σ2 ), Σ01 := Cov(X0 , X1 ). For each t ∈ [0, 1], define the straight coupling Xt = (1 − t)X0 + tX1 with Σt := Var(Xt ) = (1 − t)2 Σ1 + t2 Σ2 + t(1 − t)(Σ01 + Σ⊤ 01 ). Then the velocity field vt (x) := E[X1 − X0 | Xt = x] is linear in x and is given by h i −1 (7) vt (x) = t(Σ2 − Σ01 ) + (1 − t)(Σ⊤ 01 − Σ1 ) Σt x.

10

L EMMA 1 (Endpoint of one-step rectified flow). Let Σ1 , Σ2 ∈ Rd×d be symmetric positive definite, and consider the linear ODE
∂t Zt = tΣ2 − (1 − t)Σ1 Σ−1 Z0 = z ∈ Rd , t Zt , where Σt = (1 − t)2 Σ1 + t2 Σ2 . Then   1/2 −1/2 −1/2 1/2 −1/2 Zt = Σ1 (1 − t)2 I + t2 Σ1 Σ2 Σ1 Σ1 z. In particular, Z1 = T z , where 1/2

T := Σ1



−1/2

Σ1

 −1/2 1/2

Σ2 Σ1

−1/2

Σ1

.

L EMMA 2 (Reflow of a deterministic linear coupling). Let X0 ∼ N (0, Σ1 ) and define X1 = LX0 for an arbitrary invertible matrix L ∈ Rd×d such that X1 ∼ N (0, Σ2 ). Then the
−1 velocity is given by vt (x) = (L − I) (1 − t)I + tL x, and the corresponding ODE
−1 ∂t Zt = (L − I) (1 − t)I + tL Zt
has the explicit solution Zt = (1 − t)I + tL Z0 . In particular, one reflow step preserves the coupling map L. P ROPOSITION 2 (Non-convergence to optimal transport). For rectified flow on the Gaussian measures N (0, Σ1 ) and N (0, Σ2 ), initialized with the independent coupling, the first step produces the deterministic linear coupling   1/2 −1/2 −1/2 1/2 −1/2 X1 = T X0 , T = Σ1 Σ1 Σ2 Σ1 Σ1 . Every subsequent step preserves this coupling. Moreover, let   −1/2 1/2 1/2 1/2 −1/2 TOT := Σ1 Σ1 Σ2 Σ1 Σ1 be the Gaussian optimal transport map. Then T = TOT

⇐⇒

Σ 1 Σ2 = Σ 2 Σ1 .

Consequently, if Σ1 and Σ2 do not commute, rectified flow stabilizes after one step at a suboptimal coupling and does not recover the optimal transport map. Proofs of Proposition 1, Lemma 1, Lemma 2, and Proposition 2 are given in Appendix C. This failure is a population-level obstruction rather than a statistical or numerical artifact. It motivates the quantitative analysis below: in the same Gaussian setting, the c-rectified update contracts the excess quadratic transport cost. 3.2. Convergence Rates for c-Rectified Flow with Gaussian Marginals. In this section, we quantify the convergence rate of the c-rectified flow in the Gaussian transport setting. The previous convergence theorem shows that the iterates approach the optimal coupling under compactness and integrability assumptions, but it does not provide an explicit rate. For Gaussian marginals, the dynamics admit a more concrete description: the velocity fields remain linear, the gradient projection can be computed through a Gaussian Helmholtz decomposition, and the decrease in transport cost can be related to the non-gradient component of the initial velocity.

11

COMP & STAT GUARANTEES OF C-RECT FLOW

The main result is a one-step contraction estimate for the excess quadratic transport cost. The contraction is driven by the rotational part of the transport map. More precisely, writing a linear transport as T = T ∗ U , where T ∗ is the Gaussian optimal transport map and U is Σ1 -orthogonal, the deviation from optimality is encoded by U − I . A spectral gap excluding eigenvalues of U near −1 ensures that the divergence-free component of the velocity controls this deviation, and hence that one step of c-rectified flow removes a fixed fraction of the excess cost. 3.2.1. One Step Contraction. Let Σ1 , Σ2 ∈ Rd×d be symmetric positive definite and P = N (0, Σ1 ), Q = N (0, Σ2 ). T HEOREM 2. Let X0 ∼ P , X1 = T X0 , where T is a (linear) transport map from P to Q. Then there exists a Σ1 -orthogonal matrix U such that T = T ∗ U . Suppose dist(Spec(U ), −1) ≥ γ > 0, then this coupling (X0 , X1 ) is c-rectifiable. Denote (Z0 , Z1 ) = c-Rectify((X0 , X1 )). Then
E∥Z1 − Z0 ∥2 − W22 (P, Q) ≤ (1 − γ 2 c) E∥X1 − X0 ∥2 − W22 (P, Q) . The constant c ∈ (0, 1/4) depends only on the spectra of Σ1 and Σ2 . C OROLLARY 1 (One-step c-rectified flow cannot recover OT unless T = T ∗ ).

Let

L2 (P ; Rd ) = G0 ⊕ S0 be the orthogonal decomposition into gradient fields and p-divergencefree fields at time t = 0. If projG0 (T x) = T ∗ x, then T = T ∗ . Equivalently, if T ̸= T ∗ , then projG0 (T x) ̸= T ∗ x. In particular, one-step c-rectified flow cannot already recover the opti-

mal transport map unless the original transport is itself optimal. The proof of Theorem 2 and Corollary 1 are given in Appendix E. The theorem shows that, once the rotational component of the current linear transport is separated from the Gaussian optimal transport map, the c-rectified projection removes a fixed fraction of the excess cost. The spectral gap condition excludes the degenerate case in which this rotational component is nearly invisible to the gradient projection. 3.2.2. Iterating the One-step Contraction. The one-step contraction can now be iterated as long as the spectral gap condition remains uniform along the sequence of linear transport maps generated by c-rectified flow. This yields an exponential decay rate for the excess transport cost. (0)

(0)

T HEOREM 3 (Exponential convergence of iterative c-rectified flow). Let (Z0 , Z1 ) = (X0 , X1 ) be any centered jointly Gaussian initial coupling of P = N (0, Σ1 ), Q = N (0, Σ2 ), and for each k ≥ 0, let (k+1)

(Z0

(k+1)

, Z1

(k)

(k)

) := c-Rectify(Z0 , Z1 ). (0)

(0)

Then there exists a constant c > 0 that depends only on (Z0 , Z1 ), such that the excess transport cost decays geometrically:   (k) (k) 2 E Z1 − Z 0 − W22 (P, Q) ≤ e−c(k−1) E∥X1 − X0 ∥2 − W22 (P, Q) . The proof of Theorem 3 is also given in Appendix E. The Gaussian calculation gives a fully explicit contraction mechanism. We next abstract the part of the argument that does not rely on Gaussian algebra: a one-step decrease follows when the non-optimal component of the current map has a stable projection onto divergence-free directions.

12

3.3. A General Contraction Criterion for c-Rectified Flow. Let P and Q be probability measures on Rd , and assume that P is absolutely continuous with density p. Let T : Rd → Rd be a transport map such that T# P = Q, and let T ∗ denote the unique optimal transport map from P to Q with respect to the quadratic cost. Let X0 ∼ P and set X1 = T (X0 ). We study the one-step c-rectified coupling given by (Z0 , Z1 ) = c-Rectify((X0 , T (X0 ))). The goal of this section is to give a general criterion under which this step contracts the excess quadratic transport cost. The key structural condition is a projection stability assumption: the deviation T − T ∗ must have a nontrivial component in the p-divergence-free subspace. Consider the linear interpolation Tt = tT + (1 − t)id for all t ∈ [0, 1]. We first record a simple local-in-time invertibility estimate, which allows us to define the Eulerian velocity field along this deterministic interpolation. P ROPOSITION 3 (Invertibility of Tt for small t). Assume that T is L-Lipschitz, then for every 0 ≤ t < (1 + L)−1 , Tt is injective and bi-Lipschitz onto its image. In particular, Tt−1 is well-defined on Tt (Rd ) and (1 − (1 + L)t)−1 -Lipschitz. The proof of Proposition 3 is given in Appendix F. By Proposition 3, for every t < (2 + 2L)−1 the inverse map Tt−1 is well-defined on Tt (Rd ), and hence in particular on the support of Pt = (Tt )# P . Therefore we may define the velocity field vt = (T − id) ◦ Tt−1

on Tt (Rd ).

This definition aligns with the marginal flow velocity vt (x) = E[X1 − X0 |Xt = x] because the coupling is deterministic. Let pt denote the probability density of the interpolant Xt = Tt (X), and let p denote the density of P . We define the subspace of divergence-free vector fields with respect to pt as n o (8) St := h ∈ L2 (Pt ; Rd ) : ∇ · (pt h) = 0 in the weak sense . Equivalently, h ∈ St if and only if Z Z − φ∇ · (pt h)dx = ⟨h, ∇φ⟩pt dx = 0 Rd

Rd

∀φ ∈ Cc∞ (Rd ).

We also let (9)

Gt := {∇φ : φ ∈ Cc∞ (Rd )}

L2 (Pt ;Rd )

,

denote the closure of gradient fields in L2 (Pt ; Rd ). By this weak formulation, St = Gt⊥ , hence L2 (Pt ; Rd ) = Gt ⊕ St . Our analysis proceeds in the weighted Hilbert space L2 (P ; Rd ) R ⊤ equipped with the inner product ⟨a, b⟩P = Rd a(x) b(x)p(x)dx. 3.3.1. Assumptions and Main Results. We impose three assumptions. The first controls the interpolation and the transported test fields. The second converts control of ∥T − T ∗ ∥2P into control of the excess quadratic transport cost. The third is the structural projection stability condition that drives the contraction estimate. A SSUMPTION 1 (Lipschitz regularity).

The map T ∈ C 1 is L-Lipschitz.

A SSUMPTION 2 (Strong convexity of the Brenier potential). The optimal transport map T ∗ is generated by a λ-strongly convex Brenier potential φ, namely T ∗ = ∇φ0 and ∇2 φ0 ⪰ λId .

COMP & STAT GUARANTEES OF C-RECT FLOW

A SSUMPTION 3 (Projection stability).

13

There exists a constant c > 0 such that

∥ projS0 (T − T ∗ )∥2P ≥ h∥T − T ∗ ∥2P ,

where S0 = {u ∈ L2 (P ; Rd ) : ∇ · (pu) = 0 weakly}. Assumption 3 requires a fixed fraction of the deviation T − T ∗ to lie in the P -divergencefree subspace. Under these assumptions, one step of c-rectified flow removes a definite fraction of this deviation. T HEOREM 4 (One-step decrease of quadratic cost). Let X0 ∼ P , X1 = T (X0 ), and suppose that the coupling (X0 , X1 ) is c-rectifiable. Let (Z0 , Z1 ) = c-Rectify(X0 , X1 ). Then under Assumptions 1–3, E ∥T (X0 ) − X0 ∥2 − E ∥Z1 − Z0 ∥2 ≥

h ∥T − T ∗ ∥2P . 8(L + 1)

The proof of Theorem 4 is given in Appendix F. The corresponding excess-cost contraction follows by combining the theorem with a standard cost-difference estimate. C OROLLARY 2 (One-step contraction of excess cost). Let X0 ∼ P , X1 = T (X0 ), and suppose that the coupling (X0 , X1 ) is c-rectifiable. Let (Z0 , Z1 ) = c-Rectify(X0 , X1 ). Assume Assumptions 1–3. Then    λh 2 2 E ∥Z1 − Z0 ∥ − W2 (P, Q) ≤ 1 − E ∥T (X0 ) − X0 ∥2 − W22 (P, Q) . 8(L + 1) The proof of Corollary 2 is given in Appendix F. Thus, under local regularity and projection stability, a single c-rectified step decreases the excess quadratic transport cost by a fixed multiplicative factor. The remaining issue is whether the same hypotheses persist along the iterates. 3.3.2. Local Validity of the Projection Bound. We finally explain why Assumption 3 is natural near the Brenier map. The following result proves the bound along smooth P measure-preserving perturbations of the identity. Thus, although the main criterion is stated abstractly, it is locally valid around T ∗ in directions generated by incompressible perturbations of P . P ROPOSITION 4 (Local projection stability near T ∗ ). Assume that P has density p, and that the Brenier potential φ0 ∈ C 2 (Rd ) satisfies λId ⪯ ∇2 φ0 (x) ⪯ ΛId , for some 0 < λ ≤ Λ < ∞ and all x ∈ Rd . Let (Sε )ε be a family of P -measure-preserving maps such that S0 = id and Sε (x) = x + εu(x) + rε (x),

∥rε ∥P → 0, |ε|

for some nonzero u ∈ L2 (P ; Rd ). Define Tε := T ∗ ◦Sε . Then (Tε )# P = Q. Moreover, u ∈ S0 , and there exists ε0 > 0 such that for all 0 < |ε| < ε0 , λ2 ∥Tε − T ∗ ∥2P . 4Λ2 In particular, Assumption 3 holds locally along the family Tε , with h = λ2 /(4Λ2 ). ∥ projS0 (Tε − T ∗ )∥2P ≥

The proof of Proposition 4 is given in Appendix F.

14

3.3.3. Iterating the One-step Contraction. The one-step contraction can be iterated provided that the hypotheses of the one-step result hold uniformly along the sequence of crectified couplings. We make this uniformity explicit in the following statement. T HEOREM 5 (Exponential convergence of iterative c-rectified flow). a initial coupling of P and Q. For each k ≥ 0, define the iterates by (k+1)

(Z0

(k+1)

, Z1

(k)

(0)

(0)

Let (Z0 , Z1 ) be

(k)

) := c-Rectify(Z0 , Z1 ). (k)

(k)

Assume that for every k ≥ 1, the coupling (Z0 , Z1 ) is c-rectifiable and is induced by a transport map Tk , namely (k)

Z0 ∼ P,

(k)

(k)

Z1 = Tk (Z0 ),

(Tk )# P = Q.

Assume further that Assumptions 1–3 hold for every Tk with the same constants L, h. Then, the excess quadratic transport cost satisfies    λh (k) (k) 2 2 E Z1 − Z 0 (k − 1) E ∥T0 (X0 ) − X0 ∥2 − W22 (P, Q) . −W2 (P, Q) ≤ exp − 8(L + 1) The proof of Theorem 5 is given in Appendix F. R EMARK 1. If the initial coupling is not induced by a transport map satisfying the uniform assumptions, the same argument applies from the first index k0 at which the iterate (k ) (k ) (Z0 0 , Z1 0 ) enters this admissible class. This is expected to occur after sufficiently many iterations, since the preceding convergence result implies that the iterates approach the optimal transport coupling, for which the required structure is satisfied. In that case, for every k ≥ k0 , k−k0  λh Ek0 . Ek ≤ 1 − 8(L + 1) Thus, the only additional issue for arbitrary initial couplings is to justify that the iterates enter, and remain in, the class of map-induced couplings for which the one-step contraction criterion applies. The deterministic results in this section assume access to the population marginals and the associated population update. We next supply the statistical input needed to estimate the marginals from samples, and then combine this input with stability of optimal transport maps. 4. Statistical Guarantee of c-Rectified Flow. 4.1. Score Estimation. This subsection develops the statistical input used in the optimaltransport map estimation result of Section 4.2. We study score estimation for a d-dimensional Gaussian-ratio model and derive matching upper and lower bounds across the low-, intermediate-, and large-noise regimes. Projecting the resulting estimator onto a class with suitable matrix-valued one-sided slope bounds gives a stable reverse-time diffusion and an explicit W2 risk bound in every fixed dimension.

15

COMP & STAT GUARANTEES OF C-RECT FLOW

4.1.1. Setup and main statistical results. Fix an integer d ≥ 1, treated as constant throughout, and constants 0 < c < 1 < C < ∞, L < ∞, and α > 1. We assume that L is large enough that the constant ratio r ≡ 1 is an interior point of the smoothness constraint (d) below. Let φd be the standard Gaussian density on Rd , let φt be the density of N (0, tId ), and define   Z Fα,d = f = rφd : rφd = 1, c ≤ r ≤ C, ∥r∥C α (Rd ) ≤ L . Rd

Here C α (Rd ) denotes the usual isotropic Hölder class C mα ,α−mα (Rd ), where mα := ⌈α⌉ − 1. Thus, when α is an integer, C α is interpreted as C α−1,1 . Write Z ∥g∥2L2 (q) := ∥g(x)∥2 q(x)dx, Dn := σ(X1 , . . . , Xn ). Rd

For t ≥ 0, define (d)

(d)

pt = f ∗ φt ,

(d)

γt = φd ∗ φt = φ1+t ,

Rt =

pt . γt

For t > 0, let st = ∇ log pt . Then c ≤ Rt ≤ C and st (x) = −

x ∇Rt (x) + . 1+t Rt (x)

Throughout this section, a ≲ b and a ≳ b mean that the corresponding inequality holds up to a constant depending only on (c, C, L, α, d). We write a ≍ b when both relations hold. Denote hn = n−1/(2α+d) , and the multivariate score-risk envelope  2(α−1) 1 ∨ log+ (ntα+d/2 )d/2 1   ∧ d+1 , 0 < t ≤ 1, n− 2α+d ∧ 1+d/2 nt nt (10) rn,d (t) =    1 , 1 < t ≤ n. nt2 T HEOREM 6 (Multivariate score minimax risk). For all sufficiently large n and every 0 < t ≤ n, Z inf sup Ef ∥ŝt (x) − st (x)∥2 pt (x)dx ≍ rn,d (t), ŝt f ∈Fα,d

Rd

i.i.d.

where the infimum is over all estimators based on X1 , . . . , Xn ∼ f . Moreover, there exists an aggregate estimator ŝagg such that the lower bound is attained. t The proof of Theorem 6 is given in Appendix H. We next define the projection that turns the aggregate estimator into a stable reverse drift. Put ᾱ = α ∧ 2. With K0 as in Lemma 17, let   1 K0 ᾱ/2−1 − 1{t>1} , λd (t) = K0 t 1{t≤1} + t(1 + t) t λd (t) = K0 tᾱ/2−1 1{t≤1} + t−1 1{t>1} ,

and define the closed convex set n o Ct,d = b = ∇V ∈ L2 (γt ; Rd ) : −λd (t)Id ⪯ ∇2 V ⪯ λd (t)Id weakly .

16

Algorithm 2 Projected reverse sampler for µ bn i.i.d.

1: Input: X1 , . . . , Xn ∼ f ∈ Fα,d . agg 2: Construct ŝt from the three noise regimes. 3: Project the aggregate score: L2 (γt ;Rd ) agg ŝt , t,d

set = ProjC

0 < t ≤ n.

4: Sample Yb0 ∼ γn and, with a d-dimensional Brownian motion B, solve the reverse SDE dYbu = sen−u (Ybu )du + dBu ,

0 ≤ u ≤ n.

5: Output: µ bn = L(Ybn | Dn ).

Lemma 17 shows that st ∈ Ct,d . Consequently, Hilbert projection and the uniform equivalence pt ≍ γt give Z L2 (γ ;Rd ) agg ∥set − st ∥2 pt ≲ rn,d (t), set = ProjCt,d t ŝt . sup Ef f ∈Fα,d

Rd

The resulting marginal estimator is summarized in Algorithm 2. T HEOREM 7 (Multivariate W2 risk).

For all sufficiently large n,  1  n− 2 log log n, d = 1, p  Z n  1  r (t) 3 1/2 n,d bn , f ) sup Ef W22 (µ ≲ dt + n−1 ≲ ϵn,d := n− 2 (log n) 2 , d = 2,  1+t f ∈Fα,d 0  α+1  − 2α+d n , d ≥ 3. Here rn,d (t) denotes the local score-risk envelope at time t, whereas ϵn,d denotes the resulting global Wasserstein rate after integration along the Gaussian interpolation. The proof of Theorem 7 is given in Appendix H. These Wasserstein bounds are the marginal-estimation input for the transport map problem. The next subsection plugs the estimated source and target marginals into the optimal transport problem and uses map stability to transfer the marginal rate to the estimated optimal transport map. 4.2. Application: Optimal Estimation of Optimal Transport. This section combines marginal estimation with stability of optimal transport maps under perturbations of the source and target measures. We treat the marginal W2 error as the statistical input and first derive a plug-in risk bound for the quadratic-cost Brenier map. The convergence results for c-rectified flow established earlier provide a constructive procedure for approximating the corresponding plug-in target. We then formulate an analogous stability bound for general displacement costs. We work with the class of λ-log-concave and Λ-log-smooth probability measures o n CλΛ := P ∈ P2 (Rd ) : dP (x) = f (x)dx, λId ⪯ −∇2 log f ⪯ ΛId , and let T ∗ denote the optimal transport map from P to Q, where P, Q ∈ CλΛ . Assume that, i.i.d. i.i.d. bn from the samples X1 , . . . , Xn ∼ P , Y1 , . . . , Yn ∼ Q, we construct estimators Pbn and Q as in Section 4.1, satisfying EW22 (P, Pbn ) ≤ ρ2n ,

b n ) ≤ ρ2n . EW22 (Q, Q

COMP & STAT GUARANTEES OF C-RECT FLOW

17

The stability argument below only uses these two marginal risk bounds. To instantiate them with Algorithm 2 and the explicit rate ϵn,d , we additionally assume that the densities of P and Q belong to Fα,d , with common model constants. The projection step below only enforces membership in CλΛ , the class on which the regularity theory for optimal maps is available. It does not itself construct the optimal map; the map is obtained afterward as the exact transport between the projected marginals. The estimator is summarized in Algorithm 3. Algorithm 3 Plug-in estimator of the optimal transport map i.i.d.

i.i.d.

1: Input: samples X1 , . . . , Xn ∼ P and Y1 , . . . , Yn ∼ Q. b n as in Algorithm 2. 2: Construct marginal estimators Pbn , Q 3: Project the marginal estimators onto the structured class: Pen ∈ arg min W2 (µ, Pbn ), µ∈CλΛ

e n ∈ arg min W2 (ν, Q b n ). Q ν∈CλΛ

e n , equivalently the limiting map obtained by Algo4: Compute the exact optimal transport map from Pen to Q rithm 1. en . 5: Output: the plug-in map Ten∗ from Pen to Q

The output Ten∗ is therefore an exact population plug-in target. The deterministic contraction estimates above describe how c-rectified flow approximates this target by iteration. We use the following stability estimate for optimal transport maps under squared Euclidean cost, which has been studied in Balakrishnan and Manole (2025). T HEOREM 8 (Stability of smooth Brenier maps; Theorem 3 of Balakrishnan and Manole (2025)). Let T ∗ = ∇φ0 be the optimal transport map from P to Q. Let Ω ⊂ Rd be a convex set containing the supports of P and Pe . Assume that the Brenier potential φ0 is mφ -strongly convex and Mφ -smooth on Ω, in the sense that mφ I ⪯ ∇2 φ0 ⪯ Mφ I . Let π e be an optimal e e coupling of P and Q. Then 1 1 e + Mφ W22 (P, Pe) + 2W2 (P, Pe)W2 (Q, Q). e E(X,Y )∼πe ∥Y − T ∗ (X)∥22 ≤ W 2 (Q, Q) Mφ mφ 2

In particular, if Pe is absolutely continuous and Te∗ denotes the optimal transport map from e , then Pe to Q e EPe ∥Te∗ − T ∗ ∥22 ≲mφ ,Mφ W22 (P, Pe) + W22 (Q, Q). Theorem 8 is quoted from Balakrishnan and Manole (2025); the plug-in argument below is proved in Appendix I. P ROPOSITION 5 (Plug-in estimation of the Brenier map). Assume that P, Q ∈ CλΛ , and that there exist marginal estimators satisfying n o1/2 n o1/2 bn ) EW22 (P, Pbn ) EW22 (Q, Q ≤ ρn , ≤ ρn . Let T ∗ = ∇φ0 be the Brenier map from P to Q, and let Ten∗ be the output of Algorithm 3. Then there exists a constant C ′ = C ′ (λ, Λ) > 0 such that E∥Ten∗ − T ∗ ∥2L2 (P ) ≤ C ′ ρ2n .

18

b n from In particular, if the two marginal densities also belong to Fα,d , the samplers Pbn , Q 2 2 Algorithm 2 yield a plug-in estimator with squared L (P ) risk O(ϵn,d ). This matches the marginal-estimation scale inherited from Section 4.1, up to the logarithmic factors appearing there in dimensions d = 1, 2. The proof of Proposition 5 is given in Appendix I. Together with the marginal rates from Section 4.1, this gives a rate-optimal plug-in estimator of the optimal transport map using c-rectified flow to realize the population transport between the estimated marginals. 5. General Cost. The preceding sections focused on the quadratic cost. We now extend the same chain of results to displacement costs c(y − x): qualitative convergence, local contraction, and stability of the induced cost-optimal map under marginal perturbations. The quadratic squared distance is replaced by the dual slack and the c-transform geometry. 5.1. Convergence of c-Rectified Flow under General Cost. The following theorem is the general-cost analogue of Theorem 1. The squared error is replaced by the Bregman-type discrepancy bc , and the velocity field is expressed through the nonlinear map ∇c∗ ◦ ∇fs . The additional assumptions below ensure that this nonlinear loss is stable under weak convergence of the couplings and local convergence of the potentials. (0)

(0)

T HEOREM 9 (Convergence of c-rectified flow). Let (Z0 , Z1 ) = (X0 , X1 ) be an initial (k) (k) coupling of P and Q, and let {Z (k) = (Z0 , Z1 )}∞ k=1 be a sequence of couplings of (P, Q), (k+1) (k+1) (k) (k) (k) where (Z0 , Z1 ) = c-Rectify(Z0 , Z1 ). For brevity, for each k ≥ 1, define Zt = (k) (k) tZ1 + (1 − t)Z0 , t ∈ [0, 1], and (k)

gk (x, s) := (∇c∗ ◦ ∇fsZ )(x). (k)

Assume that for each k , the function f·Z minimizes Z 1 h
i (k) (k) LZ (k) (f ) := E bc Z1 − Z0 ; (∇c∗ ◦ ∇fs )(Zs(k) ) ds. 0

Suppose also there exists an α > 0, such that for every R > 0, there exists a constant CR > 0, for all k ≥ 1, (k)

∥f Z ∥C 2+α,1+α (B(0,R)×[0,1]) ≤ CR ;

Assume moreover that there exist a constant C > 0 and nonnegative measurable functions Φ, Ψ : Rd → [0, ∞) such that
bc (x; y) ≤ C 1 + Φ(x) + Ψ(y) for all x, y ∈ Rd , and that the three families (k) (k) {Φ(Z1 − Z0 )}∞ k=1 ,

Z 1

Ψ gk (Zs(k) , s) ds

∞

0

,

(k)

(k)

{c(Z1 − Z0 )}∞ k=1

k=1

are uniformly integrable. Then (k)

(k)

lim E[c(Z1 − Z0 )] =

k→∞ (k)

(k)

inf

X∼P, Y ∼Q

E[c(X − Y )].

Moreover, (Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ), where (Z0∗ , Z1∗ ) is the unique optimal coupling of (P, Q) under the cost function c(x − y).

COMP & STAT GUARANTEES OF C-RECT FLOW

19

The proof of Theorem 9 is given in Appendix D.1. The conclusion says that c-rectified flow still selects the cost-optimal coupling once the quadratic geometry is replaced by the corresponding c-geometry. In this setting, convergence of the objective is expressed through the cost slack rather than through the squared displacement alone. R EMARK 2. A convenient sufficient condition for the uniform integrability assumptions in the c-loss theorem is the following. Suppose there exist p ≥ 1, ϵ > 0, and a constant C > 0 such that for all x, y ∈ Rd , max{c(x), Φ(x), Ψ(x)} ≤ C(1 + |x|p ),

and |gk (x, s)| ≤ C(1 + |x|q ) for all (x, s) ∈ Rd × [0, 1], k ≥ 1. If P, Q have finite p max{q, 1} + ϵ moments, then the three families  Z 1
(k) (k) (k) (k) (k) , {c(Z1 − Z0 )}k≥1 Ψ gk (Zs , s) ds {Φ(Z1 − Z0 )}k≥1 , 0

k≥1

are uniformly integrable. Indeed, we have (k) (k)
(k) (k) (k) (k) (k) (k)
c(Z1 − Z0 ) + Φ(Z1 − Z0 ) ≤ C 1 + |Z1 − Z0 |p ≤ C 1 + |Z0 |p + |Z1 |p . (k)

(k)

(k)

Next, since |Zs | ≤ |Z0 | + |Z1 |, and by the growth assumption on gk and Hölder’s inequality,
p
(k) (k) |gk (Zs(k) , s)|p ≤ C 1 + |Zs(k) |q ≤ C 1 + |Z0 |pq + |Z1 |pq . Using the growth assumption on Ψ, we obtain Z 1



(k) (k) (k) (k) p Ψ gk (Zs(k) , s) ds ≤ C 1+|Z0 |pq +|Z1 |pq . Ψ gk (Zs , s) ≤ C 1+|gk (Zs , s)| =⇒ 0

(k) (k) Since Z0 ∼ P and Z1 ∼ Q for all k , and P, Q have finite p max{q, 1} + ϵ moments,

the two families (k)

(k)

{1 + |Z0 |pq + |Z1 |pq }k≥1 ,

(k)

(k)

{1 + |Z0 |p + |Z1 |p }k≥1

are uniformly integrable. Hence each of the three families above is uniformly integrable. 5.2. Contraction Beyond Quadratic Loss. Qualitative convergence does not by itself give a rate. We therefore state a local contraction criterion for a broader class of strictly convex cost functions. Let c : Rd → R be a strictly convex cost function. Let T : Rd → Rd be a transport map from P to Q, and let T ∗ denote the unique optimal transport map for the cost c(y − x). Such T ∗ exists (see e.g. Villani (2021)). As before, set X0 ∼ P and X1 = T (X0 ), then we consider the straight interpolation Tt = (1 − t)id + tT,

Xt = Tt (X0 ),

Pt = (Tt )# P.

Whenever Tt is invertible on its image, the velocity along this deterministic interpolation is vt = (T − id) ◦ Tt−1 . We use the same notation for the Pt -divergence-free space and gradient space as defined before at (8). We impose the following assumption on the cost function mainly by constraining its Hessian. A SSUMPTION 4. The cost function c ∈ C 2 (Rd ), and there exist constants 0 < µc ≤ Lc < ∞ such that for all z ∈ Rd , µc Id ⪯ ∇2 c(z) ⪯ Lc Id .

20

Under this assumption, we generalize the projection assumption. In the quadratic case, the relevant vector field was T − id. For a general cost, the driving force is the gradient of the cost applied to the displacement. A SSUMPTION 5.

There exists a constant γ > 0 such that:

∥ projS0 (∇c(T − id))∥2P ≥ h∥∇c(T − id) − ∇c(T ∗ − id)∥2P .

The next lemma compares the excess c-transport cost with the force discrepancy ∇c(T − id) − ∇c(T ∗ − id). This comparison is the general-cost replacement for the quadratic costdifference estimate used earlier. L EMMA 3 (Cost deficit controlled by force discrepancy). Let c : Rd → R satisfy Assumption 4. Let T ∗ be an optimal transport map from P to Q for the cost c(y − x), and let T be any transport map from P to Q. Assume that there exist optimal Kantorovich potentials (φ, ψ) given by (3), such that ψ ∈ C 2 (Rd ) and ∇2 c(y − x) − ∇2 ψ(y) ⪯ Ly Id ,

∀ (x, y) ∈ Rd × Rd ,

Then E[c(T (X) − X)] − Wc (P, Q) ≤

Ly ∥∇c(T − id) − ∇c(T ∗ − id)∥2P . 2µ2c

The proof of Lemma 3 is given in Appendix G. T HEOREM 10 (One-step Contraction for General Cost). Let X0 ∼ P , X1 = T (X0 ) ∼ Q. Suppose (X0 , T (X0 )) is c-rectifiable, and let (Z0 , Z1 ) = c-Rectify(X0 , T (X0 )). Assume Assumptions 1, 4, 5, together with the hypotheses of Lemma 3, we have E[c(T (X0 ) − X0 )] − E[c(Z1 − Z0 )] ≥

hµ2c (E[c(T (X0 ) − X0 )] − Wc (P, Q)) . 8Lc Ly (L + 1)

Equivalently,  hµ2c E[c(Z1 − Z0 )] − Wc (P, Q) ≤ 1 − (E[c(T (X0 ) − X0 )] − Wc (P, Q)) . 8Lc Ly (L + 1) 

The proof of Theorem 10 is given in Appendix G. Thus, under the general-cost projection stability condition, one c-rectified step removes a fixed fraction of the excess c-transport cost. The constants now depend on the curvature of c and on the local curvature of the dual slack. The one-step estimate can be iterated once the assumptions hold uniformly along the sequence of c-rectified couplings. T HEOREM 11 (Exponential convergence under uniform general-cost stability). Let (0) (0) (k+1) (k+1) (k) (k) (Z0 , Z1 ) be an initial coupling of P and Q, and define (Z0 , Z1 ) = c-Rectify(Z0 , Z1 ), (k) (k) k ≥ 0. Assume that for every k ≥ 0, the coupling (Z0 , Z1 ) is c-rectifiable and induced by (k) (k) (k) a transport map Tk , so that Z0 ∼ P , Z1 = Tk (Z0 ), (Tk )# P = Q. Assume further that Assumptions 1, 4, 5, and in Lemma 3 hold uniformly along Tk , with the same constants L, h. Then    hµ2c (k − 1) (k) (k) (0) (0) E[c(Z1 −Z0 )]−Wc (P, Q) ≤ exp − E[c(Z1 − Z0 )] − Wc (P, Q) . 8Lc Ly (L + 1) The proof of Theorem 11 is given in Appendix G. This gives the algorithmic part of the general-cost theory. To obtain a statistical statement, it remains to control how perturbing the source and target marginals changes the induced c-optimal map.

COMP & STAT GUARANTEES OF C-RECT FLOW

21

5.3. Estimation for General Cost. The final ingredient is a stability estimate for general displacement costs. The assumptions below play the same role as strong convexity and smoothness of the Brenier potential in the quadratic case. T HEOREM 12 (Stability bound for displacement costs). Suppose Assumption 4 holds, and let (φ, ψ) be an optimal Kantorovich dual pair for (P, Q) under cost c, where T ∗ is the c-OT map from P to Q. Define the slack function D(x, y) := c(y − x) − φ(x) − ψ(y). Assume further that there exist constants µy , Lx , Ly > 0 such that the following Hessian bounds hold for all (x, y): µy I ⪯ ∇2yy D(x, y) = ∇2 c(y − x) − ∇2 ψ(y) ⪯ Ly I, ∇2xx D(x, y) = ∇2 c(y − x) − ∇2 φ(x) ⪯ Lx I,

e for the cost c(y − x). Then Finally, let π e be an optimal coupling between Pe and Q Z ∥y − T ∗ (x)∥2 e + 2Lc W2 (P, Pe)W2 (Q, Q). e dπ e(x, y) ≤ Lx W22 (P, Pe) + Ly W22 (Q, Q) µy 2 The proof of Theorem 12 is given in Appendix I. This bound transfers marginal Wasserstein perturbations into an L2 -type control of the induced cost-optimal map. It is the generalcost analogue of the smooth Brenier-map stability used above. Combining this stability estimate with the marginal estimators from Section 4.1 gives the corresponding plug-in rate. C OROLLARY 3 (Plug-in stability for displacement costs). Let Tenc be the c-optimal map e n , and let T c be the c-optimal map from P to Q. Suppose that the Kantorovich from Pen to Q e n ) satisfy the assumptions of Theorem 12, with constants potentials associated with (Pen , Q independent of n. Then EP ∥T c (X) − Tenc (X)∥2 ≲ ρ2n . The proof of Corollary 3 is given in Appendix I. The main body has therefore established the full chain: c-rectified flow targets the correct optimal coupling, contracts under local stability conditions, and, when combined with score-based marginal estimation, yields rateoptimal estimation of the optimal transport map and its general-cost analogue. Acknowledgments. The authors would like to thank Aram-Alexandre Pooladian for helpful discussions.

22

APPENDIX A: ADDITIONAL RELATED WORK A.0.0.1. Flow-based estimation and bridge methods.. There is a broader theory of convergence rates for flow-based transport estimators that is adjacent to our objective. For general flow matching, near-minimax convergence guarantees under Wasserstein metrics are established in Fukumizu et al. (2025); Kunkel and Trabs (2025). For rectified flow, Sahoo, Gaur and Aggarwal (2026) proves order-optimal sample complexity under smoothness assumptions. These results concern statistical estimation of distributions or transport dynamics from samples, whereas our main algorithmic results concern the population rectification operator and its convergence to the optimal transport coupling. Schrödinger bridges and entropic optimal transport provide regularized counterparts of the transport problem. Classical references interpret Schrödinger bridges as entropy-regularized optimal transport on path space Léonard (2014); Di Marino and Gerolin (2020). In the small-noise limit, Schrödinger potentials converge to Kantorovich potentials Nutz and Wiesel (2022), and the associated entropic optimizers admit quantitative large-deviation asymptotics with local exponential rates Bernton, Ghosal and Nutz (2022). Diffusion Schrödinger bridge matching introduces iterative Markovian fitting as a bridge-matching procedure Shi et al. (2023); related iterative methods are studied in Peluchetti (2023); Kholkin et al. (2024); and Gentiloni Silveri, Conforti and Durmus (2025) establishes non-asymptotic exponential convergence guarantees for iterative Markovian fitting. Our results instead concern unregularized rectified-flow iteration and convergence to classical optimal transport. A.0.0.2. Score-based estimation and sampling.. Classical score matching estimates unnormalized models through the score of the log density Hyvärinen (2005), and denoising score matching provides a practical way to estimate scores after Gaussian smoothing Vincent (2011). These ideas became central in score-based generative modeling, where reverse-time diffusions use estimated scores to sample from an unknown distribution Song et al. (2021). The recent work Dou et al. (2024) studies how optimal score-estimation rates can be converted into optimal sampling guarantees, and its algorithmic structure is closely related to the projected reverse sampler used in our statistical section. In our setting, the resulting marginal estimator is an input to optimal-transport-map estimation based on c-rectified flow. A.0.0.3. Entropic statistical optimal transport.. Sinkhorn-type estimators are computationally efficient and statistically more stable than unregularized empirical optimal transport. The sample complexity of Sinkhorn divergences was studied by Genevay et al. (2019), while Mena and Weed (2019) obtained statistical bounds and central limit theorems for entropic optimal transport. More recently, Rigollet and Stromme (2025) proved dimension-free parametric rates for several entropic optimal transport quantities. In the semi-discrete setting, Pooladian, Divol and Niles-Weed (2023) proved a minimax-optimal dimension-independent n−1/2 rate for an entropic estimator of discontinuous optimal transport maps. These estimators target regularized quantities, so their statistical benefits must be balanced against regularization bias. The barycentric projection of the empirical entropic plan was analyzed by Pooladian and Niles-Weed (2021), which obtained finite-sample guarantees for a computationally tractable Sinkhorn-based map estimator. The role of regularization bias was further studied by Pooladian, Cuturi and Niles-Weed (2022), while stability results for entropic Brenier maps in Divol, Niles-Weed and Pooladian (2025b) quantify how regularized maps vary with the target measure. This literature complements the minimax theory for unregularized plug-in optimal transport map estimators studied in the main body.

COMP & STAT GUARANTEES OF C-RECT FLOW

23

APPENDIX B: ADDITIONAL DETAILS FOR SECTION 2 B.1. Additional optimal-transport facts. The Kantorovich problem can be regarded as an infinite-dimensional linear program, hence admits a dual formulation: Z  Z 1 2 (11) W (P, Q) = sup f dP + gdQ , 2 2 (f,g)∈F where   1 1 1 2 F := (f, g) : f ∈ L (P ), g ∈ L (Q), f (x) + g(y) ≤ ∥x − y∥ . 2 The functions (f, g) are called Kantorovich potentials. Under the finite second moment assumption, there exists a maximizing pair of Kantorovich potentials (f0 , g0 ) solving (11) Villani (2009). The following fundamental theorem shows that, under absolute continuity of the source measure, the Kantorovich and Monge formulations are unified by a unique optimal map. T HEOREM 13 (Brenier’s theorem Knott and Smith (1984); Villani (2009)). Let P ∈ P2 (Rd ) be absolutely continuous with respect to the Lebesgue measure, and let Q ∈ P2 (Rd ). Then there exists a P -a.e. unique optimal transport map T ∗ from P to Q. Moreover, there exists a convex function φ0 : Rd → R such that T ∗ = ∇φ0

P -a.e.

The unique optimal coupling in (1) is induced by the map dπ0 (x, y) = dP (x) · δT ∗ (x) (y). Thus, when the source distribution has a density, the optimal coupling is concentrated on the graph of a deterministic map. In particular, the solution of the Kantorovich problem (1) induces the solution of the Monge problem (2). The Brenier potential can also be obtained from the Kantorovich potentials. Let (f0 , g0 ) be optimal potentials for (11), and define 1 1 ψ0 (y) := ∥y∥2 − g0 (y). φ0 (x) := ∥x∥2 − f0 (x), 2 2 Then φ0 and ψ0 are convex functions, and φ0 is the Brenier potential whose gradient gives the optimal transport map from P to Q: T ∗ = ∇φ0 , P -a.e. If Q is also absolutely continuous, then the inverse optimal transport map from Q to P is given by (T ∗ )−1 = ∇ψ0 , Q-a.e. Moreover, φ0 and ψ0 are convex conjugates of one another, that is, ψ0 = φ∗0 . The Kantorovich dual can be rewritten in a more concise way in terms of the Brenier potentials. Specifically, if φ∗ denotes the Legendre–Fenchel conjugate of φ, then we have the semi-dual formulation Z  Z Z Z 1 2 1 1 2 2 ∗ (13) W (P, Q) = ∥x∥ dP (x) + ∥y∥ dQ(y) − inf φdP + φ dQ , φ 2 2 2 2

(12)

where the infimum is taken over suitable functions φ for which the two integrals are welldefined. Under the assumptions of Brenier’s theorem, the minimizer of (13) is precisely the Brenier potential φ0 , and the optimal transport map is recovered as T ∗ = ∇φ0 . This semidual perspective is frequently used for statistical estimation of optimal transport maps; for example, Hütter and Rigollet (2021) studies (13) over smooth function classes such as functions with bounded Hölder norms.

24

We also recall the dynamic formulation of optimal transport. Let (ρt )t∈[0,1] be a curve of probability measures on Rd such that ρ0 = P and ρ1 = Q. If particles evolve according to the velocity field vt : Rd → Rd , equivalently, if Xt ∼ ρt follows the ODE dXt = vt (Xt )dt,

then the evolution of their law is described by the continuity equation ∂t ρt + ∇ · (ρt vt ) = 0,

understood in the weak sense. The Benamou–Brenier formula gives a dynamic characterization of the 2-Wasserstein distance, which states that the optimal coupling is related to the minimizer of the total kinetic energy along the path space: Z 1Z Z 1 1 2 1 1 2 (14) W (P, Q) = inf ∥vt (x)∥ dρt (x)dt = inf E∥vt (Xt )∥2 dt, ρt ,vt 0 ρ ,v 2 2 2 2 t t Rd 0 where the infimum is taken over all pairs (ρt , vt ) satisfying the continuity equation and the boundary conditions ρ0 = P , ρ1 = Q Benamou and Brenier (2000); Villani (2009). Under the assumptions of Brenier’s theorem, let T be the optimal transport map from P to Q. Then the minimizing path in (14) is the constant-speed displacement interpolation t ∈ [0, 1], X0 ∼ P.
Equivalently, the intermediate law is ρt = (1 − t)Id + tT # P for all t ∈ [0, 1]. The curve

(15)

Xt = (1 − t)X0 + tT (X0 ),

(ρt )t∈[0,1] is a constant-speed geodesic in the Wasserstein space (P2 (Rd ), W2 ).

B.2. Statistical OT background. B.3. Statistical Property for Optimal Transport. We briefly recall the statistical estimation problem for optimal transport. In statistical estimation problems, P and Q are typically unknown and are observed through finite given samples. For instance, given i.i.d. samples X1 , . . . , Xn ∼ P and Y1 , . . . , Ym ∼ Q, one forms the empirical measures Pbn = P b m = m−1 Pm δYj . Natural plug-in estimators of transport costs are n−1 ni=1 δXi and Q j=1 b b m ), in the two-sample case. A centhen Wp (Pn , Q), in the one-sample case, or Wp (Pbn , Q tral question is to quantify the error between these empirical quantities and their population b m ) − Wp (P, Q)| or |Wpp (Pbn , Q b m ) − Wpp (P, Q)|. counterparts, for example |Wp (Pbn , Q The first major phenomenon in this literature is the curse of dimensionality. For general distributions on Rd , the empirical measure converges in Wasserstein distance at dimensiondependent rates. Nonasymptotic bounds of this type were obtained by Fournier and Guillin (2015), while sharp finite-sample and asymptotic rates were further developed by Weed and Bach (2019). In a representative compactly supported setting, the empirical Wasserstein error satisfies dimension-dependent rates of the form  −1/2 ,  d < 2p, n p −1/2 EWp (µ bn , µ) ≲ n log n, d = 2p,   −p/d n , d > 2p, up to assumptions and constants depending on the support and moment conditions; see Fournier and Guillin (2015); Weed and Bach (2019). Niles-Weed and Rigollet (2022) con1 struct a case in which the minimax rate (of the estimation of W2 (P, Q)) is at least Cn− d for large d and a constant C . Thus, when d > 2p, Wp (µ bn , µ) typically behaves like n−1/d , displaying the classical curse of dimensionality for empirical optimal transport. There is also

25

COMP & STAT GUARANTEES OF C-RECT FLOW

a line of work that studies statistical estimation of optimal transport maps under additional structural assumptions on the Brenier map. For example, Hütter and Rigollet (2021) considers optimal transport problem with quadratic loss, and studies the minimax rate for estimating T ∗ . In contrast to the distribution-free empirical Wasserstein theory, this setting imposes structural regularity assumptions on the transport map and on the underlying measures. The smoothness of the transport map is measured through ∥T ∗ ∥C α ≤ R for a fixed constant α and R. The estimation error is measured in the loss ∥T̂ − T ∗ ∥2P = EP ∥T̂ (X) − T ∗ (X)∥2 , where T̂ is an estimator constructed from the samples. Under these assumptions, Hütter and Rigollet (2021) proves the minimax lower bound 2α

inf sup ∥T̂ − T ∗ ∥2P ≳ n− 2α−2+d ∨ n−1 , T̂ P,T ∗

where the supremum is taken over the admissible pairs (P, T ∗ ) satisfying the above regularity conditions. They also construct an estimator T̂ using an estimator constructed on a wavelet basis such that 2α

sup ∥T̂ − T ∗ ∥2P ≲ n− 2α−2+d (log n)2 ∨ n−1 .

P,T

∗

2α

Thus, up to the logarithmic factor in the upper bound, the minimax rate is n− 2α−2+d ∨ n−1 . The remaining logarithmic gap is conjectured in Hütter and Rigollet (2021) to be removable. These results show how smoothness of the Brenier map can partially offset the statistical curse of dimensionality: when T ∗ is very smooth, namely when α is large, the rate approaches the parametric order n−1 ; however, when α is small and d is large, the rate remains slow and is close to the high-dimensional empirical-OT behavior. Another line of work studies the estimation of entropic optimal transport, where the objective is Z  2 inf ∥x − y∥ dπ(x, y) + η · KL (π ∥ P ⊗ Q) . π∈Π(P,Q)

Rd ×Rd

We discuss this line of work in the related work section and omit further details here. B.4. Additional rectified-flow facts. The basic properties of rectification are the following. First, since X and Z have the same expected velocity field, they have the same time marginals; in particular, L(Z1 ) = L(X1 ), and L(Zt ) = L(Xt ) for all t ∈ [0, 1]. Second, for any convex function c : Rd → R, E[c(Z1 − Z0 )] ≤ E[c(X1 − X0 )]. For the detailed proof of the above facts, we refer to (Liu, Gong and Liu, 2022, Theorem 3.3, 3.5). (0) (0) Therefore, the rectified flow can be iterated. Starting from an initial coupling (Z0 , Z1 ) = (X0 , X1 ), define recursively (k)

(k)

(k−1)

(Z0 , Z1 ) = Rectify((Z0 (k)

(k)

(k−1)

, Z1

)), (k)

Then L(Z0 ) = L(X0 ) = P , L(Z1 ) = L(X1 ) = Q, and for every convex c, E[c(Z1 − (k) Z0 )] is non-increasing in k . In practice, one estimates v X from samples by solving (4) over a parameterized class, solves the ODE (5) with the fitted field, and then uses the resulting (k) (k) pair (Z0 , Z1 ) to fit a transport map. This gives a learned transport from P to Q, although the limiting coupling is not necessarily optimal for a prescribed transport cost. If we view the rectified flow as an optimization algorithm on the path space of timedifferentiable stochastic processes with path-wise c-transport cost, then one-step rectified flow will be a one-step steepest descent. For a time-differentiable stochastic process Y , define Z 1 h i Fc (Y ) = (16) E c(Ẏs ) ds. 0

26

For every convex functions c : Rd → R,  Z = arg min Fc (Y ) s.t. v Y = v X .

L EMMA 4 (Lemma 3.3 in Liu (2022)). (17)

Z = Rectify(X)

⇐⇒

Y

B.5. Additional c-rectified-flow facts. B.5.0.1. Marginal-preserving vector fields.. We first define the notion of marginal-preserving vector fields. Let X = {Xt : t ∈ [0, 1]} be a stochastic process. D EFINITION 1 (Marginal-preserving vector field). A vector field r : Rd × [0, 1] → Rd is called X -marginal-preserving if, for every t ∈ [0, 1] and every h ∈ Cc1 (Rd ), Z t E[∇h(Xs )⊤ rs (Xs )]ds = 0. 0

This condition means that r contributes zero to the weak continuity equation along the marginal curve L(Xt ). The following characterization is the basic tool used in c-rectified flow. T HEOREM 14 (Lemma 4.2 in Liu (2022)). Let X and Y be time-differentiable stochastic processes such that L(X0 ) = L(Y0 ). Assume that X is rectifiable and that v Y exists and is locally bounded. Then L(Xt ) = L(Yt ), for all t ∈ [0, 1], if and only if v X − v Y is Y marginal-preserving. T HEOREM 15 (Theorem 4.2 in Liu (2022)). For a c-rectifiable X and c∗ ∈ C 1 (Rd ), let Z = c-Rectify(X), we have L(Zt ) = L(Xt ) for t ∈ [0, 1]. B.5.0.2. c-Rectified duality formulation.. Back to the viewpoint of the rectified flow algorithm as an optimization on path space, A natural relaxation of (17) would be (18)

Z = arg min {Fc (Y ), Y

s.t. L(Yt ) = L(Xt ), ∀t ∈ [0, 1]} ,

For each continuously differentiable f : Rd × [0, 1] → Rd , Fenchel’s inequality and Theorem 14 yield (19) Z 1 Fc (X) − Fc (Y ) =

Z 1 E[c(Ẋs ) − c(Ẏs )]ds ≤

0

Z 1 =

E[c(Ẋs ) + c∗ (∇fs (Ys )) − ⟨∇fs (Ys ), Ẏs ⟩]ds

0

E[c(Ẋs ) + c∗ (∇fs (Ys )) − ⟨∇fs (Ys ), vsY (Ys )⟩]ds

0

(20) Z 1 =

∗

E[c(Ẋs ) + c (∇fs (Xs )) − ⟨∇fs (Ys ), vsX (Ys )⟩]ds =

0

Z 1 E[mc (Ẋs , ∇fs (Xs ))]ds, 0

where (19) is because c(x) + c∗ (y) ≥ ⟨x, y⟩ and (20) is because v X − v Y is Y -marginalpreserving as stated in Theorem 14. Therefore, (19) takes equality if and only if Ẏs = ∇c∗ (∇fs (Ys )) for almost every s. This suggests the strong duality, as presented in (Liu, 2022, Theorem 5.3), that (21)   Z 1 n o min LX,c (f ) := E[mc (Ẋs , ∇fs (Xs ))]ds = sup Fc (X) − Fc (Y ) : L(Xt ) = L(Yt ), ∀t ∈ [0, 1] , f

0

Y

27

COMP & STAT GUARANTEES OF C-RECT FLOW

R EMARK 3.

For the rectified flow, the analogous dual identity is Z 1 n o inf E[bc (Ẋs ; vs (Xs ))]ds = sup Fc (X) − Fc (Y ) : v X = v Y . v

Y

0

B.5.0.3. Stationary points of c-rectified flow.. The next result identifies whether a stationary coupling of the c-rectified flow must be optimal. T HEOREM 16 (Theorem 5.6 in Liu (2022)). Let c be convex with c, c∗ ∈ C 1 (Rd ), and let X = {Xt = tX1 + (1 − t)X0 : t ∈ [0, 1]} for a coupling (X0 , X1 ). Assume that X is c-rectifiable and that f X,c ∈ C 2,1 (Rd × [0, 1]) minimizes LX,c . Then the following are equivalent: (X0 , X1 ) = c-Rectify((X0 , X1 )) ⇐⇒ LX,c (f X,c ) = 0 ⇐⇒ (X0 , X1 ) is a c-optimal coupling.

B.5.0.4. Decrease of transport cost.. Define Sc (X) = Fc (X) − E[c(X1 − X0 )], where recall Fc is defined at (16). By the convexity of c and Jensen’s inequality, for every time differentiable process X , we always have Sc (X) ≥ 0. Also, If X is the linear interpolation process between X0 and X1 , then Ẋt = X1 − X0 for all t ∈ [0, 1], we have Sc (X) = 0. Now let Y = c-Rectify(X), so that (Y0 , Y1 ) = c-Rectify(X0 , X1 ). By the dual identity (21), Fc (X) − Fc (Y ) = LX,c (f X,c ).

(22)

Therefore, we have the following inequality (23) E[c(X1 − X0 )] − E[c(Y1 − Y0 )] = Fc (X) − Fc (Y ) + Sc (Y ) = LX,c (f X,c ) + Sc (Y ) ≥ 0. Hence c-rectification does not increase the transport cost. In particular, the sequence of couplings generated by Algorithm 1 has non-increasing transport cost. Finally, by (23), for every K ≥ 1, K X

LZ (k) ,c (f

k=1

Z (k) ,c

)≤

K  X

(k−1)

E[c(Z0

(k−1)

− Z1

 (k) (k) )] − E[c(Z0 − Z1 )]

k=1 (0)

(0)

(K)

= E[c(Z1 − Z0 )] − E[c(Z0

(K)

− Z1

(0)

(0)

)] ≤ E[c(Z1 − Z0 )] < +∞.

Therefore, as stated in (Liu, 2022, Corollary 5.7), (24)

min LZ (k) ,c (f Z

k≤K

(k)

,c

) = O(1/K).

APPENDIX C: PROOF OF SECTION 3.1 P ROOF OF P ROPOSITION 1. Since (X0 , X1 ) is jointly Gaussian, the pair (X1 − X0 , Xt ) is jointly Gaussian and centered. Therefore, E[X1 − X0 | Xt = x] = Cov(X1 − X0 , Xt )Σ−1 t x. Moreover, Cov(X1 − X0 , Xt ) = Cov X1 − X0 , (1 − t)X0 + tX1

= (1 − t) Cov(X1 , X0 ) − Cov(X0 , X0 ) + t Cov(X1 , X1 ) − Cov(X0 , X1 ) = (1 − t)(Σ⊤ 01 − Σ1 ) + t(Σ2 − Σ01 ).

Substituting this identity into the Gaussian conditional expectation formula gives (7).

28 −1/2

−1/2

P ROOF OF L EMMA 1. Denote M = Σ1 Σ2 Σ1 , then M is symmetric positive definite. We factorize Σt and the numerator in the drift as
1/2
1/2 1/2 1/2 Σt = Σ1 (1 − t)2 I + t2 M Σ1 , tΣ2 − (1 − t)Σ1 = Σ1 tM − (1 − t)I Σ1 . Substituting these expressions into the ODE gives h

−1 i −1/2 1/2 ∂t Zt = Σ 1 tM − (1 − t)I (1 − t)2 I + t2 M Σ1 Zt . −1/2

Zt for all t ∈ [0, 1], then

−1

−1 1 −1/2 ∂t Yt = Σ1 ∂t Zt = tM −(1−t)I (1−t)2 I +t2 M Yt = ∂t (1−t)2 I +t2 M (1−t)2 I +t2 M Yt . 2

Now define the whitened variable Yt := Σ1

Since each (1 − t)2 I + t2 M is a polynomial in M , they commute for all t1 , t2 . Therefore, 

−1


∂s (1−s)2 I +s2 M (1−s)2 I +s2 M ds = log (1−t)2 I +t2 M −log I = log (1−t)2 I +t2 M , Hence Yt = exp

1 2

log (1 − t)2 I + t2 M



1/2

Y0 = (1 − t)2 I + t2 M

1/2

Transforming back, we obtain Zt = Σ1 Yt = Σ1

(1 − t)2 I + t2 M

1/2

1/2

Y0 .

−1/2

Σ1

Z0 , which is 1/2 −1/2 exactly the claimed formula. Evaluating at t = 1 particularly yields that Z1 = Σ1 M 1/2 Σ1 Z0 = T Z0 .

P ROOF OF L EMMA 2. Since Xt = (1 − t)I + tL X0 , we have X0 = (1 − t)I +
−1 tL Xt almost surely. Therefore vt (x) = E[(L − I)X0 | Xt = x] = (L − I) (1 − t)I +
−1 tL x.
Now consider Z̃t := (1 − t)I + tL Z0 . Then ∂t Z̃t = (L − I)Z0 . On the other hand,
−1
−1
(L − I) (1 − t)I + tL Z̃t = (L − I) (1 − t)I + tL (1 − t)I + tL Z0 = (L − I)Z0 .
−1 Thus ∂t Z̃t = (L − I) (1 − t)I + tL Z̃t , so Z̃t indeed solves the ODE. By the existence and
uniqueness of the linear ODE system, we have Zt = Z̃t = (1 − t)I + tL Z0 . Evaluating at t = 1 gives Z1 = LZ0 . Hence the deterministic coupling map L is preserved by reflow. P ROOF OF P ROPOSITION 2. By Lemma 1, the first run of rectified flow produces the deterministic coupling X1 = T X0 . Applying Lemma 2 with L = T shows that every subsequent run preserves this coupling. Thus the algorithm stabilizes at the map T after one step. Then, we compare T with the Gaussian optimal transport map TOT . −1/2 First assume that Σ1 and Σ2 commute. Then Σ1 and Σ2 also commute, and hence −1/2 −1/2 −1 Σ1 Σ2 Σ1 = Σ1 Σ2 . Therefore
1/2 −1/2 1/2 1/2 −1/2 T = Σ1 Σ−1 Σ1 = Σ 2 Σ1 . 1 Σ2
1/2 −1/2 1/2 −1/2 1/2 −1/2 Similarly, since Σ1 and Σ2 commute, TOT = Σ1 Σ1 Σ2 Σ1 = Σ2 Σ1 . Hence T = TOT . Conversely, assume that T = TOT . Since TOT is symmetric positive definite, T must be symmetric. Write −1/2

M := Σ1

−1/2

Σ2 Σ1

.

29

COMP & STAT GUARANTEES OF C-RECT FLOW −1/2

1/2

Then T = Σ1 M 1/2 Σ1

. The symmetry of T gives T = T ⊤ , which is, −1/2

1/2

Σ1 M 1/2 Σ1

−1/2

= Σ1

1/2

M 1/2 Σ1 .

1/2

Multiplying on the left and right by Σ1 yields Σ1 M 1/2 = M 1/2 Σ1 . Therefore, Σ1 commutes with M 1/2 , and hence also with M = M 1/2 M 1/2 . Since M commutes with Σ1 , M also commutes with every spectral function of Σ1 , in 1/2 1/2 1/2 particular with Σ1 . Using Σ2 = Σ1 M Σ1 , we compute 1/2

1/2

Σ1 Σ2 = Σ 1 Σ1 M Σ 1

3/2

1/2

= Σ 1 M Σ1

1/2

3/2

= Σ 1 M Σ1

1/2

1/2

= Σ1 M Σ1 Σ1 = Σ2 Σ1 ,

where we used the commutation of Σ1 and M . Thus Σ1 Σ2 = Σ2 Σ1 . We have thus shown that T = TOT implies Σ1 Σ2 = Σ2 Σ1 . Together with the first implication, this proves the equivalence. Hence noncommuting covariances lead after one step to a non-optimal fixed point of rectified flow. APPENDIX D: PROOF OF SECTION 2.5 (k)

(k)

L EMMA 5 (Continuity of integrated losses). Let Z (k) = (Z0 , Z1 ) ⇒ Z ∗ = (Z0∗ , Z1∗ ) (k) (k) (k) in Rd × Rd , and define Zt = (1 − t)Z0 + tZ1 , Zt∗ = (1 − t)Z0∗ + tZ1∗ . Let hk , h∗ : Rd × [0, 1] → Rm be continuous functions such that hk → h∗ locally uniformly on Rd × [0, 1], and let ℓ : Rd × Rm → [0, ∞) be continuous. Define Z 1 Z 1

(k) (k) (k) Vk := ℓ Z1 − Z0 ; hk (Zt , t) dt, V∗ := ℓ Z1∗ − Z0∗ ; h∗ (Zt∗ , t) dt. 0

0

If {Vk }k≥1 is uniformly integrable, then E[Vk ] −→ E[V∗ ]. P ROOF OF L EMMA 5. By the Skorokhod representation theorem, after replacing the random variables by copies with the same laws on a common probability space, we may assume that (k)

(k)

(Z0 , Z1 ) −→ (Z0∗ , Z1∗ )

almost surely.

Fix an event ω for which this convergence holds. Then (k)

(k)

(k)

sup Zt (ω) − Zt∗ (ω) ≤ ∥Z0 (ω) − Z0∗ (ω)∥ + ∥Z1 (ω) − Z1∗ (ω)∥ −→ 0.

t∈[0,1]

(k)

In particular, there exists R = R(ω) < ∞ such that Zt (ω), Zt∗ (ω) ∈ B(0, R) for every t ∈ [0, 1] and every k . Using the local uniform convergence of hk and the uniform continuity of h∗ on the compact set B(0, R) × [0, 1], we obtain (k)

sup hk (Zt (ω), t) − h∗ (Zt∗ (ω), t)

t∈[0,1]

≤

sup

(k)

∥hk (x, t) − h∗ (x, t)∥ + sup h∗ (Zt (ω), t) − h∗ (Zt∗ (ω), t) −→ 0. t∈[0,1]

(x,t)∈B(0,R)×[0,1] (k)

(k)

Moreover, Z1 (ω) − Z0 (ω) −→ Z1∗ (ω) − Z0∗ (ω). By the continuity of ℓ, which implies uniform continuity on this compact set,

(k) (k) (k) sup ℓ Z1 − Z0 ; hk (Zt , t) − ℓ Z1∗ − Z0∗ ; h∗ (Zt∗ , t) −→ 0 t∈[0,1]

30

almost surely. Consequently, we have almost surely that Vk −→ V∗ . Since {Vk }k≥1 is uniformly integrable, Vitali’s theorem yields E[Vk ] −→ E[V∗ ]. Because the expectations involved depend only on the laws of the random variables, the conclusion also holds on the original probability spaces. (k)

(k)

P ROOF OF T HEOREM 1. Since E[∥Z1 − Z0 ∥2 ] is decreasing in k by the cost-decrease inequality (23), applied with the quadratic cost, it is enough to show that there exists a sub(k ) (k ) sequence {kj }j∈N such that limj→∞ E[∥Z1 j − Z0 j ∥2 ] = W22 (P, Q). By (24), we already know that for every K > 0, there exists k ≤ K such that   1 (k) LZ (k) (f Z ) = O , K (k)

therefore, we may choose an increasing subsequence, still denoted by k , such that LZ (k) (f Z ) → 0 as k → ∞. Fix an arbitrary ϵ > 0. Since P and Q are tight, there exist compact sets Aϵ , Bϵ ∈ Rd such that P (Acϵ ) < ϵ, Q(Bϵc ) < ϵ. Let Cϵ = Aϵ × Bϵ , then for every k ∈ N, (k)

(k)

(k)

(k)

(k)

(k)

P((Z0 , Z1 ) ∈ Cϵc ) ≤ P(Z0 ∈ Acϵ ) + P(Z1 ∈ Bϵc ) = P (Acϵ ) + Q(Bϵc ) < 2ϵ. Hence {(Z0 , Z1 )}k∈N is tight. By Prokhorov’s Theorem, there exist a subsequence, still (k) (k) denoted by {(Z0 , Z1 )}k∈N , and a random vector (Z0∗ , Z1∗ ) such that as k → ∞, (k)

(k)

(Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ). (k)

(k)

Since Z0 ∼ P and Z1 ∼ Q for all k , we also have Z0∗ ∼ P and Z1∗ ∼ Q. For each m ∈ N, let Km := B(0, m) × [0, 1]. By our assumption, for every m there exists Cm > 0 such that (k)

sup ∥f Z ∥C 2+α,1+α (Km ) ≤ Cm . k

Hence, for every multi-index β with |β| ≤ 2, the family {Dxβ f Z }k≥1 is uniformly bounded (k) and equicontinuous on Km , and the same is true for {∂t f Z }k≥1 . By the Arzelà–Ascoli (k) (k) theorem, for each fixed m one may extract a subsequence such that f Z , Dxβ f Z (|β| ≤ (k) 2), ∂t f Z all converge uniformly on Km . Applying this successively for m = 1, 2, . . . and using a diagonal argument, we obtain (k) (k) (k) a subsequence, still denoted by {f Z }, such that for every m, f Z , Dxβ f Z (|β| ≤ (k) 2), ∂t f Z converge uniformly on Km as k → ∞. Denote the corresponding limits by ∗ f , gβ (|β| ≤ 2), h. (k) We verify that gβ = Dxβ f ∗ for arbitrary |β| ≤ 2, and h = ∂t f ∗ . Fix m ∈ N. Since f Z → (k) f ∗ , ∂xi f Z → gei uniformly on Km , for any (x, t) ∈ Km and any δ ∈ R such that (x + sei , t) ∈ Km for all s ∈ [0, δ], we have Z δ (k) Z (k) Z (k) f (x + δei , t) − f (x, t) = ∂xi f Z (x + sei , t) ds. (k)

0

Passing to the limit as k → ∞ yields ∗

∗

Z δ

f (x + δei , t) − f (x, t) =

gei (x + sei , t) ds. 0

Since gei is continuous on Km , dividing by δ and letting δ → 0 gives ∂xi f ∗ (x, t) = gei (x, t). Hence f ∗ is C 1 in the spatial variables on Km , and ∇x f ∗ = (ge1 , . . . , ged ).

31

COMP & STAT GUARANTEES OF C-RECT FLOW (k)

(k)

Next, fix i, j ∈ {1, . . . , d}. Since ∂xi f Z → gei , ∂xj ∂xi f Z → gei +ej uniformly on (k) Km , the same argument applied to ∂xi f Z shows that on Km , ∂xj gei = gei +ej . Because gei = ∂xi f ∗ , this implies that on Km , ∂xj ∂xi f ∗ = gei +ej . Therefore, f ∗ is twice continuously differentiable in x on Km with Dxβ f ∗ = gβ , for arbitrary |β| ≤ 2. (k) (k) Similarly, since f Z → f ∗ , ∂t f Z → h uniformly on Km , we have ∂t f ∗ (x, t) = h(x, t). Thus f ∗ ∈ C 2,1 (Km ). Since m is arbitrary, we conclude that f ∗ ∈ C 2,1 (Rd × [0, 1]). More(k) (k) over, for each m, f Z → f ∗ in C 2,1 (Km ), and in particular, ∇x f Z → ∇x f ∗ uniformly on every compact subset of Rd × [0, 1]. (k) We apply Lemma 5 with hk (x, t) := ∇ftZ (x), h∗ (x, t) := ∇ft∗ (x), ℓ(a; b) := ∥a − b∥2 . The required local uniform convergence of hk to h∗ follows from the preceding compactness argument. It remains only to verify uniform integrability of the corresponding integrated losses Z 1 (k) (k) (k) (k) 2 Vk := Z1 − Z0 − ∇ftZ (Zt ) dt. 0

(k)

By the Cauchy-Schwarz inequality and the assumption ∥∇ftZ (x)∥ ≤ Cg(x), we have Z 1 Z 1 (k) (k) 2 (k) 2 (k) 2 (k) 2 (k) Z (k) 2 Vk ≤ 2∥Z1 − Z0 ∥ + 2 ∇ft (Zt ) dt ≤ 4∥Z0 ∥ + 4∥Z1 ∥ + 2C g(Zt )2 dt. 0

0

(k) (k) (k) 2 Since Z0 ∼ P and Z1 ∼ Q for every k , and P, Q ∈ P2 (Rd )n, the families {∥Z o 0 ∥ }k≥1 R (k) (k) 2 1 and {∥Z1 ∥2 }k≥1 are uniformly integrable. By assumption, 0 g(Zt ) dt k≥1 is also

uniformly integrable. Hence {Vk }k≥1 is uniformly integrable. Lemma 5 therefore gives Z 1  (k) LZ (k) (f Z ) = E[Vk ] −→ E ∥Z1∗ − Z0∗ − ∇ft∗ (Zt∗ )∥2 dt = LZ ∗ (f ∗ ). 0 Z (k) ) −→ 0, we conclude that L (k) (f

∗ Since LZ Z ∗ (f ) = 0. Therefore, by Theorem 16, (Z0∗ , Z1∗ ) is an optimal coupling of (P, Q). It remains to prove the claimed full weak convergence under uniqueness. Since the family (k) (k) (k ) (k ) {(Z0 , Z1 )}k≥1 is tight, every subsequence {(Z0 j , Z1 j )}j≥1 admits a further weakly convergent subsequence, and the limit is given by the optimal coupling (Z0∗ , Z1∗ ) for the same (k) (k) reason as above. This implies that the full sequence satisfies (Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ).

R EMARK 4. The uniform integrability assumption in the theorem is automatically satisfied if g has polynomial growth. More precisely, suppose there exist constants C > 0 and p ≥ 0 such that g(x) ≤ C(1 + |x|p ) for all x ∈ Rd . If P and Q have finite 2p + ϵ-moments, then the family Z 1 
(k) 2 g Zs ds 0

k≥1

is uniformly integrable. (k) (k) (k) Indeed, since |Zt | ≤ |Z0 | + |Z1 |, using Hölder’s inequality, Z 1
(k) 2 (k) 2p (k) 2p (k) 2p
(k) (k) (k) g(Zt ) ≤ C(1+|Zt | ) ≤ C 1+|Z0 | +|Z1 | =⇒ g(Zt )2 dt ≤ C 1+|Z0 |2p +|Z1 |2p . 0

(k) (k) Since Z0 ∼ P and Z1 ∼ Q for all k , and P, Q have finite 2p + n ϵ-moments, the families o R1 (k) 2p (k) 2p (k) 2 {|Z0 | }k≥1 , {|Z1 | }k≥1 are uniformly integrable. Therefore g(Z ) dt is t 0 k≥1

uniformly integrable.

32

Especially, if P and Q follow a Gaussian distribution, then g will be a linear function, satisfying all the above. D.1. Proof of Section 5.1. (k)

(k)

P ROOF OF T HEOREM 9. Since E[c(Z1 − Z0 )] is decreasing along the iteration, it suffices to find a subsequence {kj }j∈N such that (k )

(k )

lim E[c(Z1 j − Z0 j )] =

j→∞

inf

X∼P, Y ∼Q

E[c(X − Y )].

By the c-analogue of (24), after passing to a subsequence, still denoted by k , we may assume (k) LZ (k) (f Z ) → 0. (k) (k) The tightness argument for {(Z0 , Z1 )}k≥1 is exactly the same as in the proof of The(k) (k) orem 1. Hence, after passing to a further subsequence, (Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ) for some ∗ ∗ ∗ coupling Z := (Z0 , Z1 ) of (P, Q). By the local C 2+α,1+α bound and the same diagonal Arzelà–Ascoli argument as in the proof of Theorem 1, after passing to another subsequence we may assume that there exists (k) f ∗ ∈ C 2,1 (Rd × [0, 1]) such that f Z → f ∗ in C 2,1 (K) for every compact K ⊂ Rd × [0, 1]. (k) In particular, ∇x f Z → ∇x f ∗ locally uniformly on Rd × [0, 1]. Since ∇c∗ is continuous, it follows that (k)

gk (x, s) = (∇c∗ ◦ ∇fsZ )(x) → g∗ (x, s) := (∇c∗ ◦ ∇fs∗ )(x)

locally uniformly on Rd × [0, 1]. Now, we apply Lemma 5 with hk (x, t) := gk (x, t), h∗ (x, t) := g∗ (x, t), ℓ(a; b) := bc (a; b). Here bc is continuous by assumption, and the preceding argument gives the required local uniform convergence gk → g∗ . Define Z 1
(k) (k) (k) Vk := bc Z1 − Z0 ; gk (Zt , t) dt. 0

By the assumed growth bound on bc ,   Z 1h Z 1
i
(k) (k) (k) (k) (k) (k) Vk ≤ C 1 + Φ(Z1 − Z0 ) + Ψ gk (Zt , t) dt = C 1 + Φ(Z1 − Z0 ) + Ψ gk (Zt , t) dt . 0

0

By assumption, the two nonconstant terms on the right-hand side form uniformly integrable families. Hence {Vk }k≥1 is uniformly integrable. Lemma 5 therefore yields Z 1 
Z (k) ∗ ∗ ∗ LZ (k) (f ) = E[Vk ] −→ E bc Z1 − Z0 ; g∗ (Zt , t) dt = LZ ∗ (f ∗ ). 0 (k) Since LZ (k) (f Z ) −→ 0, we conclude that LZ ∗ (f ∗ ) = 0. Therefore, (Z0∗ , Z1∗ ) is an optimal

coupling of (P, Q) under the cost c(y − x). (k) (k) (k) (k) (k) Finally, since (Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ), we have Z1 − Z0 ⇒ Z1∗ − Z0∗ . Thus c(Z1 − (k) (k) (k) Z0 ) ⇒ c(Z1∗ − Z0∗ ). Because {c(Z1 − Z0 )}k≥1 is uniformly integrable, Vitali’s theorem (k) (k) yields E[c(Z1 − Z0 )] → E[c(Z1∗ − Z0∗ )]. Since Z ∗ is c-optimal, we obtain (k)

(k)

lim E[c(Z1 − Z0 )] =

k→∞

This completes the proof.

inf

X∼P, Y ∼Q

E[c(X − Y )].

33

COMP & STAT GUARANTEES OF C-RECT FLOW

APPENDIX E: PROOF OF SECTION 3.2 E.0.1. Technical Preparation . We begin with two elementary structural facts that will be used throughout the proof. E.0.1.1. Factorization of linear transports.. Every linear transport can be regarded as a matrix T ∈ Rd×d and T (x) = T x, T# P = Q ⇐⇒ T Σ1 T ⊤ = Σ2 .

The quadratic-cost optimal transport map is also linear: −1/2 1/2 1/2
1/2 −1/2 (25) T ∗ (x) = Σ1 Σ1 Σ2 Σ1 Σ1 x := T ∗ x, so that T ∗ is symmetric positive definite and T ∗ Σ1 T ∗ = Σ2 . L EMMA 6 (Factorization by a Σ1 -rotation). Let T satisfy T Σ1 T ⊤ = Σ2 , and let T ∗ be as in (25). Then there exists a unique matrix U such that T = T ∗ U,

U Σ1 U ⊤ = Σ1 .

In particular, U is orthogonal with respect to the inner product ⟨x, y⟩Σ−1 := x⊤ Σ−1 1 y . When 1 Σ1 = I , U is an ordinary orthogonal matrix. P ROOF OF L EMMA 6. Define U := (T ∗ )−1 T . Using (T ∗ )⊤ = T ∗ , T ∗ Σ1 T ∗ = Σ2 and T Σ1 T ⊤ = Σ2 , U Σ1 U ⊤ = (T ∗ )−1 T Σ1 T ⊤ (T ∗ )−1 = (T ∗ )−1 Σ2 (T ∗ )−1 = Σ1 .

Thus T = T ∗ U with U Σ1 U ⊤ = Σ1 . Uniqueness is immediate since T ∗ is invertible. Henceforth we write T (x) = T x = T ∗ U x, T ∗ (x) = T ∗ x, with U Σ1 U ⊤ = Σ1 . E.0.1.2. Projection of linear fields.. We work in the Hilbert space L2 (µ; Rd ) with inner product ⟨f, g⟩µ := E[f (X)⊤ g(X)],

X ∼ N (0, Σ).

For matrices M, N ∈ Rd×d , by a slight abuse of notation, we also write (26)

⟨M, N ⟩µ := ⟨M x, N x⟩µ = E[X ⊤ M ⊤ N X] = Tr(M ΣN ⊤ ).

The next lemma is the finite-dimensional form of the weighted Helmholtz decomposition for Gaussian measures. It shows that, when the input vector field is linear, both its gradient and divergence-free components are again linear. This is the key reason that the Gaussianlinear class is preserved by one-step c-rectified flow. L EMMA 7 (Projection of a linear field under a Gaussian measure).

Let µ = N (0, Σ) on 2

d

L (µ;R ) Rd , where Σ ≻ 0, and p is the density of µ. Denote Gµ := {∇φ : φ ∈ Cc∞ (Rd )} , and

 Z 2 d Sµ := u ∈ L (µ; R ) : ∇ · (pu) = 0 in the weak sense, i.e. Rd

⊤

u(x)



∇φ(x) p(x)dx = 0 for every φ ∈ Cc∞ (Rd )

Then, (a) Gµ = Sµ⊥ in L2 (µ; Rd ), and for every linear map x 7→ M x, M x ∈ Sµ is equivalent to M = ΣK for some skew-symmetric K , M x ∈ Gµ is equivalent to M is symmetric; (b) For every matrix M ∈ Rd×d , the orthogonal projections projSµ (M x), projGµ (M x) are both linear functions;

.

34

(c) Suppose K is the unique skew-symmetric matrix satisfying the continuous Lyapunov equation ΣK + KΣ = M − M ⊤ ,

then projGµ (M x) = (M − ΣK)x, projSµ (M x) = ΣKx. P ROOF OF L EMMA 7. We argue in three parts. (a): Characterization of linear fields in Sµ . First, Gµ = Sµ⊥ comes from the definition, and for those x 7→ M x in Gµ , M x = ∇φ for some potential φ. Hence M = ∇(M x) = ∇2 φ is symmetric. On the other hand, for symmetric M , M x = ∇( 21 x⊤ M x) ∈ Gµ . We then characterize those linear fields x 7→ M x that belong to Sµ . Define K = Σ−1 M . The condition M x ∈ Sµ means ∇ · (p(x)M x) ≡ 0. Using the product rule and the identity ∇p(x) = −p(x)Σ−1 x, we compute   ∇ · (p(x)M x) = p(x)Tr(M ) + ∇p(x) · M x = p(x) Tr(M ) − x⊤ Σ−1 M x . Since p(x) > 0, this implies x⊤ Σ−1 M x = Tr(M ) for all x ∈ Rd . The quadratic form can be a constant function only if K = Σ−1 M satisfies K = −K ⊤ . Conversely, if K is skew-symmetric, then Tr(M ) = Tr(ΣK) = 0 by the symmetry of Σ, and x⊤ Σ−1 M x = x⊤ Kx = 0 for all x, satisfying the equation. So indeed M x ∈ Sµ . (b): Reduction to linear fields via adapted Hermite polynomials. Let {Hek (z)}k∈Nd be the standard multivariate Hermite polynomials, which form an orthogonal basis for L2 (γ; Rd ) where γ = N (0, Id ). Under the affine transformation z = Σ−1/2 x, the functions Φk (x) := Hek (Σ−1/2 x) form an orthogonal basis for the scalar space L2 (µ; Rd ). We can orthogonally L 2 d decompose L (µ; R ) = n≥0 Hn (µ), where the n-th chaos Hn (µ) is the span of {Φk (x) : |k| = n}. By the property of the standard Hermite polynomial, ∇z Hek (z) ∈ H|k|−1 (µ)⊕d . By the chain rule, ∇x Φk (x) = Σ−1/2 ∇z Hek (z). Therefore, ∇x Φk (x) ∈ H|k|−1 (µ)⊕d . This implies that for all φ ∈ Hn (µ),∇φ ∈ Hn−1 (µ)⊕d . Consequently, if φ ∈ Hn (µ) and ψ ∈ Hm (µ) with n ̸= m, ∇φ ∈ Hn−1 (µ)⊕d and ∇ψ ∈ Hm−1 (µ)⊕d respectively. By the orthonogonal decomposition of L2 (µ; Rd ), ⟨∇φ, ∇ψ⟩µ = 0. Thus, the gradient subspaces ∇Hn (µ) are mutually orthogonal in L2 (µ; Rd ). Now, consider the linear vector field f (x) = M x. Its coordinate functions are linear combinations of the degree-1 adapted Hermite polynomials, meaning M x ∈ H1 (µ)⊕d . Because ∇Hn (µ) ⊂ Hn−1 (µ)⊕d , for all n − 1 ̸= 1, M x ⊥ ∇Hn (µ). Therefore, projGµ (M x) ∈ ∇H2 (µ). Because H2 (µ) consists of scalar quadratic polynomials, ∇H2 (µ) only have linear vector fields. Therefore there exist matrices MG and MS such that projGµ (M x) = MG x, projSµ (M x) = MS x. Since projGµ (M x) ∈ Gµ , MG must be symmetric. (c): Identification of the two projections. Since M x = projGµ (M x) + projSµ (M x) = MG x + MS x, we have MG = M − MS = M − ΣK . Because MG is symmetric, M − ΣK = (M − ΣK)⊤ = M ⊤ − K ⊤ Σ⊤ . Using Σ⊤ = Σ and K ⊤ = −K , we obtain M − ΣK = M ⊤ + KΣ, hence ΣK + KΣ = M − M ⊤ .

It remains to prove uniqueness. Since Σ ≻ 0, the linear map K 7→ ΣK + KΣ is invertible on the space of skew-symmetric matrices. Therefore the above Lyapunov equation has a unique skew-symmetric solution K . This uniquely determines MS = ΣK, MG = M − ΣK . Thus projSµ (M x) = ΣKx, projGµ (M x) = (M − ΣK)x, as claimed.

COMP & STAT GUARANTEES OF C-RECT FLOW

35

We finally recall a standard variational lower bound for projections in Hilbert spaces, which will be the key tool for proving the lower bound in our cases. L EMMA 8. Let H be a Hilbert space and S ⊆ H a closed subspace. For any v ∈ H and nonzero w ∈ S , ∥ projS v∥H ≥

|⟨v, w⟩H | . ∥w∥H

P ROOF OF L EMMA 8. Let vS = projS v . Since v − vS ⊥ S , we have ⟨v, w⟩H = ⟨vS , w⟩H . The result follows immediately from the Cauchy-Schwarz inequality: |⟨vS , w⟩H | ≤ ∥vS ∥H ∥w∥H .

E.0.2. Explicit c-Rectified Flow Framework in the Gaussian Case. We apply the preceding projection formula to the velocity field generated by a linear coupling. This gives an explicit matrix-valued description of one-step c-rectified flow. In particular, the projected velocity remains linear at every time, so the resulting flow map is again linear. Since the joint Gaussian velocity field is always linear as suggested by Proposition 1, independent of the initial coupling (as long as the joint distribution is jointly Gaussian), onestep c-rectified flow will always produce a linear transport map. Consider the initial linear transport coupling of the Gaussian marginals X1 = T X0 , X0 ∼ P , T# P = Q. The straight interpolation associated with this coupling is Xt = (1 − t)X0 + tX1 = ((1 − t)I + tT )X0 := Tt X0 .

The marginal distribution of the straight interpolation is given by Xt ∼ Pt = (Tt )# P = N (0, Σt ), Σt = Tt Σ1 Tt⊤ , for all t ∈ [0, 1]. According to Lemma 6, T = T ∗ U , so ∥T ∥op ≤ ∥T ∗ ∥op ∥U ∥op < +∞. Hence for every t ∈ [0, ∥T − I∥−1 op ), the matrix Tt = (1 − t)I + tT is invertible. In what follows we work on the time interval [0, ∥T − I∥−1 op ∧ 1). On this interval, the velocity field along the interpolation is the linear field vt (y) = (T − I)Tt−1 y . The one-step quadratic c-rectified flow is obtained by projecting this velocity onto the gradient subspace Gt = St⊥ ⊂ L2 (Pt ; Rd ), where St denotes the pt -divergence-free subspace. By Lemma 7, projections of linear fields under Gaussian measures remain linear. Hence there exist matrices Gt and St such that vt (z) = gt (z) + st (z),

gt (z) := projGt vt (z) = Gt z,

st (z) := projSt vt (z) = St z,

and define the c-rectified flow equation by Z0 = X0 , and Żt = gt (Zt ) = Gt Zt , t ∈ [0, 1]. Consequently, the flow itself is linear: if a matrix flow Tt solves Ṫt = Gt Tt , T0 = I , then Zt = Tt X0 . In particular, one step of c-rectified flow again produces a linear Gaussian coupling c-Rectify((X0 , X1 )) = (Z0 , Z1 ) = (X0 , T1 X0 ). Thus, in the Gaussian-linear setting, one step of c-rectified flow can be implemented entirely at the matrix level. The construction is summarized below. This explicit framework also clarifies a useful limitation of one-step c-rectification. Although the projection removes the divergence-free part of the instantaneous velocity, it does not generally recover the full optimal map in a single step. The following corollary makes this obstruction precise.

36

Algorithm 4 One-step Gaussian c-rectified flow 1: Input: T such that T Σ1 T ⊤ = Σ2 . 2: for t ∈ [0, 1] do 3: Tt = (1 − t)I + tT , compute Σt = Tt Σ1 Tt⊤ , and Vt = (T − I)Tt−1 . 4: Vt = Gt + St in L2 (N (0, Σt ); Rd ) according to Lemma 7. 5: Solve Ṫt = Gt Tt , with T0 = I. 6: end forreturn T1

P ROOF OF C OROLLARY 1. We claim that projG0 (T x) = T ∗ x already forces T = T ∗ . Because of the orthogonal decomposition L2 (P ; Rd ) = G0 ⊕ S0 , T x = T ∗ x + projS0 (T x), and therefore ∥T x∥2P = ∥T ∗ x∥2P + ∥ projS0 (T x)∥2P . ∗ P = T P = Q, On the other hand, if X ∼ P , then since T# #

∥T ∗ x∥2P = EP ∥T ∗ X∥2 = EQ ∥Y ∥2 ,

∥T x∥2P = EP ∥T X∥2 = EQ ∥Y ∥2 .

∗ P = T P , these two quantities are equal. Hence ∥ proj (T x)∥2 = 0, so Since T# # S0 P projS0 (T x) = 0 in L2 (P ; Rd ). Thus P –a.s. T x = T ∗ x. Since P has full support and both fields are linear, it follows that T = T ∗ . In particular, if T ̸= T ∗ , then projG0 (T x) ̸= T ∗ x. So one-step c-rectified flow cannot already produce the optimal transport map.

E.0.3. Quantitative Variational Lower Bound for One-step c-Rectified Flow. The goal of this subsection is to show that one step of c-rectified flow removes a definite amount of the non-gradient component of the initial velocity. The argument is variational: instead of computing the full projection projSt Vt , we test it against a carefully transported divergencefree field Ht . This gives a lower bound on the projection norm that is uniform over a nontrivial time interval. Let St denote the pt -divergence-free subspace of L2 (Pt ; Rd ), and let Gt := St⊥ . By Lemma 7, suppose K is the unique skew-symmetric matrix satisfying (27)

Σ1 K + KΣ1 = (T − I) − (T − I)⊤ = T − T ⊤ ,

the orthogonal projection of T − id onto S0 is then given by u(x) = projS0 (T − id)(x) = Σ1 Kx.

Since every vector field in this Gaussian-linear setting is a time-dependent linear field, we identify a time-dependent mapping of the form y 7→ At y with its matrix At . Define Vt := (T − I)Tt−1 ,

Ht := Tt Σ1 KTt−1 ,

ht (y) = JTt (Tt−1 y) u(Tt−1 y) = Ht y.

Since ⊤  −1 −⊤ −1 −⊤ −1 ⊤ −1 Σ−1 H = (T Σ T ) T Σ KT = T KT = − T KT , t t 1 t 1 t t t t t t t in other words, Σ−1 t Ht is skew-symmetric, so according to Lemma 7, we have ht ∈ St . Applying the variational lower bound in Lemma 8, ∥ projSt Vt ∥2Pt ≥

⟨Vt , Ht ⟩2Pt . ∥Ht ∥2Pt

37

COMP & STAT GUARANTEES OF C-RECT FLOW

For the numerator,     ⟨Vt , Ht ⟩Pt = EX∼N (0,Σ1 ) (vt (Tt X))⊤ (ht (Tt X)) = EX∼N (0,Σ1 ) ((T − I)X)⊤ (Tt Σ1 KX)  
= EX∼N (0,Σ1 ) X ⊤ (T − I)⊤ Tt Σ1 KX = Tr (T − I)⊤ Tt Σ1 KΣ1 = ⟨Tt⊤ (T − I), Σ1 K⟩P . Since Tt⊤ (T − I) − (T − I) = t(T − I)⊤ (T − I), the matrix Tt⊤ (T − I) − (T − I) is symmetric. On the other hand, (Σ1 KΣ1 )⊤ = −Σ1 KΣ1 , so Σ1 KΣ1 is skew-symmetric. Hence, by (26),
⟨Tt⊤ (T − I) − T − I, Σ1 K⟩P = −Tr (Tt⊤ (T − I) − (T − I)) · Σ1 KΣ1 = 0. Therefore ⟨Vt , Ht ⟩Pt = ⟨Tt⊤ (T − I), Σ1 K⟩P = ⟨T − I, Σ1 K⟩P .

Since Σ1 Kx = projS0 ((T − I)x), we conclude that ⟨Vt , Ht ⟩Pt = ∥Σ1 K∥2P . Similarly, for the denominator, ∥Ht ∥2Pt = E∥Tt Σ1 KX∥2 ≤ ∥Tt ∥2op E∥Σ1 KX∥2 ≤ 4∥Σ1 K∥2P .

Hence for every t ∈ [0, ∥T − 1∥−1 op ∧ 1), 1 ∥ projSt Vt ∥2Pt ≥ ∥Σ1 K∥2P . 4 Integrating over t and using the c-rectified flow variational identity (23) as well as Jensen’s inequality yields Z 1 Z 1 2 2 2 E∥X1 − X0 ∥ − E∥Z1 − Z0 ∥ ≥ E∥Ẋs − gs (Xs )∥ ds ≥ E∥E[Ẋs |Xs ] − gs (Xs )∥2 ds 0

0

Z ∥T −I∥−1 op ∧1 ≥

E∥vs (Xs ) − gs (Xs )∥2 ds =

0

(28)

≥

Z ∥T −I∥−1 op ∧1 0

∥T − 1∥−1 op ∧ 1 4

∥Σ1 K∥2P ≥

∥ projSt Vt ∥2Pt ds

1 ∥Σ1 K∥2P . 4(1 + ∥T ∗ ∥op )

E.0.4. Spectral Criterion for the Projection Bound.. By Lemma 6, T − T ∗ = T ∗ (U − I). Thus the excess over the optimal map is entirely encoded by the “rotational” part U − I . We formulate the projection hypothesis explicitly as follows. The preceding estimate reduces the contraction problem to a purely algebraic question: whether the initial divergencefree component Σ1 Kx controls the deviation T − T ∗ . The next proposition records this projection bound as the finite-dimensional condition needed for contraction. P ROPOSITION 6 (Explicit Gaussian projection bound). all admissible T in Theorem 2, for K defined by (27),

There exists c > 0 such that for

∥ projS0 (T − I)∥2P = ∥Σ1 K∥2P ≥ c0 ∥T − T ∗ ∥2P .

It remains to give a checkable condition under which this projection bound holds. The natural condition is spectral: after whitening by Σ1 , the rotational factor becomes an ordinary orthogonal matrix, and the relevant obstruction is the presence of eigenvalues close to −1. The following proposition shows that excluding this obstruction quantitatively gives the desired bound.

38

E.0.4.1. Verification under a spectral gap.. To derive this bound from the spectrum of U , introduce the whitened variables e := Σ−1/2 U Σ1/2 ∈ O(d). U 1 1

1/2 1/2 1/2 1/2 Te∗ := Σ1 T ∗ Σ1 = (Σ1 Σ2 Σ1 )1/2 ,

−1/2

−1/2

e is orthogonal and Spec(U e ) = Spec(U ). Since T ∗ = Σ Te∗ Σ1 and U = Then U 1 −1/2 −1/2 e∗ e 1/2 e −1/2 ∗ ∗ T (U − I)Σ , which yields: , we have T − T = T (U − I) = Σ Σ UΣ 1

1

1

1

1/2

1/2

Σ1 (T − T ∗ )Σ1

e − I). = Te∗ (U

e P ROPOSITION 7 (Spectral criterion for the Gaussian projection bound). Assume that U ±iθ ±iθ has no −1 eigenvalue, and write its nontrivial eigenvalues as e 1 , . . . , e k , θj ∈ (0, π). If dist(Spec(U ), −1) ≥ γ > 0, then e − I))∥2F ≥ ∥Skew(Te∗ (U

(29)

λmin (T ∗ )2 γ 2 e∗ e ∥T (U − I)∥2F . λmax (T ∗ )2 4

Moreover, this implies the projection bound ∥Σ1 K∥2P ≥ c0 ∥T − T ∗ ∥2P 2

∗ 2

2

min (T ) λmin (Σ1 ) with c0 = γ4 λλmax (T ∗ )2 λmax (Σ1 )2 , which verifies the bound in Proposition 6.

P ROOF OF P ROPOSITION 7. We split the proof into three steps. Step 1: Reduction to a block-diagonal orthogonal form. Choose V ∈ O(d) such that
e V ⊤ = diag Rθ , . . . , Rθ , Im+ , VU 1 k e ). where Rθ is the standard 2 × 2 rotation matrix. There is no −1 block because −1 ∈ / Spec(U ∗ ∗ ⊤ ∗ e e e Let TV := V T V . Then TV is symmetric positive definite, and dropping all off-block contributions only decreases the Frobenius norm, so e −U e ⊤ Te∗ ∥2F ≥ ∥Te∗ U

k X

∥(TeV∗ )j Rθj − Rθ⊤j (TeV∗ )j ∥2F ,

j=1

where (TeV∗ )j is the 2 × 2 principal block corresponding to the j -th rotation block. Step 2: Lower bound from the eigenangles. Writing (TeV∗ )j explicitly and taking the trace yields ∥(TeV∗ )j Rθj − Rθ⊤j (TeV∗ )j ∥2F ≥ 8λmin (T ∗ )2 sin2 θj .

e − I)) = 1 (Te∗ U e −U e ⊤ Te∗ ), we obtain Summing over j and using Skew(Te∗ (U 2 (30)

e − I))∥2F ≥ 2λmin (T ∗ )2 ∥Skew(Te∗ (U

k X

sin2 θj .

j=1

e − I∥2 = e − I)∥2 ≤ λmax (T ∗ )2 ∥U e − I∥2 and ∥U Since ∥Te∗ (U F F F

Pk

j=1 4(1 − cos θj ), we use

sin2 θj = 2(1 − cos θj ) cos2 θ2j to conclude ∗ 2

e − I))∥2F ≥ λmin (T ) ∥Skew(Te∗ (U λmax (T ∗ )2

 min cos j

2 θj

2



e − I)∥2F . ∥Te∗ (U

39

COMP & STAT GUARANTEES OF C-RECT FLOW

Finally, since dist(Spec(U ), −1) ≥ γ , for all 1 ≤ j ≤ k , we have γ 2 ≤ |eiθj + 1|2 = 2 + 2 cos θj = 4 cos2 θ2j . This proves (29). Step 3: Connecting the whitened skew bound to the L2 (P ; Rd ) projection. We define the e := Σ1/2 KΣ1/2 . Because K is skew-symmetric and Σ1/2 is symmetric, whitened matrix K 1 1 1 e is also skew-symmetric. Furthermore, by the definition of K in (27), K (31) e + KΣ e 1 = Σ1/2 (Σ1 K + KΣ1 )Σ1/2 = Σ1/2 (T − T ∗ )Σ1/2 − Σ1/2 (T − T ∗ )⊤ Σ1/2 Σ1 K 1 1 1 1 1 1 e − I) − (Te∗ (U e − I))⊤ = 2Skew(Te∗ (U e − I)). = Te∗ (U Taking the Frobenius norm of both sides and applying the triangle inequality yields: 2 e∗ e e −I))∥F = ∥Σ1 K e + KΣ e 1 ∥F ≤ 2λmax (Σ1 )∥K∥ e F =⇒ ∥K∥ e 2F ≥ ∥Skew(T (U − I))∥F . 2∥Skew(Te∗ (U λmax (Σ1 )2 −1/2 e

Now we compute the actual projection norm in L2 (P ; Rd ). Substituting K = Σ1 we have:

−1/2

KΣ1

,

1/2 e e 1/2 eK e ⊤ Σ1 ). ∥Σ1 K∥2P = Tr(Σ1 KΣ1 (Σ1 K)⊤ ) = −Tr(Σ1 KΣ1 KΣ1 ) = −Tr(Σ1 K KΣ1 ) = Tr(K

eK e ⊤ is positive semidefinite, Tr(K eK e ⊤ Σ1 ) ≥ λmin (Σ1 )Tr(K eK e ⊤ ) = λmin (Σ1 )∥K∥ e 2. Because K F Combining this with our Frobenius bound gives: ∥Σ1 K∥2P ≥

λmin (Σ1 ) e − I))∥2F . ∥Skew(Te∗ (U λmax (Σ1 )2

Finally, by (29), observing that 1/2

1/2

e − I)∥2F = ∥Σ (T − T ∗ )Σ ∥2F = Tr(Σ1 (T − T ∗ )Σ1 (T − T ∗ )⊤ ) ∥Te∗ (U 1 1 ≥ λmin (Σ1 )Tr((T − T ∗ )Σ1 (T − T ∗ )⊤ ) = λmin (Σ1 )∥T − T ∗ ∥2P ,

we conclude: ∥Σ1 K∥2P ≥

γ 2 λmin (Σ1 )λmin (T ∗ )2 e∗ e γ 2 λmin (Σ1 )2 λmin (T ∗ )2 2 ∥ T ( U − I)∥ ≥ ∥T − T ∗ ∥2P . F 4 λmax (Σ1 )2 λmax (T ∗ )2 4 λmax (Σ1 )2 λmax (T ∗ )2

This strictly bounds the true projection in L2 (P ; Rd ) and verifies Proposition 6. We now return from the whitened matrix estimate to the original transport problem. Since T ∗ is symmetric, the linear function T ∗ x is a gradient field. Hence, the vector field u(x) = Σ1 Kx defined via projS0 (T − I) is identically projS0 (T − T ∗ ). Therefore, once Proposition 6 is established, we immediately obtain ∥Σ1 K∥2P ≥ c0 ∥T − T ∗ ∥2P for some constant c0 > 0 that only depends on γ and second moments of P , Q. Substituting this directly into (28) yields c0 E∥X1 − X0 ∥2 − E∥Z1 − Z0 ∥2 ≥ ∥T − T ∗ ∥2P := c̃ ∥T − T ∗ ∥2P . 4(1 + λmax (T ∗ )) E.0.5. Cost-difference Lemma and Contraction.. The final ingredient is to compare the matrix distance ∥T − T ∗ ∥2P with the excess quadratic transport cost. For Gaussian linear transports, this comparison is exact up to multiplication by (T ∗ )−1 , and it allows us to convert the projection lower bound into the desired contraction estimate.

40

L EMMA 9. have

For P = N (0, Σ1 ), Q = N (0, Σ2 ), and a transport map T from P to Q, we

  E∥T (X) − X∥2 − W22 (P, Q) = Tr (T ∗ )−1 (T − T ∗ )Σ1 (T − T ∗ )⊤ ≤

1 ∥T − T ∗ ∥2P . λmin (T ∗ )

P ROOF OF L EMMA 9. Since both T and T ∗ push P forward to Q, we have T Σ1 T ⊤ =

T ∗ Σ1 (T ∗ )⊤ . Because T ∗ is symmetric, this becomes

(T − T ∗ )Σ1 (T − T ∗ )⊤ + (T − T ∗ )Σ1 T ∗ + T ∗ Σ1 (T − T ∗ )⊤ = 0.

(32)

On the other hand, since T (X) and T ∗ (X) have the same law, E∥T (X)∥2 = E∥T ∗ (X)∥2 . Therefore, E∥T (X) − X∥2 − W22 (P, Q) = E∥T (X) − X∥2 − E∥T ∗ (X) − X∥2 = −2E⟨(T − T ∗ )X, X⟩ = −2Tr((T − T ∗ )Σ1 ).

Now multiply (32) on the left by (T ∗ )−1 and take traces. This gives
0 = Tr (T ∗ )−1 (T − T ∗ )Σ1 (T − T ∗ )⊤ + Tr((T − T ∗ )Σ1 ) + Tr(Σ1 (T − T ∗ )⊤ ).
Since Tr(Σ1 (T − T ∗ )⊤ ) = Tr((T − T ∗ )Σ1 ), we obtain Tr (T ∗ )−1 (T − T ∗ )Σ1 (T − T ∗ )⊤ = −2Tr((T − T ∗ )Σ1 ). Combining this with the previous identity yields the exact formula   E∥T (X) − X∥2 − W22 (P, Q) = Tr (T ∗ )−1 (T − T ∗ )Σ1 (T − T ∗ )⊤ . Finally, since T ∗ ⪰ λmin (T ∗ )I , we have (T ∗ )−1 ⪯ λmin (T ∗ )−1 I , and therefore     1 1 ∗ ∗ ⊤ = Tr (T −T )Σ (T −T ) ∥T −T ∗ ∥2P . Tr (T ∗ )−1 (T −T ∗ )Σ1 (T −T ∗ )⊤ ≤ 1 ∗ λmin (T ) λmin (T ∗ ) This proves the lemma. Combining the two inequalities gives the contraction estimate P ROOF OF T HEOREM 2. From (28) and Proposition 6, we already proved that E∥X1 − X0 ∥2 − E∥Z1 − Z0 ∥2 ≥ c̃∥T − T ∗ ∥2P .   By Lemma 9, ∥T − T ∗ ∥2P ≥ λmin (T ∗ ) E∥X1 − X0 ∥2 − W22 (P, Q) . Substituting this lower bound into the previous inequality yields   E∥X1 − X0 ∥2 − E∥Z1 − Z0 ∥2 ≥ c̃ · λmin (T ∗ ) E∥X1 − X0 ∥2 − W22 (P, Q) . Rearranging gives the contraction   E∥Z1 − Z0 ∥2 − W22 (P, Q) ≤ (1 − c̃ · λmin (T ∗ )) E∥X1 − X0 ∥2 − W22 (P, Q) . Finally, c̃ · λmin (T ∗ ) =

λmin (T ∗ )3 λmin (Σ1 )2 · γ 2 := γ 2 c, 16λmax (T ∗ )2 λmax (Σ1 )2 (1 + λmax (T ∗ ))

where c = C(Spec(Σ1 ), Spec(Σ2 )) is a constant that only depends on the spectrum of Σ1 and Σ2 , i.e. the second moments of P and Q.

41

COMP & STAT GUARANTEES OF C-RECT FLOW

P ROOF OF T HEOREM 3. Define the excess cost (k) 2

(k)

Ek := E Z1 − Z0

− W22 (P, Q).

Since W22 (P, Q) is the optimal quadratic transport cost, we have Ek ≥ 0 for all k . Whichever coupling we are starting from, as long as it is rectifiable, By Proposition 1, the velocity field of the straight coupling is always a linear field, as we have been argued in Section E.0.2. Therefore, after running one-step c-rectified flow, we will get a linear transport (1) (1) (1) (1) coupling, i.e. there exists a linear transport map T such that (Z0 , Z1 ) = (Z0 , T Z0 ). (k) (k) Similarly, for all k ≥ 1, there exists a Tk such that Z1 = Tk Z0 and Tk = T ∗ Uk where Uk is a Σ1 -orthogonal matrix by Lemma 6. We will show that there exists a γ > 0 and K ∈ N such that for all k ≥ K , dist(Spec(Uk ), −1) ≥ γ . Suppose on the contrary that there exists a subsequence kn such that dist(Spec(Ukn ), −1) < (k) (k) (k ) (k ) n−1 . According to the proof of Theorem 1, {(Z0 , Z1 )}k∈N is tight, and so {(Z0 n , Z1 n )}n∈N is tight, there is a further subsequence of kn , still denoted by the index k , such that (k)

(k)

(Z0 , Z1 ) ⇒ (Z0∗ , Z1∗ ). (k)

(k)

(k)

(k)

By the continuity property, Z1 − T ∗ Z0 ⇒ Z1∗ − T ∗ Z0∗ = 0. Since Z1 = T ∗ Uk Z0 , this further shows (k)

T ∗ (Uk − I)Z0 ⇒ 0. (k)

Since T ∗ is invertible, and Z0 ∼ P is a nondegenerate Gaussian distribution on the full space for every k , it follows that Uk − I → 0, i.e. Uk → I . Therefore, dist(Spec(Uk ), −1) → 2, contradiction! By Theorem 2, for every k ≥ 2, once there is a uniform spectral gap on the rotational part of T , there is a one-step contraction for some uniform c > 0 that Ek+1 ≤ (1 − c)Ek . Iterating this bound yields Ek ≤ (1 − c)k−1 E1 ≤ (1 − c)k−1 E0 ≤ e−c(k−1) E0 ,

finishing the proof. APPENDIX F: PROOF OF SECTION 3.3 P ROOF OF P
ROPOSITION 3. For any x, y ∈ Rd , Tt (x) − Tt (y) = (1 − t)(x − y) + t T (x) − T (y) . By the triangle inequality and the Lipschitz bound on T , for all x, y ∈ Rd ,

1 − (1 + L)t ∥x − y∥ ≤ ∥Tt (x) − Tt (y)∥ ≤ (1 − t) + tL ∥x − y∥. When t < (1 + L)−1 , the lower bound is strictly positive for x ̸= y , so Tt is injective. The same lower bound implies the Lipschitz estimate for the inverse on the image Tt (Rd ). F.1. Projection Estimates Along the Interpolation. The proof of Theorem 4 is based on testing the solenoidal part of vt against a transported initial divergence-free field. The next lemma shows that this test field remains divergence-free under the interpolation and that its pairing with vt is independent of t. To utilize the variational bound, we construct a specific test function in St . L EMMA 10 (Transported divergence-free fields). on Rd by

Let u ∈ S0 . Define the vector field ht

ht (x) = JTt (Tt−1 (x)) u(Tt−1 (x)).

Then ht ∈ St .

42

P ROOF OF L EMMA 10. Let g ∈ Cc∞ (Rd ) be an arbitrary smooth test function. Using the change of variables y = Tt (x) (noting that pt is the pushforward of p by Tt ), we compute: Z Z Z ⊤ ⊤ ∇g(y) ht (y)pt (y)dy = ∇g(Tt (x)) JTt (x)u(x)p(x)dx = ∇(g ◦ Tt )(x)⊤ u(x)p(x)dx. Since u ∈ S0 , it is orthogonal to gradients of scalar functions in L2 (P ; Rd ), so the integral vanishes. Thus, ∇ · (pt ht ) = 0 in the weak sense. The following lemma identifies the S0 -projection of the field appearing in the pairing with vt .

L EMMA 11 (Projection identity along the interpolation). It holds that   projS0 JTt⊤ (T − id) = projS0 (T − id) = projS0 (T ). P ROOF OF L EMMA 11. Recall that L2 (P ; Rd ) admits the orthogonal decomposition

L2 (P ; Rd ) = S0 ⊕ G, where G is the space of gradient fields. Since Tt = (1 − t)id + tT ,

its Jacobian is JTt = I + t(JT − I). We observe that JTt (x)⊤ (T (x) − x) = (T (x) − x) + t(JT (x) − I)⊤ (T (x) − x). Since (JT (x) − I)⊤ (T (x) − x) = 21 ∇∥T (x) − x∥2 , therefore,   t ⊤ 2 JTt (T − id) = (T − id) + ∇ ∥T − id∥ . 2 The second term is a gradient field and thus lies in S0⊥ . Consequently, projS0 (JTt⊤ (T − id)) = projS0 (T − id) = projS0 (T ) − projS0 (id).

Since id = ∇( 21 ∥x∥2 ) is a gradient, projS0 (id) = 0, completing the proof. L EMMA 12 (Transport Stability). satisfies:

Under Assumption 2, the difference in quadratic costs

E ∥T (X0 ) − X0 ∥2 − W22 (P, Q) ≤

1 ∥T − T ∗ ∥2P . λ

P ROOF OF L EMMA 12. We expand the squared norm ∥T (X0 ) − X0 ∥2 = ∥T (X0 )∥2 + ∥X0 ∥2 − 2⟨T (X0 ), X0 ⟩. Noting that ∥T (X0 )∥2 and ∥T ∗ (X0 )∥2 have the same expectation (the second moment of Q), the difference in costs becomes: E∥T (X0 ) − X0 ∥2 − E∥T ∗ (X0 ) − X0 ∥2 = 2E⟨T ∗ (X0 ) − T (X0 ), X0 ⟩. We substitute X0 = ∇φ∗0 (T ∗ (X0 )) using convex duality. Since E[φ∗0 (T (X0 ))] = E[φ∗0 (T ∗ (X0 ))], we can rewrite the term on the right-hand side as a Bregman divergence:   2E⟨T ∗ (X0 ) − T (X0 ), ∇φ∗0 (T ∗ (X0 ))⟩ = 2E Dφ∗0 (T (X0 ), T ∗ (X0 )) . By Assumption 2, φ0 is λ-strongly convex, which implies φ∗0 is (1/λ)-smooth. This smooth1 ness yields the bound Dφ∗0 (y, z) ≤ 2λ ∥y − z∥2 . Therefore, E∥T (X0 ) − X0 ∥2 − W22 (P, Q) ≤ which concludes the proof.

1 E ∥T (X0 ) − T ∗ (X0 )∥2 , λ

43

COMP & STAT GUARANTEES OF C-RECT FLOW

F.2. Proof of the Contraction Criterion. Now we prove Theorem 4 and its contraction corollary. P ROOF OF T HEOREM 4. Using the c-rectified flow variational identity (23) and Jensen’s inequality, the reduction in cost is bounded by the integrated projection of the velocity field: Z 1 Z 1 E∥T (X0 ) − X0 ∥2 − E∥Z1 − Z0 ∥2 ≥ inf E∥Ẋs − ∇fs (Xs )∥2 ds ≥ inf E∥E[Ẋs |Xs ] − ∇fs (Xs )∥2 ds f

f

0

Z 1 = inf f

0

∥vs − ∇fs ∥2Ps ds =

Z (2+2L)−1 ≥ 0

Z 1 0

0

∥vs − projGs vs ∥2Ps ds

∥vs − projSs⊥ vs ∥2Ps ds.

Let wt = projSt vt . By Lemma 8, for any test function ht ∈ St , ∥wt ∥2Pt ≥

⟨vt , ht ⟩2Pt . ∥ht ∥2Pt

We choose ht as in Lemma 10, setting u = projS0 (T ). Using the change of variables y = Tt (x) and Lemma 11, we compute the numerator: Z Z ⊤ ⟨vt , ht ⟩Pt = (vt ◦ Tt ) (ht ◦ Tt ) p(x)dx = (T (x) − x)⊤ JTt (x)u(x) p(x)dx = ⟨JTt⊤ (T − id), u⟩P = ⟨projS0 (JTt⊤ (T − id)), u⟩P = ⟨projS0 (T ), u⟩P = ∥u∥2P .

For the denominator, Assumption 1 implies ∥JT ∥op ≤ L. The Jacobian JTt = (1 − t)I + tJT therefore satisfies ∥JTt (x)∥op ≤ 2 for all t ≤ (2L + 2)−1 . Consequently: Z ∥ht ∥2Pt = ∥JTt (x)u(x)∥2 p(x)dx ≤ 4∥u∥2P . Combining these estimates gives: ∥wt ∥2Pt ≥

(∥u∥2P )2 1 = ∥u∥2P . 4 4∥u∥2P

Recalling that u = projS0 (T ) = projS0 (T − T ∗ ) (since T ∗ = ∇φ ⊥ S0 ), and invoking Assumption 3: ∥wt ∥2Pt ≥

h ∥T − T ∗ ∥2P . 4

Integrating over t ∈ [0, (2 + 2L)−1 ] yields 2

2

Z (2+2L)−1

E∥T (X0 ) − X0 ∥ − E∥Z1 − Z0 ∥ ≥ 0

∥wt ∥2Pt dt ≥

h ∥T − T ∗ ∥2P . 8(L + 1)

P ROOF OF C OROLLARY 2. Theorem 4 provides the lower bound for the cost reduction: E ∥T (X0 ) − X0 ∥2 − E ∥Z1 − Z0 ∥2 ≥

h ∥T − T ∗ ∥2P . 8(L + 1)

44

By Lemma 12, we have ∥T − T ∗ ∥2P ≥ λ E∥T (X0 ) − X0 ∥2 − W22 (P, Q) . Substituting this into the inequality yields:  λh  E ∥T (X0 ) − X0 ∥2 − E ∥Z1 − Z0 ∥2 ≥ E ∥T (X0 ) − X0 ∥2 − W22 (P, Q) . 8(L + 1) Rearranging the terms completes the proof. ∗ P = Q, we have P ROOF OF P ROPOSITION 4. Since Sε is P -measure preserving and T# ∗ ∗ (Tε )# P = (T ∗ ◦ Sε )# P = T# ((Sε )# P ) = T# P = Q. ∞ d We first show R that the infinitesimal R perturbation u lies in S0 . Let g ∈ Cc (R ). Since Sε preserves P , g(Sε (x)) p(x)dx = g(x) p(x)dx for every sufficiently small ε. Differentiating at ε = 0, using (Sε − id)/ε → u in L2 (P ; Rd ), gives Z ∇g(x)⊤ u(x) p(x)dx = 0.

Thus u ∈ S0 . By Taylor’s formula, Z 1
Sε (x) − x Tε (x) − T ∗ (x) = ∇2 φ x + s(Sε (x) − x) ds · . ε ε 0 Since (Sε − id)/ε → u in L2 (P ; Rd ), we also have Sε − id → 0 in P -probability. By continuity and boundedness of ∇2 φ0 , the integral operator above converges strongly in L2 (P ; Rd ) to multiplication by ∇2 φ0 (x). Hence Tε − T ∗ → ∇2 φ0 · u ε

in L2 (P ; Rd ).

Because projS0 is a bounded linear operator on L2 (P ; Rd ), we also have projS0 (Tε − T ∗ )/ε −→ projS0 (∇2 φ0 · u) in L2 (P ; Rd ). Therefore, ∥ projS0 (Tε − T ∗ )∥P ∥ projS0 (∇2 φ0 · u)∥P −→ . ∥Tε − T ∗ ∥P ∥∇2 φ0 · u∥P

It remains to lower bound the limiting ratio. Since u ∈ S0 , the variational characterization of orthogonal projection in Lemma 8 gives ∥ projS0 (∇2 φ0 · u)∥P ≥

⟨∇2 φ0 · u, u⟩P . ∥u∥P

Using λId ⪯ ∇2 φ0 (x) ⪯ ΛId , we have Z 2 ⟨∇ φ0 · u, u⟩P = u(x)⊤ ∇2 φ0 (x)u(x) p(x)dx ≥ λ∥u∥2P , and ∥∇2 φ0 · u∥P ≤ Λ∥u∥P . This implies ∥ projS0 (∇2 φ0 · u)∥P λ ≥ . 2 ∥∇ φ0 · u∥P Λ

Consequently, if |ε| is sufficiently small, say there exists ε0 > 0 such that for all 0 < |ε| < ε0 , ∥ projS0 (Tε − T ∗ )∥P λ ≥ . ∥Tε − T ∗ ∥P 2Λ

This gives the stated local bound with h = λ2 /(4Λ2 ).

45

COMP & STAT GUARANTEES OF C-RECT FLOW (k)

(k) 2

P ROOF OF T HEOREM 5. Define the excess cost at the k -th step by Ek := E Z1 − Z0

−

W22 (P, Q). Since W22 (P, Q) is the optimal quadratic transport cost between P and Q, we have Ek ≥ 0 for every k ≥ 0. Since c-rectified flow reduces the cost, E1 ≤ E0 .

After the first round of c-rectified flow, it induces a transport map T1 , and in each following runs, the c-rectified flow always induces a new transport map. Therefore, we can use our one-step contraction results after the first step. By the uniform assumptions, Corollary 2 (k) (k) applies  to each coupling (Z0 , Z1 ), with T replaced by Tk . Therefore, for every k ≥ 1,  λh Ek+1 ≤ 1 − 8(L+1) Ek . Iterating this inequality gives



λh Ek ≤ 1 − 8(L + 1)

k−1



λh E1 ≤ 1 − 8(L + 1)

k−1



 λh E0 ≤ exp − (k − 1) E0 . 8(L + 1)

Substituting the definition of E0 yields the stated exponential decay estimate. APPENDIX G: PROOF OF SECTION 5.2 P ROOF OF L EMMA 3. Recall that for P -a.s. x, and for all y ∈ Rd , c(y − x) − ψ(y) − φ(x) ≥ 0, with equality at y = T ∗ (x). Thus, defining D(x, y) := c(y − x) − ψ(y) − φ(x), we have that T ∗ (x) is a global minimizer of D(x, ·), and hence ∇y D(x, T ∗ (x)) = 0 for P -a.e. x. Now, because T# P = Q and (T ∗ )# P = Q, E[ψ(T (X))] = E[ψ(T ∗ (X))]. Therefore, h i E[c(T (X) − X) − c(T ∗ (X) − X)] = E c(T (X) − X) − ψ(T (X)) − c(T ∗ (X) − X) + ψ(T ∗ (X)) = E[D(X, T (X)) − D(X, T ∗ (X))].

We next bound the last expression. For each fixed x, the Hessian of D with respect to y is ∇2y D(x, y) = ∇2 c(y − x) − ∇2 ψ(y) ⪯ Ly Id . Hence D is Ly -smooth in y . Therefore, D(x, T (x)) − D(x, T ∗ (x)) ≤

Ly ∥T (x) − T ∗ (x)∥2 . 2

Taking expectation with respect to P , we get Ly ∥T − T ∗ ∥2P . 2 To relate the transport distance to the gradient difference, we invoke the strong convexity of c. Since c is µc -strongly convex, its gradient ∇c is strictly monotone:

(33)

E[c(T (X) − X)] − E[c(T ∗ (X) − X)] ≤

⟨∇c(u) − ∇c(v), u − v⟩ ≥ µc ∥u − v∥2 ,

∀u, v ∈ Rd .

Applying the Cauchy-Schwarz inequality, we have ⟨∇c(u) − ∇c(v), u − v⟩ ≤ ∥∇c(u) − ∇c(v)∥∥u − v∥. Combining these inequalities yields µc ∥u − v∥ ≤ ∥∇c(u) − ∇c(v)∥. Letting u = T (x) − x and v = T ∗ (x) − x, (34)

∥T − T ∗ ∥2P ≤

1 ∥∇c(T − id) − ∇c(T ∗ − id)∥2P . µ2c

Substituting (34) into (33) completes the proof. P ROOF OF T HEOREM 10. Let τL = (2(L + 1))−1 . By the same invertibility estimate as Proposition 3, Tt is injective for 0 ≤ t ≤ τL , and vt is well-defined on the support of Pt . Following the c-rectified flow variational identity (23), since mc (x, y) = c(x) + c∗ (y) − ⟨x, y⟩ is convex in x, combining with Jensen’s inequality, we have Z 1 Z 1 E[c(T (X0 )−X0 )]− E[c(Z1 −Z0 )] ≥ E[mc (Ẋs , ∇fs (Xs ))]ds ≥ E[mc (vs (Xs ), ∇fs (Xs ))]ds, 0

0

46

where ft denotes the dual velocity driving the flow. Consider a fixed 0 ≤ t ≤ τL , and an arbitrary vector field ht ∈ St . Since L2 (Pt ; Rd ) = Gt ⊕ St , we have E[⟨ht (Xt ), ∇ft (Xt )⟩] = 0. Consequently, since mc (vt − ht , ∇ft ) ≥ 0, Z Z mc (vt , ∇ft )dPt ≥ (mc (vt , ∇ft ) − mc (vt − ht , ∇ft )) dPt Z Z = (c(vt ) − c(vt − ht ) − ⟨ht , ∇ft ⟩) dPt = (c(vt ) − c(vt − ht )) dPt . Since the cost function c is Lc -smooth, c(vt ) − c(vt − ht ) ≥ ⟨∇c(vt ), ht ⟩ −

Lc ∥ht ∥2 . 2

Therefore, Z mc (vt , ∇ft )dPt ≥ ⟨∇c(vt ), ht ⟩Pt −

Lc ∥ht ∥2Pt . 2

Then, we choose a specific test function ht via the pushforward of a field u from the source domain P . Let u ∈ S0 be a P -divergence-free field and define ht ◦ Tt = (JTt )u. Using the change of variables y = Tt (x) and noting that vt (Tt (x)) = T (x) − x, Z D E ⟨∇c(vt ), ht ⟩Pt = ⟨∇c(T (x) − x), JTt (x)u(x)⟩ dP (x) = JTt⊤ ∇c(T − id), u ; P Z ∥ht ∥2Pt = ∥JTt (x)u(x)∥2 dP (x). First, since JTt = I + t(JT − I) = I + tJ(T − id), by the chain rule, JTt⊤ ∇c(T − id) = ∇c(T − id) + tJ(T − id)⊤ ∇c(T − id) = ∇c(T − id) + t∇(c(T − id)).

Since u ∈ S0 , we have u ⊥ ∇(c(T − id)). As a result, ⟨∇c(vt ), ht ⟩Pt = ⟨∇c(T − id), u⟩P . Second, since T is L-Lipschitz and t ≤ τL , ∥JTt (x)∥op ≤ (1 − t) + tL ≤ 2. Therefore, ∥ht ∥2Pt ≤ 4∥u∥2P . As a consequence, we have a cleaner lower bound Z mc (vt , ∇ft )dPt ≥ ⟨∇c(T − id), u⟩P − 2Lc ∥u∥2P . Now we select u proportional to the projection of the cost gradient onto the P -divergencefree subspace with ε = (4Lc )−1 , such that u = ε projS0 (∇c(T − id)). For this test function u, we have Z 1 ∥ projS0 (∇c(T − id))∥2P . mc (vt , ∇ft )dPt ≥ 8Lc Finally, invoking Assumption 5, and integrating over t ∈ [0, τL ], Z τL E[c(T (X0 ) − X0 )] − E[c(Z1 − Z0 )] ≥ E[mc (vs (Xs ), ∇fs (Xs ))]ds ≥ 0

which concludes the proof.

1 ∥ projS0 (∇c(T − id))∥2P 16Lc (L + 1)

≥

h ∥∇c(T − id) − ∇c(T ∗ − id)∥2P 16Lc (L + 1)

≥

hµ2c (E[c(T (X0 ) − X0 )] − Wc (P, Q)) , 8Lc Ly (L + 1)

COMP & STAT GUARANTEES OF C-RECT FLOW (k)

47

(k)

P ROOF OF T HEOREM 11. Define Ek := E[c(Z1 − Z0 )] − Wc (P, Q). By optimality of Wc (P, Q), we have Ek ≥ 0. Applying Theorem 10 to the coupling induced by Tk for all k ≥ 1 gives   hµ2c Ek+1 ≤ 1 − Ek . 8Lc Ly (L + 1) Iterating this inequality proves the geometric estimate bound. APPENDIX H: PROOF OF SECTION 4.1 H.1. Smoothing identities and score reduction. For bounded measurable g : Rd → Rk , define the multivariate smoothing operator   (d) (gφd ) ∗ φt (x) x t (35) At g(x) = = E[g(Mx,t )], Mx,t ∼ N , Id . γt (x) 1+t 1+t Conditional Jensen’s inequality gives Z Z ∥At g(x)∥2 γt (x)dx ≤ (36) Rd

∥g(x)∥2 φd (x)dx. Rd

Moreover, 1 At (∇r), ∥∇Rt ∥∞ ≲ (1 + t)−1 . 1+t The next lemma reduces multivariate score estimation to estimation of the smoothed ratio and its gradient. Rt = At r,

(37)

∇Rt =

L EMMA 13 (Multivariate score reduction). Rt and ∇Rt , respectively, and define ŝt (x) = −

Let R̂t,0 and R̂t,1 be arbitrary estimators of

R̂t,1 (x) x . + 1 + t Π[c/2,2C] (R̂t,0 )(x)

Then Z

∥ŝt − st ∥2 pt ≲

Z

Rd

∥R̂t,1 − ∇Rt ∥2 γt + Rd

1 (1 + t)2

Z

|R̂t,0 − Rt |2 γt . Rd

P ROOF. Put R̄t,0 = Π[c/2,2C] (R̂t,0 ). Since Rt ∈ [c, C], clipping is nonexpansive and |R̄t,0 − Rt | ≤ |R̂t,0 − Rt |. Adding and subtracting ∇Rt /R̄t,0 gives R̂t,1 ∇Rt − Rt R̄t,0

2

≲ ∥R̂t,1 − ∇Rt ∥2 + ∥∇Rt ∥2 |R̂t,0 − Rt |2 .

Now use pt = Rt γt , c ≤ Rt ≤ C , and ∥∇Rt ∥∞ ≲ (1 + t)−1 from (37). H.2. Upper bound for Theorem 6. We begin low-noise P with the multivariate Q ν Q estimator. ν For a multi-index ν = (ν1 , . . . , νd ), write |ν| = j νj , uν = j uj j , and Dν = j ∂j j . P ROPOSITION 8 (Multivariate weighted ratio derivative estimation). There exists b0 > 0, depending only on (c, C, L, α, d), for which one can construct estimators r̂b,0 and r̂b,1 such that, for every 0 < b ≤ b0 , Z 1 sup Ef |r̂b,0 (x) − r(x)|2 φd (x)dx ≲ b2α + d , nb d f ∈Fα,d R

48

and Z sup Ef

f ∈Fα,d

∥r̂b,1 (x) − ∇r(x)∥2 φd (x)dx ≲ b2(α−1) +

Rd

1 . nbd+2

P ROOF. Let p = mα , and let Ip = {ν ∈ Nd0 : |ν| ≤ p}. Choose a nonnegative C ∞ kernel K , supported on the unit ball and bounded from below by a positive constant on the ball of radius 1/2. Put Eb = {x : ∥x∥ ≤ b−1/3 },

ℓb (x) = b(1 + ∥x∥)2 .

If x ∈ Eb and ∥u − x∥ ≤ ℓb (x), then 1 | log φd (u) − log φd (x)| ≤ ∥x∥∥u − x∥ + ∥u − x∥2 ≲ 1, 2 provided b0 is sufficiently small. Hence φd (u) ≍ φd (x) uniformly on all local neighborhoods used below. For ν, µ ∈ Ip , define   Z u−x (u − x)ν+µ φd (u)du. Gνµ (x) = K ℓb (x)

After the change of variables u = x + ℓb (x)v , the rescaled moment matrix is uniformly positive definite on the finite-dimensional polynomial space of degree at most p. Consequently, −d−|ν|−|µ| |(G−1 φd (x)−1 , x )νµ | ≲ ℓb (x)

(38)

ν, µ ∈ Ip ,

uniformly over x ∈ Eb . For x ∈ Eb , let â(x) = (âν (x) : ν ∈ Ip ) minimize 2      Z n  2X u−x X Xi − x X ν φ (u)du − aν (u − x) K K aν (Xi − x)ν .  d ℓb (x)  n ℓb (x) i=1

ν∈Ip

ν∈Ip

Set r̂b,0 (x) = â0 (x),

r̂b,1 (x) = (âe1 (x), . . . , âed (x))⊤ ,

and set r̂b,0 = 1, r̂b,1 = 0 on Ebc . Write â(x) = G−1 x ĝ(x), where   n 1X Xi − x ĝν (x) = K (Xi − x)ν , n ℓb (x)

x ∈ Eb ,

gν (x) = Ef ĝν (x),

i=1

α and put a⋆ (x) = G−1 x g(x). The multivariate Taylor remainder for C functions, together with

(38), gives, for |ρ| ≤ 1, (39)

a⋆ρ (x) −

Dρ r(x) ≲ ℓb (x)α−|ρ| . ρ!

Since f ≤ Cφd , | Cov(ĝν (x), ĝµ (x))| ≲

1 ℓb (x)d+|ν|+|µ| φd (x). n

A second application of (38) yields (40)

Var(âρ (x)) ≲

1 nℓb (x)d+2|ρ| φd (x)

,

|ρ| ≤ 1.

49

COMP & STAT GUARANTEES OF C-RECT FLOW

Combining (39) and (40), and integrating over Eb , gives Z Z 2α 2α ℓb (x) φd (x)dx ≲ b , ℓb (x)2(α−1) φd (x)dx ≲ b2(α−1) , Eb

Eb

while Z

Z

dx 1 ≲ d, d nb Eb nℓb (x)

dx 1 ≲ d+2 . d+2 nb Eb nℓb (x)

R Here we used Rd (1 + ∥x∥)−2d dx < ∞. Finally, r and ∇r are uniformly bounded, and Gaussian tails give Z −2/3 φd (x)dx ≲ e−c0 b ≲ bm Ebc

for every fixed m > 0. This proves both assertions. For 0 < t ≤ 1, define lo R̂t,b,0 = At r̂b,0 ,

lo R̂t,b,1 =

1 At r̂b,1 , 1+t

and let ŝlo t,b be the score estimator obtained from Lemma 13. By (36) and Proposition 8, with b = hn , Z − 2(α−1) 2 2α+d , 0 < t ≤ 1. (41) sup Ef ∥ŝlo t,hn − st ∥ pt ≲ n f ∈Fα,d

Rd

We next construct the intermediate-noise estimator. L EMMA 14 (Multivariate Gaussian second moments). Let 0 < t ≤ 1, σ = φd . Then ( )2 (d) φt (x − Y ) 2 2 γt (x)E ≲ σ −d e−c0 σ ∥x∥ , γt (x)

√ t, and Y ∼

and ( γt (x)E ∇x

(d)

φt (x − Y ) γt (x)

) 2 2

2

≲ σ −d (σ −2 + ∥x∥2 )e−c0 σ ∥x∥ ,

where c0 > 0 is universal. P ROOF. Completing the square coordinatewise gives Z 2 2 (d) φt (x − y)2 φd (y)dy ≲ σ −d γt (x)e−c0 σ ∥x∥ . Moreover, ( ∇x

(d)

φt (x − y) γt (x)

)

  (d) 1 x φt (x − y) = y− . t 1+t γt (x)

A second coordinatewise Gaussian calculation gives the stated derivative bound. The following local polynomial is fitted on an inward set so that the Gaussian reference density is never smaller than at the point of estimation.

50

L EMMA 15 (Inward multivariate local-polynomial ratio estimation). Let Y1 , . . . , Yn be i.i.d. with density Rγt , where 0 < t ≤ 1, c ≤ R ≤ C , and ∥R∥C α (Rd ) ≤ L. There exist estimalp lp tors R̂t,0 (x) and R̂t,1 (x), defined for ∥x∥ ≥ 1, such that 2α

lp E|R̂t,0 (x) − R(x)|2 ≲ {nγt (x)}− 2α+d ∧ 1,

and 2(α−1)

lp E∥R̂t,1 (x) − ∇R(x)∥2 ≲ {nγt (x)}− 2α+d ∧ 1.

P ROOF. Let p = mα , and fix the open ball U = B(e1 /2, 1/8). Since restriction to U defines a positive-definite inner product on the finite-dimensional space of polynomials of degree at most p, there exist bounded functions L0 , L1 , . . . , Ld , supported on U , such that, for every polynomial P of degree at most p, Z Z L0 (u)P (u)du = P (0), Lj (u)P (u)du = ∂j P (0), 1 ≤ j ≤ d. U

U ⊤ Write L∇ = (L1 , . . . , Ld ) . Fix a Borel measurable choice of an orthogonal matrix Qx sat-

isfying Qx e1 = x/∥x∥, x ̸= 0. lp lp If nγt (x) < 1, set R̂t,0 (x) = 1 and R̂t,1 (x) = 0. Otherwise put bx = {nγt (x)}−1/(2α+d) ≤ 1,

Ui =

Q⊤ x (x − Yi ) , bx

and define n

lp R̂t,0 (x) =

1 X L0 (Ui )1{Ui ∈U } , γt (Yi ) nbdx i=1

lp R̂t,1 (x) = −

n Qx X L∇ (Ui )1{Ui ∈U } . γt (Yi ) nbd+1 x i=1

For u ∈ U , ∥x∥ ≥ 1, and 0 < bx ≤ 1, ∥x − bx Qx u∥2 = ∥x∥2 − 2bx ∥x∥u1 + b2x ∥u∥2 ≤ ∥x∥2 .

Hence γt (x − bx Qx u) ≥ γt (x). The reproduction identities and the multivariate Taylor remainder give lp |ER̂t,0 (x) − R(x)| ≲ bαx ,

lp ∥ER̂t,1 (x) − ∇R(x)∥ ≲ bα−1 . x

Using R ≤ C , the inward inequality above, and the change of variables y = x − bx Qx u, 1 1 lp lp lp Var(R̂t,0 (x)) ≲ , E∥R̂t,1 (x) − ER̂t,1 (x)∥2 ≲ . d nγt (x)bx nγt (x)bd+2 x The choice of bx balances squared bias and variance. When nγt (x) < 1, the result follows from the uniform bounds on R and ∇R. Consequently, for every measurable E ⊂ {x : ∥x∥ ≥ 1}, with D = 2α + d, Z Z d+2 2(α−1) lp (42) E ∥R̂t,1 − ∇R∥2 γt ≲ n− D γt D , E

E

and Z (43)

E E

2α lp |R̂t,0 − R|2 γt ≲ n− D

Z E

We finally record the exact global Gaussian calculation.

d

γtD .

51

COMP & STAT GUARANTEES OF C-RECT FLOW

L EMMA 16 (Multivariate global plug-in bound). Define P (d) n−1 ni=1 φt (x − Xi ) G G G R̂t,0 (x) = , R̂t,1 = ∇R̂t,0 , γt (x) and let ŝG t be the corresponding clipped ratio score estimator. Then, uniformly over t > 0, Z (1 + t)d−1 2 ∥ŝG − s ∥ p ≲ sup Ef . t t t ntd+1 f ∈Fα,d Rd In particular, the right-hand side is of order 1/(ntd+1 ) for 0 < t ≤ 1 and of order 1/(nt2 ) for t > 1. (d)

P ROOF. Let Kt (x, y) = φt γt(x−y) (x) . By tensorization of the corresponding one-dimensional identities,   ZZ 1+t d 2 Kt (x, y) γt (x)φd (y)dxdy = . t Also,   1 x ∇x Kt (x, y) = y− Kt (x, y), t 1+t and a direct Gaussian calculation yields ZZ (1 + t)d−1 (44) ∥∇x Kt (x, y)∥2 γt (x)φd (y)dxdy = d . td+1 Since f ≤ Cφd , these identities imply   Z 1 1+t d G 2 Ef |R̂t,0 − Rt | γt ≲ , n t

Z Ef

G ∥R̂t,1 − ∇Rt ∥2 γt ≲

(1 + t)d−1 . ntd+1

By (37), the denominator-estimation contribution in Lemma 13 is bounded by   1 + t d (1 + t)d−1 1 ≲ . (1 + t)2 n t ntd+1 The result follows. P ROOF OF THE UPPER BOUND IN T HEOREM 6. The low-noise estimator (41) supplies the first branchqof (10). It remains to obtain the second branch on h2n ≤ t ≤ 1. Put σ = √ t, Λ = 1 ∨ log+ (ntα+d/2 ). Then N ≥ 1. Fix a sufficiently small constant η > 0. If σΛ ≥ η , the global plug-in estimator of Lemma 16 gives Λd , nσ nσ d+2 so it attains, up to a constant, the smaller of the intermediate and global plug-in branches. It remains to consider σΛ < η . Choose a sufficiently large constant M , and then take η ≤ (2M )−1 . Generate independent Zi ∼ N (0, Id ) and put Yi = Xi + σZi , so that Yi ∼ G and R̂G . pt = Rt γt . On the ball {x : ∥x∥ ≤ M Λ}, use the Gaussian plug-in estimators R̂t,0 t,1 Outside this ball, apply Lemma 15 to Y1 , . . . , Yn . Since M Λ ≤ (2σ)−1 , Lemma 14 gives Z Z Λd Λd Λd G 2 G 2 Ef ∥R̂t,1 − ∇Rt ∥ γt ≲ , E | R̂ − R | γ ≲ ≤ . t t f t,0 nσ d+2 nσ d nσ d+2 ∥x∥≤M Λ ∥x∥≤M Λ 1

≤ η −d 2d+2

52

The representation Rt = At r , together with Dν Rt = (1 + t)−|ν| At (Dν r) for |ν| ≤ mα and the corresponding Hölder contraction, implies ∥Rt ∥C α (Rd ) ≲ 1 uniformly over 0 < t ≤ 1. Thus Lemma 15 applies in the complement. Let a1 = (d + 2)/D and a0 = d/D . Uniformly over 0 < t ≤ 1, Gaussian tails imply, after increasing M if necessary, ( Z N −aj , N ≥ e, γt (x)aj dx ≲ j ∈ {0, 1}. 1, 1 ≤ N < e, ∥x∥>M Λ Equations (42) and (43) show that the two tail risks are also bounded by Λd /(nσ d+2 ). Combining the central and tail estimators and applying Lemma 13 gives Z Λd 2 sup Ef ∥ŝim . t − st ∥ pt ≲ nσ d+2 f ∈Fα,d The auxiliary Gaussian randomization can be removed by taking the conditional expectation of the resulting score estimator given X1 , . . . , Xn , which does not increase squared risk. Taking the best of the low-noise, intermediate-noise, and global plug-in estimators gives (10) for 0 < t ≤ 1. For t > 1, Lemma 16 gives 1/(nt2 ). H.3. Lower bound for Theorem 6. P ROOF OF THE LOWER BOUND IN T HEOREM 6. We treat the three noise regimes separately. R H.3.0.1. Low noise. Let h = hn , and choose a nonzero ψ ∈ Cc∞ (B(0, 1)) satisfying ψ = (d) 0. For 0 ≤ u ≤ 1, put ψu = ψ ∗ φu . By Plancherel’s identity, Z 1 2 2 b 2 dξ > 0. ∥∇ψu ∥2 = ∥ξ∥2 e−u∥ξ∥ |ψ(ξ)| d (2π) Rd Continuity in u, compactness of [0, 1], and uniform Gaussian decay therefore give a fixed A > 1 such that Z Z ∥∇ψu (z)∥2 dz ≳ 1, sup |ψu (z)|2 dz ≲ 1. (45) inf 0≤u≤1 ∥z∥≤A

0≤u≤1 ∥z∥≤A

Choose m ≍ h−d points x1 , . . . , xm ∈ [−1/4, 1/4]d , separated by at least Kh, where K > 2A + 2 is fixed. For θ ∈ {−1, 1}m , define   m X x − xj fθ α fθ (x) = φd (x) + δh θj ψ , rθ = , h φd j=1

where δ > 0 is a sufficiently R small constant. Since the perturbations have disjoint supports in a fixed compact set and ψ = 0, the interior-point assumption implies fθ ∈ Fα,d for every θ . If θ(j) differs from θ only in coordinate j , then χ2 (fθ , fθ(j) ) ≲ δ 2 h2α+d .

Since nh2α+d = 1, Pinsker’s inequality gives ∥fθ⊗n − fθ⊗n (j) ∥TV ≤

after reducing δ .

1 2

53

COMP & STAT GUARANTEES OF C-RECT FLOW

For 0 < t ≤ h2 , put u = t/h2 and       · − xj x − xj (d) qj,t (x) = ψ ∗ φt . (x) = ψu h h Let Ij = {x : ∥(x − xj )/h∥ ≤ A}. These sets are pairwise disjoint. On their union, uniformly over t ≤ h2 , the smoothed densities are bounded above and below and their gradients are uniformly bounded. Writing p̄θ,j,t = (pθ,t + pθ(j) ,t )/2, a direct calculation gives sθ,t − sθ(j) ,t =

2δhα θj {∇qj,t p̄θ,j,t − qj,t ∇p̄θ,j,t } . pθ,t pθ(j) ,t

Equation (45) implies ∥∇qj,t ∥2L2 (Ij ) ≳ hd−2 ,

∥qj,t ∥2L2 (Ij ) ≲ hd .

Therefore, for all sufficiently large n, Z (46) ∥sθ,t − sθ(j) ,t ∥2 γt ≳ δ 2 h2α+d−2 . Ij

Assouad’s reduction, applied over the disjoint sets Ij , now yields Z 2(α−1) inf sup Ef ∥ŝt − st ∥2 pt ≳ mh2α+d−2 ≍ h2(α−1) = n− 2α+d . ŝt f ∈Fα,d

p √ H.3.0.2. Intermediate noise. Let h2 ≤ t ≤ 1, σ = t, and Λ = 1 ∨ log+ (nσ 2α+d ). Fix nonnegative, nonzero functions a, b ∈ Cc∞ (B(0, 1)) with disjoint supports. For x0 ∈ Rd satisfying σ∥x0 ∥ ≤ β0 , define R     ⊤ 2 2 a(u)e−σx0 u−σ ∥u∥ /2 du x − x0 x − x0 λx0 ,σ = R , qx0 ,σ (x) = a − λx0 ,σ b . ⊤ σ σ b(u)e−σx0 u−σ2 ∥u∥2 /2 du R Then qx0 ,σ φd = 0. The parameters λx0 ,σ range over a fixed compact subinterval of (0, ∞), and Z ν −|ν| (47) ∥D qx0 ,σ ∥∞ ≲ σ , qx0 ,σ (x)2 φd (x)dx ≍ σ d φd (x0 ). (d)

Put Qλ = a − λb. For every admissible λ and every v ∈ [1/2, 1], ∇(Qλ ∗ φv ) ̸≡ 0. Indeed, otherwise the convolution would be a constant vanishing at infinity, hence zero; taking Fourier transforms would imply Qλ = 0, a contradiction. By compactness, there exists a fixed A > 1 such that Z 2 (48) inf ∥∇(Qλ ∗ φ(d) v )(z)∥ dz ≳ 1. λ,v

∥z∥≤A

For x = (1 + t)(x0 + σz), a change of variables in (35) gives (d)

At qx0 ,σ (x) = (Qλx0 ,σ ∗ φ1/(1+t) )(z).

Let  Ix0 ,σ = x :

 x − x0 ≤ Aσ . 1+t

Because σ∥x0 ∥ ≤ β0 and ∥z∥ ≤ A, γt ((1 + t)(x0 + σz)) ≍ φd (x0 ) uniformly over all admissible x0 , σ, z . Therefore, the change of variables above, together with (36) and (48), implies (49) Z Z 2 d−2 ∥∇At qx0 ,σ (x)∥ γt (x)dx ≳ σ φd (x0 ), |At qx0 ,σ (x)|2 γt (x)dx ≲ σ d φd (x0 ). Ix0 ,σ

Rd

54

Set B = β0 min{Λ, σ −1 }. Choose a Kσ -separated packing x1 , . . . , xm of the ball of radius B , with K > 2A + 2. Then  d  d B B ≳ , m≍1+ σ σ and the corresponding supports and sets Ij = Ixj ,σ are pairwise disjoint. Since B ≤ β0 Λ, choosing β0 sufficiently small gives nσ 2α+d φd (xj ) ≳ 1, 1 ≤ j ≤ m. Indeed, if Λ = 1, then 1 ≤ nσ 2α+d ≤ e and the centers remain in a fixed ball. If Λ > 1, then ∥xj ∥2 ≤ 2 β02 log(nσ 2α+d ), so nσ 2α+d φd (xj ) ≳ (nσ 2α+d )1−β0 /2 . Define d

−1/2

δj = κ{nσ φd (xj )}

,

rθ = 1 +

m X

θj δj qxj ,σ ,

fθ = rθ φd .

j=1

Then δj ≲ κσ α . By (47), disjointness of the supports, and the standard scaling property of the Hölder norm, choosing κ sufficiently small gives fθ ∈ Fα,d ,

1 3 ≤ rθ ≤ . 2 2

2 d 2 For neighboring vertices, DKL (fθ⊗n ∥fθ⊗n (j) ) ≲ nδj σ φd (xj ) ≲ κ , so their total variation distance is at most 1/2 after reducing κ. Let uj,t = At qxj ,σ . For a neighboring pair, write   rθ + rθ(j) R̄θ,j,t = At . 2

Then Rθ,t = R̄θ,j,t + θj δj uj,t , Rθ(j) ,t = R̄θ,j,t − θj δj uj,t , while 12 ≤ R̄θ,j,t ≤ 23 , ∥∇R̄θ,j,t ∥∞ ≲ κ. For the derivative bound, disjointness gives ∥∇r̄θ,j ∥∞ ≲ maxk̸=j δk σ −1 ≲ κσ α−1 ≲ κ, and then (37) applies. Hence sθ,t − sθ(j) ,t =

2θj δj {∇uj,t R̄θ,j,t − uj,t ∇R̄θ,j,t } . Rθ,t Rθ(j) ,t

Equations (49) therefore give, after reducing κ, Z 1 (50) ∥sθ,t − sθ(j) ,t ∥2 γt ≳ δj2 σ d−2 φd (xj ) ≍ . nσ 2 Ij Assouad’s reduction and the disjointness of the Ij ’s imply Z m Bd . inf sup Ef ∥ŝt − st ∥2 pt ≳ ≳ ŝt f ∈Fα,d nσ 2 nσ d+2 Since B d ≍ Λd ∧ σ −d , we obtain Z inf sup Ef ∥ŝt − st ∥2 pt ≳ ŝt f ∈Fα,d

Λd 1 ∧ , d+2 2d+2 nσ nσ

h2 ≤ t ≤ 1.

Since the first line of (10) is bounded above by this quantity, this proves the desired lower bound on this range.

55

COMP & STAT GUARANTEES OF C-RECT FLOW

H.3.0.3. Large noise. Choose q ∈ Cc∞ (Rd ) such that Z Z qφd = 0, µq := ∇q(x)φd (x)dx ̸= 0. For example, one may take q(x) = x1 η(x), where η is a nonnegative smooth radial function of compact support. Let δ = κn−1/2 , rω = 1 + ωδq , and fω = rω φd , ω ∈ {−1, 1}. For sufficiently small κ, both alternatives belong to Fα,d . Moreover, Z ⊗n ⊗n 2 DKL (f+ ∥f− ) ≲ nδ q(x)2 φd (x)dx ≲ κ2 , so their product-sample total variation distance is bounded away from one. Put ut = At q . Then ∇ut =

1 At (∇q), 1+t

and conditional Jensen’s inequality gives Z ∥µq ∥2 ∥∇ut (x)∥2 γt (x)dx ≥ . (1 + t)2 2δ∇ut Since s+,t − s−,t = 1−δ 2 u2 , the two-point testing reduction yields t Z 1 1 ≍ 2, inf sup Ef ∥ŝt − st ∥2 pt ≳ 2 ŝt f ∈Fα,d n(1 + t) nt

t > 1.

This completes the proof. H.4. Projection and the resulting sampler rate. We now verify the matrix slope bounds underlying the projection in Algorithm 2. Recall that ᾱ = α ∧ 2. L EMMA 17.

There exists K0 < ∞, depending only on (c, C, L, α, d), such that −K0 tᾱ/2−1 Id ⪯ ∇st (x) ⪯ K0 tᾱ/2−1 Id ,

0 < t ≤ 1,

and 1 − Id ⪯ ∇st (x) ⪯ t



K0 1 − t(1 + t) t

 Id ,

t > 1.

P ROOF. For 0 < t ≤ 1, Gaussian smoothing and the second-difference characterization of C ᾱ give ∥∇Rt ∥∞ ≲ 1, ∥∇2 Rt ∥op,∞ ≲ tᾱ/2−1 . Since ∇st = −

1 ∇2 Rt ∇Rt ∇Rt⊤ Id + − , 1+t Rt Rt2

and c ≤ Rt ≤ C , the first assertion follows. For t > 1, the multivariate Tweedie identity gives √ 1 1 ∇st (x) = 2 Cov(X | X + tG = x) − Id . t t The conditional density is a uniformly bounded perturbation of N (x/(1 + t), t(1 + t)−1 Id ). Hence √ t 0 ⪯ Cov(X | X + tG = x) ⪯ K0 Id , 1+t which proves the second assertion.

56

Define λd (t) and λd (t) by  ᾱ/2−1 λd (t) = K0 t 1{t≤1} +

K0 1 − t(1 + t) t

 1{t>1} ,

λd (t) = K0 tᾱ/2−1 1{t≤1} +t−1 1{t>1} ,

and let n o Ct,d = b = ∇V ∈ L2 (γt ; Rd ) : −λd (t)Id ⪯ ∇2 V ⪯ λd (t)Id weakly . The set Ct,d is closed and convex in L2 (γt ; Rd ). Indeed, convergence in this weighted space implies local L2 convergence, so the curl-free constraint and the distributional matrix inequalities are preserved under limits. Every element of Ct,d has a globally Lipschitz representative. By Lemma 17, st ∈ Ct,d . Let ŝagg be the best, according to the deterministic bounds above, of the low-noise, t intermediate-noise, and global plug-in estimators. The explicit constructions, including the Borel choice of Qx , may be chosen jointly measurable in (t, x). Define L2 (γ ;Rd ) agg ŝt .

set = ProjCt,d t

Then Hilbert projection and pt ≍ γt give Z (51) sup Ef ∥set − st ∥2 pt ≲ rn,d (t), f ∈Fα,d

0 < t ≤ n.

Rd

Moreover, for every x, y ∈ Rd , ⟨set (x) − set (y), x − y⟩ ≤ λd (t)∥x − y∥2 .

This is the one-sided Lipschitz bound used in the synchronous-coupling proof below. L EMMA 18 (Integration of the multivariate score envelope). For rn,d defined in (10),   n−1/2 log log n, d = 1, p  Z n  rn,d (t) dt + n−1 ≲ n−1/2 (log n)3/2 , d = 2,  1 + t 0  α+1  − 2α+d , d ≥ 3. n α−1

α+1

P ROOF. Let t0 = h2n = n−2/(2α+d) . The contribution of 0 < t ≤ t0 is t0 n− 2α+d = n− 2α+d . On t0 ≤ t ≤ 1, the second and third branches of (10) exchange dominance at a point τn ≍ (log n)−1 , determined by tΛn,d (t)2 ≍ 1. Hence the remaining contribution on (0, 1] is bounded by Z τn Z 1 1 1 d/2 −(d+2)/4 √ Λn,d (t) t dt + √ t−(d+1)/2 dt. n t0 n τn For d = 1, the first integral is O(n−1/2 ), while the second is O(n−1/2 log log n). For d = 2, the substitution u = log(ntα+1 ) gives Z τn 1 {log(ntα+1 )}1/2 √ dt ≲ n−1/2 (log n)3/2 , t n t0 while the second integral is only O(n−1/2 (log n)1/2 ). If d > 2, put t = t0 ev . Since ntα+d/2 = e(2α+d)v/2 , the first integral is bounded by (2−d)/4 Z ∞ α+1 t0 √ (1 + v)d/4 e−(d−2)v/4 dv ≲ n− 2α+d . n 0

COMP & STAT GUARANTEES OF C-RECT FLOW

57

The second integral is O(n−1/2 (log n)(d−1)/2 ), which is of smaller order. Finally, the contribution of t > 1 is Z n 1 dt √ ≲ n−1/2 . t(1 + t) n 1

P ROOF OF T HEOREM 7. Let X be the true reverse process dXu = sn−u (Xu )du + dBu ,

X0 ∼ p n ,

constructed independently of Dn . By time reversal of the heat flow Haussmann and Pardoux (1986), Xn ∼ f . Conditional on Dn , let Y solve dYu = sen−u (Yu )du + dBu ,

Y0 = X0 ,

with the same Brownian motion. This gives a coupling of f and L(Yn | Dn ). Put ∆u = Yu − Xu . The one-sided Lipschitz inequality for sen−u gives, for almost every u, d ∥∆u ∥ ≤ λd (n − u)∥∆u ∥ + ∥sen−u (Xu ) − sn−u (Xu )∥. du Gronwall’s inequality and the change of variables t = n − u therefore yield Z t  Z n ∥∆n ∥ ≤ exp λd (q)dq ∥set (Xn−t ) − st (Xn−t )∥dt. 0

0

For 0 < t ≤ 1, the integral in the exponential is uniformly bounded. For t > 1,   Z t 2t λd (q)dq = K0 log − log t. 1+t 1 Consequently, Z t

 λd (q)dq ≲

exp 0

1 , 1+t

t > 0.

Since Xn−t ∼ pt , Minkowski’s inequality and (51) give  Z 1/2 Z n 
1/2
1 2 2 1/2 2 Ef W2 f, L(Yn | Dn ) ≤ Ef ∥∆n ∥ ≲ Ef ∥set − st ∥ pt dt 0 1+t Rd Z np rn,d (t) dt. ≲ 1+t 0 It remains to replace the initialization pn by γn . Couple Y0 ∼ pn and Yb0 ∼ γn optimally and drive the two projected reverse diffusions with the same Brownian motion. The same one-sided Lipschitz calculation gives
1 1 W2 L(Yn | Dn ), µ bn ≲ W2 (pn , γn ) ≤ W2 (f, φd ) ≲ n−1 . 1+n 1+n The last bound is uniform over Fα,d , since f ≤ Cφd . The triangle inequality and Lemma 18 complete the proof.

58

APPENDIX I: PROOF OF SECTION 4.2 P ROOF OF P ROPOSITION 5. Since P, Q ∈ CλΛ , the projection property and the triangle inequality give W2 (P, Pen ) ≤ W2 (P, Pbn ) + W2 (Pbn , Pen ) ≤ 2W2 (P, Pbn );

e n ) ≤ 2W2 (Q, Q b n ). W2 (Q, Q

e n ∈ C Λ , applying Caffarelli’s contraction theorem Caffarelli (2000) to Ten∗ and to Since Pen , Q λ its inverse gives Ten∗ = ∇φ en , whose Brenier potential φ en has two-sided Hessian bounds: it is mφ (λ, Λ)-strongly convex and Mφ (λ, Λ)-smooth. e n ), and perWe now apply Theorem 8 with reference map Ten∗ , reference marginals (Pen , Q turbed marginals (P, Q). Since the optimal coupling between P and Q is induced by T ∗ , the R theorem controls ∥T ∗ (x) − Ten∗ (x)∥2 P (dx), and gives e n ) ≲ ρ2n . E∥Ten∗ − T ∗ ∥2L2 (P ) ≲mφ ,Mφ EW22 (P, Pen ) + EW22 (Q, Q Substituting the projection bounds above yields the claimed ρ2n rate. b n are generated as in AlgoFinally, if the two marginal densities belong to Fα,d and Pbn , Q rithm 2, then Theorem 7 gives ρn = ϵn,d , yielding the stated plug-in rate. P ROOF OF T HEOREM R12. Define R the duality gap evaluated at the reference potentials e e e e e e . Since π e , we have E(P , Q) := Wc (P , Q) − φ dP − ψ dQ e is optimal for Wc (Pe, Q) Z Z e = {c(y − x) − φ(x) − ψ(y)} dπ E(Pe, Q) e(x, y) = D(x, y) dπ e(x, y). e . For a fixed x, the point T ∗ (x) minimizes y 7→ We first prove a lower bound on E(Pe, Q) ∗ D(x, y). Hence D(x, T (x)) = 0, ∇y D(x, T ∗ (x)) = 0. By the assumption ∇2yy D(x, y) ⪰ µy I , Taylor’s theorem gives D(x, y) ≥ µy

∥y − T ∗ (x)∥2 . 2

Therefore Z e = E(Pe, Q)

Z D(x, y) dπ e(x, y) ≥ µy

∥y − T ∗ (x)∥2 dπ e(x, y). 2

e . Let γP ∈ Π(P, Pe) be optimal for W2 (P, Pe), and let It remains to upper bound E(Pe, Q) e e . Also define π ∗ := (id, T ∗ )# P ∈ Π(P, Q). Since γQ ∈ Π(Q, Q) be optimal for W2 (Q, Q) ∗ γP and π have the same first marginal P , the gluing lemma gives a probability measure on triples (X, U, Y ) such that (X, U ) ∼ γP , (X, Y ) ∼ π ∗ . In particular, Y = T ∗ (X) almost surely. Since Y ∼ Q, and since the first marginal of γQ is also Q, another application of the gluing lemma gives a joint distribution of (X, U, Y, V ) such that (X, U ) ∼ γP , (X, Y ) ∼ π ∗ , e . Therefore Wc (Pe, Q) e ≤ Ec(V − U ). Using (Y, V ) ∼ γQ . Consequently, (U, V ) ∈ Π(Pe, Q) e ≤ Ec(V −U )− Eφ(U )− Eψ(V ) = ED(U, V ). the marginals of U and V , we obtain E(Pe, Q) Now D ≥ 0 everywhere, while D(X, Y ) = D(X, T ∗ (X)) = 0. Thus (X, Y ) is a global minimizer of D , and hence ∇x D(X, Y ) = 0, ∇y D(X, Y ) = 0 almost surely. Taylor’s theorem, together with the assumed Hessian bounds as well as ∥∇2xy D(x, y)∥op = ∥∇2 c(y − x)∥op ≤ Lc , gives ED(U, V ) ≤ Lx E

  ∥V − Y ∥2 ∥U − X∥2 + Ly E + Lc E ∥U − X∥∥V − Y ∥ . 2 2

COMP & STAT GUARANTEES OF C-RECT FLOW

59

Since (X, U ) ∼ γP and (Y, V ) ∼ γQ , and since γP , γQ are optimal for W2 , the Cauchy– Schwarz inequality gives Z ∥y − T ∗ (x)∥2 e + 2Lc W2 (P, Pe)W2 (Q, Q). e µy dπ e(x, y) ≤ Lx W22 (P, Pe) + Ly W22 (Q, Q) 2 This proves the claim. e n ) as the reference pair and P ROOF OF C OROLLARY 3. Apply Theorem 12 with (Pen , Q (P, Q) as the perturbed pair. The optimal coupling between P and Q is induced by T c , so the left-hand side in the theorem becomes the displayed L2 (P ) error. The two Wasserstein perturbation terms are both bounded by ρn , which gives the claim. REFERENCES A LBERGO , M. S., B OFFI , N. M. and VANDEN -E IJNDEN , E. (2023). Stochastic Interpolants: A Unifying Framework for Flows and Diffusions. arXiv preprint arXiv:2303.08797. BALAKRISHNAN , S. and M ANOLE , T. (2025). Stability bounds for smooth optimal transport maps and their statistical implications. arXiv preprint arXiv:2502.12326. BANSAL , V., ROY, S., S ARKAR , P. and R INALDO , A. (2025). On the Wasserstein Convergence and Straightness of Rectified Flow. arXiv preprint arXiv:2410.14949. B ENAMOU , J.-D. and B RENIER , Y. (2000). A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numerische Mathematik 84 375–393. B ERNTON , E., G HOSAL , P. and N UTZ , M. (2022). Entropic Optimal Transport: Geometry and Large Deviations. Duke Mathematical Journal 171 3363–3400. C AFFARELLI , L. A. (2000). Monotonicity properties of optimal transportation and the fkg and related inequalities. Communications in Mathematical Physics 214 547–563. DEL BARRIO , E. and L OUBES , J.-M. (2019). Central Limit Theorems for Empirical Transportation Cost in General Dimension. The Annals of Probability 47 926–951. D I M ARINO , S. and G EROLIN , A. (2020). An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm. Journal of Scientific Computing 85 27. D IVOL , V., N ILES -W EED , J. and P OOLADIAN , A.-A. (2025a). Optimal Transport Map Estimation in General Function Spaces. The Annals of Statistics 53 963–988. https://doi.org/10.1214/24-AOS2482 D IVOL , V., N ILES -W EED , J. and P OOLADIAN , A.-A. (2025b). Tight Stability Bounds for Entropic Brenier Maps. International Mathematics Research Notices 2025 rnaf078. https://doi.org/10.1093/imrn/rnaf078 D OU , Z., KOTEKAL , S., X U , Z. and Z HOU , H. H. (2024). From optimal score matching to optimal sampling. arXiv preprint arXiv:2409.07032. E SSER , P., K ULAL , S., B LATTMANN , A., E NTEZARI , R., M ÜLLER , J., S AINI , H., L EVI , Y., L ORENZ , D., S AUER , A., B OESEL , F., P ODELL , D., D OCKHORN , T., E NGLISH , Z. and ROMBACH , R. (2024). Scaling Rectified Flow Transformers for High-Resolution Image Synthesis. In Proceedings of the 41st International Conference on Machine Learning. Proceedings of Machine Learning Research 235 12606–12633. PMLR. F OURNIER , N. and G UILLIN , A. (2015). On the Rate of Convergence in Wasserstein Distance of the Empirical Measure. Probability Theory and Related Fields 162 707–738. F UKUMIZU , K., S UZUKI , T., I SOBE , N., O KO , K. and KOYAMA , M. (2025). Flow Matching Achieves Almost Minimax Optimal Convergence. In International Conference on Learning Representations. G ENEVAY, A., C HIZAT, L., BACH , F., C UTURI , M. and P EYRÉ , G. (2019). Sample Complexity of Sinkhorn Divergences. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics 1574–1583. G ENTILONI S ILVERI , M., C ONFORTI , G. and D URMUS , A. (2025). Exponential Convergence Guarantees for Iterative Markovian Fitting. arXiv preprint arXiv:2510.20871. H AUSSMANN , U. G. and PARDOUX , E. (1986). Time reversal of diffusions. The Annals of Probability 1188– 1205. H ERTRICH , J., C HAMBOLLE , A. and D ELON , J. (2025). On the relation between rectified flows and optimal transport. arXiv preprint arXiv:2505.19712. H ÜTTER , J.-C. and R IGOLLET, P. (2021). Minimax estimation of smooth optimal transport maps. The Annals of Statistics 49 1166 – 1194. H YVÄRINEN , A. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research 6 695–709.

60 K HOLKIN , S., K SENOFONTOV, G., L I , D., KORNILOV, N., G USHCHIN , N., S UVORIKOVA , A., K ROSHNIN , A., B URNAEV, E. and KOROTIN , A. (2024). Diffusion & Adversarial Schrödinger Bridges via Iterative Proportional Markovian Fitting. arXiv preprint arXiv:2410.02601. K NOTT, M. and S MITH , C. S. (1984). On the optimal mapping of distributions. Journal of Optimization Theory and Applications 43 39–49. K UNKEL , L. and T RABS , M. (2025). On the Minimax Optimality of Flow Matching through the Connection to Kernel Density Estimation. arXiv preprint arXiv:2504.13336. B LACK F OREST L ABS (2025). FLUX.1 Kontext: Flow Matching for In-Context Image Generation and Editing in Latent Space. arXiv preprint arXiv:2506.15742. L ÉONARD , C. (2014). A Survey of the Schrödinger Problem and Some of its Connections with Optimal Transport. Discrete and Continuous Dynamical Systems - Series A 34 1533–1574. L IPMAN , Y., C HEN , R. T. Q., B EN -H AMU , H., N ICKEL , M. and L E , M. (2023). Flow Matching for Generative Modeling. In International Conference on Learning Representations. L IU , Q. (2022). Rectified flow: A marginal preserving approach to optimal transport. arXiv preprint arXiv:2209.14577. L IU , X., G ONG , C. and L IU , Q. (2022). Flow straight and fast: Learning to generate and transfer data with rectified flow. arXiv preprint arXiv:2209.03003. L IU , X., Z HANG , X., M A , J., P ENG , J. and L IU , Q. (2024). InstaFlow: One Step Is Enough for High-Quality Diffusion-Based Text-to-Image Generation. In International Conference on Learning Representations. M AKKUVA , A. V., TAGHVAEI , A., O H , S. and L EE , J. D. (2020). Optimal Transport Mapping via Input Convex Neural Networks. In Proceedings of the 37th International Conference on Machine Learning 6672–6681. M ANOLE , T., BALAKRISHNAN , S., N ILES -W EED , J. and WASSERMAN , L. (2024). Plugin Estimation of Smooth Optimal Transport Maps. The Annals of Statistics 52 966–998. M ENA , G., K UCHIBHOTLA , A. K. and WASSERMAN , L. (2025). Statistical Properties of Rectified Flow. arXiv preprint arXiv:2511.03193. M ENA , G. and W EED , J. (2019). Statistical Bounds for Entropic Optimal Transport: Sample Complexity and the Central Limit Theorem. In Advances in Neural Information Processing Systems. N ILES -W EED , J. and B ERTHET, Q. (2022). Minimax Estimation of Smooth Densities in Wasserstein Distance. The Annals of Statistics 50. N ILES -W EED , J. and R IGOLLET, P. (2022). Estimation of wasserstein distances in the spiked transport model. Bernoulli 28 2663–2688. N UTZ , M. and W IESEL , J. (2022). Entropic Optimal Transport: Convergence of Potentials. Probability Theory and Related Fields 184 401–424. P ELUCHETTI , S. (2023). Diffusion Bridge Mixture Transports, Schrödinger Bridge Problems and Generative Modeling. Journal of Machine Learning Research 24 1–51. P OOLADIAN , A.-A., C UTURI , M. and N ILES -W EED , J. (2022). Debiaser Beware: Pitfalls of Centering Regularized Transport Maps. In Proceedings of the 39th International Conference on Machine Learning. Proceedings of Machine Learning Research 162 17830–17847. PMLR. P OOLADIAN , A.-A., D IVOL , V. and N ILES -W EED , J. (2023). Minimax Estimation of Discontinuous Optimal Transport Maps: The Semi-Discrete Case. In Proceedings of the 40th International Conference on Machine Learning. Proceedings of Machine Learning Research 202 28128–28150. PMLR. P OOLADIAN , A.-A. and N ILES -W EED , J. (2021). Entropic Estimation of Optimal Transport Maps. arXiv preprint arXiv:2109.12004. P OOLADIAN , A.-A., B EN -H AMU , H., D OMINGO -E NRICH , C., A MOS , B., L IPMAN , Y. and C HEN , R. T. Q. (2023). Multisample Flow Matching: Straightening Flows with Minibatch Couplings. arXiv preprint arXiv:2304.14772. R IGOLLET, P. and S TROMME , A. J. (2025). On the Sample Complexity of Entropic Optimal Transport. The Annals of Statistics 53. S AHOO , H. K., G AUR , M. and AGGARWAL , V. (2026). Order-Optimal Sample Complexity of Rectified Flows. arXiv preprint arXiv:2601.20250. S HI , Y., D E B ORTOLI , V., C AMPBELL , A. and D OUCET, A. (2023). Diffusion Schrödinger Bridge Matching. arXiv preprint arXiv:2303.16852. S OMMERFELD , M. and M UNK , A. (2018). Inference for Empirical Wasserstein Distances on Finite Spaces. Journal of the Royal Statistical Society: Series B 80 219–238. S ONG , Y., S OHL -D ICKSTEIN , J., K INGMA , D. P., K UMAR , A., E RMON , S. and P OOLE , B. (2021). ScoreBased Generative Modeling through Stochastic Differential Equations. International Conference on Learning Representations. T ONG , A., FATRAS , K., M ALKIN , N., H UGUET, G., Z HANG , Y., R ECTOR -B ROOKS , J., W OLF, G. and B EN GIO , Y. (2024). Improving and Generalizing Flow-Based Generative Models with Minibatch Optimal Transport. Transactions on Machine Learning Research.

COMP & STAT GUARANTEES OF C-RECT FLOW

61

V ILLANI , C. (2009). Optimal transport: old and new 338. Springer. V ILLANI , C. (2021). Topics in optimal transportation 58. American Mathematical Soc. V INCENT, P. (2011). A connection between score matching and denoising autoencoders. Neural Computation 23 1661–1674. W EED , J. and BACH , F. (2019). Sharp Asymptotic and Finite-Sample Rates of Convergence of Empirical Measures in Wasserstein Distance. Bernoulli 25.

Related documents

• Etude expérimentale et simulation numérique d’un procédé de friction-compression pour le recyclage de mélanges de thermoplastiques#1146639
• Reactive transport models without mathematical solution#641067
• Reactive transport models without mathematical solution#641066
• Recherche & Formation#23294
• Maximisation numérique et mesures acoustiques des précipitations#456706