Introduction
Generative models have become a central component of modern machine learning, with applications in image synthesis, scientific modeling, computational biology, and reinforcement learning. Diffusion and score-based generative models have achieved strong empirical performance by transforming a simple source distribution into a target data distribution through a learned reverse-time stochastic process [20 ] . Their success has motivated a substantial theoretical literature on score estimation, denoising objectives, numerical discretization, optimization error, and statistical guarantees for accurate generation. At the same time, diffusion-based sampling can require many numerical integration steps, and its training objective is tied to estimating score functions along a noisy probability path.
Flow matching provides an alternative framework for continuous-time generative modeling [17 ] . Rather than learning a score function, flow matching learns a time-dependent velocity field whose associated ordinary differential equation transports samples from a source distribution to a target distribution. The learned model is a deployable velocity field of the form
u θ ( x , t ) , u_\theta(x,t), u θ ( x , t ) ,
which depends only on the current state and time. This viewpoint leads to a regression-based training objective and can enable efficient deterministic sampling through ODE simulation. Several variants have been proposed, including rectified flow, conditional flow matching, optimal-transport flow matching, and stochastic interpolants [17 , 18 , 23 , 2 ] . These works demonstrate that both the interpolation path and the coupling between source and target samples can substantially affect the geometry, regularity, and computational efficiency of the resulting generative flow.
Despite this empirical and methodological progress, the theoretical understanding of how flow-matching velocity fields are learned from finite data remains incomplete. In the diffusion setting, recent works study sample complexity and convergence guarantees for score estimation and score-based generation [5 , 14 , 10 , 13 ] , as well as discrete diffusion models [22 ] . These results address questions such as how accurately a learned vector field must approximate its population target and how many samples or optimization steps are sufficient for the generated distribution to approach the desired target distribution. In the flow-matching setting, existing work has established stability and error-propagation guarantees for learned flows [3 ] , while recent analyses study statistical, approximation, and sample-complexity properties of flow matching and rectified flows [26 , 19 ] . These results provide important complementary perspectives on velocity estimation and terminal distributional error.
This paper focuses on a distinction between statistical and optimization error that arises in practical finite-dataset training. A flow-matching model is commonly trained using a fixed stored dataset and a finite number of stochastic-gradient updates. Consequently, the empirical flow-matching objective is generally only approximately minimized. This setting differs both from an idealized exact empirical-risk-minimization formulation and from a population-oracle or fresh-sample optimization model. Two distinct effects must therefore be controlled. The first is the statistical error incurred by replacing the population objective with a finite empirical objective. The second is the empirical optimization error incurred by performing only finitely many stochastic-gradient updates on that fixed objective.
We develop an empirical-risk-minimizer-free analysis for this finite-dataset setting. Given a training dataset of N N N flow-matching samples, we study the parameter θ T \theta_T θ T obtained after T T T stochastic-gradient updates on the empirical objective L ^ N \widehat{L}_N L N . Our analysis explicitly separates the discrepancy between the population loss L L L and the empirical loss L ^ N \widehat{L}_N L N from the error caused by only approximately minimizing L ^ N \widehat{L}_N L N . An empirical risk minimizer is introduced only as a theoretical comparator and is not assumed to be available to the training algorithm.
Our formulation is based on a coupling between a source distribution ( π 0 ) (\pi_0) ( π 0 ) and a target distribution ( π 1 ) (\pi_1) ( π 1 ) , together with a linear, or rectified, interpolation path. The regression target is the associated pathwise velocity, while the deployable target is its conditional mean given the current state and time. This marginal velocity field depends only on the current state and time and can therefore be used during generation. We explicitly assume that the marginal velocity field is path-consistent with the prescribed interpolation path, so that the corresponding reference ODE reproduces the path marginals and reaches ( π 1 ) (\pi_1) ( π 1 ) at terminal time. A uniform flow-stability argument then converts integrated velocity-field error along the reference path into Wasserstein-2 error for the generated terminal distribution.
A further distinction from compact-support formulations is that we allow sub-exponential source and target distributions. This is important because standard source distributions used in generative modeling, including Gaussian noise, are unbounded. We handle unbounded data through endpoint-magnitude truncation. On the event that both coupled endpoints have bounded norm, the linear interpolation state, pathwise velocity, and induced squared-loss class are uniformly controlled. The contribution of the complementary event is then bounded using the assumed endpoint-tail behavior. This construction avoids truncation arguments involving singular factors near the terminal time and is naturally compatible with linear and rectified interpolation paths.
The central question addressed in this work is:
How many training samples and stochastic-gradient updates are sufficient for a neural velocity field trained by flow matching to generate a distribution close to the target distribution?
Our proof proceeds in two stages. First, uniform flow stability converts excess population flow-matching risk into terminal Wasserstein-2 error. Second, the excess population risk is decomposed into approximation, finite-dataset statistical, and empirical optimization contributions. Under unbounded endpoint distributions, the statistical term further separates into a truncated uniform-convergence contribution and an endpoint-tail contribution. For a prescribed bounded-parameter smooth neural velocity class, the truncated statistical contribution is controlled through a metric-entropy and Rademacher uniform convergence argument for the induced scalar squared-loss class. The empirical optimization contribution is controlled through an expected finite time stochastic gradient guarantee under empirical smoothness, an empirical proximal Polyak Łojasiewicz condition, and a finite dataset stochastic gradient oracle.
The resulting theorem holds with high probability over the draw of the finite training dataset and in conditional expectation over the stochastic-gradient randomness. Under the stated approximation, endpoint-tail, flow-stability, neural-class-complexity, and empirical-optimization conditions, the bound yields expected Wasserstein-2 error of order O ( ϵ ) O(\epsilon) O ( ϵ ) with dataset size O ~ ( ϵ − 4 ) \widetilde{O}(\epsilon^{-4}) O ( ϵ − 4 ) and optimization budget O ~ ( ϵ − 2 ) \widetilde{O}(\epsilon^{-2}) O ( ϵ − 2 ) , up to the displayed problem-dependent and logarithmic factors. These rates should be interpreted for a prescribed bounded-parameter smooth neural velocity class. In particular, dimension and architecture dependence may enter through the neural-class complexity, approximation error, endpoint-tail parameters, flow-stability constant, and empirical optimization constants. We do not claim that these quantities are dimension free or uniformly controlled over arbitrary architectures.
We complement the theoretical analysis with synthetic experiments designed to illustrate the mechanisms represented in the bound. The experiments examine how velocity-estimation and terminal distributional errors vary with the dataset and optimization budgets, compare fixed finite-dataset training with a one-pass fresh-sample procedure, and study the effect of different couplings for a linear interpolation path. These experiments are not intended to verify the formal asymptotic rates or to compete with large-scale generative-model benchmarks. Rather, they provide controlled diagnostic evidence for the approximation–statistical–optimization structure underlying the analysis.
The main contributions of this work are summarized as follows:
Sub-exponential endpoints and explicit tail control. We replace compact-support assumptions with sub-exponential source and target distributions. Endpoint-magnitude truncation yields a bounded squared-loss class on a high-probability event, while the contribution of its complement is controlled through an explicit tail term. This permits standard unbounded source distributions such as Gaussian noise.
Metric-entropy control for a smooth neural squared-loss class. For a prescribed bounded-parameter smooth neural velocity class, we derive a uniform-convergence bound for the induced truncated scalar squared-loss class using parameter-space covering numbers and Rademacher complexity. This yields a squared-loss-level statistical contribution of order O ~ ( N − 1 / 2 ) \widetilde{O}(N^{-1/2}) O ( N − 1/2 ) , up to the displayed network-complexity, truncation-envelope, and logarithmic factors.
Finite-time empirical optimization guarantee. Under empirical smoothness, an empirical proximal-PL condition, bounded conditional gradient variance, and the stated uniform empirical regularity conditions, we control the expected empirical suboptimality after T T T finite-dataset stochastic-gradient updates. Combined with the statistical and flow-stability arguments, this produces a finite-sample and finite-time terminal distributional guarantee.
Related Work
Works such as Chen et al. [5 ] proved iteration complexity bounds for diffusion models. More recent work, such as Guan et al. [13 ] , provides convergence analysis for generative modeling in convex domains. Several recent works have analyzed the sample complexity of score-based diffusion models. Gupta et al. [14 ] derive a sample complexity bound assuming access to ERM, and Gaur et al. [10 ] relax this assumption, not requiring access to ERM.
Zhou and Liu [26 ] performed a sample complexity analysis for flow matching models wherein the Wasserstein distance between the true and estimated distributions is bounded by decomposing the error in calculating the velocity function into errors incurred due to the limited approximation power of the neural network function class, as well as the finite sample size. As stated earlier, this work assumes access to the ERM of the velocity estimation loss. Additionally, the sample complexity result obtained in Zhou and Liu [26 ] is exponential in the data dimension. Our result avoids this exponential dependence by assuming a constant error due to the limited approximation power of the class of neural networks used to approximate the velocity function. We do this since the focus of our work is to analyze the statistical and optimization errors incurred in flow matching. Similar assumptions have been used in previous works on diffusion modeling, such as Gupta et al. [14 ] and Guan et al. [13 ] .
Recently, Benton et al. [3 ] presented error bounds for the generative process using flow matching, assuming that the true velocity field lies within an ϵ 2 \epsilon^2 ϵ 2 neighborhood of the learned velocity field. Their analysis provides error bounds under the assumption of upper bounded L 2 L_2 L 2 approximation error and certain regularity conditions on the data distribution. However, their results do not address the finite time sample complexity, a crucial aspect for understanding the number of training samples required for estimating the velocity field. This work is inspired by existing theoretical analyses such as [7 ] , (Gaur et al., 2023b), [9 ] as well as diffusion models [11 , 21 ] . We adopt a similar high-level decomposition as a conceptual starting point.
Preliminaries and Problem Formulation
We introduce the flow-matching setup used throughout the paper. The goal is to learn a continuous-time generative model that transports samples from a source distribution to a target distribution by solving an ordinary differential equation. We first define the source and target distributions, specify probability paths through couplings, introduce the associated marginal velocity field, and then state the finite-dataset learning objective analyzed in this work.
Source and target distributions. Let π 0 \pi_0 π 0 denote a source distribution on R d \mathbb{R}^{d} R d , such as a standard Gaussian distribution, and let π 1 \pi_1 π 1 denote the target data distribution. The goal of generative modeling is to construct a sampling procedure that transforms an initial sample from π 0 \pi_0 π 0 into a sample whose distribution is close to π 1 \pi_1 π 1 . Given a time-dependent velocity field
u : R d × [ 0 , 1 ] → R d , u : \mathbb{R}^{d} \times[0, 1] \to\mathbb{R}^{d}, u : R d × [ 0 , 1 ] → R d ,
the associated ODE is
d d t Y t = u ( Y t , t ) , Y 0 ∼ π 0 . \frac{d}{dt}Y_t = u(Y_t,t), \qquad Y_0 \sim\pi_0. d t d Y t = u ( Y t , t ) , Y 0 ∼ π 0 .
If the terminal law of Y 1 Y_1 Y 1 is close to π 1 \pi_1 π 1 , then this ODE defines a generative model.
Probability paths and couplings. Flow matching specifies a reference probability path connecting π 0 \pi_0 π 0 and π 1 \pi_1 π 1 . Let
( X 0 , X 1 ) ∼ Γ , X 0 ∼ π 0 , X 1 ∼ π 1 , (X_0, X_1) \sim\Gamma, \qquad X_0 \sim\pi_0, \qquad X_1 \sim\pi_1, ( X 0 , X 1 ) ∼ Γ , X 0 ∼ π 0 , X 1 ∼ π 1 ,
where Γ ∈ Π ( π 0 , π 1 ) \Gamma\in\Pi(\pi_0,\pi_1) Γ ∈ Π ( π 0 , π 1 ) is a coupling between the source and target distributions. Let
I t : R d × R d → R d , t ∈ [ 0 , 1 ] , I_t : \mathbb{R}^{d} \times\mathbb{R}^{d} \to\mathbb{R}^{d}, \qquad t \in[0,1], I t : R d × R d → R d , t ∈ [ 0 , 1 ] ,
be an interpolation map satisfying the endpoint conditions
I 0 ( x 0 , x 1 ) = x 0 , I 1 ( x 0 , x 1 ) = x 1 . I_0(x_0,x_1) = x_0, \qquad I_1(x_0,x_1) = x_1. I 0 ( x 0 , x 1 ) = x 0 , I 1 ( x 0 , x 1 ) = x 1 .
The associated path is
X t : = I t ( X 0 , X 1 ) , ρ t : = Law ( X t ) . X_t := I_t(X_0,X_1), \qquad\rho_t := \operatorname{Law}(X_t). X t := I t ( X 0 , X 1 ) , ρ t := Law ( X t ) .
Thus,
ρ 0 = π 0 , ρ 1 = π 1 . \rho_0 = \pi_0, \qquad\rho_1 = \pi_1. ρ 0 = π 0 , ρ 1 = π 1 .
When the interpolation map is differentiable in time, define the pathwise velocity by
X ˙ t : = d d t I t ( X 0 , X 1 ) . \dot{X}_t := \frac{d}{dt}I_t(X_0,X_1). X ˙ t := d t d I t ( X 0 , X 1 ) .
This quantity describes the velocity of a particle moving along the interpolation path associated with the coupled endpoint pair ( X 0 , X 1 ) (X_0,X_1) ( X 0 , X 1 ) .
Marginal velocity field. The pathwise velocity X ˙ t \dot{X}_t X ˙ t depends on the coupled endpoints ( X 0 , X 1 ) (X_0, X_1) ( X 0 , X 1 ) . During generation, however, these endpoints are not observed. A generative ODE can only depend on the current state and time. The relevant deployable target velocity field is therefore the conditional mean
u ⋆ ( x , t ) : = E [ X ˙ t ∣ X t = x , t ] . u^\star(x,t) := \mathbb{E}\left[\dot{X}_t \mid X_t = x,\, t\right]. u ⋆ ( x , t ) := E [ X ˙ t ∣ X t = x , t ] .
The field u ⋆ u^\star u ⋆ depends only on ( x , t ) (x,t) ( x , t ) and is the ideal deployable target that the learned velocity field seeks to approximate. The fact that the ODE driven by u ⋆ u^\star u ⋆ reproduces the prescribed path marginals is not inferred solely from the conditional-mean definition above. Instead, the required path-consistency property is imposed explicitly in Assumption 3.7 .
The linear interpolation path. The main theorem in this work is stated for the linear, or rectified, interpolation path
X t = ( 1 − t ) X 0 + t X 1 , t ∈ [ 0 , 1 ] . X_t = (1-t)X_0 + tX_1,\qquad t \in[0,1]. X t = ( 1 − t ) X 0 + t X 1 , t ∈ [ 0 , 1 ] .
For this path,
X ˙ t = X 1 − X 0 . \dot{X}_t = X_1 - X_0. X ˙ t = X 1 − X 0 .
The corresponding marginal velocity field is
u ⋆ ( x , t ) = E [ X 1 − X 0 ∣ X t = x , t ] . u^\star(x,t) = \mathbb{E}\left[X_1-X_0 \mid X_t=x,\,t\right]. u ⋆ ( x , t ) = E [ X 1 − X 0 ∣ X t = x , t ] .
This formulation includes the standard rectified-flow setup and allows different choices of the coupling Γ \Gamma Γ , such as independent couplings or optimal-transport-inspired couplings. The coupling is part of the probability-path specification: changing Γ \Gamma Γ changes the regression target and can affect the difficulty of learning the marginal velocity field, even when the interpolation map itself remains linear.
Learned velocity field. We approximate the marginal velocity field u ⋆ u^\star u ⋆ using a neural network
u θ : R d × [ 0 , 1 ] → R d , θ ∈ Θ . u_\theta: \mathbb{R}^{d} \times[0,1] \to\mathbb{R}^{d},\qquad\theta\in\Theta. u θ : R d × [ 0 , 1 ] → R d , θ ∈ Θ.
The learned velocity field is deployable because it takes only the current state x x x and time t t t as inputs. For a fixed parameter θ \theta θ , samples are generated by solving
d d t Y t θ = u θ ( Y t θ , t ) , Y 0 θ ∼ π 0 . \frac{\mathrm{d}}{\mathrm{d}t}Y_t^\theta= u_\theta(Y_t^\theta,t),\qquad Y_0^\theta\sim\pi_0. d t d Y t θ = u θ ( Y t θ , t ) , Y 0 θ ∼ π 0 .
We denote the terminal law of this learned flow by
π ^ 1 θ : = Law ( Y 1 θ ) . \widehat{\pi}_1^\theta:= \operatorname{Law}(Y_1^\theta). π 1 θ := Law ( Y 1 θ ) .
For the final learned parameter θ T \theta_T θ T , the generated terminal distribution is π ^ 1 θ T \widehat{\pi}_1^{\theta_T} π 1 θ T . The objective is to make this distribution close to the target distribution π 1 \pi_1 π 1 .
Population flow-matching objective. For the linear interpolation path, a population flow-matching sample is
Z = ( X 0 , X 1 , t ) , ( X 0 , X 1 ) ∼ Γ , t ∼ Uniform [ 0 , 1 ] . Z=(X_0,X_1,t),\qquad(X_0,X_1)\sim\Gamma,\qquad t\sim\operatorname{Uniform}[0,1]. Z = ( X 0 , X 1 , t ) , ( X 0 , X 1 ) ∼ Γ , t ∼ Uniform [ 0 , 1 ] .
The corresponding state and pathwise velocity are
X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 . X_t=(1-t)X_0+tX_1,\qquad\dot{X}_t=X_1-X_0. X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 .
For a parameter θ ∈ Θ \theta\in\Theta θ ∈ Θ , define the single-sample flow-matching loss
ℓ θ ( Z ) : = ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 . \ell_\theta(Z) := \left\|u_\theta\left((1-t)X_0+tX_1,t\right)-(X_1-X_0)\right\|_2^2. ℓ θ ( Z ) := ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 .
The population flow-matching loss is
L ( θ ) : = E [ ℓ θ ( Z ) ] . L(\theta) := \mathbb{E}\left[\ell_\theta(Z)\right]. L ( θ ) := E [ ℓ θ ( Z ) ] .
Equivalently,
L ( θ ) = ∫ 0 1 E ( X 0 , X 1 ) ∼ Γ [ ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 ] d t . L(\theta)=\int_0^1\mathbb{E}_{(X_0,X_1)\sim\Gamma}\left[\left\|u_\theta\left((1-t)X_0+tX_1,t\right)-(X_1-X_0)\right\|_2^2\right]\,dt. L ( θ ) = ∫ 0 1 E ( X 0 , X 1 ) ∼ Γ [ ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 ] d t .
Let
L ⋆ : = inf u E [ ∥ u ( X t , t ) − X ˙ t ∥ 2 2 ] , L^\star:= \inf_u \mathbb{E}\left[\left\|u(X_t,t)-\dot{X}_t\right\|_2^2\right], L ⋆ := u inf E [ u ( X t , t ) − X ˙ t 2 2 ] ,
where the infimum is over all measurable deployable velocity fields
u : R d × [ 0 , 1 ] → R d . u:\mathbb{R}^d\times[0,1]\to\mathbb{R}^d. u : R d × [ 0 , 1 ] → R d .
The minimizer is the marginal velocity field u ⋆ u^\star u ⋆ . By the L 2 L^2 L 2 projection identity,
L ( θ ) − L ⋆ = E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . L(\theta)-L^\star=\mathbb{E}\left[\left\|u_\theta(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]. L ( θ ) − L ⋆ = E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] .
Thus, controlling the excess population flow-matching loss is equivalent to controlling the integrated squared error between the learned deployable velocity field and the target marginal velocity field along the reference path.
Empirical flow-matching objective. In practice, the population objective is replaced by a finite empirical objective. Given an i.i.d. training dataset
D N : = { Z i } i = 1 N , Z i = ( X 0 , i , X 1 , i , t i ) , D_N:=\{Z_i\}_{i=1}^N,\qquad Z_i=(X_{0,i},X_{1,i},t_i), D N := { Z i } i = 1 N , Z i = ( X 0 , i , X 1 , i , t i ) ,
where
( X 0 , i , X 1 , i ) ∼ Γ , t i ∼ Uniform [ 0 , 1 ] , (X_{0,i},X_{1,i})\sim\Gamma,\qquad t_i\sim\operatorname{Uniform}[0,1], ( X 0 , i , X 1 , i ) ∼ Γ , t i ∼ Uniform [ 0 , 1 ] ,
the empirical flow-matching loss is
L ^ N ( θ ) : = 1 N ∑ i = 1 N ℓ θ ( Z i ) . \widehat{L}_N(\theta):=\frac{1}{N}\sum_{i=1}^N\ell_\theta(Z_i). L N ( θ ) := N 1 i = 1 ∑ N ℓ θ ( Z i ) .
Equivalently,
L ^ N ( θ ) = 1 N ∑ i = 1 N ∥ u θ ( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) − ( X 1 , i − X 0 , i ) ∥ 2 2 . \widehat{L}_N(\theta)=\frac{1}{N}\sum_{i=1}^N\left\|u_\theta\left((1-t_i)X_{0,i}+t_iX_{1,i},t_i\right)-(X_{1,i}-X_{0,i})\right\|_2^2. L N ( θ ) = N 1 i = 1 ∑ N ∥ u θ ( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) − ( X 1 , i − X 0 , i ) ∥ 2 2 .
Let
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N\in\arg\min_{\theta\in\Theta}\widehat{L}_N(\theta) θ N ∈ arg θ ∈ Θ min L N ( θ )
denote an empirical risk minimizer. This parameter is used only as a theoretical comparator; the algorithm is not assumed to have access to it. Instead, the learned parameter is obtained by running a finite number T T T of stochastic-gradient updates on the empirical objective L ^ N \widehat{L}_N L N . We denote the resulting parameter by θ T \theta_T θ T . Thus, the analysis distinguishes two resources:
N = number of training samples , T = number of stochastic-gradient updates . N=\text{number of training samples},\qquad T=\text{number of stochastic-gradient updates}. N = number of training samples , T = number of stochastic-gradient updates .
The dataset size N N N controls the statistical error between L L L and L ^ N \widehat{L}_N L N , while the optimization budget T T T controls how closely θ T \theta_T θ T approaches the empirical minimizer θ ^ N \widehat{\theta}_N θ N .
Problem statement. This work studies the following question:
How many training samples and stochastic-gradient updates are sufficient for a neural velocity field trained by flow matching to generate a distribution close to the target distribution?
More precisely, if θ T \theta_T θ T denotes the parameter obtained after T T T stochastic-gradient updates on the finite empirical objective L ^ N \widehat{L}_N L N , we seek to bound W 2 ( π ^ 1 θ T , π 1 ) W_2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right) W 2 ( π 1 θ T , π 1 ) . The remainder of the paper develops a finite-sample and finite-time analysis of this quantity without assuming access to the exact empirical risk minimizer θ ^ N \widehat{\theta}_N θ N .
Our Approach
We now describe the assumptions and proof strategy used to obtain an ERM-free finite-dataset sample-complexity guarantee for flow matching. The goal is to control the terminal distributional error of the learned flow in terms of the finite-sample and finite-time errors incurred while learning the velocity field. The main ingredients are a sub-exponential data condition, an approximation condition for the neural velocity class, a statistical uniform-convergence bound for the empirical flow-matching objective, an empirical optimization condition for projected finite-dataset stochastic-gradient training, and a path-consistent uniform flow-stability condition converting velocity-field error into Wasserstein error.
Assumptions
We first collect the assumptions used in the main result.
Assumption 3.1 (Sub-exponential source and target distributions). There exist constants K X K_X K X , c 0 c_0 c 0 , c 1 > 0 c_1 > 0 c 1 > 0 such that, for every r ≥ 0 r \ge0 r ≥ 0 ,
P ( ∥ X 0 ∥ 2 > r ) ≤ c 0 exp ( − c 1 r / K X ) , P ( ∥ X 1 ∥ 2 > r ) ≤ c 0 exp ( − c 1 r / K X ) . \mathbb{P}\left(\lVert X_0\rVert_2 > r\right) \le c_0\exp\left(-c_1r/K_X\right), \qquad\mathbb{P}\left(\lVert X_1\rVert_2 > r\right) \le c_0\exp\left(-c_1r/K_X\right). P ( ∥ X 0 ∥ 2 > r ) ≤ c 0 exp ( − c 1 r / K X ) , P ( ∥ X 1 ∥ 2 > r ) ≤ c 0 exp ( − c 1 r / K X ) . Here
( X 0 , X 1 ) ∼ Γ , Γ ∈ Π ( π 0 , π 1 ) , (X_0,X_1) \sim\Gamma, \qquad\Gamma\in\Pi(\pi_0,\pi_1), ( X 0 , X 1 ) ∼ Γ , Γ ∈ Π ( π 0 , π 1 ) , is the coupling used to define the interpolation path.
Assumption 3.1 replaces compact support of the source and target distributions. This is important because standard source distributions used in generative modeling, such as Gaussian noise, are unbounded. Sub-exponential and related tail assumptions are standard in high-dimensional probability and statistical learning theory [24 , 25 ] , and analogous tail-control conditions are common in recent analyses of diffusion and generative models [14 , 10 ] . In our proof, this assumption is used only to control the contribution of the endpoint-truncation complement.
Assumption 3.2 (Approximation error). Let L ∗ L^* L ∗ denote the minimum population flow-matching risk over all measurable deployable velocity fields. Let θ Θ ∗ ∈ arg min θ ∈ Θ L ( θ ) \theta_\Theta^* \in\arg\min_{\theta\in\Theta} L(\theta) θ Θ ∗ ∈ arg min θ ∈ Θ L ( θ ) be a population minimizer within the prescribed neural velocity class. There exists ϵ a p p r o x ≥ 0 \epsilon_{\mathrm{approx}} \ge0 ϵ approx ≥ 0 such that
L ( θ Θ ∗ ) − L ∗ ≤ ϵ a p p r o x . L(\theta_\Theta^*) - L^* \le\epsilon_{\mathrm{approx}}. L ( θ Θ ∗ ) − L ∗ ≤ ϵ approx .
Assumption 3.2 isolates the approximation power of the prescribed neural velocity class. We keep ϵ a p p r o x \epsilon_{\mathrm{approx}} ϵ approx explicit throughout the theorem rather than optimizing over architectures. This separates approximation effects from finite-dataset statistical error and finite-time optimization error.
Assumption 3.3 (Empirical proximal-PL condition). For the finite dataset D N = { Z i } i = 1 N \mathcal{D}_N = \{Z_i\}_{i=1}^N D N = { Z i } i = 1 N , let
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N \in\arg\min_{\theta\in\Theta} \widehat{L}_N(\theta) θ N ∈ arg θ ∈ Θ min L N ( θ ) denote an empirical risk minimizer over the compact convex set Θ \Theta Θ . For θ ∈ Θ \theta\in\Theta θ ∈ Θ , define the constrained gradient-mapping quantity
M N ( θ ) : = − 2 α N min θ ′ ∈ Θ [ ⟨ ∇ L ^ N ( θ ) , θ ′ − θ ⟩ + α N 2 ∥ θ ′ − θ ∥ 2 2 ] \mathcal{M}_N(\theta) := -2\alpha_N \min_{\theta'\in\Theta}\left[\left\langle\nabla\widehat{L}_N(\theta),\theta'-\theta\right\rangle+\frac{\alpha_N}{2}\left\|\theta'-\theta\right\|_2^2\right] M N ( θ ) := − 2 α N θ ′ ∈ Θ min [ ⟨ ∇ L N ( θ ) , θ ′ − θ ⟩ + 2 α N ∥ θ ′ − θ ∥ 2 2 ] where α N \alpha_N α N is the empirical smoothness constant from Assumption Assumption 3.4 . The empirical flow-matching loss L ^ N \widehat{L}_N L N satisfies the proximal Polyak–Łojasiewicz condition on Θ \Theta Θ : there exists μ N > 0 \mu_N>0 μ N > 0 such that, for every θ ∈ Θ \theta\in\Theta θ ∈ Θ ,
1 2 M N ( θ ) ≥ μ N ( L ^ N ( θ ) − L ^ N ( θ ^ N ) ) . \frac{1}{2}\mathcal{M}_N(\theta)\geq\mu_N\left(\widehat{L}_N(\theta)-\widehat{L}_N(\widehat{\theta}_N)\right). 2 1 M N ( θ ) ≥ μ N ( L N ( θ ) − L N ( θ N ) ) . The proximal Polyak–Łojasiewicz condition is the constrained analogue of the usual gradient-domination condition used in the analysis of projected and proximal first-order methods [15 ] . When Θ = R P \Theta=\mathbb{R}^P Θ = R P , or whenever the constraint is inactive in the relevant optimization region, we have
M N ( θ ) = ∥ ∇ L ^ N ( θ ) ∥ 2 2 , \mathcal{M}_N(\theta)=\left\|\nabla\widehat{L}_N(\theta)\right\|_2^2, M N ( θ ) = ∇ L N ( θ ) 2 2 , and Assumption 3.3 reduces to the ordinary Polyak–Łojasiewicz inequality
1 2 ∥ ∇ L ^ N ( θ ) ∥ 2 2 ≥ μ N ( L ^ N ( θ ) − L ^ N ( θ ^ N ) ) . \frac{1}{2}\left\|\nabla\widehat{L}_N(\theta)\right\|_2^2\geq\mu_N\left(\widehat{L}_N(\theta)-\widehat{L}_N(\widehat{\theta}_N)\right). 2 1 ∇ L N ( θ ) 2 2 ≥ μ N ( L N ( θ ) − L N ( θ N ) ) . The empirical minimizer θ ^ N \widehat{\theta}_N θ N is a theoretical comparator; the algorithm is not assumed to have access to it.
Assumption 3.4 (Empirical smoothness, projected SGD, and interior operating regime). For the finite dataset
D N = { Z i } i = 1 N , \mathcal{D}_N=\{Z_i\}_{i=1}^N, D N = { Z i } i = 1 N , the empirical loss
L ^ N ( θ ) = 1 N ∑ i = 1 N ℓ θ ( Z i ) \widehat{L}_N(\theta)=\frac{1}{N}\sum_{i=1}^N\ell_\theta(Z_i) L N ( θ ) = N 1 i = 1 ∑ N ℓ θ ( Z i ) is differentiable in θ \theta θ and is α N \alpha_N α N -smooth on the compact convex parameter region Θ \Theta Θ . That is, for every θ , θ ′ ∈ Θ \theta,\theta'\in\Theta θ , θ ′ ∈ Θ ,
∥ ∇ L ^ N ( θ ) − ∇ L ^ N ( θ ′ ) ∥ 2 ≤ α N ∥ θ − θ ′ ∥ 2 . \left\|\nabla\widehat{L}_N(\theta)-\nabla\widehat{L}_N(\theta')\right\|_2\leq\alpha_N\left\|\theta-\theta'\right\|_2. ∇ L N ( θ ) − ∇ L N ( θ ′ ) 2 ≤ α N ∥ θ − θ ′ ∥ 2 . For the smooth-activation network class described in § 3.2 , this differentiability requirement is compatible with the architecture. In particular, for every fixed finite dataset D N \mathcal{D}_N D N , bounded parameters and bounded activation derivatives imply that a finite empirical smoothness constant α N \alpha_N α N exists on Θ \Theta Θ . The value of α N \alpha_N α N may depend on the fixed dataset, the architecture, the parameter bound, the activation constants, and the endpoint magnitudes in the dataset.
Conditioned on D N \mathcal{D}_N D N , the algorithm is initialized at θ 0 ∈ Θ \theta_0\in\Theta θ 0 ∈ Θ and performs projected finite-dataset stochastic-gradient updates
θ k + 1 = Π Θ ( θ k − η k g k ) , g k = ∇ θ ℓ θ k ( Z I k ) , \theta_{k+1}=\Pi_\Theta\left(\theta_k-\eta_k g_k\right),\qquad g_k=\nabla_\theta\ell_{\theta_k}(Z_{I_k}), θ k + 1 = Π Θ ( θ k − η k g k ) , g k = ∇ θ ℓ θ k ( Z I k ) , where I k ∼ Uniform { 1 , … , N } I_k\sim\operatorname{Uniform}\{1,\ldots,N\} I k ∼ Uniform { 1 , … , N } is sampled independently of the past optimization history and Π Θ \Pi_\Theta Π Θ denotes Euclidean projection onto Θ \Theta Θ .
Let { F k } k ≥ 0 \{\mathcal{F}_k\}_{k\geq0} { F k } k ≥ 0 denote the filtration generated by the optimization process up to iteration k k k , conditioned on D N D_N D N . The stochastic-gradient oracle is conditionally unbiased for the empirical objective:
E [ g k ∣ F k , D N ] = ∇ L ^ N ( θ k ) . \mathbb{E}\left[g_k \mid\mathcal{F}_k,D_N\right]=\nabla\widehat{L}_N(\theta_k). E [ g k ∣ F k , D N ] = ∇ L N ( θ k ) .
Moreover, there exists σ N 2 > 0 \sigma_N^2>0 σ N 2 > 0 such that
E [ ∥ g k − ∇ L ^ N ( θ k ) ∥ 2 2 ∣ F k , D N ] ≤ σ N 2 . \mathbb{E}\left[\left\|g_k-\nabla\widehat{L}_N(\theta_k)\right\|_2^2\mid\mathcal{F}_k,D_N\right]\leq\sigma_N^2. E [ g k − ∇ L N ( θ k ) 2 2 ∣ F k , D N ] ≤ σ N 2 .
Finally, to obtain the clean O ( T − 1 ) O(T^{-1}) O ( T − 1 ) optimization bound under the bounded conditional-variance assumption above, we work in an interior operating regime: for every k = 0 , … , T − 1 k=0,\ldots,T-1 k = 0 , … , T − 1 , the projected update is inactive both for the realized stochastic step and for the corresponding mean-gradient step, namely
θ k − η k g k ∈ Θ , θ k − η k ∇ L ^ N ( θ k ) ∈ Θ \theta_k-\eta_k g_k\in\Theta,\qquad\theta_k-\eta_k\nabla\widehat{L}_N(\theta_k)\in\Theta θ k − η k g k ∈ Θ , θ k − η k ∇ L N ( θ k ) ∈ Θ
almost surely conditional on D N D_N D N . Equivalently, the projection acts as the identity along the optimization trajectory and the corresponding mean-gradient trajectory.
Lemma 3.5 (Automatic containment). Since θ 0 ∈ Θ \theta_0\in\Theta θ 0 ∈ Θ and Π Θ \Pi_\Theta Π Θ maps R P \mathbb{R}^P R P into Θ \Theta Θ , the projected recursion in Assumption 3.4 satisfies θ k ∈ Θ \theta_k\in\Theta θ k ∈ Θ , k = 0 , 1 , … , T k=0,1,\ldots,T k = 0 , 1 , … , T . In particular, θ T ∈ Θ \theta_T\in\Theta θ T ∈ Θ .
Smoothness and bounded conditional gradient variance are standard assumptions in stochastic-gradient analysis [12 , 1 , 16 ] . In the present finite-dataset setting, the stochastic gradient is unbiased for the empirical gradient ∇ L ^ N ( θ k ) \nabla\widehat{L}_N(\theta_k) ∇ L N ( θ k ) , rather than for the population gradient ∇ L ( θ k ) \nabla L(\theta_k) ∇ L ( θ k ) . This distinction is central to the analysis because the statistical error of the empirical objective and the optimization error from approximately minimizing it are controlled separately.
The projection guarantees that the iterates remain in the compact parameter region on which the empirical smoothness and network regularity properties are imposed. The separate interior-operating-regime clause is used only to retain the clean bounded-variance O ( T − 1 ) O(T^{-1}) O ( T − 1 ) optimization recursion without an additional boundary-active error term. If projection is active at non-negligible frequency, one would instead require an interpolation-type noise condition or a separate boundary analysis.
Assumption 3.6 (Uniform-in-N N N empirical-constant regularity). There exist deterministic constants
μ min > 0 , α max < ∞ , σ max 2 < ∞ , e ‾ 0 < ∞ , \mu_{\min}>0,\qquad\alpha_{\max}<\infty,\qquad\sigma_{\max}^2<\infty,\qquad\overline{e}_0<\infty, μ m i n > 0 , α m a x < ∞ , σ m a x 2 < ∞ , e 0 < ∞ , all independent of N N N , and for each N N N an event G N \mathcal{G}_N G N over the draw of D N D_N D N such that P ( G N ) ≥ 1 − δ o p t \mathbb{P}(\mathcal{G}_N)\geq1-\delta_{\mathrm{opt}} P ( G N ) ≥ 1 − δ opt . On G N \mathcal{G}_N G N , the empirical proximal-PL constant μ N \mu_N μ N , the empirical smoothness constant α N \alpha_N α N , the conditional gradient-variance bound σ N 2 \sigma_N^2 σ N 2 , and the initialization gap
e 0 : = L ^ N ( θ 0 ) − L ^ N ( θ ^ N ) e_0:=\widehat{L}_N(\theta_0)-\widehat{L}_N(\widehat{\theta}_N) e 0 := L N ( θ 0 ) − L N ( θ N ) satisfy simultaneously μ min ≤ μ N ≤ α N ≤ α max \mu_{\min}\leq\mu_N\leq\alpha_N\leq\alpha_{\max} μ m i n ≤ μ N ≤ α N ≤ α m a x , σ N 2 ≤ σ max 2 \sigma_N^2\leq\sigma_{\max}^2 σ N 2 ≤ σ m a x 2 , e 0 ≤ e ‾ 0 e_0\leq\overline{e}_0 e 0 ≤ e 0 .
Assumption 3.6 makes explicit the N N N -uniformity required for the displayed T = O ~ ( ϵ − 2 ) T=\widetilde{O}(\epsilon^{-2}) T = O ( ϵ − 2 ) optimization scaling. It is a regularity condition on the realized empirical optimization landscape that is stated rather than derived. Deriving μ min \mu_{\min} μ m i n , or more generally characterizing the N N N -dependence of the empirical constants for a particular architecture and initialization scheme, is outside the scope of the present modular guarantee.
Assumption 3.7 (Flow regularity, path consistency, and uniform stability). For every θ ∈ Θ \theta\in\Theta θ ∈ Θ , the learned ODE
d d t Y t = u θ ( Y t , t ) \frac{d}{dt}Y_t=u_\theta(Y_t,t) d t d Y t = u θ ( Y t , t ) admits a unique solution on [ 0 , 1 ] [0,1] [ 0 , 1 ] for every initial condition. The reference ODE driven by the marginal velocity field u ⋆ u^\star u ⋆ also admits a unique solution on [ 0 , 1 ] [0,1] [ 0 , 1 ] for every initial condition. For every θ ∈ Θ \theta\in\Theta θ ∈ Θ , t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] , let L θ ( t ) L_\theta(t) L θ ( t ) be a spatial Lipschitz constant of u θ ( ⋅ , t ) u_\theta(\cdot,t) u θ ( ⋅ , t ) . That is,
∥ u θ ( x , t ) − u θ ( x ′ , t ) ∥ 2 ≤ L θ ( t ) ∥ x − x ′ ∥ 2 \|u_\theta(x,t)-u_\theta(x',t)\|_2 \leq L_\theta(t)\|x-x'\|_2 ∥ u θ ( x , t ) − u θ ( x ′ , t ) ∥ 2 ≤ L θ ( t ) ∥ x − x ′ ∥ 2 for every x , x ′ ∈ R d x,x' \in\mathbb{R}^d x , x ′ ∈ R d . Assume that there exists a deterministic constant Λ f l o w < ∞ \Lambda_{\mathrm{flow}} < \infty Λ flow < ∞ such that
sup θ ∈ Θ ∫ 0 1 L θ ( t ) d t ≤ Λ f l o w . \sup_{\theta\in\Theta}\int_0^1 L_\theta(t)\,\mathrm{d}t \leq\Lambda_{\mathrm{flow}}. θ ∈ Θ sup ∫ 0 1 L θ ( t ) d t ≤ Λ flow . Define the uniform flow-stability constant
K f l o w : = exp ( Λ f l o w ) . K_{\mathrm{flow}} := \exp\left(\Lambda_{\mathrm{flow}}\right). K flow := exp ( Λ flow ) . Assume moreover that the marginal velocity field u ⋆ u^\star u ⋆ is path-consistent with the prescribed interpolation path. That is, if Z t Z_t Z t denotes the unique solution of
d d t Z t = u ⋆ ( Z t , t ) , Z 0 ∼ π 0 , \frac{d}{dt}Z_t=u^\star(Z_t,t), \qquad Z_0\sim\pi_0, d t d Z t = u ⋆ ( Z t , t ) , Z 0 ∼ π 0 , then
Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] . \operatorname{Law}(Z_t)=\rho_t \qquad\text{for every }t\in[0,1]. Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] . In particular,
Law ( Z 1 ) = ρ 1 = π 1 . \operatorname{Law}(Z_1)=\rho_1=\pi_1. Law ( Z 1 ) = ρ 1 = π 1 .
Assumption 3.7 is used to convert velocity-field estimation error into terminal distributional error. The constant K f l o w K_{\mathrm{flow}} K flow is a deterministic class-level quantity associated with the prescribed bounded-parameter velocity class and its regularity regime, rather than with a particular random realization of the stochastic-gradient algorithm. The main theorem is stated for the exact learned ODE flow. If a numerical ODE solver is used in implementation, an additional solver error can be added separately by the triangle inequality, but we do not include this term in the main sample-complexity statement.
Neural Velocity Class
The learned velocity field u θ : R d × [ 0 , 1 ] → R d u_\theta:\mathbb{R}^d\times[0,1]\to\mathbb{R}^d u θ : R d × [ 0 , 1 ] → R d is parameterized by a fully connected feedforward network taking ( x , t ) ∈ R d + 1 (x,t)\in\mathbb{R}^{d+1} ( x , t ) ∈ R d + 1 as input and returning a vector in R d \mathbb{R}^d R d . Let the network have depth D D D , hidden width W W W , and parameter count
P = W ( d + 1 ) + W + ( D − 2 ) ( W 2 + W ) + d W + d . P=W(d+1)+W+(D-2)(W^2+W)+dW+d. P = W ( d + 1 ) + W + ( D − 2 ) ( W 2 + W ) + d W + d .
Thus,
P = O ( D W 2 + d W ) . P=O(DW^2+dW). P = O ( D W 2 + d W ) .
The parameter set Θ ⊂ R P \Theta\subset\mathbb{R}^P Θ ⊂ R P is a nonempty compact convex subset of the finite-dimensional parameter space. Compactness is used to obtain uniform bounds on the network output, its spatial Lipschitz constants, and the empirical Hessian on a fixed finite dataset. Convexity ensures that line segments between points in Θ \Theta Θ remain inside the parameter region on which empirical smoothness is imposed. By Lemma 3.5 , projected SGD ensures that these bounded-parameter properties apply to every optimization iterate and to the final learned parameter θ T \theta_T θ T .
Unlike the ReLU case, which is only piecewise smooth as a function of the parameters, we work with a smooth activation function
σ : R → R . \sigma: \mathbb{R} \to\mathbb{R}. σ : R → R .
Specifically, we assume
σ ∈ C 2 ( R ) , sup z ∈ R ∣ σ ′ ( z ) ∣ ≤ M 1 , \sigma\in C^2(\mathbb{R}), \qquad\sup_{z\in\mathbb{R}}|\sigma'(z)| \le M_1, σ ∈ C 2 ( R ) , z ∈ R sup ∣ σ ′ ( z ) ∣ ≤ M 1 ,
sup z ∈ R ∣ σ ′ ′ ( z ) ∣ ≤ M 2 , ∣ σ ( 0 ) ∣ ≤ M 0 . \sup_{z\in\mathbb{R}}|\sigma''(z)| \le M_2, \qquad|\sigma(0)| \le M_0. z ∈ R sup ∣ σ ′′ ( z ) ∣ ≤ M 2 , ∣ σ ( 0 ) ∣ ≤ M 0 .
Softplus and tanh are canonical examples satisfying these conditions. This smooth-activation setup makes the empirical loss differentiable in the parameters and is therefore compatible with finite-time projected-SGD analysis under empirical smoothness. The empirical proximal-PL condition remains a separate optimization assumption.
We use two standard consequences of this bounded-parameter smooth network class. First, the class has uniform linear growth. There exist constants A N N , B N N > 0 A_{\mathrm{NN}}, B_{\mathrm{NN}} > 0 A NN , B NN > 0 , depending only on the architecture, the parameter bound, and the activation constants, such that, for every θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] \theta\in\Theta, x \in\mathbb{R}^d, t \in[0,1] θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] , we have
∥ u θ ( x , t ) ∥ 2 ≤ A N N + B N N ∥ x ∥ 2 . \lVert u_\theta(x,t)\rVert_2 \le A_{\mathrm{NN}} + B_{\mathrm{NN}}\lVert x\rVert_2. ∥ u θ ( x , t ) ∥ 2 ≤ A NN + B NN ∥ x ∥ 2 .
This fact is proved in Lemma D.3 . It is used to control both the loss on the endpoint-truncation event and the contribution of the sub-exponential tail region. We do not require a dimension-free approximation theorem for the neural velocity class.
Second, we use a metric-entropy uniform-convergence bound for the induced truncated squared-loss class. For a sample
Z = ( X 0 , X 1 , t ) , Z = (X_0,X_1,t), Z = ( X 0 , X 1 , t ) ,
define
X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 , X_t = (1-t)X_0 + tX_1, \qquad\dot{X}_t = X_1 - X_0, X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 ,
and
ℓ θ ( Z ) : = ∥ u θ ( X t , t ) − X ˙ t ∥ 2 2 . \ell_\theta(Z) := \lVert u_\theta(X_t,t) - \dot{X}_t\rVert_2^2. ℓ θ ( Z ) := ∥ u θ ( X t , t ) − X ˙ t ∥ 2 2 .
For R > 0 R > 0 R > 0 , let
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } \mathcal{E}_R := \{\lVert X_0\rVert_2 \le R,\ \lVert X_1\rVert_2 \le R\} E R := {∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R }
and define the truncated squared-loss class
G W , D ( R ) : = { Z ↦ ℓ θ ( Z ) 1 E R : θ ∈ Θ } . \mathcal{G}_{W,D}^{(R)} := \{Z \mapsto\ell_\theta(Z)\mathbf{1}_{\mathcal{E}_R} : \theta\in\Theta\}. G W , D ( R ) := { Z ↦ ℓ θ ( Z ) 1 E R : θ ∈ Θ } .
On E R \mathcal{E}_R E R , the linear path satisfies
∥ X t ∥ 2 ≤ R , ∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ 2 R . \lVert X_t\rVert_2 \le R, \qquad\lVert\dot{X}_t\rVert_2 = \lVert X_1-X_0\rVert_2 \le2R. ∥ X t ∥ 2 ≤ R , ∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ 2 R .
Together with the uniform linear-growth bound, this implies
0 ≤ ℓ θ ( Z ) 1 E R ≤ B ℓ ( R ) , 0 \le\ell_\theta(Z)\mathbf{1}_{\mathcal{E}_R} \le B_\ell(R), 0 ≤ ℓ θ ( Z ) 1 E R ≤ B ℓ ( R ) ,
where
B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 . B_\ell(R) := \left(A_{\mathrm{NN}} + (B_{\mathrm{NN}}+2)R\right)^2. B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2 .
The relevant statistical complexity object is the scalar truncated squared-loss class G W , D ( R ) \mathcal{G}_{W,D}^{(R)} G W , D ( R ) , not merely the raw vector-valued velocity class. For bounded-parameter smooth networks, the map
θ ↦ ℓ θ ( Z ) 1 E R \theta\mapsto\ell_\theta(Z)1_{\mathcal{E}_R} θ ↦ ℓ θ ( Z ) 1 E R
is uniformly Lipschitz over Θ \Theta Θ , uniformly for samples satisfying E R \mathcal{E}_R E R . Since Θ ⊂ R P \Theta\subset\mathbb{R}^{P} Θ ⊂ R P is bounded, this yields the covering-number bound
log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( C s m ( R ) ε ) , 0 < ε ≤ B ℓ ( R ) , \log\mathcal{N}\left(\varepsilon,\mathcal{G}_{W,D}^{(R)},\|\cdot\|_{\infty}\right) \le P\log\left(\frac{C_{\mathrm{sm}}(R)}{\varepsilon}\right), \qquad0<\varepsilon\le B_{\ell}(R), log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( ε C sm ( R ) ) , 0 < ε ≤ B ℓ ( R ) ,
where
max { e , B ℓ ( R ) } ≤ C s m ( R ) < ∞ \max\{e,B_{\ell}(R)\}\le C_{\mathrm{sm}}(R)<\infty max { e , B ℓ ( R )} ≤ C sm ( R ) < ∞
depends on the architecture, parameter bound, activation derivative bounds, and truncation radius. The detailed argument is given in Lemma D.5. Although the lemma label is retained for notational continuity, the result used here is a metric-entropy uniform-convergence bound rather than a ReLU pseudo-dimension bound.
Define the N N N -dependent entropy radius
C ‾ s m ( R , N ) : = e N C s m ( R ) B ℓ ( R ) . \overline{C}_{\mathrm{sm}}(R,N):=e^{\frac{NC_{\mathrm{sm}}(R)}{B_{\ell}(R)}}. C sm ( R , N ) := e B ℓ ( R ) N C sm ( R ) .
Since
C s m ( R ) ≥ B ℓ ( R ) , C_{\mathrm{sm}}(R)\ge B_{\ell}(R), C sm ( R ) ≥ B ℓ ( R ) ,
we have
C ‾ s m ( R , N ) ≥ e . \overline{C}_{\mathrm{sm}}(R,N)\ge e. C sm ( R , N ) ≥ e .
Define the corresponding smooth-network complexity quantity by
C s m ( R , N ) : = P log ( C ‾ s m ( R , N ) ) . \mathcal{C}_{\mathrm{sm}}(R,N):=P\log\left(\overline{C}_{\mathrm{sm}}(R,N)\right). C sm ( R , N ) := P log ( C sm ( R , N ) ) .
With this notation, the statistical term appearing in the main theorem has the form
C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N . C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{\mathcal{C}_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}. C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) .
Population and Empirical Objectives
The population flow-matching loss is
L ( θ ) : = E [ ℓ θ ( Z ) ] . L(\theta):=\mathbb{E}\left[\ell_\theta(Z)\right]. L ( θ ) := E [ ℓ θ ( Z ) ] .
Equivalently,
L ( θ ) = ∫ 0 1 E ( X 0 , X 1 ) ∼ Γ [ ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 ] d t . L(\theta)=\int_{0}^{1}\mathbb{E}_{(X_0,X_1)\sim\Gamma}\left[\left\|u_\theta\left((1-t)X_0+tX_1,t\right)-(X_1-X_0)\right\|_{2}^{2}\right]\mathrm{d}t. L ( θ ) = ∫ 0 1 E ( X 0 , X 1 ) ∼ Γ [ ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 ] d t .
Given an independent finite training dataset
D N : = { Z i } i = 1 N , Z i = ( X 0 , i , X 1 , i , t i ) , \mathcal{D}_N:=\{Z_i\}_{i=1}^{N},\qquad Z_i=(X_{0,i},X_{1,i},t_i), D N := { Z i } i = 1 N , Z i = ( X 0 , i , X 1 , i , t i ) ,
where
( X 0 , i , X 1 , i ) ∼ Γ , t i ∼ Uniform [ 0 , 1 ] , (X_{0,i},X_{1,i})\sim\Gamma,\qquad t_i\sim\operatorname{Uniform}[0,1], ( X 0 , i , X 1 , i ) ∼ Γ , t i ∼ Uniform [ 0 , 1 ] ,
the empirical flow-matching loss is
L ^ N ( θ ) : = 1 N ∑ i = 1 N ℓ θ ( Z i ) . \widehat{L}_N(\theta) := \frac{1}{N}\sum_{i=1}^{N}\ell_\theta(Z_i). L N ( θ ) := N 1 i = 1 ∑ N ℓ θ ( Z i ) .
That is,
L ^ N ( θ ) = 1 N ∑ i = 1 N ∥ u θ ( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) − ( X 1 , i − X 0 , i ) ∥ 2 2 . \widehat{L}_N(\theta) = \frac{1}{N}\sum_{i=1}^{N}\left\|u_\theta\left((1-t_i)X_{0,i}+t_iX_{1,i},t_i\right)-(X_{1,i}-X_{0,i})\right\|_2^2. L N ( θ ) = N 1 i = 1 ∑ N ∥ u θ ( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) − ( X 1 , i − X 0 , i ) ∥ 2 2 .
The parameter
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N \in\arg\min_{\theta\in\Theta}\widehat{L}_N(\theta) θ N ∈ arg θ ∈ Θ min L N ( θ )
is used only as a theoretical comparator and is not assumed to be available to the algorithm. The learned parameter θ T \theta_T θ T is instead obtained after T T T projected stochastic-gradient updates on L ^ N \widehat{L}_N L N . Thus, N N N denotes the number of training samples used for statistical control, while T T T denotes the number of stochastic-gradient updates used to approximately minimize the fixed empirical objective.
Projection Identity
The regression target in the flow-matching loss is the pathwise velocity
X ˙ t = X 1 − X 0 , \dot{X}_t = X_1-X_0, X ˙ t = X 1 − X 0 ,
which depends on the coupled endpoint pair. The deployable target velocity is the conditional mean
u ∗ ( x , t ) : = E [ X ˙ t ∣ X t = x , t ] . u^*(x,t) := \mathbb{E}\left[\dot{X}_t \mid X_t=x,t\right]. u ∗ ( x , t ) := E [ X ˙ t ∣ X t = x , t ] .
Let
L ∗ : = inf u E [ ∥ u ( X t , t ) − X ˙ t ∥ 2 2 ] , L^* := \inf_u \mathbb{E}\left[\left\|u(X_t,t)-\dot{X}_t\right\|_2^2\right], L ∗ := u inf E [ u ( X t , t ) − X ˙ t 2 2 ] ,
where the infimum is over all measurable deployable velocity fields
u : R d × [ 0 , 1 ] → R d . u:\mathbb{R}^d\times[0,1]\to\mathbb{R}^d. u : R d × [ 0 , 1 ] → R d .
By the L 2 L^2 L 2 projection identity, u ∗ u^* u ∗ minimizes this population risk over all measurable deployable velocity fields. Moreover, for every θ ∈ Θ \theta\in\Theta θ ∈ Θ , we have
L ( θ ) − L ∗ = E [ ∥ u θ ( X t , t ) − u ∗ ( X t , t ) ∥ 2 2 ] . L(\theta)-L^*=\mathbb{E}\left[\left\|u_\theta(X_t,t)-u^*(X_t,t)\right\|_2^2\right]. L ( θ ) − L ∗ = E [ ∥ u θ ( X t , t ) − u ∗ ( X t , t ) ∥ 2 2 ] .
Thus, the excess population flow-matching loss is exactly the integrated squared error between the learned deployable velocity field and the target marginal velocity field along the reference path.
From Velocity Error to Distributional Error
Let π ^ 1 θ \widehat{\pi}^{\theta}_1 π 1 θ denote the terminal law generated by the exact learned ODE driven by u θ u_\theta u θ :
d d t Y t θ = u θ ( Y t θ , t ) , Y 0 θ ∼ π 0 . \frac{d}{dt}Y_t^\theta=u_\theta(Y_t^\theta,t),\qquad Y_0^\theta\sim\pi_0. d t d Y t θ = u θ ( Y t θ , t ) , Y 0 θ ∼ π 0 .
Let Z t Z_t Z t denote the reference flow driven by u ∗ u^* u ∗ :
d d t Z t = u ∗ ( Z t , t ) , Z 0 ∼ π 0 . \frac{d}{dt}Z_t=u^*(Z_t,t),\qquad Z_0\sim\pi_0. d t d Z t = u ∗ ( Z t , t ) , Z 0 ∼ π 0 .
By the path-consistency clause in Assumption 3.7 ,
Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] . \operatorname{Law}(Z_t)=\rho_t \qquad\text{for every } t\in[0,1]. Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] .
In particular,
Law ( Z 1 ) = π 1 . \operatorname{Law}(Z_1)=\pi_1. Law ( Z 1 ) = π 1 .
For every θ ∈ Θ \theta\in\Theta θ ∈ Θ , Assumption 3.7 provides the deterministic uniform bound
∫ 0 1 L θ ( t ) d t ≤ Λ f l o w , \int_0^1 L_\theta(t)\,\mathrm{d}t\leq\Lambda_{\mathrm{flow}}, ∫ 0 1 L θ ( t ) d t ≤ Λ flow ,
and defines
K f l o w : = exp ( Λ f l o w ) . K_{\mathrm{flow}}:=\exp\left(\Lambda_{\mathrm{flow}}\right). K flow := exp ( Λ flow ) .
The uniform flow-stability argument then gives
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( ∫ 0 1 E [ ∥ u θ ( Z t , t ) − u ⋆ ( Z t , t ) ∥ 2 2 ] d t ) 1 / 2 . W_2\left(\widehat{\pi}_1^\theta,\pi_1\right)\leq K_{\mathrm{flow}}\left(\int_0^1\mathbb{E}\left[\left\|u_\theta(Z_t,t)-u^\star(Z_t,t)\right\|_2^2\right]\mathrm{d}t\right)^{1/2}. W 2 ( π 1 θ , π 1 ) ≤ K flow ( ∫ 0 1 E [ ∥ u θ ( Z t , t ) − u ⋆ ( Z t , t ) ∥ 2 2 ] d t ) 1/2 .
Since Z t ∼ ρ t Z_t\sim\rho_t Z t ∼ ρ t , this can be written equivalently as
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] ) 1 / 2 . W_2\left(\widehat{\pi}_1^\theta,\pi_1\right)\leq K_{\mathrm{flow}}\left(\mathbb{E}\left[\left\|u_\theta(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]\right)^{1/2}. W 2 ( π 1 θ , π 1 ) ≤ K flow ( E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] ) 1/2 .
By the projection identity,
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( L ( θ ) − L ⋆ ) 1 / 2 , ∀ θ ∈ Θ . W_2\left(\widehat{\pi}_1^\theta,\pi_1\right)\leq K_{\mathrm{flow}}\left(L(\theta)-L^\star\right)^{1/2},\qquad\forall\theta\in\Theta. W 2 ( π 1 θ , π 1 ) ≤ K flow ( L ( θ ) − L ⋆ ) 1/2 , ∀ θ ∈ Θ.
The factor K f l o w K_{\mathrm{flow}} K flow is a uniform stability amplification constant for the prescribed learned velocity-field class. It is treated as an explicit problem-dependent regularity quantity; we do not claim that it is dimension free or automatically bounded uniformly over arbitrary neural architectures.
Error Decomposition
Let θ T \theta_T θ T denote the parameter obtained after T T T projected stochastic-gradient updates on the finite empirical objective L ^ N \widehat{L}_N L N . By Lemma 3.5 , θ T ∈ Θ \theta_T\in\Theta θ T ∈ Θ . Let θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N\in\arg\min_{\theta\in\Theta}\widehat{L}_N(\theta) θ N ∈ arg min θ ∈ Θ L N ( θ ) be an empirical risk minimizer, used only as a theoretical comparator. Also let θ Θ ⋆ ∈ arg min θ ∈ Θ L ( θ ) \theta_\Theta^\star\in\arg\min_{\theta\in\Theta}L(\theta) θ Θ ⋆ ∈ arg min θ ∈ Θ L ( θ ) be a population minimizer within the prescribed neural velocity class. Then
L ( θ T ) − L ⋆ ≤ L ( θ Θ ⋆ ) − L ⋆ + 2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ + L ^ N ( θ T ) − L ^ N ( θ ^ N ) . L(\theta_T)-L^\star\leq L(\theta_\Theta^\star)-L^\star+2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|+\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N). L ( θ T ) − L ⋆ ≤ L ( θ Θ ⋆ ) − L ⋆ + 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) + L N ( θ T ) − L N ( θ N ) .
Define
E a p p r o x : = L ( θ Θ ⋆ ) − L ⋆ , E_{\mathrm{approx}}:=L(\theta_\Theta^\star)-L^\star, E approx := L ( θ Θ ⋆ ) − L ⋆ ,
E s t a t : = 2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ , E_{\mathrm{stat}}:=2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|, E stat := 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) ,
and
E o p t : = L ^ N ( θ T ) − L ^ N ( θ ^ N ) . E_{\mathrm{opt}}:=\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N). E opt := L N ( θ T ) − L N ( θ N ) .
Then
L ( θ T ) − L ⋆ ≤ E a p p r o x + E s t a t + E o p t . L(\theta_T)-L^\star\leq E_{\mathrm{approx}}+E_{\mathrm{stat}}+E_{\mathrm{opt}}. L ( θ T ) − L ⋆ ≤ E approx + E stat + E opt .
The approximation term is controlled by Assumption 3.2, the statistical term by uniform convergence over the finite dataset, and the optimization term by the projected empirical proximal-PL stochastic-gradient analysis. While the algebraic decomposition above contains approximation, statistical, and optimization terms, under unbounded data the bound on the statistical term further separates into a truncated uniform-convergence contribution and a tail contribution. Combining this decomposition with uniform flow stability gives
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( E a p p r o x + E s t a t + E o p t ) 1 / 2 . W_2\left(\widehat{\pi}_1^\theta,\pi_1\right) \le K_{\mathrm{flow}}\left(E_{\mathrm{approx}}+E_{\mathrm{stat}}+E_{\mathrm{opt}}\right)^{1/2}. W 2 ( π 1 θ , π 1 ) ≤ K flow ( E approx + E stat + E opt ) 1/2 .
This decomposition follows a general pattern in learning theory: one separates the limitation of the prescribed function class, the error incurred by replacing a population objective with a finite empirical objective, and the error incurred by only approximately optimizing that empirical objective. In large-scale statistical learning, related approximation–estimation–optimization tradeoffs are used to distinguish model-class limitations, finite-sample generalization, and incomplete numerical optimization [4 , 6 ] .
Statistical Control Under Sub-Exponential Data
For R > 0 R > 0 R > 0 , define the endpoint-truncation event
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . \mathcal{E}_R := \{\lVert X_0\rVert_2 \le R,\ \lVert X_1\rVert_2 \le R\}. E R := {∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } .
On E R \mathcal{E}_R E R , the linear path satisfies
∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R . \lVert X_t\rVert_2 \le R,\qquad\lVert X_1-X_0\rVert_2 \le2R. ∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R .
The uniform linear-growth property gives
ℓ θ ( Z ) ≤ B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 \ell_\theta(Z) \le B_\ell(R) := \left(A_{\mathrm{NN}}+\left(B_{\mathrm{NN}}+2\right)R\right)^2 ℓ θ ( Z ) ≤ B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2
on E R \mathcal{E}_R E R . Define the tail contribution by
ϵ t a i l ( R ) : = sup θ ∈ Θ E [ ℓ θ ( Z ) 1 E R c ] . \epsilon_{\mathrm{tail}}(R) := \sup_{\theta\in\Theta}\mathbb{E}\left[\ell_\theta(Z)\mathbf{1}_{\mathcal{E}_R^c}\right]. ϵ tail ( R ) := θ ∈ Θ sup E [ ℓ θ ( Z ) 1 E R c ] .
The linear-growth property implies that there exists a constant C > 0 C > 0 C > 0 such that
ℓ θ ( Z ) ≤ C ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 ) \ell_\theta(Z) \le C\left(1+\lVert X_0\rVert_2^2+\lVert X_1\rVert_2^2\right) ℓ θ ( Z ) ≤ C ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 )
uniformly over θ ∈ Θ \theta\in\Theta θ ∈ Θ . Since
E R c ⊂ { ∥ X 0 ∥ 2 > R } ∪ { ∥ X 1 ∥ 2 > R } , \mathcal{E}_R^c \subset\{\lVert X_0\rVert_2 > R\}\cup\{\lVert X_1\rVert_2 > R\}, E R c ⊂ {∥ X 0 ∥ 2 > R } ∪ {∥ X 1 ∥ 2 > R } ,
the endpoint-tail calculation in Lemma D.6 gives
ϵ t a i l ( R ) ≤ C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . \epsilon_{\mathrm{tail}}(R) \le C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right). ϵ tail ( R ) ≤ C tail ( 1 + R ) 2 exp ( − c tail R / K X ) .
The metric-entropy uniform-convergence result for the truncated squared-loss class gives the statistical contribution
E s t a t ( N , R , δ ) : = C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . E_{\mathrm{stat}}(N,R,\delta) := C_{\mathrm{stat}}B_\ell(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}
+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right). E stat ( N , R , δ ) := C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) .
For every truncation radius satisfying
R ≥ K X c 1 log ( 8 N c 0 δ ) , R \ge\frac{K_X}{c_1}\log\left(\frac{8Nc_0}{\delta}\right), R ≥ c 1 K X log ( δ 8 N c 0 ) ,
with probability at least
over the draw of D N \mathcal{D}_N D N , we have
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ ≤ E s t a t ( N , R , δ ) , 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|\leq E_{\mathrm{stat}}(N,R,\delta), 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) ≤ E stat ( N , R , δ ) ,
where the leading factor 2 from the error decomposition has been absorbed into the constants. Choosing
R ≲ K X log ( N / δ ) R\lesssim K_X\log(N/\delta) R ≲ K X log ( N / δ )
makes the tail contribution lower order up to logarithmic factors. Thus, the finite-dataset statistical contribution scales as
O ~ ( C s m ( R , N ) N ) \widetilde{O}\left(\sqrt{\frac{C_{\mathrm{sm}}(R,N)}{N}}\right) O ( N C sm ( R , N ) )
at the squared-loss level, up to the truncation-dependent envelope and other logarithmic factors.
Optimization Control
Conditioned on the finite dataset D N \mathcal{D}_N D N , the projected stochastic-gradient updates are
θ k + 1 = Π Θ ( θ k − η k g k ) , \theta_{k+1}=\Pi_{\Theta}\left(\theta_k-\eta_k g_k\right), θ k + 1 = Π Θ ( θ k − η k g k ) ,
g k = ∇ θ ℓ θ k ( Z I k ) , k = 0 , 1 , … , T − 1 , g_k=\nabla_{\theta}\ell_{\theta_k}(Z_{I_k}),\qquad k=0,1,\ldots,T-1, g k = ∇ θ ℓ θ k ( Z I k ) , k = 0 , 1 , … , T − 1 ,
where
I k ∼ Uniform { 1 , … , N } . I_k\sim\operatorname{Uniform}\{1,\ldots,N\}. I k ∼ Uniform { 1 , … , N } .
By Lemma 3.5 , θ k ∈ Θ \theta_k\in\Theta θ k ∈ Θ , k = 0 , 1 , … , T k=0,1,\ldots,T k = 0 , 1 , … , T . Because Θ \Theta Θ is convex and L ^ N \widehat{L}_N L N is α N \alpha_N α N -smooth on Θ \Theta Θ , the smoothness descent inequality applies along every update segment.
For the projected recursion, define the stochastic gradient-mapping quantity
G k : = 1 η k ( θ k − Π Θ ( θ k − η k g k ) ) . G_k:=\frac{1}{\eta_k}\left(\theta_k-\Pi_{\Theta}\left(\theta_k-\eta_k g_k\right)\right). G k := η k 1 ( θ k − Π Θ ( θ k − η k g k ) ) .
Under the interior operating regime in Assumption 3.4 , the projection is inactive along the relevant trajectory, so that G k = g k G_k=g_k G k = g k and the resulting one-step recursion agrees with the standard empirical PL-SGD recursion:
e k + 1 ≤ ( 1 − μ N η k ) e k + α N σ N 2 2 η k 2 , e_{k+1}\leq(1-\mu_N\eta_k)e_k+\frac{\alpha_N\sigma_N^2}{2}\eta_k^2, e k + 1 ≤ ( 1 − μ N η k ) e k + 2 α N σ N 2 η k 2 ,
where
e k : = E S G D [ L ^ N ( θ k ) − L ^ N ( θ ^ N ) ∣ D N ] . e_k:=\mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_k)-\widehat{L}_N(\widehat{\theta}_N)\mid\mathcal{D}_N\right]. e k := E SGD [ L N ( θ k ) − L N ( θ N ) ∣ D N ] .
We use a dataset-independent decreasing-stepsize choice based on the uniform constants in Assumption 3.6:
α 0 : = 2 μ min , γ : = α 0 α max , η k : = α 0 k + γ . \alpha_0:=\frac{2}{\mu_{\min}},\qquad\gamma:=\alpha_0\alpha_{\max},\qquad\eta_k:=\frac{\alpha_0}{k+\gamma}. α 0 := μ m i n 2 , γ := α 0 α m a x , η k := k + γ α 0 .
On the event G N \mathcal{G}_N G N , we have
α 0 μ N ≥ α 0 μ min = 2 > 1 , \alpha_0\mu_N\geq\alpha_0\mu_{\min}=2>1, α 0 μ N ≥ α 0 μ m i n = 2 > 1 ,
γ = α 0 α max ≥ α 0 μ N , \gamma=\alpha_0\alpha_{\max}\geq\alpha_0\mu_N, γ = α 0 α m a x ≥ α 0 μ N ,
and
η k ≤ α 0 γ = 1 α max ≤ 1 α N . \eta_k \le\frac{\alpha_0}{\gamma} = \frac{1}{\alpha_{\max}} \le\frac{1}{\alpha_N}. η k ≤ γ α 0 = α m a x 1 ≤ α N 1 .
Thus,
0 ≤ 1 − μ N η k ≤ 1 0 \le1-\mu_N\eta_k \le1 0 ≤ 1 − μ N η k ≤ 1
for every
Lemma 4.8 shows that, conditional on D N \mathcal{D}_N D N , the empirical optimization error satisfies
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C o p t ( D N ) T . \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid\mathcal{D}_N\right]\le\frac{C_{\mathrm{opt}}(\mathcal{D}_N)}{T}. E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt ( D N ) .
where, up to universal numerical constants,
C o p t ( D N ) ≤ max { γ ϵ 0 , α N σ N 2 α 0 2 2 ( α 0 μ N − 1 ) } . C_{\mathrm{opt}}(\mathcal{D}_N)\le\max\left\{\gamma\epsilon_0,\frac{\alpha_N\sigma_N^2\alpha_0^2}{2(\alpha_0\mu_N-1)}\right\}. C opt ( D N ) ≤ max { γ ϵ 0 , 2 ( α 0 μ N − 1 ) α N σ N 2 α 0 2 } .
On the event G N \mathcal{G}_N G N , this quantity is bounded by the deterministic envelope
C ‾ o p t : = max { γ ϵ ‾ 0 , α max σ max 2 α 0 2 2 ( α 0 μ min − 1 ) } . \overline{C}_{\mathrm{opt}}:=\max\left\{\gamma\overline{\epsilon}_0,\frac{\alpha_{\max}\sigma_{\max}^2\alpha_0^2}{2(\alpha_0\mu_{\min}-1)}\right\}. C opt := max { γ ϵ 0 , 2 ( α 0 μ m i n − 1 ) α m a x σ m a x 2 α 0 2 } .
Since
α 0 = 2 μ min , γ = 2 α max μ min , \alpha_0=\frac{2}{\mu_{\min}},\qquad\gamma=\frac{2\alpha_{\max}}{\mu_{\min}}, α 0 = μ m i n 2 , γ = μ m i n 2 α m a x ,
we may equivalently write
C ‾ o p t = max { 2 α max μ min ϵ ‾ 0 , 2 α max σ max 2 μ min 2 } . \overline{C}_{\mathrm{opt}}=\max\left\{\frac{2\alpha_{\max}}{\mu_{\min}}\overline{\epsilon}_0,\frac{2\alpha_{\max}\sigma_{\max}^2}{\mu_{\min}^2}\right\}. C opt = max { μ m i n 2 α m a x ϵ 0 , μ m i n 2 2 α m a x σ m a x 2 } .
Therefore, on G N \mathcal{G}_N G N ,
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C ‾ o p t T . \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid\mathcal{D}_N\right]\le\frac{\overline{C}_{\mathrm{opt}}}{T}. E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt .
The smooth-activation setup makes differentiability and empirical smoothness compatible with bounded parameter finite dataset training. The empirical proximal-PL condition, the uniform-in-N N N regularity condition, and the interior operating regime remain optimization assumptions; they are not implied by smoothness alone. The main theorem uses the conditional expectation guarantee above. A fully high-probability optimization result would require additional martingale-tail assumptions and a separate concentration analysis.
Summary of the Proof Strategy
The preceding subsections identify the ingredients required for the finite-dataset analysis. The approximation condition controls the best achievable population error within the prescribed neural velocity class. The statistical argument controls the discrepancy between the population objective and the fixed empirical objective through endpoint truncation, sub-exponential tail control, and metric-entropy uniform convergence. The projected empirical proximal-PL stochastic-gradient analysis controls the error from running only a finite number of updates on that fixed empirical objective.
More precisely, the error decomposition in § 3.6 separates the excess population flow-matching loss into an approximation contribution, a finite-dataset statistical contribution, and an empirical optimization contribution. The endpoint-tail term arises when bounding the statistical contribution under unbounded source and target distributions. The optimization term is controlled on the uniform regularity event G N \mathcal{G}_N G N from
Assumption 3.6. The deterministic uniform flow-stability constant from Assumption 3.7 then converts the resulting integrated velocity-field error into a Wasserstein-2 bound for the terminal distribution generated by the exact learned ODE.
The formal finite-sample and finite-time guarantee combines the statistical event from Lemma 4.7 with the event G N \mathcal{G}_N G N . Accordingly, its conclusion holds with high probability over the sampled finite dataset and in conditional expectation over the stochastic-gradient randomness. The resulting theorem and sample-complexity consequence are stated in Theorem 4.1 in § 4 .
Theoretical Results
In this section, we state the main finite-sample and finite-time guarantee for flow matching under sub-exponential data and projected finite-dataset stochastic-gradient training. The theorem combines the approximation condition, the metric-entropy statistical bound for the smooth neural velocity class, the empirical projected-optimization bound, and the path-consistent uniform flow-stability argument described in the previous section.
Throughout this section, π ^ 1 θ T \widehat{\pi}^{\theta_T}_1 π 1 θ T denotes the terminal law of the exact learned ODE flow driven by the learned velocity field u θ T u_{\theta_T} u θ T . The dataset size N N N controls the statistical error incurred by replacing the population objective with the empirical objective L ^ N \widehat{L}_N L N , whereas T T T denotes the number of projected stochastic-gradient updates used to approximately minimize that fixed empirical objective.
The learned velocity field
u θ : R d × [ 0 , 1 ] → R d u_\theta:\mathbb{R}^{d} \times[0,1] \to\mathbb{R}^{d} u θ : R d × [ 0 , 1 ] → R d
is parameterized by the bounded-parameter smooth-activation network class described in § 3.2 . The network has depth D D D , hidden width W W W , and parameter count
P = W ( d + 1 ) + W + ( D − 2 ) ( W 2 + W ) + d W + d . P = W(d+1) + W + (D-2)(W^2+W) + dW + d. P = W ( d + 1 ) + W + ( D − 2 ) ( W 2 + W ) + d W + d .
Thus,
P = O ( D W 2 + d W ) . P = O(DW^2+dW). P = O ( D W 2 + d W ) .
For R > 0 R>0 R > 0 , define the endpoint-truncation event
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . \mathcal{E}_R := \{\lVert X_0\rVert_2 \le R,\ \lVert X_1\rVert_2 \le R\}. E R := {∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } .
On this event, the single-sample flow-matching loss is bounded by
B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 , B_{\ell}(R) := \left(A_{\mathrm{NN}}+(B_{\mathrm{NN}}+2)R\right)^2, B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2 ,
where A N N A_{\mathrm{NN}} A NN , B N N B_{\mathrm{NN}} B NN are the constants from the uniform linear-growth property of the bounded-parameter smooth neural velocity class.
Recall that
max { e , B ℓ ( R ) } ≤ C s m ( R ) < ∞ \max\{e,B_{\ell}(R)\} \le C_{\mathrm{sm}}(R) < \infty max { e , B ℓ ( R )} ≤ C sm ( R ) < ∞
denotes the raw metric-entropy radius of the truncated squared-loss class. Define the corresponding N N N -dependent entropy radius by
C ‾ s m ( R , N ) : = e N C s m ( R ) B ℓ ( R ) . \overline{C}_{\mathrm{sm}}(R,N) := e^{\frac{N C_{\mathrm{sm}}(R)}{B_{\ell}(R)}}. C sm ( R , N ) := e B ℓ ( R ) N C sm ( R ) .
Since
C s m ( R ) ≥ B ℓ ( R ) , C_{\mathrm{sm}}(R) \ge B_{\ell}(R), C sm ( R ) ≥ B ℓ ( R ) ,
we have
C ‾ s m ( R , N ) ≥ e . \overline{C}_{\mathrm{sm}}(R,N) \ge e. C sm ( R , N ) ≥ e .
The associated smooth-network complexity quantity is
C s m ( R , N ) : = P log ( C ‾ s m ( R , N ) ) . C_{\mathrm{sm}}(R,N) := P\log\left(\overline{C}_{\mathrm{sm}}(R,N)\right). C sm ( R , N ) := P log ( C sm ( R , N ) ) .
This is the complexity quantity appearing in the theorem and in Lemma D.5 . Under Assumption 3.7 , the quantity K f l o w = exp ( Λ f l o w ) K_{\mathrm{flow}}=\exp(\Lambda_{\mathrm{flow}}) K flow = exp ( Λ flow ) is a deterministic uniform flow-stability constant satisfying
sup θ ∈ Θ ∫ 0 1 L θ ( t ) d t ≤ Λ f l o w . \sup_{\theta\in\Theta}\int_{0}^{1}L_{\theta}(t)\,\mathrm{d}t\le\Lambda_{\mathrm{flow}}. θ ∈ Θ sup ∫ 0 1 L θ ( t ) d t ≤ Λ flow .
By Lemma 3.5 , projected SGD guarantees that every optimization iterate, including the final learned parameter θ T \theta_T θ T , belongs to Θ \Theta Θ . Hence the same deterministic flow-stability constant applies to every iterate and to the final learned velocity field.
Theorem 4.1 (Finite-sample and finite-time guarantee for flow matching). Suppose Assumptions 3.1, 3.2, 3.3 , 3.4 , 3.6, and 3.7 hold. Suppose that the velocity field u θ u_\theta u θ is parameterized by the bounded-parameter smooth-activation network class described in § 3.2 .
Let θ T \theta_T θ T be the output of the projected finite-dataset stochastic-gradient recursion in Assumption 3.4 , with the decreasing stepsizes
α 0 : = 2 μ min , γ : = α 0 α max , η k : = α 0 k + γ . \alpha_0:=\frac{2}{\mu_{\min}},\qquad\gamma:=\alpha_0\alpha_{\max},\qquad\eta_k:=\frac{\alpha_0}{k+\gamma}. α 0 := μ m i n 2 , γ := α 0 α m a x , η k := k + γ α 0 . For δ , δ o p t ∈ ( 0 , 1 ) \delta,\delta_{\mathrm{opt}}\in(0,1) δ , δ opt ∈ ( 0 , 1 ) and any truncation radius satisfying
R ≥ K X c 1 log ( 8 N c 0 δ ) , R\ge\frac{K_X}{c_1}\log\left(\frac{8Nc_0}{\delta}\right), R ≥ c 1 K X log ( δ 8 N c 0 ) , define
E N , T ( R , δ ) : = ϵ a p p r o x + C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) + C o p t T . \mathcal{E}_{N,T}(R,\delta):=\epsilon_{\mathrm{approx}}+C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}
+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right)+\frac{C_{\mathrm{opt}}}{T}. E N , T ( R , δ ) := ϵ approx + C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) + T C opt . Then, with probability at least
1 − δ − δ o p t 1-\delta-\delta_{\mathrm{opt}} 1 − δ − δ opt over the draw of the finite dataset
the following conditional expected excess-risk bound holds:
E S G D [ L ( θ T ) − L ⋆ ∣ D N ] ≤ E N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[L(\theta_T)-L^\star\mid D_N\right]\le\mathcal{E}_{N,T}(R,\delta). E SGD [ L ( θ T ) − L ⋆ ∣ D N ] ≤ E N , T ( R , δ ) . Equivalently, by the projection identity,
E S G D [ E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ∣ D N ] ] ≤ E N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[\mathbb{E}\left[\left\|u_{\theta_T}(X_t,t)-u^\star(X_t,t)\right\|_2^2\mid D_N\right]\right]\le\mathcal{E}_{N,T}(R,\delta). E SGD [ E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ∣ D N ] ] ≤ E N , T ( R , δ ) .
Consequently, the terminal distribution of the exact learned ODE flow satisfies
E S G D [ W 2 2 ( π ^ 1 θ T , π 1 ) | D N ] ≤ K f l o w 2 E N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[W_2^2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\middle|D_N\right]\le K_{\mathrm{flow}}^2\mathcal{E}_{N,T}(R,\delta). E SGD [ W 2 2 ( π 1 θ T , π 1 ) D N ] ≤ K flow 2 E N , T ( R , δ ) .
By Jensen’s inequality,
E S G D [ W 2 ( π ^ 1 θ T , π 1 ) | D N ] ≤ K f l o w E N , T ( R , δ ) 1 / 2 . \mathbb{E}_{\mathrm{SGD}}\left[W_2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\middle|D_N\right]\le K_{\mathrm{flow}}\mathcal{E}_{N,T}(R,\delta)^{1/2}. E SGD [ W 2 ( π 1 θ T , π 1 ) D N ] ≤ K flow E N , T ( R , δ ) 1/2 .
Remark 4.2 (Exact learned flow versus numerical sampling). Theorem 4.1 is stated for the exact learned ODE flow. This matches the main theoretical focus of the paper: controlling the finite-dataset statistical and finite-time optimization errors incurred in learning the velocity field. If the learned ODE is solved numerically in implementation, a separate solver error can be added by the triangle inequality. We do not include this numerical term in the main sample-complexity statement.
Remark 4.3 (Sample-complexity consequence). Choose
R = c R K X log ( N / δ ) , R=c_RK_X\log(N/\delta), R = c R K X log ( N / δ ) ,
where c R > 0 c_R>0 c R > 0 is sufficiently large that the truncation condition in Theorem 4.1 holds and the tail contribution C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) C_{\mathrm{tail}}(1+R)^2\exp(-c_{\mathrm{tail}}R/K_X) C tail ( 1 + R ) 2 exp ( − c tail R / K X ) is lower order up to logarithmic factors. Suppose that the approximation and tail contributions satisfy
ϵ a p p r o x + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) ≤ ϵ 2 2 K f l o w 2 . \epsilon_{\mathrm{approx}}+C_{\mathrm{tail}}(1+R)^2\exp(-c_{\mathrm{tail}}R/K_X)\le\frac{\epsilon^2}{2K_{\mathrm{flow}}^2}. ϵ approx + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) ≤ 2 K flow 2 ϵ 2 .
For example, it is sufficient to require
ϵ a p p r o x ≤ ϵ 2 4 K f l o w 2 \epsilon_{\mathrm{approx}}\le\frac{\epsilon^2}{4K_{\mathrm{flow}}^2} ϵ approx ≤ 4 K flow 2 ϵ 2
and to choose R R R sufficiently large that the tail term is at most ϵ 2 4 K f l o w 2 \frac{\epsilon^2}{4K_{\mathrm{flow}}^2} 4 K flow 2 ϵ 2 . Then a sufficient dataset-size condition for
E S G D [ W 2 ( π ^ 1 θ T , π 1 ) | D N ] ≤ O ( ϵ ) \mathbb{E}_{\mathrm{SGD}}\left[W_2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\middle|D_N\right]\le O(\epsilon) E SGD [ W 2 ( π 1 θ T , π 1 ) D N ] ≤ O ( ϵ )
on the event in Theorem 4.1 is
N ≥ C K f l o w 4 B ℓ ( R ) 2 ( C s m ( R , N ) + log ( 1 / δ ) ) ϵ 4 , N\ge C\frac{K_{\mathrm{flow}}^4B_\ell(R)^2\left(C_{\mathrm{sm}}(R,N)+\log(1/\delta)\right)}{\epsilon^4}, N ≥ C ϵ 4 K flow 4 B ℓ ( R ) 2 ( C sm ( R , N ) + log ( 1/ δ ) ) ,
for a sufficiently large constant C > 0 C>0 C > 0 . A sufficient optimization-budget condition is T ≥ C K f l o w 2 C ‾ o p t ϵ 2 T\ge C\frac{K_{\mathrm{flow}}^2\overline{C}_{\mathrm{opt}}}{\epsilon^2} T ≥ C ϵ 2 K flow 2 C opt , for a sufficiently large constant C > 0 C>0 C > 0 .
Because the truncation radius R R R and the entropy quantity C s m ( R , N ) C_{\mathrm{sm}}(R,N) C sm ( R , N ) depend logarithmically on N N N , the preceding display is an implicit sufficient condition on the dataset size.
The optimization requirement is deterministic conditional on the displayed uniform constants in Assumption 3.6. In particular, C ‾ o p t \overline{C}_{\mathrm{opt}} C opt does not depend on the realized dataset once μ min \mu_{\min} μ m i n , α max \alpha_{\max} α m a x , σ max 2 \sigma_{\max}^2 σ m a x 2 , e ‾ 0 \overline{e}_0 e 0 have been fixed.
When the approximation, tail, flow-stability, smooth-network-complexity, and uniform empirical-optimization quantities are treated as fixed or displayed separately, the shorthand scaling is N = O ~ ( ϵ − 4 ) N=\widetilde{O}(\epsilon^{-4}) N = O ( ϵ − 4 ) , T = O ~ ( ϵ − 2 ) T=\widetilde{O}(\epsilon^{-2}) T = O ( ϵ − 2 ) .
Remark 4.4 (Status of the displayed constants). The bound is stated modularly. The quantities ϵ a p p r o x \epsilon_{\mathrm{approx}} ϵ approx , K f l o w = exp ( Λ f l o w ) K_{\mathrm{flow}}=\exp(\Lambda_{\mathrm{flow}}) K flow = exp ( Λ flow ) , and the uniform empirical constants μ min \mu_{\min} μ m i n , α max \alpha_{\max} α m a x , σ max 2 \sigma_{\max}^2 σ m a x 2 , e ‾ 0 \overline{e}_0 e 0 , which enter through C ‾ o p t \overline{C}_{\mathrm{opt}} C opt , are displayed problem-dependent constants and are not derived in this work.
In particular, ϵ a p p r o x \epsilon_{\mathrm{approx}} ϵ approx is not claimed to vanish for an arbitrary fixed architecture. The factor K f l o w K_{\mathrm{flow}} K flow is a deterministic class-level amplification factor in the terminal Wasserstein bound; it is not claimed to be dimension free or uniformly bounded over arbitrary neural architectures or parameter balls. Finally, the shorthand optimization scaling T = O ~ ( ϵ − 2 ) T = \widetilde{O}\left(\epsilon^{-2}\right) T = O ( ϵ − 2 ) is conditional on the uniform lower bound μ N ≥ μ min \mu_N \ge\mu_{\min} μ N ≥ μ m i n and the other uniform empirical-constant bounds in Assumption 3.6.
The contribution of the theorem is an explicit reduction of terminal Wasserstein-2 error to these displayed approximation, statistical, optimization, and flow-stability quantities.
Remark 4.5 (High-probability optimization variant). Theorem 4.1 uses the optimization guarantee implied by the bounded conditional-variance assumption in Assumption 3.4 . Accordingly, its conclusion holds with high probability over the finite dataset and in conditional expectation over the stochastic-gradient randomness.
A fully high-probability optimization guarantee would require additional explicit assumptions on the stochastic gradient noise, together with a separate martingale-concentration analysis of the resulting recursion. For example, one could impose a conditional Bernstein-type or conditionally sub-Gaussian martingale-difference assumption. We do not require such a strengthening here and therefore do not state a high-probability optimization rate in the main result.
The proof of Theorem 4.1 follows by combining the next three lemmas.
Lemma 4.6 (Approximation error). Under Assumption 3.2,
L ( θ Θ ⋆ ) − L ⋆ ≤ ϵ a p p r o x . L(\theta_{\Theta}^{\star}) - L^{\star} \le\epsilon_{\mathrm{approx}}. L ( θ Θ ⋆ ) − L ⋆ ≤ ϵ approx . Proof. This is exactly Assumption 3.2. By the projection identity,
L ( θ Θ ⋆ ) − L ⋆ = E [ ∥ u θ Θ ⋆ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . L(\theta_{\Theta}^{\star}) - L^{\star} = \mathbb{E}\left[\left\|u_{\theta_{\Theta}^{\star}}(X_t,t)-u^{\star}(X_t,t)\right\|_2^2\right]. L ( θ Θ ⋆ ) − L ⋆ = E [ u θ Θ ⋆ ( X t , t ) − u ⋆ ( X t , t ) 2 2 ] . Therefore,
L ( θ Θ ⋆ ) − L ⋆ ≤ ϵ a p p r o x . L(\theta_{\Theta}^{\star}) - L^{\star} \le\epsilon_{\mathrm{approx}}. L ( θ Θ ⋆ ) − L ⋆ ≤ ϵ approx .
Lemma 4.7 (Statistical error under sub-exponential data). Suppose Assumption 3.1 holds, and suppose the bounded-parameter smooth neural velocity class has the uniform linear-growth and metric-entropy properties stated in § 3.2 . For R > 0 R>0 R > 0 , define
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } , \mathcal{E}_R := \left\{\|X_0\|_2 \le R,\ \|X_1\|_2 \le R\right\}, E R := { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } , and
B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 . B_{\ell}(R) := \left(A_{\mathrm{NN}}+\left(B_{\mathrm{NN}}+2\right)R\right)^2. B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2 . If
R ≥ K X c 1 log ( 8 N c 0 δ ) , R \ge\frac{K_X}{c_1}\log\left(\frac{8Nc_0}{\delta}\right), R ≥ c 1 K X log ( δ 8 N c 0 ) , then, with probability at least 1 − δ 1-\delta 1 − δ over the draw of D N \mathcal{D}_N D N , we have
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ ≤ C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|
\le C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}
+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right). 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) ≤ C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) . Choosing R = c R K X log ( N / δ ) R=c_RK_X\log(N/\delta) R = c R K X log ( N / δ ) with sufficiently large c R > 0 c_R>0 c R > 0 makes the tail contribution lower order up to logarithmic factors. Thus,
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ = O ~ ( B ℓ ( R ) C s m ( R , N ) + log ( 1 / δ ) N ) , 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|
=\widetilde{O}\left(B_{\ell}(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(1/\delta)}{N}}\right), 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) = O ( B ℓ ( R ) N C sm ( R , N ) + log ( 1/ δ ) ) , up to logarithmic factors arising from the truncation radius and smooth-network entropy radius.
The proof of Lemma 4.7 is given in Appendix § 6 . The proof uses endpoint truncation, sub-exponential tail control, and the metric-entropy/Rademacher uniform-convergence bound for the smooth-network truncated squared-loss class.
Lemma 4.8 (Empirical optimization error). Let
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N \in\arg\min_{\theta\in\Theta} \widehat{L}_N(\theta) θ N ∈ arg θ ∈ Θ min L N ( θ ) be an empirical risk minimizer. Let θ T \theta_T θ T be obtained after T T T projected stochastic-gradient updates on the fixed finite empirical objective:
θ k + 1 = Π Θ ( θ k − η k g k ) , \theta_{k+1} = \Pi_{\Theta}\left(\theta_k-\eta_k g_k\right), θ k + 1 = Π Θ ( θ k − η k g k ) , g k = ∇ θ ℓ θ k ( Z I k ) , I k ∼ Uniform { 1 , … , N } . g_k = \nabla_{\theta}\ell_{\theta_k}(Z_{I_k}), \qquad I_k \sim\operatorname{Uniform}\{1,\ldots,N\}. g k = ∇ θ ℓ θ k ( Z I k ) , I k ∼ Uniform { 1 , … , N } . Suppose Assumptions 3.3 3.3 3.3 , 3.4 3.4 3.4 , and 3.6 3.6 3.6 hold. In particular, the projected recursion guarantees θ k ∈ Θ \theta_k \in\Theta θ k ∈ Θ , k = 0 , 1 , … , T k=0,1,\ldots,T k = 0 , 1 , … , T , by Lemma 3.5 , and the clean recursion below uses the interior operating regime in Assumption 3.4 3.4 3.4 . On the event G N G_N G N , choose
α 0 : = 2 μ min , γ : = α 0 α max , η k : = α 0 k + γ . \alpha_0 := \frac{2}{\mu_{\min}}, \qquad\gamma:= \alpha_0\alpha_{\max}, \qquad\eta_k := \frac{\alpha_0}{k+\gamma}. α 0 := μ m i n 2 , γ := α 0 α m a x , η k := k + γ α 0 . Then α 0 μ N > 1 \alpha_0\mu_N > 1 α 0 μ N > 1 , γ ≥ α 0 μ N \gamma\ge\alpha_0\mu_N γ ≥ α 0 μ N , η k ≤ 1 α N \eta_k \le\frac{1}{\alpha_N} η k ≤ α N 1 for every k ≥ 0 k \ge0 k ≥ 0 .
Define e 0 : = L ^ N ( θ 0 ) − L ^ N ( θ ^ N ) e_0 := \widehat{L}_N(\theta_0)-\widehat{L}_N(\widehat{\theta}_N) e 0 := L N ( θ 0 ) − L N ( θ N ) . Then, conditional on D N D_N D N , the empirical optimization error satisfies
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C o p t ( D N ) T , \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid D_N\right] \le\frac{C_{\mathrm{opt}}(D_N)}{T}, E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt ( D N ) , where the bound follows from
e T ≤ C o p t ( D N ) T + γ ≤ C o p t ( D N ) T , T ≥ 1 e_T \le\frac{C_{\mathrm{opt}}(D_N)}{T+\gamma} \le\frac{C_{\mathrm{opt}}(D_N)}{T}, \qquad T \ge1 e T ≤ T + γ C opt ( D N ) ≤ T C opt ( D N ) , T ≥ 1 Moreover, on G N G_N G N , C o p t ( D N ) ≤ C ‾ o p t C_{\mathrm{opt}}(D_N) \le\overline{C}_{\mathrm{opt}} C opt ( D N ) ≤ C opt , and hence
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C ‾ o p t T . \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid D_N\right] \le\frac{\overline{C}_{\mathrm{opt}}}{T}. E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt .
The proof of Lemma 4.8 is given in Appendix § 7 . The proof uses the stochastic gradient mapping associated with the projected update and the empirical proximal-PL condition. Under the interior operating regime, the projection is inactive along the relevant stochastic and mean-gradient steps, and the resulting recursion reduces to
e k + 1 ≤ ( 1 − μ N η k ) e k + α N σ N 2 2 η k 2 , e_{k+1} \le(1-\mu_N\eta_k)e_k+\frac{\alpha_N\sigma_N^2}{2}\eta_k^2, e k + 1 ≤ ( 1 − μ N η k ) e k + 2 α N σ N 2 η k 2 ,
where
e k : = E S G D [ L ^ N ( θ k ) − L ^ N ( θ ^ N ) ∣ D N ] . e_k := \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_k)-\widehat{L}_N(\widehat{\theta}_N)\mid D_N\right]. e k := E SGD [ L N ( θ k ) − L N ( θ N ) ∣ D N ] .
This is the same form as the unconstrained empirical PL-SGD recursion, but its validity here follows from the projected update, automatic containment, and the interior operating regime.
Proof sketch of Theorem 4.1. Let H N , R , δ \mathcal{H}_{N,R,\delta} H N , R , δ denote the event supplied by Lemma 4.7 . By that lemma, P ( H N , R , δ ) ≥ 1 − δ \mathbb{P}(\mathcal{H}_{N,R,\delta}) \ge1-\delta P ( H N , R , δ ) ≥ 1 − δ . By Assumption 3.6 3.6 3.6 , P ( G N ) ≥ 1 − δ o p t \mathbb{P}(G_N) \ge1-\delta_{\mathrm{opt}} P ( G N ) ≥ 1 − δ opt . Hence, by the union bound, P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ o p t \mathbb{P}(\mathcal{H}_{N,R,\delta}\cap G_N) \ge1-\delta-\delta_{\mathrm{opt}} P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ opt . Fix a dataset realization in H N , R , δ ∩ G N \mathcal{H}_{N,R,\delta} \cap\mathcal{G}_N H N , R , δ ∩ G N . The error decomposition gives
L ( θ T ) − L ⋆ ≤ L ( θ Θ ⋆ ) − L ⋆ + 2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ + L ^ N ( θ T ) − L ^ N ( θ ^ N ) . L(\theta_T) - L^\star\leq L(\theta^\star_{\Theta}) - L^\star+ 2 \sup_{\theta\in\Theta} \left|L(\theta) - \widehat{L}_N(\theta)\right| + \widehat{L}_N(\theta_T) - \widehat{L}_N(\widehat{\theta}_N). L ( θ T ) − L ⋆ ≤ L ( θ Θ ⋆ ) − L ⋆ + 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) + L N ( θ T ) − L N ( θ N ) .
The first term is bounded by Lemma 4.6, the second by Lemma 4.7, and the third in conditional expectation by Lemma 4.8. Taking conditional expectation with respect to the stochastic-gradient randomness yields
E S G D [ L ( θ T ) − L ⋆ ∣ D N ] ≤ E N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[L(\theta_T) - L^\star\mid D_N\right] \leq\mathcal{E}_{N,T}(R,\delta). E SGD [ L ( θ T ) − L ⋆ ∣ D N ] ≤ E N , T ( R , δ ) .
By Lemma 3.5, θ T ∈ Θ \theta_T \in\Theta θ T ∈ Θ . The deterministic uniform stability inequality from Lemma D.7 may therefore be applied pointwise to θ T \theta_T θ T . Taking conditional expectation and using Jensen’s inequality gives the stated Wasserstein guarantees. The full proof is given in Appendix C. □
Remark 4.9 (Pure population-oracle version). For comparison, suppose instead that the optimization algorithm has access to a population stochastic-gradient oracle and that the corresponding population objective satisfies suitable population proximal-PL, smoothness, and stochastic-gradient conditions. The finite-dataset statistical term is then absent. Under those distinct assumptions, the corresponding flow-stability argument gives
E [ W 2 ( π ^ 1 θ T , π 1 ) ] ≤ K f l o w ( ϵ a p p r o x + C o p t , p o p T ) 1 / 2 , \mathbb{E}\left[W_2\left(\widehat{\pi}^{\theta_T}_1,\pi_1\right)\right] \leq K_{\mathrm{flow}}\left(\epsilon_{\mathrm{approx}} + \frac{C_{\mathrm{opt,pop}}}{T}\right)^{1/2}, E [ W 2 ( π 1 θ T , π 1 ) ] ≤ K flow ( ϵ approx + T C opt , pop ) 1/2 ,
where C o p t , p o p C_{\mathrm{opt,pop}} C opt , pop is the optimization constant associated with the distinct population-oracle assumptions. This comparison highlights that the O ~ ( ϵ − 4 ) \widetilde{O}\left(\epsilon^{-4}\right) O ( ϵ − 4 ) dataset-size scaling in the finite-dataset result arises from the O ~ ( N − 1 / 2 ) \widetilde{O}\left(N^{-1/2}\right) O ( N − 1/2 ) statistical contribution at the squared-loss level.
Remark 4.10 (Dependence on dimension and architecture). The theorem should be interpreted for a prescribed bounded-parameter smooth neural velocity class. The ambient dimension enters through the parameter count P = O ( D W 2 + d W ) P = O(DW^2 + dW) P = O ( D W 2 + d W ) , the smooth-network metric-entropy complexity C s m ( R , N ) C_{\mathrm{sm}}(R,N) C sm ( R , N ) , the truncation envelope B ℓ ( R ) B_{\ell}(R) B ℓ ( R ) , the tail and truncation constants, the flow-stability factor K f l o w K_{\mathrm{flow}} K flow , the approximation error ϵ a p p r o x \epsilon_{\mathrm{approx}} ϵ approx , and the uniform empirical optimization quantity C ‾ o p t \overline{C}_{\mathrm{opt}} C opt .
Conclusion
We developed a finite-sample and finite-time analysis of flow matching when the velocity field is learned by stochastic-gradient training on a fixed empirical objective. Rather than assuming that the learning algorithm can access an exact empirical risk minimizer, we analyze the parameter obtained after a finite number of stochastic-gradient updates on a finite stored dataset.
At the population-loss level, the analysis uses a three-term algebraic decomposition. The excess flow-matching loss is bounded by an approximation contribution associated with the prescribed bounded-parameter smooth neural velocity class, a finite-dataset statistical contribution arising from replacing the population objective with its empirical counterpart, and an empirical optimization contribution arising from approximate minimization of the fixed empirical objective. The empirical minimizer appears only as a theoretical comparator and is not assumed to be available to the learning algorithm.
Because the source and target distributions are allowed to be unbounded, the statistical contribution is controlled through endpoint-magnitude truncation. More specifically, its bound consists of a truncated metric-entropy or Rademacher uniform-convergence term together with an explicit endpoint-tail remainder under the sub exponential endpoint assumption. Consequently, the final theorem displays approximation, finite-dataset statistical, endpoint tail, and empirical optimization contributions separately, while the tail term arises as part of the control of the statistical component.
Combining these ingredients with the path-consistent uniform flow-stability condition yields a Wasserstein-2 guarantee for the terminal law of the exact learned ODE flow. The guarantee holds with high probability over the sampled finite dataset and in conditional expectation over the stochastic-gradient randomness. It makes explicit that the dataset size N N N controls the finite-dataset statistical contribution, whereas the optimization budget T T T controls the finite-time empirical optimization contribution.
For a prescribed bounded-parameter smooth neural velocity class, and after displaying the approximation, tail, flow stability, smooth-network-complexity, and empirical-optimization quantities, the result yields the shorthand requirements
N = O ~ ( ϵ − 4 ) , T = O ~ ( ϵ − 2 ) N = \widetilde{O}\left(\epsilon^{-4}\right), \qquad T = \widetilde{O}\left(\epsilon^{-2}\right) N = O ( ϵ − 4 ) , T = O ( ϵ − 2 )
for obtaining Wasserstein-2 error of order O ( ϵ ) O(\epsilon) O ( ϵ ) . These rates should be interpreted only under the stated assumptions. In particular, the ambient dimension and network architecture enter through the parameterization of the neural class, the metric-entropy quantity, the truncation envelope, the approximation error, the flow-stability factor, and the empirical optimization constant. We do not claim dimension-free approximation or dimension-free flow-stability guarantees.
Several directions remain open. First, deriving explicit approximation results for marginal velocity fields under structural assumptions on the target distribution would clarify the dependence on dimension, regularity, and network size. Second, replacing the empirical proximal Polyak–Łojasiewicz condition, the interior operating regime, and the uniform-in-N N N empirical-constant regularity condition with weaker or more directly verifiable optimization requirements would broaden the scope of the result. Third, additional martingale-tail assumptions could support a fully high-probability optimization analysis jointly over the dataset and stochastic-gradient randomness. Fourth, incorporating numerical ODE solver error into the main theorem would yield an end-to-end guarantee for practical sampling. Finally, extending the analysis beyond linear or rectified interpolation paths to more general conditional flow-matching, optimal-transport, and stochastic-interpolant constructions remains an important direction for future work.
Proof of Lemma 4.7
Proof. Let
Z = ( X 0 , X 1 , t ) , ( X 0 , X 1 ) ∼ Γ , t ∼ Uniform [ 0 , 1 ] . Z = (X_0, X_1, t), \qquad(X_0, X_1) \sim\Gamma, \qquad t \sim\operatorname{Uniform}[0,1]. Z = ( X 0 , X 1 , t ) , ( X 0 , X 1 ) ∼ Γ , t ∼ Uniform [ 0 , 1 ] .
For the linear interpolation path,
X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 . X_t = (1-t)X_0 + tX_1, \qquad\dot{X}_t = X_1-X_0. X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 .
For every θ ∈ Θ \theta\in\Theta θ ∈ Θ , define the single-sample flow-matching loss
g θ ( Z ) : = ℓ θ ( Z ) ≡ ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 . g_\theta(Z) := \ell_\theta(Z) \equiv\lVert u_\theta((1-t)X_0+tX_1,t) - (X_1-X_0)\rVert_2^2. g θ ( Z ) := ℓ θ ( Z ) ≡ ∥ u θ (( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 .
Thus,
L ( θ ) = E [ g θ ( Z ) ] , L ^ N ( θ ) = 1 N ∑ i = 1 N g θ ( Z i ) , L(\theta) = \mathbb{E}[g_\theta(Z)], \qquad\widehat{L}_N(\theta) = \frac{1}{N}\sum_{i=1}^{N}g_\theta(Z_i), L ( θ ) = E [ g θ ( Z )] , L N ( θ ) = N 1 i = 1 ∑ N g θ ( Z i ) ,
where
D N = { Z i } i = 1 N \mathcal{D}_N = \{Z_i\}_{i=1}^{N} D N = { Z i } i = 1 N
consists of independent copies of Z Z Z . We seek a high-probability bound on
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ . 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|. 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) .
The source and target distributions are not assumed to be compactly supported, so the loss need not be uniformly bounded on the full sample space. We therefore use endpoint truncation. For R > 0 R>0 R > 0 , define the endpoint-truncation event
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . \mathcal{E}_R := \{\lVert X_0\rVert_2 \le R,\ \lVert X_1\rVert_2 \le R\}. E R := {∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } .
For the i i i -th sample, write
E R , i : = { ∥ X 0 , i ∥ 2 ≤ R , ∥ X 1 , i ∥ 2 ≤ R } . \mathcal{E}_{R,i} := \{\lVert X_{0,i}\rVert_2 \le R,\ \lVert X_{1,i}\rVert_2 \le R\}. E R , i := {∥ X 0 , i ∥ 2 ≤ R , ∥ X 1 , i ∥ 2 ≤ R } .
On E R \mathcal{E}_R E R , the linear path satisfies
∥ X t ∥ 2 = ∥ ( 1 − t ) X 0 + t X 1 ∥ 2 ≤ ( 1 − t ) ∥ X 0 ∥ 2 + t ∥ X 1 ∥ 2 ≤ R , \begin{aligned}
\lVert X_t\rVert_2 &= \lVert(1-t)X_0+tX_1\rVert_2 \\
&\le(1-t)\lVert X_0\rVert_2+t\lVert X_1\rVert_2 \\
&\le R,
\end{aligned} ∥ X t ∥ 2 = ∥( 1 − t ) X 0 + t X 1 ∥ 2 ≤ ( 1 − t ) ∥ X 0 ∥ 2 + t ∥ X 1 ∥ 2 ≤ R ,
and
∥ X 1 − X 0 ∥ 2 ≤ ∥ X 1 ∥ 2 + ∥ X 0 ∥ 2 ≤ 2 R . \lVert X_1-X_0\rVert_2 \le\lVert X_1\rVert_2+\lVert X_0\rVert_2 \le2R. ∥ X 1 − X 0 ∥ 2 ≤ ∥ X 1 ∥ 2 + ∥ X 0 ∥ 2 ≤ 2 R .
By the uniform linear-growth property of the bounded-parameter smooth neural velocity class from Lemma D.3 , there exist constants
A N N , B N N > 0 A_{\mathrm{NN}}, B_{\mathrm{NN}} > 0 A NN , B NN > 0
such that
∥ u θ ( x , t ) ∥ 2 ≤ A N N + B N N ∥ x ∥ 2 \lVert u_\theta(x,t)\rVert_2 \le A_{\mathrm{NN}}+B_{\mathrm{NN}}\lVert x\rVert_2 ∥ u θ ( x , t ) ∥ 2 ≤ A NN + B NN ∥ x ∥ 2
for every
θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] . \theta\in\Theta,\qquad x\in\mathbb{R}^d,\qquad t\in[0,1]. θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] .
Hence, on E R \mathcal{E}_R E R ,
∥ u θ ( X t , t ) ∥ 2 ≤ A N N + B N N R . \lVert u_\theta(X_t,t)\rVert_2 \le A_{\mathrm{NN}}+B_{\mathrm{NN}}R. ∥ u θ ( X t , t ) ∥ 2 ≤ A NN + B NN R .
Therefore,
g θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ ( A N N + ( B N N + 2 ) R ) 2 . g_\theta(Z)=\lVert u_\theta(X_t,t)-(X_1-X_0)\rVert_2^2\leq(A_{\mathrm{NN}}+(B_{\mathrm{NN}}+2)R)^2. g θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ ( A NN + ( B NN + 2 ) R ) 2 .
Define the truncated-loss envelope
B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 . B_\ell(R):=(A_{\mathrm{NN}}+(B_{\mathrm{NN}}+2)R)^2. B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2 .
Define the truncated loss
g θ , R ( Z ) : = g θ ( Z ) 1 E R , g_{\theta,R}(Z):=g_\theta(Z)\mathbf{1}_{\mathcal{E}_R}, g θ , R ( Z ) := g θ ( Z ) 1 E R ,
and the truncated squared-loss class
G W , D ( R ) : = { Z ↦ g θ , R ( Z ) : θ ∈ Θ } . \mathcal{G}^{(R)}_{W,D}:=\{Z\mapsto g_{\theta,R}(Z):\theta\in\Theta\}. G W , D ( R ) := { Z ↦ g θ , R ( Z ) : θ ∈ Θ } .
Every function in G W , D ( R ) \mathcal{G}^{(R)}_{W,D} G W , D ( R ) takes values in [ 0 , B ℓ ( R ) ] [0,B_\ell(R)] [ 0 , B ℓ ( R )] . Recall that C s m ( R ) C_{\mathrm{sm}}(R) C sm ( R ) is the raw metric-entropy radius of this class. Let us define define
C s m ( R , N ) : = P log ( C ‾ s m ( R , N ) ) . C_{\mathrm{sm}}(R,N):=P\log\left(\overline{C}_{\mathrm{sm}}(R,N)\right). C sm ( R , N ) := P log ( C sm ( R , N ) ) .
By the metric-entropy/Rademacher uniform-convergence result in Lemma D.5 , there exists a constant C u c > 0 C_{\mathrm{uc}}>0 C uc > 0 such that, for every
δ u c ∈ ( 0 , 1 ) , \delta_{\mathrm{uc}}\in(0,1), δ uc ∈ ( 0 , 1 ) ,
with probability at least
1 − δ u c , 1-\delta_{\mathrm{uc}}, 1 − δ uc ,
sup θ ∈ Θ ∣ E [ g θ , R ( Z ) ] − 1 N ∑ i = 1 N g θ , R ( Z i ) ∣ ≤ C u c B ℓ ( R ) C s m ( R , N ) + log ( 1 / δ u c ) N . \sup_{\theta\in\Theta}\left|\mathbb{E}[g_{\theta,R}(Z)]-\frac{1}{N}\sum_{i=1}^{N}g_{\theta,R}(Z_i)\right|\leq C_{\mathrm{uc}}B_\ell(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(1/\delta_{\mathrm{uc}})}{N}}. θ ∈ Θ sup E [ g θ , R ( Z )] − N 1 i = 1 ∑ N g θ , R ( Z i ) ≤ C uc B ℓ ( R ) N C sm ( R , N ) + log ( 1/ δ uc ) .
Set δ u c : = 3 δ 4 \delta_{\mathrm{uc}}:=\frac{3\delta}{4} δ uc := 4 3 δ . Since
log ( 1 δ u c ) = log ( 4 3 δ ) ≤ log ( 4 δ ) , \log\left(\frac{1}{\delta_{\mathrm{uc}}}\right)=\log\left(\frac{4}{3\delta}\right)\leq\log\left(\frac{4}{\delta}\right), log ( δ uc 1 ) = log ( 3 δ 4 ) ≤ log ( δ 4 ) ,
it follows that, with probability at least 1 − 3 δ 4 1-\frac{3\delta}{4} 1 − 4 3 δ ,
sup θ ∈ Θ ∣ E [ g θ , R ( Z ) ] − 1 N ∑ i = 1 N g θ , R ( Z i ) ∣ ≤ C u c B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N . \sup_{\theta\in\Theta}\left|\mathbb{E}[g_{\theta,R}(Z)]-\frac{1}{N}\sum_{i=1}^{N}g_{\theta,R}(Z_i)\right|\leq C_{\mathrm{uc}}B_\ell(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}. θ ∈ Θ sup E [ g θ , R ( Z )] − N 1 i = 1 ∑ N g θ , R ( Z i ) ≤ C uc B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) .
It remains to control the contribution outside the endpoint-truncation event. Define
ϵ t a i l ( R ) : = sup θ ∈ Θ E [ g θ ( Z ) 1 E R c ] . \epsilon_{\mathrm{tail}}(R):=\sup_{\theta\in\Theta}\mathbb{E}\left[g_\theta(Z)\mathbf{1}_{\mathcal{E}_R^c}\right]. ϵ tail ( R ) := θ ∈ Θ sup E [ g θ ( Z ) 1 E R c ] .
By the linear-growth property,
∥ u θ ( X t , t ) ∥ 2 ≤ A N N + B N N ∥ X t ∥ 2 . \lVert u_\theta(X_t,t)\rVert_2\leq A_{\mathrm{NN}}+B_{\mathrm{NN}}\lVert X_t\rVert_2. ∥ u θ ( X t , t ) ∥ 2 ≤ A NN + B NN ∥ X t ∥ 2 .
Since
X t = ( 1 − t ) X 0 + t X 1 , X_t=(1-t)X_0+tX_1, X t = ( 1 − t ) X 0 + t X 1 ,
we have
∥ X t ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 , \lVert X_t\rVert_2\leq\lVert X_0\rVert_2+\lVert X_1\rVert_2, ∥ X t ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 ,
and
∥ X 1 − X 0 ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 . \lVert X_1-X_0\rVert_2\leq\lVert X_0\rVert_2+\lVert X_1\rVert_2. ∥ X 1 − X 0 ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 .
Thus, after increasing a constant if necessary, there exists C e n v > 0 C_{\mathrm{env}} > 0 C env > 0 such that
g θ ( Z ) ≤ C e n v ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 ) g_\theta(Z) \le C_{\mathrm{env}}\left(1 + \lVert X_0\rVert_2^2 + \lVert X_1\rVert_2^2\right) g θ ( Z ) ≤ C env ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 )
uniformly over θ ∈ Θ \theta\in\Theta θ ∈ Θ . Moreover,
E R c = { ∥ X 0 ∥ 2 > R } ∪ { ∥ X 1 ∥ 2 > R } . \mathcal{E}^{\mathrm{c}}_R = \{\lVert X_0\rVert_2 > R\} \cup\{\lVert X_1\rVert_2 > R\}. E R c = {∥ X 0 ∥ 2 > R } ∪ {∥ X 1 ∥ 2 > R } .
Using Assumption 3.1 and the tail-integration identity for nonnegative random variables, there exist constants C t a i l ′ , c t a i l > 0 C'_{\mathrm{tail}}, c_{\mathrm{tail}} > 0 C tail ′ , c tail > 0 such that
ϵ t a i l ( R ) ≤ C t a i l ′ ( 1 + R ) 2 exp ( − c t a i l R / K X ) . \epsilon_{\mathrm{tail}}(R) \le C'_{\mathrm{tail}}(1+R)^2 \exp\left(-c_{\mathrm{tail}}R/K_X\right). ϵ tail ( R ) ≤ C tail ′ ( 1 + R ) 2 exp ( − c tail R / K X ) .
We next connect the truncated empirical loss to the original empirical loss. Define the all-sample truncation event
A R : = ⋂ i = 1 N E R , i . \mathcal{A}_R := \bigcap_{i=1}^{N} \mathcal{E}_{R,i}. A R := i = 1 ⋂ N E R , i .
On
g θ , R ( Z i ) = g θ ( Z i ) , i = 1 , … , N , ∀ θ ∈ Θ . g_{\theta,R}(Z_i) = g_\theta(Z_i), \qquad i=1,\ldots,N,\qquad\forall\theta\in\Theta. g θ , R ( Z i ) = g θ ( Z i ) , i = 1 , … , N , ∀ θ ∈ Θ.
Consequently, on A R \mathcal{A}_R A R ,
L ^ N ( θ ) = 1 N ∑ i = 1 N g θ , R ( Z i ) , ∀ θ ∈ Θ . \widehat{L}_N(\theta) = \frac{1}{N}\sum_{i=1}^{N}g_{\theta,R}(Z_i), \qquad\forall\theta\in\Theta. L N ( θ ) = N 1 i = 1 ∑ N g θ , R ( Z i ) , ∀ θ ∈ Θ.
By Assumption 3.1 and the union bound,
P ( A R c ) ≤ ∑ i = 1 N P ( E R , i c ) ≤ N [ P ( ∥ X 0 ∥ 2 > R ) + P ( ∥ X 1 ∥ 2 > R ) ] ≤ 2 N C 0 exp ( − c 1 R / K X ) . \begin{aligned}
\mathbb{P}\left(\mathcal{A}_R^{\mathrm{c}}\right)
&\le\sum_{i=1}^{N}\mathbb{P}\left(\mathcal{E}_{R,i}^{\mathrm{c}}\right)\\
&\le N\left[\mathbb{P}\left(\lVert X_0\rVert_2 > R\right) + \mathbb{P}\left(\lVert X_1\rVert_2 > R\right)\right]\\
&\le2NC_0\exp\left(-c_1R/K_X\right).
\end{aligned} P ( A R c ) ≤ i = 1 ∑ N P ( E R , i c ) ≤ N [ P ( ∥ X 0 ∥ 2 > R ) + P ( ∥ X 1 ∥ 2 > R ) ] ≤ 2 N C 0 exp ( − c 1 R / K X ) .
Therefore, if
R ≥ K X c 1 log ( 8 N C 0 δ ) , R \ge\frac{K_X}{c_1}\log\left(\frac{8NC_0}{\delta}\right), R ≥ c 1 K X log ( δ 8 N C 0 ) ,
then
P ( A R c ) ≤ δ 4 . \mathbb{P}\left(\mathcal{A}_R^{\mathrm{c}}\right) \le\frac{\delta}{4}. P ( A R c ) ≤ 4 δ .
On the intersection of the truncated uniform-convergence event and A R \mathcal{A}_R A R , for every θ ∈ Θ \theta\in\Theta θ ∈ Θ ,
∣ L ( θ ) − L ^ N ( θ ) ∣ = ∣ E [ g θ ( Z ) ] − 1 N ∑ i = 1 N g θ ( Z i ) ∣ ≤ ∣ E [ g θ , R ( Z ) ] − 1 N ∑ i = 1 N g θ , R ( Z i ) ∣ + E [ g θ ( Z ) 1 E R c ] . \begin{aligned}
\left|L(\theta)-\widehat{L}_N(\theta)\right|
&= \left|\mathbb{E}\left[g_\theta(Z)\right] - \frac{1}{N}\sum_{i=1}^{N}g_\theta(Z_i)\right|\\
&\le\left|\mathbb{E}\left[g_{\theta,R}(Z)\right] - \frac{1}{N}\sum_{i=1}^{N}g_{\theta,R}(Z_i)\right|\\
&\quad+ \mathbb{E}\left[g_\theta(Z)\mathbf{1}_{\mathcal{E}^{\mathrm{c}}_R}\right].
\end{aligned} L ( θ ) − L N ( θ ) = E [ g θ ( Z ) ] − N 1 i = 1 ∑ N g θ ( Z i ) ≤ E [ g θ , R ( Z ) ] − N 1 i = 1 ∑ N g θ , R ( Z i ) + E [ g θ ( Z ) 1 E R c ] .
Taking the supremum over θ ∈ Θ \theta\in\Theta θ ∈ Θ , we obtain
sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ ≤ C u c B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ′ ( 1 + R ) 2 exp ( − c t a i l R / K X ) . \sup_{\theta\in\Theta} \left|L(\theta)-\widehat{L}_N(\theta)\right| \le C_{\mathrm{uc}}B_{\ell}(R)\sqrt{\frac{\mathcal{C}_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}+C'_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right). θ ∈ Θ sup L ( θ ) − L N ( θ ) ≤ C uc B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ′ ( 1 + R ) 2 exp ( − c tail R / K X ) .
Multiplying by 2 and absorbing the factor into the constants, there exist constants
C s t a t , C t a i l > 0 C_{\mathrm{stat}},C_{\mathrm{tail}}>0 C stat , C tail > 0
such that
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ ≤ C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right| \le C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{\mathcal{C}_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right). 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) ≤ C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) .
The truncated uniform-convergence event fails in the set with probability at most 3 δ 4 \frac{3\delta}{4} 4 3 δ , and A R A_R A R fails with probability at most δ 4 \frac{\delta}{4} 4 δ . Hence, by the union bound, the preceding display holds with probability at least 1 − δ 1-\delta 1 − δ . This proves the first claim.
Finally, choosing
R ≍ K X log ( N / δ ) R \asymp K_X\log(N/\delta) R ≍ K X log ( N / δ )
satisfies the all-sample truncation requirement and makes
C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right) C tail ( 1 + R ) 2 exp ( − c tail R / K X )
lower order up to logarithmic factors. Hence,
2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ = O ~ ( B ℓ ( R ) C s m ( R , N ) + log ( 1 / δ ) N ) . 2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|=\widetilde{O}\left(B_{\ell}(R)\sqrt{\frac{\mathcal{C}_{\mathrm{sm}}(R,N)+\log(1/\delta)}{N}}\right). 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) = O ( B ℓ ( R ) N C sm ( R , N ) + log ( 1/ δ ) ) .
where the suppressed factors include the truncation-dependent envelope, the smooth-network entropy factors, and logarithmic terms. This completes the proof.
Proof of Lemma 4.8
Proof. Let
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) , L ^ N ⋆ : = L ^ N ( θ ^ N ) . \widehat{\theta}_N \in\underset{\theta\in\Theta}{\arg\min}\ \widehat{L}_N(\theta), \qquad\widehat{L}_N^\star:= \widehat{L}_N(\widehat{\theta}_N). θ N ∈ θ ∈ Θ arg min L N ( θ ) , L N ⋆ := L N ( θ N ) .
We analyze projected stochastic-gradient descent on the fixed finite empirical objective
L ^ N ( θ ) = 1 N ∑ i = 1 N ℓ θ ( Z i ) , \widehat{L}_N(\theta)=\frac{1}{N}\sum_{i=1}^{N}\ell_\theta(Z_i), L N ( θ ) = N 1 i = 1 ∑ N ℓ θ ( Z i ) ,
where
D N = { Z i } i = 1 N D_N=\{Z_i\}_{i=1}^{N} D N = { Z i } i = 1 N
is held fixed throughout the optimization analysis. The empirical minimizer θ ^ N \widehat{\theta}_N θ N is used only as a theoretical comparator; the algorithm is not assumed to have access to it. Conditioned on D N D_N D N , the projected stochastic-gradient recursion is
θ k + 1 = Π Θ ( θ k − η k g k ) , k = 0 , 1 , … , T − 1 , \theta_{k+1}=\Pi_{\Theta}\left(\theta_k-\eta_k g_k\right), \qquad k=0,1,\ldots,T-1, θ k + 1 = Π Θ ( θ k − η k g k ) , k = 0 , 1 , … , T − 1 ,
where
g k = ∇ θ ℓ θ k ( Z I k ) , I k ∼ Uniform { 1 , … , N } . g_k = \nabla_\theta\ell_{\theta_k}(Z_{I_k}), \qquad I_k \sim\operatorname{Uniform}\{1,\ldots,N\}. g k = ∇ θ ℓ θ k ( Z I k ) , I k ∼ Uniform { 1 , … , N } .
By Lemma 3.5 ,
θ k ∈ Θ , k = 0 , 1 , … , T . \theta_k \in\Theta,\qquad k=0,1,\ldots,T. θ k ∈ Θ , k = 0 , 1 , … , T .
Moreover, by the interior-operating-regime clause in Assumption 3.4 , the projection is inactive along the analyzed stochastic trajectory. Thus, almost surely conditional on D N \mathcal{D}_N D N ,
θ k + 1 = θ k − η k g k . \theta_{k+1}=\theta_k-\eta_k g_k. θ k + 1 = θ k − η k g k .
Since θ k , θ k + 1 ∈ Θ \theta_k,\theta_{k+1}\in\Theta θ k , θ k + 1 ∈ Θ and Θ \Theta Θ is convex, the line segment joining θ k \theta_k θ k and θ k + 1 \theta_{k+1} θ k + 1 lies in Θ \Theta Θ . Hence the α N \alpha_N α N -smoothness inequality for L ^ N \widehat{L}_N L N applies along this segment.
Let
{ F k } k ≥ 0 \{\mathcal{F}_k\}_{k\geq0} { F k } k ≥ 0
denote the filtration generated by the optimization process up to iteration k k k , conditionally on D N \mathcal{D}_N D N . By Assumption 3.4 ,
E [ g k ∣ F k , D N ] = ∇ L ^ N ( θ k ) , \mathbb{E}\left[g_k\mid\mathcal{F}_k,\mathcal{D}_N\right]=\nabla\widehat{L}_N(\theta_k), E [ g k ∣ F k , D N ] = ∇ L N ( θ k ) ,
and
E [ ∥ g k − ∇ L ^ N ( θ k ) ∥ 2 2 ∣ F k , D N ] ≤ σ N 2 . \mathbb{E}\left[\left\|g_k-\nabla\widehat{L}_N(\theta_k)\right\|_2^2\mid\mathcal{F}_k,\mathcal{D}_N\right]\leq\sigma_N^2. E [ g k − ∇ L N ( θ k ) 2 2 ∣ F k , D N ] ≤ σ N 2 .
Thus, the stochastic gradient is conditionally unbiased for the empirical gradient, rather than for the population gradient.
For convenience, define the random empirical suboptimality
Δ k : = L ^ N ( θ k ) − L ^ N ⋆ . \Delta_k:=\widehat{L}_N(\theta_k)-\widehat{L}_N^\star. Δ k := L N ( θ k ) − L N ⋆ .
Because θ k ∈ Θ \theta_k\in\Theta θ k ∈ Θ and
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) , \widehat{\theta}_N\in\arg\min_{\theta\in\Theta}\widehat{L}_N(\theta), θ N ∈ arg θ ∈ Θ min L N ( θ ) ,
we have Δ k ≥ 0 \Delta_k\geq0 Δ k ≥ 0 .
We first record the consequence of the empirical proximal-PL condition needed below. For every θ ∈ Θ \theta\in\Theta θ ∈ Θ , the definition of the constrained gradient-mapping quantity gives
M N ( θ ) = − 2 α N min θ ′ ∈ Θ [ ⟨ ∇ L ^ N ( θ ) , θ ′ − θ ⟩ + α N 2 ∥ θ ′ − θ ∥ 2 2 ] ≤ − 2 α N min θ ′ ∈ R P [ ⟨ ∇ L ^ N ( θ ) , θ ′ − θ ⟩ + α N 2 ∥ θ ′ − θ ∥ 2 2 ] = ∥ ∇ L ^ N ( θ ) ∥ 2 2 . \begin{aligned}
M_N(\theta)=-2\alpha_N\min_{\theta'\in\Theta}\left[\left\langle\nabla\widehat{L}_N(\theta),\theta'-\theta\right\rangle+\frac{\alpha_N}{2}\|\theta'-\theta\|_2^2\right] \\
&\leq-2\alpha_N\min_{\theta'\in\mathbb{R}^P}\left[\left\langle\nabla\widehat{L}_N(\theta),\theta'-\theta\right\rangle+\frac{\alpha_N}{2}\|\theta'-\theta\|_2^2\right]
=\left\|\nabla\widehat{L}_N(\theta)\right\|_2^2.
\end{aligned} M N ( θ ) = − 2 α N θ ′ ∈ Θ min [ ⟨ ∇ L N ( θ ) , θ ′ − θ ⟩ + 2 α N ∥ θ ′ − θ ∥ 2 2 ] ≤ − 2 α N θ ′ ∈ R P min [ ⟨ ∇ L N ( θ ) , θ ′ − θ ⟩ + 2 α N ∥ θ ′ − θ ∥ 2 2 ] = ∇ L N ( θ ) 2 2 .
Therefore, Assumption 3.3 implies
1 2 ∥ ∇ L ^ N ( θ ) ∥ 2 2 ≥ 1 2 M N ( θ ) ≥ μ N ( L ^ N ( θ ) − L ^ N ⋆ ) . \frac{1}{2}\left\|\nabla\widehat{L}_N(\theta)\right\|_2^2\geq\frac{1}{2}M_N(\theta)\geq\mu_N\left(\widehat{L}_N(\theta)-\widehat{L}_N^\star\right). 2 1 ∇ L N ( θ ) 2 2 ≥ 2 1 M N ( θ ) ≥ μ N ( L N ( θ ) − L N ⋆ ) .
In particular,
1 2 ∥ ∇ L ^ N ( θ k ) ∥ 2 2 ≥ μ N Δ k . \frac{1}{2}\left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2\geq\mu_N\Delta_k. 2 1 ∇ L N ( θ k ) 2 2 ≥ μ N Δ k .
By α N \alpha_N α N -smoothness of
we have
L ^ N ( θ k + 1 ) ≤ L ^ N ( θ k ) + ⟨ ∇ L ^ N ( θ k ) , θ k + 1 − θ k ⟩ + α N 2 ∥ θ k + 1 − θ k ∥ 2 2 = L ^ N ( θ k ) − η k ⟨ ∇ L ^ N ( θ k ) , g k ⟩ + α N η k 2 2 ∥ g k ∥ 2 2 . \begin{aligned}
\widehat{L}_N(\theta_{k+1}) \le\widehat{L}_N(\theta_k) + \left\langle\nabla\widehat{L}_N(\theta_k), \theta_{k+1}-\theta_k \right\rangle+ \frac{\alpha_N}{2}\left\|\theta_{k+1}-\theta_k\right\|_2^2 \\
&= \widehat{L}_N(\theta_k) - \eta_k\left\langle\nabla\widehat{L}_N(\theta_k), g_k \right\rangle+ \frac{\alpha_N\eta_k^2}{2}\left\|g_k\right\|_2^2.
\end{aligned} L N ( θ k + 1 ) ≤ L N ( θ k ) + ⟨ ∇ L N ( θ k ) , θ k + 1 − θ k ⟩ + 2 α N ∥ θ k + 1 − θ k ∥ 2 2 = L N ( θ k ) − η k ⟨ ∇ L N ( θ k ) , g k ⟩ + 2 α N η k 2 ∥ g k ∥ 2 2 .
Taking conditional expectation given F k \mathcal{F}_k F k and D N \mathcal{D}_N D N ,
conditional unbiasedness gives
E [ ⟨ ∇ L ^ N ( θ k ) , g k ⟩ | F k , D N ] = ∥ ∇ L ^ N ( θ k ) ∥ 2 2 . \mathbb{E}\left[\left\langle\nabla\widehat{L}_N(\theta_k),g_k \right\rangle\,\middle|\, \mathcal{F}_k,\mathcal{D}_N\right] = \left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2. E [ ⟨ ∇ L N ( θ k ) , g k ⟩ F k , D N ] = ∇ L N ( θ k ) 2 2 .
Moreover,
E [ ∥ g k ∥ 2 2 | F k , D N ] = ∥ ∇ L ^ N ( θ k ) ∥ 2 2 + E [ ∥ g k − ∇ L ^ N ( θ k ) ∥ 2 2 | F k , D N ] ≤ ∥ ∇ L ^ N ( θ k ) ∥ 2 2 + σ N 2 . \begin{aligned}
\mathbb{E}\left[\left\|g_k\right\|_2^2 \,\middle|\, \mathcal{F}_k,\mathcal{D}_N\right] = \left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2
+ \mathbb{E}\left[\left\|g_k-\nabla\widehat{L}_N(\theta_k)\right\|_2^2 \,\middle|\, \mathcal{F}_k,\mathcal{D}_N\right] \\
&\le\left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2+\sigma_N^2.
\end{aligned} E [ ∥ g k ∥ 2 2 F k , D N ] = ∇ L N ( θ k ) 2 2 + E [ g k − ∇ L N ( θ k ) 2 2 F k , D N ] ≤ ∇ L N ( θ k ) 2 2 + σ N 2 .
Consequently,
E [ Δ k + 1 | F k , D N ] ≤ Δ k − η k ∥ ∇ L ^ N ( θ k ) ∥ 2 2 + α N η k 2 2 ( ∥ ∇ L ^ N ( θ k ) ∥ 2 2 + σ N 2 ) . \mathbb{E}\left[\Delta_{k+1}\,\middle|\,\mathcal{F}_k,\mathcal{D}_N\right]
\le\Delta_k-\eta_k\left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2
+\frac{\alpha_N\eta_k^2}{2}\left(\left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2+\sigma_N^2\right). E [ Δ k + 1 ∣ F k , D N ] ≤ Δ k − η k ∇ L N ( θ k ) 2 2 + 2 α N η k 2 ( ∇ L N ( θ k ) 2 2 + σ N 2 ) .
Since
η k ≤ 1 α N , \eta_k\le\frac{1}{\alpha_N}, η k ≤ α N 1 ,
we have
− η k + α N η k 2 2 ≤ − η k 2 . -\eta_k+\frac{\alpha_N\eta_k^2}{2}\le-\frac{\eta_k}{2}. − η k + 2 α N η k 2 ≤ − 2 η k .
Therefore,
E [ Δ k + 1 | F k , D N ] ≤ Δ k − η k 2 ∥ ∇ L ^ N ( θ k ) ∥ 2 2 + α N σ N 2 2 η k 2 ≤ ( 1 − μ N η k ) Δ k + α N σ N 2 2 η k 2 . \begin{aligned}
\mathbb{E}\left[\Delta_{k+1}\,\middle|\,\mathcal{F}_k,\mathcal{D}_N\right]
\le\Delta_k-\frac{\eta_k}{2}\left\|\nabla\widehat{L}_N(\theta_k)\right\|_2^2
+\frac{\alpha_N\sigma_N^2}{2}\eta_k^2 \\
&\le(1-\mu_N\eta_k)\Delta_k+\frac{\alpha_N\sigma_N^2}{2}\eta_k^2.
\end{aligned} E [ Δ k + 1 ∣ F k , D N ] ≤ Δ k − 2 η k ∇ L N ( θ k ) 2 2 + 2 α N σ N 2 η k 2 ≤ ( 1 − μ N η k ) Δ k + 2 α N σ N 2 η k 2 .
Define
e k : = E S G D [ Δ k ∣ D N ] . e_k:=\mathbb{E}_{\mathrm{SGD}}\left[\Delta_k\mid\mathcal{D}_N\right]. e k := E SGD [ Δ k ∣ D N ] .
Taking expectation over the optimization randomness conditional on D N \mathcal{D}_N D N , we obtain
e k + 1 ≤ ( 1 − μ N η k ) e k + α N σ N 2 2 η k 2 . e_{k+1}\le(1-\mu_N\eta_k)e_k+\frac{\alpha_N\sigma_N^2}{2}\eta_k^2. e k + 1 ≤ ( 1 − μ N η k ) e k + 2 α N σ N 2 η k 2 .
We first establish the bound for arbitrary positive parameters α 0 \alpha_0 α 0 , γ \gamma γ satisfying
α 0 μ N > 1 , γ ≥ α 0 μ N , η k = α 0 k + γ ≤ 1 α N . \alpha_0\mu_N>1,\qquad\gamma\ge\alpha_0\mu_N,\qquad\eta_k=\frac{\alpha_0}{k+\gamma}\le\frac{1}{\alpha_N}. α 0 μ N > 1 , γ ≥ α 0 μ N , η k = k + γ α 0 ≤ α N 1 .
Substitute
η k = α 0 k + γ , p : = α 0 μ N , b : = α N σ N 2 α 0 2 2 . \eta_k=\frac{\alpha_0}{k+\gamma},\qquad p:=\alpha_0\mu_N,\qquad b:=\frac{\alpha_N\sigma_N^2\alpha_0^2}{2}. η k = k + γ α 0 , p := α 0 μ N , b := 2 α N σ N 2 α 0 2 .
Then
e k + 1 ≤ ( 1 − p k + γ ) e k + b ( k + γ ) 2 . e_{k+1} \le\left(1-\frac{p}{k+\gamma}\right)e_k+\frac{b}{(k+\gamma)^2}. e k + 1 ≤ ( 1 − k + γ p ) e k + ( k + γ ) 2 b .
The step-size conditions imply
p > 1 , γ ≥ p . p>1,\qquad\gamma\ge p. p > 1 , γ ≥ p .
Hence, for every
0 ≤ 1 − p k + γ ≤ 1. 0\le1-\frac{p}{k+\gamma}\le1. 0 ≤ 1 − k + γ p ≤ 1.
Define
e 0 : = L ^ N ( θ 0 ) − L ^ N ( θ ^ N ) , e_0:=\widehat{L}_N(\theta_0)-\widehat{L}_N(\widehat{\theta}_N), e 0 := L N ( θ 0 ) − L N ( θ N ) ,
and
C 0 : = max { γ e 0 , b p − 1 } . C_0:=\max\left\{\gamma e_0,\frac{b}{p-1}\right\}. C 0 := max { γ e 0 , p − 1 b } .
We claim that
e k ≤ C 0 k + γ for every k ≥ 0. e_k\le\frac{C_0}{k+\gamma}\qquad\text{for every }k\ge0. e k ≤ k + γ C 0 for every k ≥ 0.
For
the claim follows from
C 0 ≥ γ e 0 . C_0\ge\gamma e_0. C 0 ≥ γ e 0 .
Suppose the claim holds for some
and write
s : = k + γ . s:=k+\gamma. s := k + γ .
Since
1 − p s ≥ 0 , 1-\frac{p}{s}\ge0, 1 − s p ≥ 0 ,
the recursion and the induction hypothesis imply
e k + 1 ≤ ( 1 − p s ) C 0 s + b s 2 = C 0 s − p C 0 − b s 2 . \begin{aligned}
e_{k+1}
&\le\left(1-\frac{p}{s}\right)\frac{C_0}{s}+\frac{b}{s^2}\\
&=\frac{C_0}{s}-\frac{pC_0-b}{s^2}.
\end{aligned} e k + 1 ≤ ( 1 − s p ) s C 0 + s 2 b = s C 0 − s 2 p C 0 − b .
Because
C 0 ≥ b p − 1 , C_0\ge\frac{b}{p-1}, C 0 ≥ p − 1 b ,
we have
C 0 ( p − 1 ) ≥ b , C_0(p-1)\ge b, C 0 ( p − 1 ) ≥ b ,
and hence
p C 0 − b ≥ C 0 . pC_0-b\ge C_0. p C 0 − b ≥ C 0 .
It follows that
e k + 1 ≤ C 0 s − C 0 s 2 = C 0 ( s − 1 ) s 2 . e_{k+1}\le\frac{C_0}{s}-\frac{C_0}{s^2}=\frac{C_0(s-1)}{s^2}. e k + 1 ≤ s C 0 − s 2 C 0 = s 2 C 0 ( s − 1 ) .
Since
s ≥ γ ≥ p > 1 , s \ge\gamma\ge p > 1, s ≥ γ ≥ p > 1 ,
we have
s − 1 s 2 ≤ 1 s + 1 . \frac{s-1}{s^2} \le\frac{1}{s+1}. s 2 s − 1 ≤ s + 1 1 .
Thus,
e k + 1 ≤ C 0 s + 1 = C 0 k + 1 + γ . e_{k+1} \le\frac{C_0}{s+1} = \frac{C_0}{k+1+\gamma}. e k + 1 ≤ s + 1 C 0 = k + 1 + γ C 0 .
This completes the induction.
Consequently,
e T ≤ C 0 T + γ ≤ C 0 T . e_T \le\frac{C_0}{T+\gamma} \le\frac{C_0}{T}. e T ≤ T + γ C 0 ≤ T C 0 .
Therefore,
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C o p t ( D N ) T , \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid D_N\right] \le\frac{C_{\mathrm{opt}}(D_N)}{T}, E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt ( D N ) ,
where we may take
C o p t ( D N ) : = max { γ e 0 , α N σ N 2 α 0 2 2 ( α 0 μ N − 1 ) } . C_{\mathrm{opt}}(D_N) := \max\left\{\gamma e_0,\frac{\alpha_N\sigma_N^2\alpha_0^2}{2(\alpha_0\mu_N-1)}\right\}. C opt ( D N ) := max { γ e 0 , 2 ( α 0 μ N − 1 ) α N σ N 2 α 0 2 } .
It remains to derive the deterministic uniform bound used in the main theorem. On the event G N \mathcal{G}_N G N from Assumption 3.6, choose
α 0 : = 2 μ min , γ : = α 0 α max , η k : = α 0 k + γ . \alpha_0 := \frac{2}{\mu_{\min}},\qquad\gamma:= \alpha_0\alpha_{\max},\qquad\eta_k := \frac{\alpha_0}{k+\gamma}. α 0 := μ m i n 2 , γ := α 0 α m a x , η k := k + γ α 0 .
Then
α 0 μ N ≥ α 0 μ min = 2 > 1 , \alpha_0\mu_N \ge\alpha_0\mu_{\min}=2>1, α 0 μ N ≥ α 0 μ m i n = 2 > 1 ,
γ = α 0 α max ≥ α 0 μ N , \gamma=\alpha_0\alpha_{\max}\ge\alpha_0\mu_N, γ = α 0 α m a x ≥ α 0 μ N ,
and
η k ≤ α 0 γ = 1 α max ≤ 1 α N . \eta_k\le\frac{\alpha_0}{\gamma}=\frac{1}{\alpha_{\max}}\le\frac{1}{\alpha_N}. η k ≤ γ α 0 = α m a x 1 ≤ α N 1 .
Moreover,
γ e 0 ≤ γ ‾ e 0 , \gamma e_0\le\overline{\gamma}e_0, γ e 0 ≤ γ e 0 ,
and
α N σ N 2 α 0 2 2 ( α 0 μ N − 1 ) ≤ α max σ ‾ 2 α 0 2 2 ( α 0 μ min − 1 ) . \frac{\alpha_N\sigma_N^2\alpha_0^2}{2(\alpha_0\mu_N-1)}
\le
\frac{\alpha_{\max}\overline{\sigma}^2\alpha_0^2}{2(\alpha_0\mu_{\min}-1)}. 2 ( α 0 μ N − 1 ) α N σ N 2 α 0 2 ≤ 2 ( α 0 μ m i n − 1 ) α m a x σ 2 α 0 2 .
Hence, on
C o p t ( D N ) ≤ C ‾ o p t , C_{\mathrm{opt}}(D_N)\le\overline{C}_{\mathrm{opt}}, C opt ( D N ) ≤ C opt ,
where
C ‾ o p t : = max { γ ‾ e 0 , α max σ ‾ 2 α 0 2 2 ( α 0 μ min − 1 ) } . \overline{C}_{\mathrm{opt}}:=\max\left\{\overline{\gamma}e_0,\frac{\alpha_{\max}\overline{\sigma}^2\alpha_0^2}{2(\alpha_0\mu_{\min}-1)}\right\}. C opt := max { γ e 0 , 2 ( α 0 μ m i n − 1 ) α m a x σ 2 α 0 2 } .
Therefore, on
E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C ‾ o p t T . \mathbb{E}_{\mathrm{SGD}}\left[\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\mid D_N\right]\le\frac{\overline{C}_{\mathrm{opt}}}{T}. E SGD [ L N ( θ T ) − L N ( θ N ) ∣ D N ] ≤ T C opt .
A high-probability analogue would require an additional explicit conditional tail assumption on the stochastic-gradient noise and a separate martingale-concentration analysis. Under the bounded conditional-variance assumption used here, the conditional expectation guarantee above is the asserted conclusion.
Additional Details for Theorem 4.1
This section provides the detailed proof of Theorem 4.1 . The theorem and its supporting lemmas are stated in the main text, so we do not restate them here. The proof combines the projection identity, the finite-dataset statistical bound from Lemma 4.7 , the projected empirical optimization bound from Lemma 4.8 , and the deterministic uniform flow-stability bound from Lemma D.7.
Proof of Theorem 4.1. Let
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) \widehat{\theta}_N \in\underset{\theta\in\Theta}{\arg\min}\ \widehat{L}_N(\theta) θ N ∈ θ ∈ Θ arg min L N ( θ )
be an empirical risk minimizer, and let
θ Θ ⋆ ∈ arg min θ ∈ Θ L ( θ ) \theta_\Theta^\star\in\underset{\theta\in\Theta}{\arg\min}\ L(\theta) θ Θ ⋆ ∈ θ ∈ Θ arg min L ( θ )
be a population minimizer within the prescribed neural velocity class. Both parameters are theoretical comparators: the algorithm is only required to produce the finite-time projected stochastic-gradient iterate θ T \theta_T θ T . By Lemma 3.5 , θ T ∈ Θ \theta_T \in\Theta θ T ∈ Θ .
For every realization of the stochastic-gradient randomness, we decompose the excess population loss as
L ( θ T ) − L ⋆ = L ( θ T ) − L ^ N ( θ T ) + L ^ N ( θ T ) − L ^ N ( θ ^ N ) + L ^ N ( θ ^ N ) − L ^ N ( θ Θ ⋆ ) + L ^ N ( θ Θ ⋆ ) − L ( θ Θ ⋆ ) + L ( θ Θ ⋆ ) − L ⋆ . \begin{aligned}
L(\theta_T)-L^\star
={}&L(\theta_T)-\widehat{L}_N(\theta_T)+\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\\
&+\widehat{L}_N(\widehat{\theta}_N)-\widehat{L}_N(\theta_\Theta^\star)\\
&+\widehat{L}_N(\theta_\Theta^\star)-L(\theta_\Theta^\star)\\
&+L(\theta_\Theta^\star)-L^\star.
\end{aligned} L ( θ T ) − L ⋆ = L ( θ T ) − L N ( θ T ) + L N ( θ T ) − L N ( θ N ) + L N ( θ N ) − L N ( θ Θ ⋆ ) + L N ( θ Θ ⋆ ) − L ( θ Θ ⋆ ) + L ( θ Θ ⋆ ) − L ⋆ .
Since
θ ^ N ∈ arg min θ ∈ Θ L ^ N ( θ ) , \widehat{\theta}_N \in\underset{\theta\in\Theta}{\arg\min}\ \widehat{L}_N(\theta), θ N ∈ θ ∈ Θ arg min L N ( θ ) ,
we have
L ^ N ( θ ^ N ) − L ^ N ( θ Θ ⋆ ) ≤ 0. \widehat{L}_N(\widehat{\theta}_N)-\widehat{L}_N(\theta_\Theta^\star)\le0. L N ( θ N ) − L N ( θ Θ ⋆ ) ≤ 0.
Therefore,
L ( θ T ) − L ⋆ ≤ L ( θ Θ ⋆ ) − L ⋆ + ∣ L ( θ T ) − L ^ N ( θ T ) ∣ + ∣ L ^ N ( θ Θ ⋆ ) − L ( θ Θ ⋆ ) ∣ + L ^ N ( θ T ) − L ^ N ( θ ^ N ) ≤ L ( θ Θ ⋆ ) − L ⋆ + 2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ + L ^ N ( θ T ) − L ^ N ( θ ^ N ) . \begin{aligned}
L(\theta_T)-L^\star
\le{}&L(\theta_\Theta^\star)-L^\star\\
&+\left|L(\theta_T)-\widehat{L}_N(\theta_T)\right|\\
&+\left|\widehat{L}_N(\theta_\Theta^\star)-L(\theta_\Theta^\star)\right|\\
&+\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\\
\le{}&L(\theta_\Theta^\star)-L^\star\\
&+2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|\\
&+\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N).
\end{aligned} L ( θ T ) − L ⋆ ≤ ≤ L ( θ Θ ⋆ ) − L ⋆ + L ( θ T ) − L N ( θ T ) + L N ( θ Θ ⋆ ) − L ( θ Θ ⋆ ) + L N ( θ T ) − L N ( θ N ) L ( θ Θ ⋆ ) − L ⋆ + 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) + L N ( θ T ) − L N ( θ N ) .
Define
E a p p r o x : = L ( θ Θ ⋆ ) − L ⋆ , E_{\mathrm{approx}}:=L(\theta_\Theta^\star)-L^\star, E approx := L ( θ Θ ⋆ ) − L ⋆ ,
E s t a t : = 2 sup θ ∈ Θ ∣ L ( θ ) − L ^ N ( θ ) ∣ , E_{\mathrm{stat}}:=2\sup_{\theta\in\Theta}\left|L(\theta)-\widehat{L}_N(\theta)\right|, E stat := 2 θ ∈ Θ sup L ( θ ) − L N ( θ ) ,
and
E o p t : = L ^ N ( θ T ) − L ^ N ( θ ^ N ) . E_{\mathrm{opt}}:=\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N). E opt := L N ( θ T ) − L N ( θ N ) .
Then
L ( θ T ) − L ⋆ ≤ E a p p r o x + E s t a t + E o p t . L(\theta_T)-L^\star\le E_{\mathrm{approx}}+E_{\mathrm{stat}}+E_{\mathrm{opt}}. L ( θ T ) − L ⋆ ≤ E approx + E stat + E opt .
By Lemma 4.6,
E a p p r o x ≤ ϵ a p p r o x . E_{\mathrm{approx}} \le\epsilon_{\mathrm{approx}}. E approx ≤ ϵ approx .
Fix δ , δ o p t ∈ ( 0 , 1 ) \delta, \delta_{\mathrm{opt}} \in(0,1) δ , δ opt ∈ ( 0 , 1 ) and a truncation radius satisfying
R ≥ K X c 1 log ( 8 N c 0 δ ) . R \ge\frac{K_X}{c_1}\log\left(\frac{8Nc_0}{\delta}\right). R ≥ c 1 K X log ( δ 8 N c 0 ) .
Let
H N , R , δ \mathcal{H}_{N,R,\delta} H N , R , δ
denote the statistical event from Lemma 4.7. On this event,
E s t a t ≤ C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) , E_{\mathrm{stat}} \le C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right), E stat ≤ C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) ,
and
P ( H N , R , δ ) ≥ 1 − δ . \mathbb{P}\left(\mathcal{H}_{N,R,\delta}\right)\ge1-\delta. P ( H N , R , δ ) ≥ 1 − δ .
By Assumption 3.6, there is an event G N \mathcal{G}_N G N such that
P ( G N ) ≥ 1 − δ o p t , \mathbb{P}\left(\mathcal{G}_N\right)\ge1-\delta_{\mathrm{opt}}, P ( G N ) ≥ 1 − δ opt ,
and, on G N \mathcal{G}_N G N , the uniform empirical-constant bounds hold. In particular, Lemma 4.8 gives
E S G D [ E o p t ∣ D N ] = E S G D [ L ^ N ( θ T ) − L ^ N ( θ ^ N ) ∣ D N ] ≤ C ‾ o p t T . \mathbb{E}_{\mathrm{SGD}}\left[E_{\mathrm{opt}}\mid D_N\right]
=
\mathbb{E}_{\mathrm{SGD}}\left[\left.\widehat{L}_N(\theta_T)-\widehat{L}_N(\widehat{\theta}_N)\right|D_N\right]
\le\frac{\overline{C}_{\mathrm{opt}}}{T}. E SGD [ E opt ∣ D N ] = E SGD [ L N ( θ T ) − L N ( θ N ) D N ] ≤ T C opt .
By the union bound,
P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ o p t . \mathbb{P}\left(\mathcal{H}_{N,R,\delta}\cap\mathcal{G}_N\right)\ge1-\delta-\delta_{\mathrm{opt}}. P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ opt .
Fix a dataset realization in
H N , R , δ ∩ G N . \mathcal{H}_{N,R,\delta}\cap\mathcal{G}_N. H N , R , δ ∩ G N .
Taking conditional expectation over the stochastic-gradient randomness in the error decomposition gives
E S G D [ L ( θ T ) − L ⋆ ∣ D N ] ≤ ϵ a p p r o x + C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) + C ‾ o p t T . \mathbb{E}_{\mathrm{SGD}}\left[\left.L(\theta_T)-L^\star\right|D_N\right]
\le\epsilon_{\mathrm{approx}}+C_{\mathrm{stat}}B_{\ell}(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}+C_{\mathrm{tail}}(1+R)^2\exp\left(-c_{\mathrm{tail}}R/K_X\right)+\frac{\overline{C}_{\mathrm{opt}}}{T}. E SGD [ L ( θ T ) − L ⋆ ∣ D N ] ≤ ϵ approx + C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) + T C opt .
Equivalently,
E S G D [ L ( θ T ) − L ⋆ ∣ D N ] ≤ ϵ N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[\left.L(\theta_T)-L^\star\right|D_N\right]\le\epsilon_{N,T}(R,\delta). E SGD [ L ( θ T ) − L ⋆ ∣ D N ] ≤ ϵ N , T ( R , δ ) .
By the projection identity,
L ( θ T ) − L ⋆ = E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . L(\theta_T)-L^\star=\mathbb{E}\left[\left\|u_{\theta_T}(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]. L ( θ T ) − L ⋆ = E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] .
Hence, on
H N , R , δ ∩ G N , \mathcal{H}_{N,R,\delta}\cap\mathcal{G}_N, H N , R , δ ∩ G N ,
E S G D [ E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] | D N ] ≤ ϵ N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[\mathbb{E}\left[\left\|u_{\theta_T}(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]\middle|D_N\right]\le\epsilon_{N,T}(R,\delta). E SGD [ E [ ∥ u θ T ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] D N ] ≤ ϵ N , T ( R , δ ) .
It remains to convert velocity-field error into terminal distributional error. By Assumption 3.7 , the flow-stability constant
K f l o w K_{\mathrm{flow}} K flow
is deterministic and uniform over Θ \Theta Θ . In particular, Lemma D.7 gives, for every θ ∈ Θ \theta\in\Theta θ ∈ Θ ,
W 2 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w 2 ( L ( θ ) − L ⋆ ) . W_2^2\left(\widehat{\pi}_1^\theta,\pi_1\right) \le K_{\mathrm{flow}}^2\left(L(\theta)-L^\star\right). W 2 2 ( π 1 θ , π 1 ) ≤ K flow 2 ( L ( θ ) − L ⋆ ) .
Applying this inequality to
θ = θ T ∈ Θ \theta=\theta_T\in\Theta θ = θ T ∈ Θ
yields
W 2 2 ( π ^ 1 θ T , π 1 ) ≤ K f l o w 2 ( L ( θ T ) − L ⋆ ) . W_2^2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right) \le K_{\mathrm{flow}}^2\left(L(\theta_T)-L^\star\right). W 2 2 ( π 1 θ T , π 1 ) ≤ K flow 2 ( L ( θ T ) − L ⋆ ) .
Since K f l o w K_{\mathrm{flow}} K flow is deterministic and independent of the stochastic-gradient randomness, taking conditional expectation gives
E S G D [ W 2 2 ( π ^ 1 θ T , π 1 ) ∣ D N ] ≤ K f l o w 2 E S G D [ L ( θ T ) − L ⋆ ∣ D N ] ≤ K f l o w 2 E N , T ( R , δ ) . \mathbb{E}_{\mathrm{SGD}}\left[W_2^2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\mid D_N\right]
\le K_{\mathrm{flow}}^2\mathbb{E}_{\mathrm{SGD}}\left[L(\theta_T)-L^\star\mid D_N\right]
\le K_{\mathrm{flow}}^2\mathcal{E}_{N,T}(R,\delta). E SGD [ W 2 2 ( π 1 θ T , π 1 ) ∣ D N ] ≤ K flow 2 E SGD [ L ( θ T ) − L ⋆ ∣ D N ] ≤ K flow 2 E N , T ( R , δ ) .
Finally, Jensen’s inequality gives
E S G D [ W 2 ( π ^ 1 θ T , π 1 ) ∣ D N ] ≤ ( E S G D [ W 2 2 ( π ^ 1 θ T , π 1 ) ∣ D N ] ) 1 / 2 ≤ K f l o w E N , T ( R , δ ) 1 / 2 . \mathbb{E}_{\mathrm{SGD}}\left[W_2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\mid D_N\right]
\le\left(\mathbb{E}_{\mathrm{SGD}}\left[W_2^2\left(\widehat{\pi}_1^{\theta_T},\pi_1\right)\mid D_N\right]\right)^{1/2}
\le K_{\mathrm{flow}}\mathcal{E}_{N,T}(R,\delta)^{1/2}. E SGD [ W 2 ( π 1 θ T , π 1 ) ∣ D N ] ≤ ( E SGD [ W 2 2 ( π 1 θ T , π 1 ) ∣ D N ] ) 1/2 ≤ K flow E N , T ( R , δ ) 1/2 .
Since
P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ o p t , \mathbb{P}\left(\mathcal{H}_{N,R,\delta}\cap\mathcal{G}_N\right)\ge1-\delta-\delta_{\mathrm{opt}}, P ( H N , R , δ ∩ G N ) ≥ 1 − δ − δ opt ,
this proves all conclusions of Theorem 4.1 . □
Sample-complexity consequence. Choose
R = c R K X log ( N / δ ) , R=c_RK_X\log(N/\delta), R = c R K X log ( N / δ ) ,
where
is sufficiently large that the truncation condition in Theorem 4.1 is satisfied. Then the tail term
C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) C_{\mathrm{tail}}(1+R)^2\exp(-c_{\mathrm{tail}}R/K_X) C tail ( 1 + R ) 2 exp ( − c tail R / K X )
is lower order up to logarithmic factors.
Suppose that the approximation and tail terms satisfy
ϵ a p p r o x + C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) ≤ ϵ 2 2 K f l o w 2 . \epsilon_{\mathrm{approx}}+C_{\mathrm{tail}}(1+R)^2\exp(-c_{\mathrm{tail}}R/K_X)
\le\frac{\epsilon^2}{2K_{\mathrm{flow}}^2}. ϵ approx + C tail ( 1 + R ) 2 exp ( − c tail R / K X ) ≤ 2 K flow 2 ϵ 2 .
It is then sufficient to impose
C s t a t B ℓ ( R ) C s m ( R , N ) + log ( 4 / δ ) N ≤ ϵ 2 4 K f l o w 2 . C_{\mathrm{stat}}B_\ell(R)\sqrt{\frac{C_{\mathrm{sm}}(R,N)+\log(4/\delta)}{N}}
\le\frac{\epsilon^2}{4K_{\mathrm{flow}}^2}. C stat B ℓ ( R ) N C sm ( R , N ) + log ( 4/ δ ) ≤ 4 K flow 2 ϵ 2 .
and
C ‾ o p t T ≤ ϵ 2 4 K f l o w 2 . \frac{\overline{C}_{\mathrm{opt}}}{T} \le\frac{\epsilon^2}{4K_{\mathrm{flow}}^2}. T C opt ≤ 4 K flow 2 ϵ 2 .
In particular, there exists a sufficiently large constant C > 0 C > 0 C > 0 such that it is sufficient to choose
N ≥ C K f l o w 4 B ℓ ( R ) 2 ( C s m ( R , N ) + log ( 1 / δ ) ) ϵ 4 , N \ge C\frac{K_{\mathrm{flow}}^4B_{\ell}(R)^2\left(C_{\mathrm{sm}}(R,N)+\log(1/\delta)\right)}{\epsilon^4}, N ≥ C ϵ 4 K flow 4 B ℓ ( R ) 2 ( C sm ( R , N ) + log ( 1/ δ ) ) ,
and
T ≥ C K f l o w 2 C ‾ o p t ϵ 2 . T \ge C\frac{K_{\mathrm{flow}}^2\overline{C}_{\mathrm{opt}}}{\epsilon^2}. T ≥ C ϵ 2 K flow 2 C opt .
The quantity C ‾ o p t \overline{C}_{\mathrm{opt}} C opt is deterministic once the constants in Assumption 3.6 have been fixed. Thus, the displayed optimization-budget requirement is no longer conditional on uncontrolled dataset-specific constants. Rather, it holds on the event G N \mathcal{G}_N G N , which is already included in the theorem’s probability statement.
When the approximation, tail, flow-stability, smooth-network-complexity, and uniform empirical-optimization quantities are treated as fixed or displayed separately, the shorthand scaling is
N = O ~ ( ϵ − 4 ) , T = O ~ ( ϵ − 2 ) . N = \widetilde{O}\left(\epsilon^{-4}\right), \qquad T = \widetilde{O}\left(\epsilon^{-2}\right). N = O ( ϵ − 4 ) , T = O ( ϵ − 2 ) .
The latter shorthand is conditional on the uniform empirical-constant regularity in Assumption 3.6 and on the interior operating regime in Assumption 3.4 .
Pure population-oracle comparison. For comparison, suppose instead that the algorithm has access to a population stochastic-gradient oracle and that the population objective satisfies corresponding population proximal-PL, smoothness, and stochastic-gradient conditions. The finite-dataset statistical term is then absent. Under these distinct assumptions, the corresponding flow-stability argument gives
E [ W 2 ( π 1 θ T , π 1 ) ] ≤ K f l o w ( ϵ a p p r o x + C o p t , p o p T ) 1 / 2 . \mathbb{E}\left[W_2\left(\pi_1^{\theta_T},\pi_1\right)\right] \le K_{\mathrm{flow}}\left(\epsilon_{\mathrm{approx}}+\frac{C_{\mathrm{opt,pop}}}{T}\right)^{1/2}. E [ W 2 ( π 1 θ T , π 1 ) ] ≤ K flow ( ϵ approx + T C opt , pop ) 1/2 .
where C o p t , p o p C_{\mathrm{opt,pop}} C opt , pop is the optimization constant associated with the distinct population-oracle assumptions. This comparison highlights that the finite-dataset O ~ ( ϵ − 4 ) \widetilde{O}\left(\epsilon^{-4}\right) O ( ϵ − 4 ) dataset-size scaling arises from the O ~ ( N − 1 / 2 ) \widetilde{O}\left(N^{-1/2}\right) O ( N − 1/2 ) statistical contribution at the squared-loss level.
Supplementary Lemmas
In this appendix, we collect auxiliary facts used in the proof of the main theorem. These lemmas are stated for the revised flow-matching formulation based on the linear, or rectified, path
X t = ( 1 − t ) X 0 + t X 1 , ( X 0 , X 1 ) ∼ Γ , X 0 ∼ π 0 , X 1 ∼ π 1 . X_t = (1-t)X_0 + tX_1, \qquad(X_0,X_1) \sim\Gamma, \qquad X_0 \sim\pi_0, \qquad X_1 \sim\pi_1. X t = ( 1 − t ) X 0 + t X 1 , ( X 0 , X 1 ) ∼ Γ , X 0 ∼ π 0 , X 1 ∼ π 1 .
They provide the pathwise bounds, projection identity, smooth-network properties, metric-entropy control, tail bound, flow-stability argument, and numerical-discretization observation used throughout the paper.
Lemma D.1 (Boundedness of the linear interpolation path). Suppose that the source and target variables satisfy
∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R . \lVert X_0\rVert_2 \le R, \qquad\lVert X_1\rVert_2 \le R. ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R . Then, for every
t ∈ [ 0 , 1 ] , t \in[0,1], t ∈ [ 0 , 1 ] , ∥ X t ∥ 2 ≤ R , ∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ 2 R . \lVert X_t\rVert_2 \le R, \qquad\lVert\dot{X}_t\rVert_2 = \lVert X_1-X_0\rVert_2 \le2R. ∥ X t ∥ 2 ≤ R , ∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ 2 R .
Proof. For the linear path,
X t = ( 1 − t ) X 0 + t X 1 . X_t = (1-t)X_0 + tX_1. X t = ( 1 − t ) X 0 + t X 1 .
By convexity of the Euclidean norm,
∥ X t ∥ 2 ≤ ( 1 − t ) ∥ X 0 ∥ 2 + t ∥ X 1 ∥ 2 ≤ ( 1 − t ) R + t R = R . \lVert X_t\rVert_2 \le(1-t)\lVert X_0\rVert_2 + t\lVert X_1\rVert_2
\le(1-t)R + tR
= R. ∥ X t ∥ 2 ≤ ( 1 − t ) ∥ X 0 ∥ 2 + t ∥ X 1 ∥ 2 ≤ ( 1 − t ) R + tR = R .
Moreover,
X ˙ t = X 1 − X 0 , \dot{X}_t = X_1 - X_0, X ˙ t = X 1 − X 0 ,
so the triangle inequality gives
∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ ∥ X 1 ∥ 2 + ∥ X 0 ∥ 2 ≤ 2 R . \lVert\dot{X}_t\rVert_2 = \lVert X_1-X_0\rVert_2
\le\lVert X_1\rVert_2 + \lVert X_0\rVert_2
\le2R. ∥ X ˙ t ∥ 2 = ∥ X 1 − X 0 ∥ 2 ≤ ∥ X 1 ∥ 2 + ∥ X 0 ∥ 2 ≤ 2 R .
Lemma D.2 (L 2 L^2 L 2 projection identity for flow matching). Let
L ( u ) : = E [ ∥ u ( X t , t ) − X ˙ t ∥ 2 2 ] , L(u) := \mathbb{E}\left[\left\lVert u(X_t,t)-\dot{X}_t\right\rVert_2^2\right], L ( u ) := E [ u ( X t , t ) − X ˙ t 2 2 ] , where the expectation is over ( X 0 , X 1 ) ∼ Γ (X_0,X_1)\sim\Gamma ( X 0 , X 1 ) ∼ Γ and t ∼ Uniform [ 0 , 1 ] t\sim\operatorname{Uniform}[0,1] t ∼ Uniform [ 0 , 1 ] . Define the marginal velocity field by
u ⋆ ( x , t ) : = E [ X ˙ t ∣ X t = x , t ] . u^\star(x,t):=\mathbb{E}\left[\dot{X}_t\mid X_t=x,t\right]. u ⋆ ( x , t ) := E [ X ˙ t ∣ X t = x , t ] . Then u ⋆ u^\star u ⋆ minimizes L ( u ) L(u) L ( u ) over all measurable deployable velocity fields
u : R d × [ 0 , 1 ] → R d . u:\mathbb{R}^d\times[0,1]\to\mathbb{R}^d. u : R d × [ 0 , 1 ] → R d . Moreover, for every candidate field u u u ,
L ( u ) − L ( u ⋆ ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . L(u)-L(u^\star)=\mathbb{E}\left[\left\lVert u(X_t,t)-u^\star(X_t,t)\right\rVert_2^2\right]. L ( u ) − L ( u ⋆ ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . In particular, for the neural velocity field u θ u_\theta u θ ,
L ( θ ) − L ⋆ = E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . L(\theta)-L^\star=\mathbb{E}\left[\left\lVert u_\theta(X_t,t)-u^\star(X_t,t)\right\rVert_2^2\right]. L ( θ ) − L ⋆ = E [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] . Proof. For every measurable deployable field u u u , write
u ( X t , t ) − X ˙ t = ( u ( X t , t ) − u ⋆ ( X t , t ) ) + ( u ⋆ ( X t , t ) − X ˙ t ) . u(X_t,t)-\dot{X}_t=\left(u(X_t,t)-u^\star(X_t,t)\right)+\left(u^\star(X_t,t)-\dot{X}_t\right). u ( X t , t ) − X ˙ t = ( u ( X t , t ) − u ⋆ ( X t , t ) ) + ( u ⋆ ( X t , t ) − X ˙ t ) . Squaring both sides and taking expectation gives
L ( u ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] + E [ ∥ u ⋆ ( X t , t ) − X ˙ t ∥ 2 2 ] + 2 E [ ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , u ⋆ ( X t , t ) − X ˙ t ⟩ ] . \begin{aligned}
L(u)={}&\mathbb{E}\left[\left\lVert u(X_t,t)-u^\star(X_t,t)\right\rVert_2^2\right]\\
&+\mathbb{E}\left[\left\lVert u^\star(X_t,t)-\dot{X}_t\right\rVert_2^2\right]\\
&+2\mathbb{E}\left[\left\langle u(X_t,t)-u^\star(X_t,t),u^\star(X_t,t)-\dot{X}_t\right\rangle\right].
\end{aligned} L ( u ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] + E [ u ⋆ ( X t , t ) − X ˙ t 2 2 ] + 2 E [ ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , u ⋆ ( X t , t ) − X ˙ t ⟩ ] .
The cross term is zero. Indeed, conditioning on
X t and t , X_t \quad\text{and} \quad t, X t and t ,
we obtain
E [ ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , u ⋆ ( X t , t ) − X ˙ t ⟩ | X t , t ] = ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , E [ u ⋆ ( X t , t ) − X ˙ t | X t , t ] ⟩ = 0. \mathbb{E}\left[\left\langle u(X_t,t)-u^\star(X_t,t),u^\star(X_t,t)-\dot{X}_t\right\rangle\middle|X_t,t\right]
= \left\langle u(X_t,t)-u^\star(X_t,t),\mathbb{E}\left[u^\star(X_t,t)-\dot{X}_t\middle|X_t,t\right]\right\rangle
= 0. E [ ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , u ⋆ ( X t , t ) − X ˙ t ⟩ X t , t ] = ⟨ u ( X t , t ) − u ⋆ ( X t , t ) , E [ u ⋆ ( X t , t ) − X ˙ t X t , t ] ⟩ = 0.
Therefore,
L ( u ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] + L ( u ⋆ ) . L(u)=\mathbb{E}\left[\left\|u(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]+L(u^\star). L ( u ) = E [ ∥ u ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] + L ( u ⋆ ) .
This proves both the optimality of u ⋆ u^\star u ⋆ and the excess-risk identity.
Lemma D.3 (Uniform linear growth and parameter regularity of bounded smooth networks). Let
u θ : R d × [ 0 , 1 ] → R d u_\theta:\mathbb{R}^d\times[0,1]\to\mathbb{R}^d u θ : R d × [ 0 , 1 ] → R d be a fully connected feedforward network with depth D D D , hidden width W W W , and parameters θ ∈ Θ \theta\in\Theta θ ∈ Θ . Suppose that Θ ⊂ R P \Theta\subset\mathbb{R}^P Θ ⊂ R P is nonempty, compact, and convex. Suppose that the activation function σ : R → R \sigma:\mathbb{R}\to\mathbb{R} σ : R → R satisfies
σ ∈ C 2 ( R ) , sup z ∈ R ∣ σ ′ ( z ) ∣ ≤ M 1 , sup z ∈ R ∣ σ ′ ′ ( z ) ∣ ≤ M 2 , ∣ σ ( 0 ) ∣ ≤ M 0 . \sigma\in C^2(\mathbb{R}),\qquad\sup_{z\in\mathbb{R}}|\sigma'(z)|\le M_1,\qquad\sup_{z\in\mathbb{R}}|\sigma''(z)|\le M_2,\qquad|\sigma(0)|\le M_0. σ ∈ C 2 ( R ) , z ∈ R sup ∣ σ ′ ( z ) ∣ ≤ M 1 , z ∈ R sup ∣ σ ′′ ( z ) ∣ ≤ M 2 , ∣ σ ( 0 ) ∣ ≤ M 0 . Then there exist finite constants
A N N , B N N > 0 , A_{\mathrm{NN}},B_{\mathrm{NN}}>0, A NN , B NN > 0 , depending only on the architecture, parameter constraint, and activation constants, such that
∥ u θ ( x , t ) ∥ 2 ≤ A N N + B N N ∥ x ∥ 2 \|u_\theta(x,t)\|_2\le A_{\mathrm{NN}}+B_{\mathrm{NN}}\|x\|_2 ∥ u θ ( x , t ) ∥ 2 ≤ A NN + B NN ∥ x ∥ 2 for every
θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] . \theta\in\Theta,\qquad x\in\mathbb{R}^d,\qquad t\in[0,1]. θ ∈ Θ , x ∈ R d , t ∈ [ 0 , 1 ] . Moreover, for every fixed finite dataset
D N = { Z i } i = 1 N , \mathcal{D}_N=\{Z_i\}_{i=1}^N, D N = { Z i } i = 1 N , the empirical flow-matching loss
L ^ N ( θ ) = 1 N ∑ i = 1 N ℓ θ ( Z i ) \widehat{L}_N(\theta)=\frac{1}{N}\sum_{i=1}^N\ell_\theta(Z_i) L N ( θ ) = N 1 i = 1 ∑ N ℓ θ ( Z i ) is twice continuously differentiable in θ \theta θ . There exists a finite constant α N < ∞ \alpha_N<\infty α N < ∞ , depending on the fixed dataset, architecture, parameter constraint, and activation constants, such that
∥ ∇ L ^ N ( θ ) − ∇ L ^ N ( θ ′ ) ∥ 2 ≤ α N ∥ θ − θ ′ ∥ 2 \left\|\nabla\widehat{L}_N(\theta)-\nabla\widehat{L}_N(\theta')\right\|_2\le\alpha_N\|\theta-\theta'\|_2 ∇ L N ( θ ) − ∇ L N ( θ ′ ) 2 ≤ α N ∥ θ − θ ′ ∥ 2 for every θ , θ ′ ∈ Θ \theta,\theta'\in\Theta θ , θ ′ ∈ Θ . Thus, for smooth activations, empirical smoothness is compatible with bounded-parameter finite-dataset training on the compact convex region Θ \Theta Θ . The projected recursion in Assumption 3.4 ensures that all optimization iterates remain in Θ \Theta Θ by Lemma 3.5. The empirical proximal Polyak–Łojasiewicz condition, the interior operating regime, and the uniform-in-N N N empirical-constant condition remain separate optimization assumptions.
Proof. Let
h 0 = ( x , t ) ∈ R d + 1 h_0=(x,t)\in\mathbb{R}^{d+1} h 0 = ( x , t ) ∈ R d + 1
denote the network input. Since
t ∈ [ 0 , 1 ] , t\in[0,1], t ∈ [ 0 , 1 ] ,
∥ h 0 ∥ 2 ≤ ∥ x ∥ 2 + 1. \lVert h_0\rVert_2\leq\lVert x\rVert_2+1. ∥ h 0 ∥ 2 ≤ ∥ x ∥ 2 + 1.
Write the hidden-layer recursion as
h ℓ + 1 = σ ( A ℓ h ℓ + b ℓ ) , ℓ = 0 , … , D − 1 , h_{\ell+1}=\sigma(A_\ell h_\ell+b_\ell),\qquad\ell=0,\ldots,D-1, h ℓ + 1 = σ ( A ℓ h ℓ + b ℓ ) , ℓ = 0 , … , D − 1 ,
where σ \sigma σ is applied coordinatewise. Since σ \sigma σ has bounded first derivative,
∣ σ ( z ) ∣ ≤ ∣ σ ( 0 ) ∣ + M 1 ∣ z ∣ . \lvert\sigma(z)\rvert\leq\lvert\sigma(0)\rvert+M_1\lvert z\rvert. ∣ σ ( z )∣ ≤ ∣ σ ( 0 )∣ + M 1 ∣ z ∣ .
Therefore, for a vector v v v ,
∥ σ ( v ) ∥ 2 ≤ M 1 ∥ v ∥ 2 + M 0 dim ( v ) . \lVert\sigma(v)\rVert_2\leq M_1\lVert v\rVert_2+M_0\sqrt{\dim(v)}. ∥ σ ( v ) ∥ 2 ≤ M 1 ∥ v ∥ 2 + M 0 dim ( v ) .
Because Θ \Theta Θ is compact and the network has finitely many layers and parameters, there exist finite constants
M A , M b > 0 M_A,M_b>0 M A , M b > 0
such that, for every layer and every θ ∈ Θ \theta\in\Theta θ ∈ Θ ,
∥ A ℓ ∥ o p ≤ M A , ∥ b ℓ ∥ 2 ≤ M b . \lVert A_\ell\rVert_{\mathrm{op}}\leq M_A,\qquad\lVert b_\ell\rVert_2\leq M_b. ∥ A ℓ ∥ op ≤ M A , ∥ b ℓ ∥ 2 ≤ M b .
Hence, after adjusting constants to absorb the finite layer widths, there exist
c 1 , c 2 > 0 c_1,c_2>0 c 1 , c 2 > 0
such that
∥ h ℓ + 1 ∥ 2 ≤ c 1 ∥ h ℓ ∥ 2 + c 2 . \lVert h_{\ell+1}\rVert_2\leq c_1\lVert h_\ell\rVert_2+c_2. ∥ h ℓ + 1 ∥ 2 ≤ c 1 ∥ h ℓ ∥ 2 + c 2 .
Iterating this recursion over the finitely many layers gives finite constants
a D , b D > 0 a_D,b_D>0 a D , b D > 0
such that
∥ h D ∥ 2 ≤ a D ∥ h 0 ∥ 2 + b D . \lVert h_D\rVert_2\leq a_D\lVert h_0\rVert_2+b_D. ∥ h D ∥ 2 ≤ a D ∥ h 0 ∥ 2 + b D .
The final affine output layer is controlled by the same compact-parameter argument. Thus, after enlarging the constants if necessary,
∥ u θ ( x , t ) ∥ 2 ≤ a D ( ∥ x ∥ 2 + 1 ) + b D = ( a D + b D ) + a D ∥ x ∥ 2 . \lVert u_\theta(x,t)\rVert_2\leq a_D(\lVert x\rVert_2+1)+b_D=(a_D+b_D)+a_D\lVert x\rVert_2. ∥ u θ ( x , t ) ∥ 2 ≤ a D (∥ x ∥ 2 + 1 ) + b D = ( a D + b D ) + a D ∥ x ∥ 2 .
The linear-growth conclusion follows by taking
A N N : = a D + b D , B N N : = a D . A_{\mathrm{NN}}:=a_D+b_D,\qquad B_{\mathrm{NN}}:=a_D. A NN := a D + b D , B NN := a D .
For the parameter-regularity claim, fix
D N = { Z i } i = 1 N . \mathcal{D}_N=\{Z_i\}_{i=1}^N. D N = { Z i } i = 1 N .
For every sample
Z i = ( X 0 , i , X 1 , i , t i ) , Z_i=(X_{0,i},X_{1,i},t_i), Z i = ( X 0 , i , X 1 , i , t i ) ,
the corresponding input
( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) ((1-t_i)X_{0,i}+t_iX_{1,i},t_i) (( 1 − t i ) X 0 , i + t i X 1 , i , t i )
and target velocity
X 1 , i − X 0 , i X_{1,i}-X_{0,i} X 1 , i − X 0 , i
are fixed finite vectors. Because the activation is C 2 C^2 C 2 , the map
θ ↦ u θ ( ( 1 − t i ) X 0 , i + t i X 1 , i , t i ) \theta\mapsto u_\theta((1-t_i)X_{0,i}+t_iX_{1,i},t_i) θ ↦ u θ (( 1 − t i ) X 0 , i + t i X 1 , i , t i )
is twice continuously differentiable. Consequently,
θ ↦ ℓ θ ( Z i ) \theta\mapsto\ell_\theta(Z_i) θ ↦ ℓ θ ( Z i )
is twice continuously differentiable, and hence so is L ^ N ( θ ) \widehat{L}_N(\theta) L N ( θ ) . Since Θ \Theta Θ is compact and
∇ 2 L ^ N ( θ ) \nabla^2\widehat{L}_N(\theta) ∇ 2 L N ( θ )
is continuous in θ \theta θ , the quantity
α N : = sup θ ∈ Θ ∥ ∇ 2 L ^ N ( θ ) ∥ o p \alpha_N:=\sup_{\theta\in\Theta}\left\|\nabla^2\widehat{L}_N(\theta)\right\|_{\mathrm{op}} α N := θ ∈ Θ sup ∇ 2 L N ( θ ) op
is finite. Since Θ \Theta Θ is convex, the line segment joining any two points
θ , θ ′ ∈ Θ \theta,\theta'\in\Theta θ , θ ′ ∈ Θ
remains in Θ \Theta Θ . Applying the fundamental theorem of calculus to the gradient along this segment yields
∥ ∇ L ^ N ( θ ) − ∇ L ^ N ( θ ′ ) ∥ 2 ≤ sup ξ ∈ Θ ∥ ∇ 2 L ^ N ( ξ ) ∥ o p ∥ θ − θ ′ ∥ 2 ≤ α N ∥ θ − θ ′ ∥ 2 . \left\|\nabla\widehat{L}_N(\theta)-\nabla\widehat{L}_N(\theta')\right\|_2
\leq\sup_{\xi\in\Theta}\left\|\nabla^2\widehat{L}_N(\xi)\right\|_{\mathrm{op}}\left\|\theta-\theta'\right\|_2
\leq\alpha_N\left\|\theta-\theta'\right\|_2. ∇ L N ( θ ) − ∇ L N ( θ ′ ) 2 ≤ ξ ∈ Θ sup ∇ 2 L N ( ξ ) op ∥ θ − θ ′ ∥ 2 ≤ α N ∥ θ − θ ′ ∥ 2 .
This proves the empirical smoothness compatibility claim.
Lemma D.4 (Boundedness of the truncated flow-matching loss). Suppose the endpoint-truncation event
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } \mathcal{E}_R:=\{\|X_0\|_2\leq R,\ \|X_1\|_2\leq R\} E R := { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } *holds. Then, for every θ ∈ Θ \theta\in\Theta θ ∈ Θ ,
ℓ θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ B ℓ ( R ) , \ell_\theta(Z)=\|u_\theta(X_t,t)-(X_1-X_0)\|_2^2\leq B_\ell(R), ℓ θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ B ℓ ( R ) , where
B ℓ ( R ) : = ( A N N + ( B N N + 2 ) R ) 2 . B_\ell(R):=(A_{\mathrm{NN}}+(B_{\mathrm{NN}}+2)R)^2. B ℓ ( R ) := ( A NN + ( B NN + 2 ) R ) 2 . Proof. On E R \mathcal{E}_R E R , Lemma D.1 gives
∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R . \|X_t\|_2\leq R,\qquad\|X_1-X_0\|_2\leq2R. ∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R . By the smooth-network linear-growth bound in Lemma D.3 ,
∥ u θ ( X t , t ) ∥ 2 ≤ A N N + B N N ∥ X t ∥ 2 ≤ A N N + B N N R . \|u_\theta(X_t,t)\|_2\leq A_{\mathrm{NN}}+B_{\mathrm{NN}}\|X_t\|_2\leq A_{\mathrm{NN}}+B_{\mathrm{NN}}R. ∥ u θ ( X t , t ) ∥ 2 ≤ A NN + B NN ∥ X t ∥ 2 ≤ A NN + B NN R . Therefore,
ℓ θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ ( ∥ u θ ( X t , t ) ∥ 2 + ∥ X 1 − X 0 ∥ 2 ) 2 ≤ ( A N N + ( B N N + 2 ) R ) 2 = B ℓ ( R ) . \begin{aligned}
\ell_\theta(Z)&=\|u_\theta(X_t,t)-(X_1-X_0)\|_2^2\\
&\leq\left(\|u_\theta(X_t,t)\|_2+\|X_1-X_0\|_2\right)^2\\
&\leq\left(A_{\mathrm{NN}}+(B_{\mathrm{NN}}+2)R\right)^2\\
&=B_\ell(R).
\end{aligned} ℓ θ ( Z ) = ∥ u θ ( X t , t ) − ( X 1 − X 0 ) ∥ 2 2 ≤ ( ∥ u θ ( X t , t ) ∥ 2 + ∥ X 1 − X 0 ∥ 2 ) 2 ≤ ( A NN + ( B NN + 2 ) R ) 2 = B ℓ ( R ) .
Lemma D.5 (Metric-entropy uniform-convergence bound for the truncated loss class). Let G \mathcal{G} G be a class of real-valued functions satisfying 0 ≤ g ( z ) ≤ B 0 \le g(z) \le B 0 ≤ g ( z ) ≤ B for every g ∈ G g \in\mathcal{G} g ∈ G , where B > 0 B > 0 B > 0 . Let Z 1 , … , Z N Z_1,\ldots,Z_N Z 1 , … , Z N be independent samples, and suppose that, for some V ≥ 1 V \ge1 V ≥ 1 and some entropy radius C e n t ≥ max { e , B } C_{\mathrm{ent}} \ge\max\{e,B\} C ent ≥ max { e , B } , the class satisfies
log N ( ε , G , ∥ ⋅ ∥ ∞ ) ≤ V log ( C e n t ε ) , 0 < ε ≤ B . \log\mathcal{N}(\varepsilon,\mathcal{G},\|\cdot\|_{\infty}) \le V\log\left(\frac{C_{\mathrm{ent}}}{\varepsilon}\right), \qquad0 < \varepsilon\le B. log N ( ε , G , ∥ ⋅ ∥ ∞ ) ≤ V log ( ε C ent ) , 0 < ε ≤ B . Define
C ‾ e n t ( B , N ) : = e N C e n t B . \overline{C}_{\mathrm{ent}}(B,N) := e^{\frac{N C_{\mathrm{ent}}}{B}}. C ent ( B , N ) := e B N C ent . Then
C ‾ e n t ( B , N ) ≥ e , \overline{C}_{\mathrm{ent}}(B,N) \ge e, C ent ( B , N ) ≥ e , and, with probability at least 1 − δ 1-\delta 1 − δ ,
sup g ∈ G ∣ E [ g ( Z ) ] − 1 N ∑ i = 1 N g ( Z i ) ∣ ≤ C B V log ( C ‾ e n t ( B , N ) ) + log ( 1 / δ ) N , \sup_{g\in\mathcal{G}}\left|\mathbb{E}[g(Z)]-\frac{1}{N}\sum_{i=1}^{N}g(Z_i)\right| \le CB\sqrt{\frac{V\log\left(\overline{C}_{\mathrm{ent}}(B,N)\right)+\log(1/\delta)}{N}}, g ∈ G sup E [ g ( Z )] − N 1 i = 1 ∑ N g ( Z i ) ≤ C B N V log ( C ent ( B , N ) ) + log ( 1/ δ ) , where C > 0 C>0 C > 0 is a universal constant.
In particular, consider the truncated flow-matching squared-loss class
G W , D ( R ) : = { Z ↦ ℓ θ ( Z ) 1 E R : θ ∈ Θ } , \mathcal{G}_{W,D}^{(R)} := \left\{Z \mapsto\ell_{\theta}(Z)\mathbf{1}_{\mathcal{E}_R}:\theta\in\Theta\right\}, G W , D ( R ) := { Z ↦ ℓ θ ( Z ) 1 E R : θ ∈ Θ } , where
ℓ θ ( Z ) : = ∥ u θ ( ( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 \ell_{\theta}(Z) := \left\|u_{\theta}((1-t)X_0+tX_1,t)-(X_1-X_0)\right\|_2^2 ℓ θ ( Z ) := ∥ u θ (( 1 − t ) X 0 + t X 1 , t ) − ( X 1 − X 0 ) ∥ 2 2 and
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . \mathcal{E}_R := \{\|X_0\|_2\le R,\ \|X_1\|_2\le R\}. E R := { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . For the i i i -th sample, write
E R , i : = { ∥ X 0 , i ∥ 2 ≤ R , ∥ X 1 , i ∥ 2 ≤ R } . \mathcal{E}_{R,i} := \{\|X_{0,i}\|_2\le R,\ \|X_{1,i}\|_2\le R\}. E R , i := { ∥ X 0 , i ∥ 2 ≤ R , ∥ X 1 , i ∥ 2 ≤ R } . For the bounded-parameter smooth-activation neural velocity class in Lemma D.3 , there exists a finite constant
L l o s s ( R ) > 0 L_{\mathrm{loss}}(R)>0 L loss ( R ) > 0 such that
sup Z : E R ∣ ℓ θ ( Z ) − ℓ θ ′ ( Z ) ∣ ≤ L l o s s ( R ) ∥ θ − θ ′ ∥ 2 \sup_{Z:\mathcal{E}_R}|\ell_{\theta}(Z)-\ell_{\theta'}(Z)|\le L_{\mathrm{loss}}(R)\|\theta-\theta'\|_2 Z : E R sup ∣ ℓ θ ( Z ) − ℓ θ ′ ( Z ) ∣ ≤ L loss ( R ) ∥ θ − θ ′ ∥ 2 for every θ , θ ′ ∈ Θ \theta,\theta'\in\Theta θ , θ ′ ∈ Θ . Consequently, there exists a finite raw entropy radius
C s m ( R ) ≥ max { e , B ℓ ( R ) } , C_{\mathrm{sm}}(R)\ge\max\{e,B_{\ell}(R)\}, C sm ( R ) ≥ max { e , B ℓ ( R )} , depending only on the architecture, parameter constraint, activation derivative bounds, and truncation radius, such that
log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( C s m ( R ) ε ) , 0 < ε ≤ B ℓ ( R ) . \log\mathcal{N}\left(\varepsilon,\mathcal{G}_{W,D}^{(R)},\|\cdot\|_{\infty}\right)\le P\log\left(\frac{C_{\mathrm{sm}}(R)}{\varepsilon}\right),\qquad0<\varepsilon\le B_{\ell}(R). log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( ε C sm ( R ) ) , 0 < ε ≤ B ℓ ( R ) . Define
C ‾ s m ( R , N ) : = e N C s m ( R ) B ℓ ( R ) \overline{C}_{\mathrm{sm}}(R,N):=e^{\frac{N C_{\mathrm{sm}}(R)}{B_{\ell}(R)}} C sm ( R , N ) := e B ℓ ( R ) N C sm ( R ) and
C s m ( R , N ) : = P log ( C ‾ s m ( R , N ) ) . C_{\mathrm{sm}}(R,N):=P\log\left(\overline{C}_{\mathrm{sm}}(R,N)\right). C sm ( R , N ) := P log ( C sm ( R , N ) ) .
Then, with probability at least
sup θ ∈ Θ ∣ E [ ℓ θ ( Z ) 1 ϵ R ] − 1 N ∑ i = 1 N ℓ θ ( Z i ) 1 R , i ∣ ≤ C B ℓ ( R ) c s m ( R , N ) + log ( 1 / δ ) N . \sup_{\theta\in\Theta}\left|\mathbb{E}\left[\ell_\theta(Z)1_{\epsilon_R}\right]-\frac{1}{N}\sum_{i=1}^{N}\ell_\theta(Z_i)1_{\mathcal{R},i}\right|\leq CB_\ell(R)\sqrt{\frac{c_{\mathrm{sm}}(R,N)+\log(1/\delta)}{N}}. θ ∈ Θ sup E [ ℓ θ ( Z ) 1 ϵ R ] − N 1 i = 1 ∑ N ℓ θ ( Z i ) 1 R , i ≤ C B ℓ ( R ) N c sm ( R , N ) + log ( 1/ δ ) .
Proof. We first prove the generic statement. Let
ϵ N : = B N . \epsilon_N:=\frac{B}{N}. ϵ N := N B .
Since
0 < ϵ N ≤ B , 0<\epsilon_N\leq B, 0 < ϵ N ≤ B ,
the assumed covering-number bound implies that there exists an ϵ N \epsilon_N ϵ N net
N ϵ N ⊆ G \mathcal{N}_{\epsilon_N}\subseteq\mathcal{G} N ϵ N ⊆ G
with cardinality satisfying
log ∣ N ϵ N ∣ ≤ V log ( C e n t ϵ N ) = V log ( N C e n t B ) . \begin{aligned}
\log\left|\mathcal{N}_{\epsilon_N}\right|\leq V\log\left(\frac{C_{\mathrm{ent}}}{\epsilon_N}\right) \\
&=V\log\left(\frac{NC_{\mathrm{ent}}}{B}\right).
\end{aligned} log ∣ N ϵ N ∣ ≤ V log ( ϵ N C ent ) = V log ( B N C ent ) .
For every h ∈ N ϵ N h\in\mathcal{N}_{\epsilon_N} h ∈ N ϵ N , Hoeffding’s inequality gives
P ( ∣ E [ h ( Z ) ] − 1 N ∑ i = 1 N h ( Z i ) ∣ > B log ( 2 ∣ N ϵ N ∣ / δ ) 2 N ) ≤ δ ∣ N ϵ N ∣ . \mathbb{P}\left(\left|\mathbb{E}[h(Z)]-\frac{1}{N}\sum_{i=1}^{N}h(Z_i)\right|>B\sqrt{\frac{\log\left(2\left|\mathcal{N}_{\epsilon_N}\right|/\delta\right)}{2N}}\right)\leq\frac{\delta}{\left|\mathcal{N}_{\epsilon_N}\right|}. P ( E [ h ( Z )] − N 1 i = 1 ∑ N h ( Z i ) > B 2 N log ( 2 ∣ N ϵ N ∣ / δ ) ) ≤ ∣ N ϵ N ∣ δ .
Applying the union bound over h ∈ N ϵ N h\in\mathcal{N}_{\epsilon_N} h ∈ N ϵ N shows that, with probability at least 1 − δ 1-\delta 1 − δ ,
sup h ∈ N ϵ N ∣ E [ h ( Z ) ] − 1 N ∑ i = 1 N h ( Z i ) ∣ ≤ B log ( 2 ∣ N ϵ N ∣ / δ ) 2 N . \sup_{h\in\mathcal{N}_{\epsilon_N}}\left|\mathbb{E}[h(Z)]-\frac{1}{N}\sum_{i=1}^{N}h(Z_i)\right|\leq B\sqrt{\frac{\log\left(2\left|\mathcal{N}_{\epsilon_N}\right|/\delta\right)}{2N}}. h ∈ N ϵ N sup E [ h ( Z )] − N 1 i = 1 ∑ N h ( Z i ) ≤ B 2 N log ( 2 ∣ N ϵ N ∣ / δ ) .
Because
and
C ‾ e n t ( B , N ) = e N C e n t B , \overline{C}_{\mathrm{ent}}(B,N)=e^{\frac{NC_{\mathrm{ent}}}{B}}, C ent ( B , N ) = e B N C ent ,
we have
log ( 2 ∣ N ϵ N ∣ / δ ) ≤ V log ( C ‾ e n t ( B , N ) ) + log ( 1 / δ ) . \log\left(2\left|\mathcal{N}_{\epsilon_N}\right|/\delta\right)\leq V\log\left(\overline{C}_{\mathrm{ent}}(B,N)\right)+\log(1/\delta). log ( 2 ∣ N ϵ N ∣ / δ ) ≤ V log ( C ent ( B , N ) ) + log ( 1/ δ ) .
Now fix an arbitrary g ∈ G g\in\mathcal{G} g ∈ G , and let h g ∈ N ϵ N h_g\in\mathcal{N}_{\epsilon_N} h g ∈ N ϵ N satisfy
∥ g − h g ∥ ∞ ≤ ϵ N . \|g-h_g\|_\infty\leq\epsilon_N. ∥ g − h g ∥ ∞ ≤ ϵ N .
Then
∣ E [ g ( Z ) ] − 1 N ∑ i = 1 N g ( Z i ) ∣ ≤ ∣ E [ h g ( Z ) ] − 1 N ∑ i = 1 N h g ( Z i ) ∣ + 2 ϵ N . \left|\mathbb{E}[g(Z)]-\frac{1}{N}\sum_{i=1}^{N}g(Z_i)\right|
\leq\left|\mathbb{E}[h_g(Z)]-\frac{1}{N}\sum_{i=1}^{N}h_g(Z_i)\right|
+2\epsilon_N. E [ g ( Z )] − N 1 i = 1 ∑ N g ( Z i ) ≤ E [ h g ( Z )] − N 1 i = 1 ∑ N h g ( Z i ) + 2 ϵ N .
Since
2 ε N = 2 B N , 2\varepsilon_N = \frac{2B}{N}, 2 ε N = N 2 B ,
this approximation term is bounded by a universal constant multiple of
B V log C ‾ e n t ( B , N ) + log ( 1 / δ ) N . B\sqrt{\frac{V\log\overline{C}_{\mathrm{ent}}(B,N)+\log(1/\delta)}{N}}. B N V log C ent ( B , N ) + log ( 1/ δ ) .
Taking the supremum over g ∈ G g \in\mathcal{G} g ∈ G proves the generic claim.
We next verify the entropy condition for the truncated smooth-network loss class. On E R \mathcal{E}_R E R , Lemma D.1 gives
∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R . \lVert X_t\rVert_2 \le R,\qquad\lVert X_1-X_0\rVert_2 \le2R. ∥ X t ∥ 2 ≤ R , ∥ X 1 − X 0 ∥ 2 ≤ 2 R .
By Lemma D.4 ,
0 ≤ ℓ θ ( Z ) 1 E R ≤ B ℓ ( R ) . 0 \le\ell_\theta(Z)\mathbf{1}_{\mathcal{E}_R} \le B_\ell(R). 0 ≤ ℓ θ ( Z ) 1 E R ≤ B ℓ ( R ) .
Because the activation is smooth and the parameter region Θ \Theta Θ is compact, the map θ ↦ ℓ θ ( Z ) \theta\mapsto\ell_\theta(Z) θ ↦ ℓ θ ( Z ) is continuously differentiable jointly over Θ \Theta Θ and the compact truncated input–target domain. Hence there exists a finite constant L l o s s ( R ) > 0 L_{\mathrm{loss}}(R)>0 L loss ( R ) > 0 such that
sup Z : E R ∣ ℓ θ ( Z ) − ℓ θ ′ ( Z ) ∣ ≤ L l o s s ( R ) ∥ θ − θ ′ ∥ 2 . \sup_{Z:\mathcal{E}_R}\left|\ell_\theta(Z)-\ell_{\theta'}(Z)\right|
\le L_{\mathrm{loss}}(R)\lVert\theta-\theta'\rVert_2. Z : E R sup ∣ ℓ θ ( Z ) − ℓ θ ′ ( Z ) ∣ ≤ L loss ( R ) ∥ θ − θ ′ ∥ 2 .
for every θ , θ ′ ∈ Θ \theta,\theta'\in\Theta θ , θ ′ ∈ Θ . Since the indicator 1 E R \mathbf{1}_{\mathcal{E}_R} 1 E R does not depend on θ \theta θ , the same inequality holds for the truncated losses.
Because Θ \Theta Θ is compact in R P \mathbb{R}^P R P , there exists a finite constant C Θ > 0 C_\Theta>0 C Θ > 0 such that, for every 0 < η ≤ C Θ 0<\eta\le C_\Theta 0 < η ≤ C Θ , the parameter region has an η \eta η net with cardinality at most ( C Θ η ) P \left(\frac{C_\Theta}{\eta}\right)^P ( η C Θ ) P . Consequently, for every 0 < ε ≤ C Θ L l o s s ( R ) 0<\varepsilon\le C_\Theta L_{\mathrm{loss}}(R) 0 < ε ≤ C Θ L loss ( R ) ,
log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( C Θ L l o s s ( R ) ε ) . \log\mathcal{N}\left(\varepsilon,\mathcal{G}_{W,D}^{(R)},\lVert\cdot\rVert_\infty\right)
\le P\log\left(\frac{C_\Theta L_{\mathrm{loss}}(R)}{\varepsilon}\right). log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( ε C Θ L loss ( R ) ) .
For larger ε \varepsilon ε , a one-element cover suffices after increasing C Θ C_\Theta C Θ if necessary. Therefore, defining
C s m ( R ) : = max { e , B ℓ ( R ) , C Θ L l o s s ( R ) } , C_{\mathrm{sm}}(R):=\max\left\{e,B_\ell(R),C_\Theta L_{\mathrm{loss}}(R)\right\}, C sm ( R ) := max { e , B ℓ ( R ) , C Θ L loss ( R ) } ,
we obtain
log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( C s m ( R ) ε ) , 0 < ε ≤ B ℓ ( R ) . \log\mathcal{N}\left(\varepsilon,\mathcal{G}_{W,D}^{(R)},\lVert\cdot\rVert_\infty\right)
\le P\log\left(\frac{C_{\mathrm{sm}}(R)}{\varepsilon}\right),
\qquad0<\varepsilon\le B_\ell(R). log N ( ε , G W , D ( R ) , ∥ ⋅ ∥ ∞ ) ≤ P log ( ε C sm ( R ) ) , 0 < ε ≤ B ℓ ( R ) .
Finally, apply the generic result with
V = P , B = B ℓ ( R ) , C e n t = C s m ( R ) . V=P,\qquad B=B_\ell(R),\qquad C_{\mathrm{ent}}=C_{\mathrm{sm}}(R). V = P , B = B ℓ ( R ) , C ent = C sm ( R ) .
Then
C ‾ e n t ( B , N ) = e N C s m ( R ) B ℓ ( R ) = C ‾ s m ( R , N ) , \overline{C}_{\mathrm{ent}}(B,N)
=e^{\frac{NC_{\mathrm{sm}}(R)}{B_\ell(R)}}
=\overline{C}_{\mathrm{sm}}(R,N), C ent ( B , N ) = e B ℓ ( R ) N C sm ( R ) = C sm ( R , N ) ,
and the claimed uniform-convergence bound follows.
Lemma D.6 (Tail control under sub-exponential endpoints). Suppose Assumption 3.1 holds and the neural velocity class satisfies the uniform linear-growth bound from Lemma D.3 . Define
ε t a i l ( R ) : = sup θ ∈ Θ E [ ℓ θ ( Z ) 1 E R c ] . \varepsilon_{\mathrm{tail}}(R):=\sup_{\theta\in\Theta}\mathbb{E}\left[\ell_\theta(Z)\mathbf{1}_{\mathcal{E}_R^c}\right]. ε tail ( R ) := θ ∈ Θ sup E [ ℓ θ ( Z ) 1 E R c ] .
where
E R : = { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } . \mathcal{E}_R := \{\|X_0\|_2 \le R, \|X_1\|_2 \le R\}. E R := { ∥ X 0 ∥ 2 ≤ R , ∥ X 1 ∥ 2 ≤ R } .
Then there exist constants
C t a i l , c t a i l > 0 C_{\mathrm{tail}},c_{\mathrm{tail}} > 0 C tail , c tail > 0
such that
ϵ t a i l ( R ) ≤ C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . \epsilon_{\mathrm{tail}}(R) \le C_{\mathrm{tail}}(1+R)^2 \exp(-c_{\mathrm{tail}}R/K_X). ϵ tail ( R ) ≤ C tail ( 1 + R ) 2 exp ( − c tail R / K X ) .
Proof. By the uniform linear-growth property from Lemma D.3 ,
∥ u θ ( X t , t ) ∥ 2 ≤ A N N + B N N ∥ X t ∥ 2 . \|u_\theta(X_t,t)\|_2 \le A_{\mathrm{NN}} + B_{\mathrm{NN}}\|X_t\|_2. ∥ u θ ( X t , t ) ∥ 2 ≤ A NN + B NN ∥ X t ∥ 2 .
For the linear path,
X t = ( 1 − t ) X 0 + t X 1 , X_t = (1-t)X_0 + tX_1, X t = ( 1 − t ) X 0 + t X 1 ,
so
∥ X t ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 . \|X_t\|_2 \le\|X_0\|_2 + \|X_1\|_2. ∥ X t ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 .
Also,
∥ X 1 − X 0 ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 . \|X_1-X_0\|_2 \le\|X_0\|_2 + \|X_1\|_2. ∥ X 1 − X 0 ∥ 2 ≤ ∥ X 0 ∥ 2 + ∥ X 1 ∥ 2 .
Therefore, after increasing constants if necessary, there exists C e n v > 0 C_{\mathrm{env}} > 0 C env > 0 such that
ℓ θ ( Z ) ≤ C e n v ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 ) \ell_\theta(Z) \le C_{\mathrm{env}}\left(1+\|X_0\|_2^2+\|X_1\|_2^2\right) ℓ θ ( Z ) ≤ C env ( 1 + ∥ X 0 ∥ 2 2 + ∥ X 1 ∥ 2 2 )
uniformly over θ ∈ Θ \theta\in\Theta θ ∈ Θ . Moreover,
E R c ⊆ { ∥ X 0 ∥ 2 > R } ∪ { ∥ X 1 ∥ 2 > R } . \mathcal{E}_R^c \subseteq\{\|X_0\|_2 > R\} \cup\{\|X_1\|_2 > R\}. E R c ⊆ { ∥ X 0 ∥ 2 > R } ∪ { ∥ X 1 ∥ 2 > R } .
Thus,
ϵ t a i l ( R ) ≤ C e n v ∑ j ∈ { 0 , 1 } E [ ( 1 + ∥ X j ∥ 2 2 ) 1 { ∥ X j ∥ 2 > R } ] . \epsilon_{\mathrm{tail}}(R) \le C_{\mathrm{env}} \sum_{j\in\{0,1\}} \mathbb{E}\left[(1+\|X_j\|_2^2)\mathbb{1}_{\{\|X_j\|_2>R\}}\right]. ϵ tail ( R ) ≤ C env j ∈ { 0 , 1 } ∑ E [ ( 1 + ∥ X j ∥ 2 2 ) 1 { ∥ X j ∥ 2 > R } ] .
Let
Y j : = ∥ X j ∥ 2 , j ∈ { 0 , 1 } . Y_j := \|X_j\|_2,\qquad j\in\{0,1\}. Y j := ∥ X j ∥ 2 , j ∈ { 0 , 1 } .
By Assumption 3.1,
P ( Y j > r ) ≤ c 0 exp ( − c 1 r / K X ) \mathbb{P}(Y_j>r) \le c_0\exp(-c_1r/K_X) P ( Y j > r ) ≤ c 0 exp ( − c 1 r / K X )
for every
Moreover,
E [ 1 { Y j > R } ] = P ( Y j > R ) ≤ c 0 exp ( − c 1 R / K X ) . \mathbb{E}\left[\mathbb{1}_{\{Y_j>R\}}\right] = \mathbb{P}(Y_j>R) \le c_0\exp(-c_1R/K_X). E [ 1 { Y j > R } ] = P ( Y j > R ) ≤ c 0 exp ( − c 1 R / K X ) .
For the quadratic contribution, the tail-integration identity gives
E [ Y j 2 1 { Y j > R } ] = R 2 P ( Y j > R ) + ∫ R ∞ 2 r P ( Y j > r ) d r . \mathbb{E}\left[Y_j^2\mathbb{1}_{\{Y_j>R\}}\right] = R^2\mathbb{P}(Y_j>R)
+ \int_R^\infty2r\mathbb{P}(Y_j>r)\,\mathrm{d}r. E [ Y j 2 1 { Y j > R } ] = R 2 P ( Y j > R ) + ∫ R ∞ 2 r P ( Y j > r ) d r .
Using the sub-exponential tail bound and setting
a : = c 1 / K X , a := c_1/K_X, a := c 1 / K X ,
we obtain
E [ Y j 2 1 { Y j > R } ] ≤ c 0 R 2 exp ( − a R ) + 2 c 0 ∫ R ∞ r exp ( − a r ) d r = c 0 R 2 exp ( − a R ) + 2 c 0 exp ( − a R ) ( R a + 1 a 2 ) . \mathbb{E}\left[Y_j^2\mathbf{1}_{\{Y_j>R\}}\right]\le c_0R^2\exp(-aR)
+2c_0\int_R^\infty r\exp(-ar)\,dr
= c_0R^2\exp(-aR)
+2c_0\exp(-aR)\left(\frac{R}{a}+\frac{1}{a^2}\right). E [ Y j 2 1 { Y j > R } ] ≤ c 0 R 2 exp ( − a R ) + 2 c 0 ∫ R ∞ r exp ( − a r ) d r = c 0 R 2 exp ( − a R ) + 2 c 0 exp ( − a R ) ( a R + a 2 1 ) .
After absorbing problem-dependent constants into C t a i l C_{\mathrm{tail}} C tail and, if necessary, decreasing the exponential rate to c t a i l c_{\mathrm{tail}} c tail , this gives
E [ ( 1 + Y j 2 ) 1 { Y j > R } ] ≤ C t a i l ( 1 + R ) 2 exp ( − c t a i l R / K X ) . \mathbb{E}\left[(1+Y_j^2)\mathbf{1}_{\{Y_j>R\}}\right]\le C_{\mathrm{tail}}(1+R)^2\exp(-c_{\mathrm{tail}}R/K_X). E [ ( 1 + Y j 2 ) 1 { Y j > R } ] ≤ C tail ( 1 + R ) 2 exp ( − c tail R / K X ) .
Applying this bound for
j = 0 and j = 1 , j=0 \qquad\text{and}\qquad j=1, j = 0 and j = 1 ,
and enlarging C t a i l C_{\mathrm{tail}} C tail if necessary, proves the claim.
Lemma D.7 (Uniform flow stability by Gronwall). Let u ⋆ u^\star u ⋆ be the target marginal velocity field, and let { u θ : θ ∈ Θ } \{u_\theta:\theta\in\Theta\} { u θ : θ ∈ Θ } be a class of learned velocity fields. Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ . Let Z t Z_t Z t and Y t θ Y_t^\theta Y t θ solve
d d t Z t = u ⋆ ( Z t , t ) , d d t Y t θ = u θ ( Y t θ , t ) , Y 0 θ = Z 0 ∼ π 0 . \frac{d}{dt}Z_t=u^\star(Z_t,t),\qquad
\frac{d}{dt}Y_t^\theta=u_\theta(Y_t^\theta,t),\qquad
Y_0^\theta=Z_0\sim\pi_0. d t d Z t = u ⋆ ( Z t , t ) , d t d Y t θ = u θ ( Y t θ , t ) , Y 0 θ = Z 0 ∼ π 0 . Suppose Assumption 3.7 holds. Then, by its path-consistency clause,
Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] , \operatorname{Law}(Z_t)=\rho_t\qquad\text{for every }t\in[0,1], Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] , and, in particular,
Law ( Z 1 ) = π 1 . \operatorname{Law}(Z_1)=\pi_1. Law ( Z 1 ) = π 1 . Moreover,
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( ∫ 0 1 E [ ∥ u θ ( Z t , t ) − u ⋆ ( Z t , t ) ∥ 2 2 ] d t ) 1 / 2 , W_2(\widehat{\pi}_1^\theta,\pi_1)\le K_{\mathrm{flow}}\left(\int_0^1\mathbb{E}\left[\left\|u_\theta(Z_t,t)-u^\star(Z_t,t)\right\|_2^2\right]\,dt\right)^{1/2}, W 2 ( π 1 θ , π 1 ) ≤ K flow ( ∫ 0 1 E [ ∥ u θ ( Z t , t ) − u ⋆ ( Z t , t ) ∥ 2 2 ] d t ) 1/2 , where
K f l o w = exp ( Λ f l o w ) K_{\mathrm{flow}}=\exp(\Lambda_{\mathrm{flow}}) K flow = exp ( Λ flow ) is the deterministic uniform flow-stability constant from Assumption 3.7 . Equivalently,
W 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w ( ∫ 0 1 E X t ∼ ρ t [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] d t ) 1 / 2 . W_2(\widehat{\pi}_1^\theta,\pi_1)\le K_{\mathrm{flow}}\left(\int_0^1\mathbb{E}_{X_t\sim\rho_t}\left[\left\|u_\theta(X_t,t)-u^\star(X_t,t)\right\|_2^2\right]\,dt\right)^{1/2}. W 2 ( π 1 θ , π 1 ) ≤ K flow ( ∫ 0 1 E X t ∼ ρ t [ ∥ u θ ( X t , t ) − u ⋆ ( X t , t ) ∥ 2 2 ] d t ) 1/2 .
Proof. Fix
and couple the learned and reference flows through the same initial condition
Y 0 θ = Z 0 ∼ π 0 . Y_0^\theta=Z_0\sim\pi_0. Y 0 θ = Z 0 ∼ π 0 .
By the path-consistency clause in Assumption 3.7 ,
Law ( Z 1 ) = π 1 . \operatorname{Law}(Z_1)=\pi_1. Law ( Z 1 ) = π 1 .
Consequently, the joint construction of
( Y 1 θ , Z 1 ) (Y^\theta_1,Z_1) ( Y 1 θ , Z 1 )
is a coupling of π ^ 1 θ \hat{\pi}^\theta_1 π ^ 1 θ and π 1 \pi_1 π 1 . Therefore,
W 2 2 ( π ^ 1 θ , π 1 ) ≤ E [ ∥ Y 1 θ − Z 1 ∥ 2 2 ] . W^2_2\left(\hat{\pi}^\theta_1,\pi_1\right) \leq\mathbb{E}\left[\left\|Y^\theta_1-Z_1\right\|_2^2\right]. W 2 2 ( π ^ 1 θ , π 1 ) ≤ E [ Y 1 θ − Z 1 2 2 ] .
Define
Δ t : = Y t θ − Z t . \Delta_t:=Y^\theta_t-Z_t. Δ t := Y t θ − Z t .
Then
d d t Δ t = u θ ( Y t θ , t ) − u ∗ ( Z t , t ) = ( u θ ( Y t θ , t ) − u θ ( Z t , t ) ) + ( u θ ( Z t , t ) − u ∗ ( Z t , t ) ) . \begin{aligned}
\frac{d}{dt}\Delta_t=u_\theta(Y^\theta_t,t)-u^*(Z_t,t) \\
&=\left(u_\theta(Y^\theta_t,t)-u_\theta(Z_t,t)\right)+\left(u_\theta(Z_t,t)-u^*(Z_t,t)\right).
\end{aligned} d t d Δ t = u θ ( Y t θ , t ) − u ∗ ( Z t , t ) = ( u θ ( Y t θ , t ) − u θ ( Z t , t ) ) + ( u θ ( Z t , t ) − u ∗ ( Z t , t ) ) .
For almost every t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , the spatial Lipschitz property of u θ u_\theta u θ gives
d d t ∥ Δ t ∥ 2 ≤ L θ ( t ) ∥ Δ t ∥ 2 + ∥ u θ ( Z t , t ) − u ∗ ( Z t , t ) ∥ 2 . \frac{d}{dt}\|\Delta_t\|_2\leq L_\theta(t)\|\Delta_t\|_2+\|u_\theta(Z_t,t)-u^*(Z_t,t)\|_2. d t d ∥ Δ t ∥ 2 ≤ L θ ( t ) ∥ Δ t ∥ 2 + ∥ u θ ( Z t , t ) − u ∗ ( Z t , t ) ∥ 2 .
Since
Gronwall’s inequality yields
∥ Δ 1 ∥ 2 ≤ ∫ 0 1 exp ( ∫ s 1 L θ ( r ) d r ) ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 d s ≤ K f l o w ∫ 0 1 ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 d s , \begin{aligned}
\|\Delta_1\|_2\leq\int_0^1\exp\left(\int_s^1L_\theta(r)\,dr\right)\|u_\theta(Z_s,s)-u^*(Z_s,s)\|_2\,ds \\
&\leq K_{\mathrm{flow}}\int_0^1\|u_\theta(Z_s,s)-u^*(Z_s,s)\|_2\,ds,
\end{aligned} ∥ Δ 1 ∥ 2 ≤ ∫ 0 1 exp ( ∫ s 1 L θ ( r ) d r ) ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 d s ≤ K flow ∫ 0 1 ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 d s ,
where the second inequality follows from
∫ 0 1 L θ ( r ) d r ≤ Λ f l o w . \int_0^1L_\theta(r)\,dr\leq\Lambda_{\mathrm{flow}}. ∫ 0 1 L θ ( r ) d r ≤ Λ flow .
By the Cauchy–Schwarz inequality,
∥ Δ 1 ∥ 2 2 ≤ K f l o w 2 ∫ 0 1 ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 2 d s . \|\Delta_1\|_2^2\leq K_{\mathrm{flow}}^2\int_0^1\|u_\theta(Z_s,s)-u^*(Z_s,s)\|_2^2\,ds. ∥ Δ 1 ∥ 2 2 ≤ K flow 2 ∫ 0 1 ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 2 d s .
Taking expectation and combining the result with the coupling inequality for W 2 W_2 W 2 gives
W 2 2 ( π ^ 1 θ , π 1 ) ≤ K f l o w 2 ∫ 0 1 E [ ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 2 ] d s . W^2_2\left(\hat{\pi}^\theta_1,\pi_1\right)\leq K_{\mathrm{flow}}^2\int_0^1\mathbb{E}\left[\|u_\theta(Z_s,s)-u^*(Z_s,s)\|_2^2\right]\,ds. W 2 2 ( π ^ 1 θ , π 1 ) ≤ K flow 2 ∫ 0 1 E [ ∥ u θ ( Z s , s ) − u ∗ ( Z s , s ) ∥ 2 2 ] d s .
Taking square roots proves the first stated inequality. The equivalent formulation follows from
Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] . \operatorname{Law}(Z_t)=\rho_t\qquad\text{for every }t\in[0,1]. Law ( Z t ) = ρ t for every t ∈ [ 0 , 1 ] .
Lemma D.8 (Numerical ODE discretization). Suppose the learned velocity field u θ u_\theta u θ satisfies the regularity assumptions required by a chosen ODE solver. Let π ^ 1 θ \widehat{\pi}_1^\theta π 1 θ denote the terminal law of the exact learned ODE, and let π ^ 1 , K θ \widehat{\pi}_{1,K}^\theta π 1 , K θ denote the terminal law obtained by a numerical solver with K K K steps. If the solver has distributional discretization error
W 2 ( π ^ 1 , K θ , π ^ 1 θ ) ≤ ϵ d i s c ( K ) , W_2\left(\widehat{\pi}_{1,K}^\theta,\widehat{\pi}_1^\theta\right) \le\epsilon_{\mathrm{disc}}(K), W 2 ( π 1 , K θ , π 1 θ ) ≤ ϵ disc ( K ) , then
W 2 ( π ^ 1 , K θ , π 1 ) ≤ W 2 ( π ^ 1 θ , π 1 ) + ϵ d i s c ( K ) . W_2\left(\widehat{\pi}_{1,K}^\theta,\pi_1\right) \le W_2\left(\widehat{\pi}_1^\theta,\pi_1\right) + \epsilon_{\mathrm{disc}}(K). W 2 ( π 1 , K θ , π 1 ) ≤ W 2 ( π 1 θ , π 1 ) + ϵ disc ( K ) . Proof. This follows immediately from the triangle inequality for W 2 W_2 W 2 :
W 2 ( π ^ 1 , K θ , π 1 ) ≤ W 2 ( π ^ 1 , K θ , π ^ 1 θ ) + W 2 ( π ^ 1 θ , π 1 ) . W_2\left(\widehat{\pi}_{1,K}^\theta,\pi_1\right) \le W_2\left(\widehat{\pi}_{1,K}^\theta,\widehat{\pi}_1^\theta\right) + W_2\left(\widehat{\pi}_1^\theta,\pi_1\right). W 2 ( π 1 , K θ , π 1 ) ≤ W 2 ( π 1 , K θ , π 1 θ ) + W 2 ( π 1 θ , π 1 ) . Substituting the assumed discretization bound proves the result.
Simulation Results
This section reports mechanism-oriented simulations for the finite-dataset flow-matching analysis. The experiments are designed to illustrate the distinct roles of the stored dataset size N N N , which controls the statistical discrepancy between the population objective L L L and the fixed empirical objective L ^ N \widehat{L}_N L N , and the optimization budget T T T , which controls the extent to which stochastic-gradient training minimizes that empirical objective.
The simulations are not proofs of the theorem and should not be interpreted as empirical verification of the formal sample-complexity exponent or the high-probability statement over datasets. Rather, they provide controlled diagnostics of whether the mechanisms separated in the theoretical decomposition are visible in a two-dimensional example. All reported numerical values are means over five independent seeds, with standard errors reported after the ± \pm ± symbol unless otherwise stated. The raw seed-level measurements are included in the supplementary material.
All experiments use the standard Gaussian source distribution
π 0 = N ( 0 , I 2 ) \pi_0 = \mathcal{N}(0, I_2) π 0 = N ( 0 , I 2 )
and an eight-component Gaussian-mixture target distribution π 1 \pi_1 π 1 . For each stored-dataset experiment and each seed, a finite dataset
D N = { ( X 0 , i , X 1 , i , t i ) } i = 1 N \mathcal{D}_N = \{(X_{0,i}, X_{1,i}, t_i)\}_{i=1}^{N} D N = {( X 0 , i , X 1 , i , t i ) } i = 1 N
is sampled once and reused during stochastic-gradient training. The interpolation path is
X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 . X_t = (1-t)X_0 + tX_1,\qquad\dot{X}_t = X_1 - X_0. X t = ( 1 − t ) X 0 + t X 1 , X ˙ t = X 1 − X 0 .
The learned velocity field is a multilayer perceptron u θ ( x , t ) u_\theta(x,t) u θ ( x , t ) . Training uses projected stochastic gradient descent with projection onto a global Euclidean parameter ball of radius 25. The observed parameter norms are approximately 11, well below the projection radius, so the projection does not appear to be active in these runs. Velocity loss is evaluated on independent validation samples unless otherwise stated. Terminal quality is measured using sliced Wasserstein distance, empirical W 2 W_2 W 2 , MMD, and scatter plots of samples generated by numerical integration of the learned ODE.
Endpoint Sanity Check
The endpoint sanity check verifies the probability-path convention used in the theory. If the variable used as the terminal endpoint has law π 0 \pi_0 π 0 , then the interpolation does not terminate at the target distribution. In contrast, when the terminal endpoint is sampled as X 1 ∼ π 1 X_1 \sim\pi_1 X 1 ∼ π 1 , the path reaches the target endpoint by construction.
The quantitative diagnostics agree with the visual comparison in Figure 1 . The incorrect endpoint construction has sliced Wasserstein distance 0.819 ± \pm ± 0.005, MMD 0.270 ± \pm ± 0.004, and empirical W 2 W_2 W 2 distance 1.317 ± \pm ± 0.013 from the target samples. The corrected construction has zero sample discrepancy in this diagnostic because it directly uses the target endpoint samples themselves. Thus, this experiment is retained as an implementation and notation sanity check, rather than as evidence for the learning or sample-complexity claims of the theorem.
Figure 1. Endpoint sanity check. The incorrect endpoint construction remains close to the Gaussian source, whereas the corrected construction terminates at the target mixture by construction. Three scatter plots compare target samples, an incorrect endpoint construction, and the corrected endpoint construction. The target and corrected endpoint panels show eight compact clusters arranged in a ring. The incorrect endpoint panel shows samples from a diffuse Gaussian source distribution instead of the target mixture.
Dataset-Size Scaling
The dataset-size experiment varies N N N while training each fixed empirical objective for T = 4000 T = 4000 T = 4000 projected-SGD updates. This diagnostic examines the finite-dataset component of the analysis: as the stored dataset changes, the empirical objective may provide a more or less accurate approximation to the population flow-matching objective.
The mean validation velocity losses are 3.004 ± \pm ± 0.042, 3.040 ± \pm ± 0.037, 3.033 ± \pm ± 0.050, 2.987 ± \pm ± 0.029, and 2.969 ± \pm ± 0.038 for N = 256 N = 256 N = 256 , 512, 1024, 2048, and 4096, respectively. Terminal sliced Wasserstein distance decreases from 0.649 ± \pm ± 0.016 at N = 256 N = 256 N = 256 to 0.538 ± \pm ± 0.017 at $N = 4096, although the trend is not monotone at intermediate values. Thus the experiment shows a modest finite-dataset effect under this optimizer and training budget. This is consistent with the theorem’s decomposition, which separates the finite-dataset contribution from optimization and approximation effects, but it does not by itself identify a sample-complexity exponent.
Figure 2. Dataset-size diagnostic. Points show seed means and error bars show standard errors over five seeds. Two side-by-side line plots show validation velocity loss and terminal sliced Wasserstein distance as functions of stored dataset size. Both horizontal axes use a logarithmic scale. Validation loss remains close to 3 across all dataset sizes, with a small improvement at the largest sizes. Terminal sliced Wasserstein distance decreases overall from the smallest to the largest dataset size, but not monotonically. Error bars show standard errors across five seeds.
Optimization-Budget Scaling
The optimization-budget experiment fixes N = 2048 N = 2048 N = 2048 and varies the number of empirical projected-SGD updates T T T . Since the exact empirical minimizer θ ^ N \hat{\theta}_N θ ^ N is unavailable, the smallest empirical loss observed along each seed’s training trajectory is used only as a visualization proxy for
L ^ N ( θ T ) − L ^ N ( θ ^ N ) . \hat{L}_N(\theta_T) - \hat{L}_N(\hat{\theta}_N). L ^ N ( θ T ) − L ^ N ( θ ^ N ) .
The empirical optimization proxy decreases from 0.740 ± 0.028 0.740 \pm0.028 0.740 ± 0.028 at T = 250 T = 250 T = 250 to 0 at T = 4000 T = 4000 T = 4000 , where the proxy minimum is attained by construction. Validation velocity loss decreases from 3.731 ± 0.030 3.731 \pm0.030 3.731 ± 0.030 at T = 250 T = 250 T = 250 to 3.008 ± 0.039 3.008 \pm0.039 3.008 ± 0.039 at T = 4000 T = 4000 T = 4000 . Thus additional optimization visibly improves both the empirical proxy and held-out loss, but held-out validation improves more slowly than the empirical proxy. This illustrates that reducing empirical optimization error alone need not eliminate finite-dataset statistical error, approximation error, or endpoint-tail effects.
The plotted proxy should not be interpreted as the exact empirical suboptimality appearing in Lemma 4.8 . It is included only as a qualitative diagnostic for finite-time optimization of the stored empirical objective.
Joint Dataset-Size and Optimization-Budget Diagnostic
The joint diagnostic varies N N N and T T T simultaneously. The theorem separates a finite-dataset statistical contribution from a finite-time empirical optimization contribution. Accordingly, this diagnostic examines whether the stored dataset size and the training budget can have visibly different effects on held-out velocity loss.
The heatmap in Figure 4 shows a consistent improvement as the projected-SGD budget increases. At N = 256 N = 256 N = 256 , validation loss decreases from 3.352 ± 0.083 3.352 \pm0.083 3.352 ± 0.083 at T = 500 T = 500 T = 500 to 3.086 ± 0.019 3.086 \pm0.019 3.086 ± 0.019 at T = 4000 T = 4000 T = 4000 .
Figure 4. Joint N N N -versus-T T T diagnostic for mean held-out velocity loss over five seeds. A heatmap shows validation velocity loss for three dataset sizes and three optimization budgets. Dataset size is on the vertical axis and optimization updates are on the horizontal axis. Brighter colors indicate larger validation loss and darker colors indicate smaller validation loss. For each dataset size, the cells become darker as the optimization budget increases from 500 to 4000 updates.
Figure 3. Optimization-budget diagnostic. Points show seed means and error bars show standard errors over five seeds. Two side-by-side line plots show how performance changes as the number of projected-SGD updates increases. The left plot shows empirical loss above a proxy minimum on logarithmic horizontal and vertical axes; it decreases sharply toward zero as the update budget increases. The right plot shows validation velocity loss on a logarithmic horizontal axis; it decreases more gradually and begins to flatten at larger budgets.
At N = 1024 N = 1024 N = 1024 , it decreases from 3.433 ± 0.047 3.433 \pm0.047 3.433 ± 0.047 to 2.934 ± 0.061 2.934 \pm0.061 2.934 ± 0.061 , and at N = 4096 N = 4096 N = 4096 , it decreases from 3.461 ± 0.037 3.461 \pm0.037 3.461 ± 0.037 to 2.917 ± 0.042 2.917 \pm0.042 2.917 ± 0.042 . Across this limited grid, increasing T T T has a clearer effect than increasing N N N . The diagnostic therefore supports the qualitative distinction between optimization budget and stored sample size, but it does not imply that either effect is monotone in general or that the asymptotic theorem’s rates can be read from this small grid.
Finite-Dataset Training Versus One-Pass Training
The main theorem analyzes stochastic-gradient training on a fixed empirical objective L ^ N \widehat{L}_N L N . As an ablation, we compare this finite-dataset protocol with a one-pass population-style protocol in which each update uses freshly generated flow-matching samples. These procedures optimize different objectives, so this comparison is outside the formal scope of the finite-dataset theorem.
Figure 5. Finite-dataset training versus one-pass training. Points show seed means and error bars show standard errors over five seeds. A line plot compares validation velocity loss for finite-dataset training and one-pass population training as the number of updates increases. Both curves decrease with more updates. The one-pass population curve is slightly below the finite-dataset curve at most budgets, and the two curves are close at the largest budget.
Both protocols improve with additional optimization. At T = 4000 T = 4000 T = 4000 , the finite-dataset validation loss is 3.008 ± 0.039 3.008 \pm0.039 3.008 ± 0.039 , while the one-pass validation loss is 2.984 ± 0.038 2.984 \pm0.038 2.984 ± 0.038 . This does not contradict the theorem: the one-pass method receives fresh samples at each update and therefore does not repeatedly optimize a single fixed empirical objective. The comparison illustrates why the finite-dataset analysis separately accounts for statistical error from the stored dataset and optimization error from approximately minimizing its empirical objective.
Coupling Choice in the Linear Path
The coupling experiment compares independent coupling and minibatch optimal-transport coupling for the same linear interpolation path. The relevant velocity-loss comparison evaluates each trained model on held-out validation data drawn from the same coupling used during training. For context, we also report independent-coupling validation loss for the OT-trained model, but this cross-coupling quantity is not the objective optimized by that model.
Table 1. Coupling comparison metrics. The same-coupling validation loss is the appropriate objective-specific velocity-regression quantity. The independent-coupling loss for the OT model is reported only as a cross-objective diagnostic.
Figure 6. Coupling comparison for the linear path. The scatter panels show one representative seed; the table reports five-seed summaries. Three side-by-side scatter plots compare target samples, generated samples from independent coupling, and generated samples from minibatch optimal-transport coupling. The target distribution has eight compact clusters arranged in a ring. The independent-coupling samples form a broad diffuse cloud. The optimal-transport-coupling samples are still diffuse, but are more concentrated near the target support.
The same-coupling validation loss is substantially smaller for minibatch OT coupling than for independent coupling, and the terminal sliced Wasserstein and empirical W 2 W_2 W 2 metrics are also improved on average. However, the two couplings define different regression problems, so their loss values should not be interpreted as a common-objective comparison. The high independent-coupling loss of the OT-trained model confirms that changing the coupling changes the learning problem itself. This supports treating Γ \Gamma Γ as part of the probability-path specification rather than as a cosmetic implementation detail.
Assumption Diagnostics
These plots are not proofs of the empirical proximal Polyak–Łojasiewicz condition, the interior operating regime required for inactive projection, the uniform-in-N N N empirical-constant condition, or a conditional stochastic-gradient variance bound. They are included only to assess whether the assumed optimization behavior is qualitatively plausible for the finite empirical objective in this controlled setting.
The PL-style diagnostic is noisy and should not be interpreted as empirical verification of gradient dominance. The longer-run empirical-loss baseline is not known to equal
L ^ N ( θ ^ N ) , \widehat{L}_N(\widehat{\theta}_N), L N ( θ N ) ,
Figure 7. Empirical optimization diagnostics. The PL-style plot pools seed-level trajectory points, while the variance plot reports seed means and standard errors. Two diagnostic plots are shown side by side. The left plot is a log-log scatter plot of empirical excess-loss proxy against squared gradient norm, pooling trajectory points from five seeds. The points form a noisy cloud rather than a clean line. The right plot is a log-log line plot of gradient variance versus minibatch size. Gradient variance decreases sharply as minibatch size increases, and error bars show standard errors across five seeds.
which is why the empirical PL condition remains an explicit assumption in the theory. The final parameter norms reported in the experiment logs are approximately 11, well below the projection radius 25. This observation is consistent with, but does not by itself verify, the interior operating regime assumed in the analysis.
The gradient-variance diagnostic is more direct. The estimated gradient variance decreases from 292.0 ± 55.2 292.0 \pm55.2 292.0 ± 55.2 for single-sample gradients to 1.28 ± 0.17 1.28 \pm0.17 1.28 ± 0.17 for minibatches of size 256. This observed reduction is consistent with the finite-dataset stochastic-gradient oracle formulation and with the appearance of a conditional variance quantity in the empirical optimization analysis. It does not, by itself, establish the uniform conditional variance assumption required by Lemma 4.8 .