Research map / Learning theory and algorithms / Sample complexity
Improved Sample Complexity Bounds for Diffusion Model Training
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that score matching ERM over ReLU networks learns diffusion scores in a (1-δ)-quantile L2 sense with polylog(1/γ) samples, yielding DDPM sampling guarantees with an exponential improvement in depth and Wasserstein error over prior sample complexity bounds.
Problem
Sample complexity of learning score functions with neural networks via score matching so that DDPM produces samples close in TV and Wasserstein; prior bounds are exponential in depth and polynomial in 1/gamma.
Approach
Relaxes the L2 score accuracy requirement to a (1-δ)-quantile error measure, which can be learned from polylogarithmic-in-1/γ samples for each time t independent of σ_t, and shows this weaker guarantee still suffices for fast DDPM sampling via a TV-conditioning argument.
Key results
- Sample complexity O~(d^2 P D/eps^5 * log Theta * log^3(1/gamma)) for DDPM output eps-close in TV to gamma*m2-close in W2, versus prior poly(1/gamma) and exponential-in-D bounds.
- Main lemma: (1-δ)-quantile score accuracy eps/sigma_t achieved with m ~ O~((d + log(1/δ_train)) P D / (eps^2 δ_score)) log(Theta/δ_train) samples, independent of sigma_t.
- Hard instances show L2 score learning requires poly(1/gamma) samples in general.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the (1−δ)-quantile error guarantee instead of requiring L²-accurate scores | Score-matching training for DDPM · Diffusion model score training | sample complexity: \widetilde O\left(\frac{d^2 P D}{\varepsilon^5} \cdot \log \Theta \cdot {\log^3\frac{1}{\gamma}}\right) versus \widetild | Helped |
| Require L² accuracy for score estimates | Score learning for diffusion models · Smoothed distributions at small σ | sample complexity: m < \frac{R^2}{\varepsilon^2\sigma^2} | Hurt |
| Use quantile-error score estimates in place of L² estimates | DDPM sampling · Sampling to Wasserstein error γ | sample complexity dependence on γ: O(\log^3\frac{1}{\gamma}) versus \poly(\frac{1}{\gamma}) | Helped |
Surprising findings
- Learning the score in L2 to accuracy eps/sigma_t is information-theoretically impossible with polylogarithmic samples in 1/sigma, even though score matching + DDPM still works in practice on such examples.
Limitations
- Analyzes the empirical minimizer over ReLU networks, not SGD optimization
- Worse polynomial dependence on eps (eps^-5 in the stated theorem) compared with prior work
- Assumes neural networks can represent the score to required accuracy (A2) and second moment bounded by poly(d)
Experimental setup
Metrics: sample complexity bound TV distance 2-Wasserstein distance
Baselines: Block et al. 2020 score matching bound
Builds on: DDPM Chen et al. sampling guarantees Block et al. score matching sample complexity Girsanov-based KL analysis
Closest papers by meaning
- Align Your Steps: Optimizing Sampling Schedules in Diffusion Models (ICML 2024 · similarity 0.89)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.89)
- Assessing the quality of denoising diffusion models in Wasserstein distance: noisy score and optimal bounds (NeurIPS 2025 · similarity 0.88)
- The Emergence of Reproducibility and Consistency in Diffusion Models (ICML 2024 · similarity 0.88)
- Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models (NeurIPS 2025 · similarity 0.88)
- Dimension-free Score Matching and Time Bootstrapping for Diffusion Models (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.