wikillm

Paper · 2026-11-01 · cs.LG, cs.AI

Finite-Time Online Sample Complexity for Conditional Diffusion Models

Theory paper: conditional diffusion trained by online SGD on fresh denoising samples. A total-variation bound separates initialisation, discretisation, score-class approximation (M^(-eta_app)) and finite-time optimisation (N = RB samples) under a stated local PL assumption. Stopped-law rate: O~(eps) with M ~ eps^-(2+d_x'/alpha_x+d_y'/alpha_y) and N ~ eps^-2. No experiments test the rates.

Diffusion modelsScore matchingIntrinsic dimensiondiffusionconditional-generationsample-complexitystochastic-gradienttheory

arXivPDFMarkdown14 min read

AI-compiled by claude-haiku-5-5 on 2026-11-21, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Diffusion models make new data by learning, at every noise level, which direction leads back toward realistic examples. A conditional model also gets a side input, such as a prompt or a set of measurements, and has to learn that direction for every combination of input, condition and noise level.

This paper asks a question that many theory results skip. If the network is trained by taking one fresh batch of examples after another, never looping over a stored dataset, how far off is the distribution it samples from? The answer is split into named parts: how rich the network is, how much training budget is spent, how coarsely the reverse process is stepped, and where the sampler starts. Each part gets an explicit exponent. The result depends on assumptions the authors state rather than prove, most notably a Polyak-Lojasiewicz-type condition on the training loss, which says that a small gradient means the loss is close to its best value. The paper has no benchmark numbers. Its experiments are small synthetic pilots.

TL;DR

  • Analyses conditional diffusion trained by online SGD on a randomized-time denoising objective, where each step uses fresh samples §1 §2.
  • Gives a total-variation bound with four separate error terms: terminal initialisation, time discretisation, score-class approximation and finite-time optimisation §3.3 eq. 22.
  • The approximation term is O~(M^(-eta_app)), where eta_app depends on the smoothness and intrinsic dimensions of the response and conditioning variables §3.1 eq. 19 eq. 25.
  • The optimisation term rests on a localized PL assumption and a trajectory-containment assumption. The authors do not derive either for neural networks §3.2.
  • Relevant if you need a budget-style answer (how many samples, how big a network) under stated assumptions. Not relevant if you need validated rates for real models.

Problem

Analyses of conditional diffusion often assume the score estimator is an exact empirical or population risk minimiser. A finite run of stochastic gradient descent does not return such an estimator §1. The paper asks how the error of the network obtained after finitely many SGD updates propagates through the reverse diffusion to the law the sampler produces §1. The approximation side needs the joint geometry of the response and the condition, not just each one alone, because the two are not low-dimensional in a combined sense by default §3.1.

The guarantee compares the sampler to the conditional law after a short forward noising, stopped at a positive time t_0, rather than to the original data law. The original law needs an extra full-dimensional density assumption and a separate result §2 §3.6 app. D.

Method

Forward process and target. The forward process is the variance-preserving Ornstein-Uhlenbeck SDE with the standard Brownian motion, so that the state at time t is an exponentially shrunk copy of the data plus Gaussian noise with variance 1 - exp(-2t) eq. 1. The learned object is the conditional score of the noised state, and the reverse-time process driven by that score recovers the stopped law when started from the terminal law eq. 3 eq. 4. The kernel score of the transition, which is available in closed form, is the regression target eq. 2.

Score class. The score network is a time-gated sum of blockwise conditional approximants over a dyadic cover of time, with fixed smooth gates that SGD does not optimise eq. 5. The complexity index M is a calibrated approximation scale, not a parameter count and not the sample size §2.

Randomized-time objective. Time is discretised on a grid t_0 < t_1 < ... < t_K = T with steps Delta_k. An index J is drawn with probability proportional to Delta_k, which makes the expectation over J the time-weighted grid average used in the stability argument eq. 6. Each observation is a clean point, a condition, a grid index and Gaussian noise, from which the noised state and the kernel-score target are built eq. 7 eq. 8. The population loss is the expected squared error between the network and that target eq. 9. Its minimum over the class is the benchmark L*. The denoising identity shows that the loss equals a constant plus the squared distance to the true score, so the approximation error A_K(M) is the excess over that constant eq. 10 eq. 11 eq. 12 eq. 13 eq. 14.

Online SGD. At iteration r = 0, ..., R-1, a fresh mini-batch of B independent randomized-time observations is drawn and the parameters move by the step size times the mini-batch gradient eq. 15. The total number of online denoising samples is N = RB eq. 16. The output is the final iterate. The finite-time population optimisation error E_opt(N, M) is the expected excess of the final iterate over L* eq. 17. Algorithm 1 gives the training and sampling loop alg. 1.

Sampler. The implementable sampler starts from the standard Gaussian at time T and runs an exponential-integrator update per grid interval, with the learned score evaluated at the right endpoint of each interval eq. 18. Algorithm 1 uses the same update alg. 1. The training and sampling loop in pseudocode, following alg. 1 and the equations cited above:

Pseudocode
# Training: fresh randomized-time samples, one SGD step per mini-batch  [alg. 1]
# Input:  grid t[0..K] with t[K] = T; weights pi[k] = Delta_k / H_K
#         step sizes eta[r] = 2 / (mu (r + r0)); batch size B; steps R
# Output: trained parameters theta

def train_online(theta, grid, pi, eta, B, R):
    for r in range(R):
        # Fresh conditional samples from P_0; none are stored  [§2] [alg. 1]
        x0, y = sample_p0(B)                # (B, d_x), (B, d_y)
        # Grid index J per sample, with P(J = k) = pi[k]  [eq. 6]
        j = sample_categorical(pi, B)       # (B,)
        t = grid[j]                         # right endpoint t_J  [eq. 7]
        eps = sample_normal(B, d_x)         # (B, d_x)
        # Noised state X_t = e^(-t) X_0 + sigma_t eps  [eq. 7]
        sigma2 = 1 - exp(-2 * t)            # (B,)
        x_t = exp(-t) * x0 + sqrt(sigma2) * eps
        # Kernel-score target Z = -(X_t - e^(-t) X_0) / sigma_t^2  [eq. 8]
        target = -(x_t - exp(-t) * x0) / sigma2
        # Mini-batch mean squared denoising error  [eq. 9] [alg. 1]
        pred = score_net(theta, x_t, y, t)
        sq_err = (pred - target) ** 2
        loss = mean(sum(sq_err, dim=-1))
        # SGD step with the decreasing schedule  [eq. 15] [eq. 26]
        theta = theta - eta[r] * grad(loss, theta)
    return theta
Pseudocode
# Sampling: exponential-integrator reverse sweep  [eq. 18] [alg. 1]
# Input:  trained score_hat; condition y; grid t[0..K]
# Output: approximate draw at the stopping time t_0

def sample(score_hat, y, grid, K):
    # Start from the reference Gaussian at the terminal time T  [alg. 1]
    x = sample_normal(d_x)
    for k in range(K, 0, -1):
        # Interval length h = t_k - t_{k-1}  [§2]
        h = grid[k] - grid[k - 1]
        # Learned score evaluated at the right endpoint t_k  [§2]
        s = score_hat(x, y, grid[k])
        # Drift 2 (e^h - 1) s and noise scale sqrt(e^(2h) - 1)  [eq. 18]
        noise = sample_normal(d_x)
        x = exp(h) * x + 2 * (exp(h) - 1) * s
        x = x + sqrt(exp(2 * h) - 1) * noise
    return x

Main bound. Theorem 3.3 bounds the expected total variation between the stopped law and the generated law, over SGD randomness and the condition. It is a sum of an e^(-T) initialisation term, a K^(-1/2) discretisation term, and a square-root term whose argument is the grid weight H_K = T - t_0 times the sum of the approximation and optimisation errors §3.3 eq. 22. The constants depend only on the diffusion, moment and grid parameters. The decomposition itself does not tie the approximation complexity to the sample count §3.3.

Approximation term. Under Assumption 3.1 §3.1, the approximation error is bounded by a constant times M^(-eta_app) plus the largest grid step eq. 23, where eta_app = 2 alpha_x / (2 alpha_x + d_x' + (alpha_x / alpha_y) d_y') eq. 19. Under the grid condition Delta_max <= O~(M^(-eta_app)) eq. 24 this becomes O~(M^(-eta_app)) eq. 25. The statement uses the conditional approximation theorem of Tang et al. as an input and assumes that the class contains the localized blockwise approximants; the authors do not derive that containment §3.1 §4.

Optimisation term. Under Assumption 3.2 §3.2, which assumes local smoothness, a localized PL inequality eq. 21, an unbiased stochastic gradient with bounded variance, and that every SGD iterate stays in the local region, the decreasing step size eta_r = 2 / (mu_M (r + r_0)) with r_0 >= max{4, 2 L_M / mu_M} eq. 26 gives the bound in eq. 27. Its first term is an initialisation transient and its second is the stochastic-gradient term, scaled by 1 / (B (R + r_0)).

Stopped-law corollaries. Plugging the two bounds into Theorem 3.3 gives Corollary 3.5 eq. 28. With uniform constants across M (Corollary 3.6, eq. 29), E_opt is O(1/N) eq. 30, and the choices M, N, K and T in eq. 31 to eq. 34 give O~(eps) total variation for the stopped law.

Original law. Under the full-dimensional Assumption D.1 app. D, the authors add a smoothing-bias term and an OU-rescaling term (C_OU d_x t_0), use a later-time approximation rate with exponents rho_0, zeta_0 and gamma_0 eq. 35, and require M^(-rho_0) <= t_0 eq. 36 and a finer grid eq. 37. Corollary 3.7 gives the bound in eq. 38. Choosing t_0, M, N, K and T as in eq. 41 to eq. 42, with the exponents in eq. 39 and eq. 40, gives O~(eps) total variation to p_0 §3.6.

Hyperparameters

NameValueWhereNotes
Stopping time t_00 < t_0 < 1 <= T§2Fixed in the stopped-law results. Shrinks as t_0 = O~(eps^(a_beta)) for the original-law result, with a_beta = max{1, 2/beta} §3.6 eq. 41
Terminal time TTheta(log(1/eps))§3.5 eq. 34Enters through the e^(-T) initialisation term
Approximation exponent eta_app2 alpha_x / (2 alpha_x + d_x' + (alpha_x/alpha_y) d_y')§3.1 eq. 19alpha_x, alpha_y: smoothness; d_x', d_y': intrinsic dimensions
Approximation complexity M (stopped law)Theta~(eps^(-(2 + d_x'/alpha_x + d_y'/alpha_y)))§3.5 eq. 31Equals eps^(-2/eta_app)
Approximation complexity M (original law)Theta~(eps^(-Gamma_app,0))§3.6 eq. 39 eq. 41Gamma_app,0 is the max of two expressions in d_x, d_y', alpha_x, alpha_y, beta
Online samples N = RBTheta~(eps^(-2))§3.5 eq. 32Requires uniform optimisation constants eq. 29; not stated as a finite number
Grid size KTheta~((d_x + m_2) eps^(-2)) (stopped law); Theta~(eps^(-Lambda_0)) (original law)§3.5 eq. 33 §3.6 eq. 40 eq. 42Grid must satisfy the admissibility condition in app. E
Mini-batch size Bnot stated§2Any positive constant; it enters the bound as 1 / (B (R + r_0)) eq. 27
Iterations Rnot stated§2Only the relation N = RB is given eq. 16
SGD step size eta_r2 / (mu_M (r + r_0))§3.2 eq. 26 alg. 1mu_M is a constant of the objective; no numerical value is given
Step-size offset r_0>= max{4, 2 L_M / mu_M}eq. 26 alg. 1Depends on L_M and mu_M, which are not stated numerically
Local smoothness L_M, PL constant mu_M, gradient variance sigma_M^2not stated§3.2Assumed to exist, and to be uniform across M for the simplified rate eq. 29
Score network (pilots)fully connected MLP with Softplus_10 activationapp. FImplementation surrogate; not the theoretical blockwise class
Pilot optimiserplain SGD, step size c / (r + r_0)app. Fc and r_0 not stated
Pilot noise schedulelinear beta-scheduleapp. FValues not stated
Pilot widths, depth, B, R, seedsnot statedapp. FSingle-seed pilots per the authors

Results

Author-reported. This is a theory paper. It reports no benchmark numbers. The table gives the paper's bounds, not measurements. No baseline is compared numerically. tab. 1 is a structural comparison with related theory and says it is not a rate comparison. Setup for the pilots: synthetic Gaussian and normal-Laplace conditionals with analytic scores app. F.

SettingMetricBaselineThis paperSource
Stopped law, general boundE TV between p_{t_0} and samplernoneC_term e^(-T) + C_disc sqrt((d_x + m_2) / K) + C_stab sqrt(H_K [A_K(M) + E_opt(N, M)])§3.3 eq. 22
Stopped law, rateE TVnoneO~(eps) with M, N, K, T as in eq. 31 to eq. 34§3.5 eq. 34
ApproximationA_K(M)noneO~(M^(-eta_app)) under the grid condition§3.4 eq. 25
Optimisation, explicitE_opt(N, M)noneInit transient (Delta_0,M r_0^2 / (R + r_0)^2) plus SGD term (L_M sigma_M^2 / (mu_M^2 B (R + r_0)))§3.4 eq. 27
Original law, rateE TV to p_0noneO~(eps) with t_0, M, N, K as in eq. 41 and eq. 42§3.6 eq. 43
Pilot online trainingrandomized-time score MSEnonePilot only: "does not decrease systematically"; no sample-complexity trend claimedapp. F fig. 1

The constants C_term, C_disc, C_stab, C_1, C_2 and C_smooth are not given numerically. The O~ and Theta~ notation hides logarithmic factors and fixed dimension and moment factors §2. The paper therefore gives orders, not absolute sample or parameter budgets.

Paper vs code

No official code.

Searched: the paper's text, abstract and bibliography contain no repository or project-page link. The arXiv metadata has no comments field with a link. A GitHub repository search for "conditional diffusion sample complexity" and a search for "diffusion sample complexity bedi" both returned zero repositories. I did not search by organisation, because no organisation is named in the paper.

The experiments in appendix F are described only in prose and figures, with no released implementation, so nothing in them can be checked against code.

Differences between the theory and the pilots, both taken from the paper itself, not from code: the theory's step size is 2 / (mu_M (r + r_0)) eq. 26, while the pilots use c / (r + r_0) with c not stated app. F. The theory uses the blockwise smooth-gated class eq. 5, while the pilots use a single MLP, which the authors say does not instantiate the approximation construction app. F. The theory uses the OU forward process directly, while the pilots use a variance-preserving linear beta-schedule in a reparametrised time u, with effective OU time tau(u) = -log alpha(u) app. F. The pilot loss is the squared error between the network and the same kernel-score target, written with alpha(u) app. F, which matches eq. 8 and eq. 9 with sigma^2 = 1 - alpha^2.

Pitfalls

  • The optimisation bound is conditional. Assumption 3.2 asserts a localized PL inequality, smoothness and bounded gradient variance on a region that must contain every SGD iterate §3.2. The authors do not derive any of these for neural score networks, and their pilots do not test the PL inequality §4 app. F. Treat E_opt as a bound given the assumption, not a prediction.
  • Trajectory containment is almost-sure and unmodified. The theorem covers only the plain SGD trajectory, not projected or stopped variants. A high-probability version would need an extra exit-time argument §3.2 app. B.
  • Approximation containment is assumed, not derived. The bound needs the score class to contain the localized blockwise approximants of Tang et al. §3.1. The geometric assumptions alone do not give the rate §1.
  • The stopped law is not the data law. The main result compares to p_{t_0}. For strictly lower-dimensional data, p_0 is singular and its ambient total-variation distance to p_{t_0} does not vanish as t_0 goes to zero. Reporting the stopped-law result as convergence to the data distribution is wrong. The original-law result needs Assumption D.1, which requires a full-dimensional Holder density, a Besov-type integral condition, and a weighted gradient bound app. D §3.6.
  • The grid condition is not met by a uniform grid for small t_0. The stability lemma requires Delta_k <= kappa min{1, t_{k-1}} with kappa = Theta((T + log(1/t_0)) / K) app. E. Near t_0, a uniform grid over [t_0, T] does not satisfy this for small t_0, so the grid must be refined there. The paper cites Benton et al. for the construction and does not give an explicit grid app. E.
  • Uniform constants are a strong assumption for the simplified rate. The O(1/N) rate and the N = O~(eps^(-2)) claim need L_M, mu_M, sigma_M^2 and Delta_0,M bounded uniformly along the sequence of classes eq. 29. If they deteriorate with M, use the explicit bound eq. 28 instead, and the N requirement is no longer eps^(-2) §3.5.
  • Step size needs unknown constants. eta_r = 2 / (mu_M (r + r_0)) and r_0 >= max{4, 2 L_M / mu_M} require mu_M and L_M, which the paper does not estimate for any model. The pilots use c / (r + r_0) with c unstated app. F.
  • The training target is the kernel score, not the marginal score. The loss regresses onto the kernel-score target Z_J eq. 8 eq. 9. It is the marginal conditional score that the reverse process needs eq. 11. The identity holds only in expectation over the joint distribution, so per-sample targets are noisy and the variance is absorbed in sigma_M^2 §2 §3.2.
  • The stability lemma uses the forward-law error. The score error is measured on the forward marginals at the grid points, weighted by the grid steps, not on the sampler's own iterates app. E. Training on the same randomized-time distribution is what makes the two line up. Changing the time distribution J breaks the H_K weighting in eq. 22.
  • Initialisation is a free parameter. The sampler starts from N(0, I) instead of the terminal law p_T §2. That error is only absorbed into the e^(-T) term, so T must be chosen as Theta(log(1/eps)) §3.5.
  • Experiments do not verify the claims. The authors say the pilots show no clear learning curve, use single seeds, and do not validate the PL condition or the scaling exponents. Some score-MSE curves are numerically sensitive because the exact normal-Laplace score is hard to evaluate app. F fig. 1 fig. 9.
  • Figures are not reproduced here. The experiment figures are described in words only fig. 1 to fig. 9.

Lineage

  • Builds on: Tang, Lin and Yang (ICLR 2025), conditional approximation theorem and the blockwise construction used as an input §3.1 §3.4. Benton et al. (ICLR 2024), the admissible-grid condition and reverse-process stability §2 app. E.
  • Relates to: Gaur et al. (TMLR 2026) and Han et al. (ICLR 2024), finite-time gradient analyses for unconditional diffusion §1. Strasman et al. (arXiv:2607.04775), non-asymptotic SGD for unconditional score models §1. Fu et al. (arXiv:2403.11968), conditional statistical theory whose bounds depend on the ambient dimension §1. Hu et al. (ICLR 2025), conditional diffusion transformers with statistical rates §1.
  • Compared against: tab. 1 is a structural comparison (conditional, intrinsic dimension, gradient training, sampling bound) that the authors say is not a rate comparison §1.
  • Superseded by: none known.

Source and license

Adapted from “Finite-Time Online Sample Complexity for Conditional Diffusion Models” by Mudit Gaur, Prashant Trivedi, Sasidhar Kunapuli, Amrit Singh Bedi, Vaneet Aggarwal (arXiv:2611.01562), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.