Research map / Learning theory and algorithms / Sample complexity
Dimension-free Score Matching and Time Bootstrapping for Diffusion Models
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 nearly dimension-free sample complexity for denoising score matching with a single time-shared function approximator via martingale decomposition and variance bounds, and proposes Bootstrapped Score Matching (BSM) for variance reduction.
Problem
Sample complexity of learning diffusion score functions across all noise levels with a single function approximator, where prior bounds scale polynomially with dimension d (apart from log|H|) and data come from dependent Markov trajectories.
Approach
Uses a single function approximator jointly across timesteps, a martingale decomposition of the DSM error over dependent Markov-chain data, and second-order Tweedie variance bounds to get nearly dimension-free rates depending on smoothness L and log|H|; additionally bootstraps targets from the previous lower-noise score estimate to reduce variance.
Key results
- Establishes nearly dimension-free sample complexity bounds (log log d dependence) for joint DSM across noise levels, versus poly(d) in prior work.
- Experiment on 2-layer networks sampling from a Gaussian shows the L2 error across timesteps is consistent with the dimension-free bound after scaling.
- Proposes Bootstrapped Score Matching, reported to show improved performance over DSM in simple empirical studies, with no rigorous guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Bootstrapped Score Matching instead of Denoising Score Matching | score estimation in diffusion models · simple empirical studies | performance | Helped |
Limitations
- BSM lacks theoretical and rigorous empirical guarantees.
- Requires time discretization Delta = O(1/d^3) for the bound, and smoothness/Lipschitz assumptions on the function class.
- Bounds depend on log|H| and assume the true score lies in the (finite) hypothesis class.
Experimental setup
Metrics: L2 score estimation error
Baselines: denoising score matching
Builds on: denoising score matching Freedman's inequality Tweedie's formula
Closest papers by meaning
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.91)
- Beyond Scores: Proximal Diffusion Models (NeurIPS 2025 · similarity 0.90)
- Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models (NeurIPS 2024 · similarity 0.90)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.90)
- Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models (NeurIPS 2025 · similarity 0.90)
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.90)
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.