Finite-Time Online Sample Complexity for Conditional Diffusion Models
Mudit Gaur, Prashant Trivedi, Sasidhar Kunapuli, Amrit Singh Bedi, Vaneet Aggarwal
Abstract
We study the finite-time training and sampling error of conditional diffusion models trained by online stochastic-gradient denoising score matching. Rather than assuming access to an exact empirical or population risk minimizer, we analyze the score network produced after a finite number of stochastic-gradient updates under an explicit localized Polyak--Łojasiewicz (PL) condition, stochastic-gradient regularity, and a trajectory-containment assumption. Our analysis separates the network approximation complexity from the online training-sample budget and propagates both errors through the reverse diffusion process. Under anisotropic smoothness, a joint intrinsic-dimensional structure for the data and conditioning variables, sub-exponential tails, and explicit approximation-class compatibility, we obtain a conditional score approximation error of order \[ \widetilde{\mathcal O}\!\left(M^{-η_{\mathrm{app}}}\right), \qquad η_{\mathrm{app}} = \frac{2α_x} {2α_x+d_x'+(α_x/α_y)d_y'}, \] where \(M\) denotes the approximation complexity, \(d_x'\) and \(d_y'\) are the intrinsic response and conditioning dimensions, and \(α_x,α_y\) are their corresponding smoothness exponents. For \(N=RB\) online denoising samples used by SGD, the finite-time optimization error is controlled explicitly in terms of the PL, smoothness, gradient-noise, and initialization constants. Combining these ingredients with reverse-process stability yields a total-variation bound that decomposes into terminal-initialization, time-discretization, approximation/localization, and finite-time optimization errors.