Low-dimensional adaptation of diffusion models: Convergence in total variation

In plain words

Diffusion models make new samples by starting from random noise and removing it in steps. Each step uses an estimate of the score, the direction in which the data becomes more likely. Older theory said the number of steps needed grows with the full size of the data, such as the number of pixels in an image, which predicts far more steps than practice needs.

This paper shows that the two standard samplers, DDIM and DDPM, need a number of steps that depends on a smaller intrinsic dimension of the data, when the score is known exactly. It then extends the result to learned scores under stated conditions, and shows that the standard step-size choices are nearly the only ones that work in a single-step test. It is a proof paper with no experiments.

TL;DR

• DDIM and DDPM with their original coefficients reach total-variation error ε in about k/ε steps, up to log factors, where k is an intrinsic dimension of the data §3.1.
• No smoothness or log-concavity is assumed; the support must only be polynomially bounded §3.1.
• The bounds extend to learned scores under error conditions; DDIM needs stronger, Jacobian- and Hessian-level conditions than DDPM §3.2.
• A one-step lower bound shows the standard coefficients are almost necessary for this adaptation §3.3.

Problem

Under exact scores, the best earlier total-variation (TV) bound for both samplers needs on the order of d/ε iterations, where d is the ambient dimension §1. For ImageNet, the paper notes an ambient dimension of 150,528 pixels against an estimated intrinsic dimension of 43 or less, so that bound would suggest more than a million iterations, while practical samplers often produce good samples in a few hundred or a few tens of steps §1.

Earlier DDIM theory did not show adaptation to low-dimensional structure at all §1. Earlier DDPM adaptation results were mainly stated in KL divergence, which translates loosely into TV guarantees §1. The main assumptions are a polynomially bounded data support and a covering-number notion of intrinsic dimension §3.1.

Method

Setting. Data X_0 \sim p_{\mathrm{data}} in \mathbb{R}^d is noised by a discrete forward process X_t = \sqrt{\bar\alpha_t}X_0 + \sqrt{1-\bar\alpha_t}\,\bar W_t, where \bar\alpha_t = \prod_{i \le t}\alpha_i and \alpha_t = 1-\beta_t §2. The paper uses a fixed noise schedule: \beta_1 = T^{-c_0}, and \beta_{t+1} grows geometrically from \beta_1 at rate (1 + c_1\log T/T) and is capped at c_1\log T/T, so the schedule has an exponential phase followed by a flat phase §2. c_0, c_1 are called "large enough" numerical constants; no values are given §2.

Samplers. Both start from Y_T \sim \mathcal{N}(0, I_d) and step t = T, \dots, 1 §2:

• DDIM-type (deterministic): Y_{t-1} = (Y_t + \eta^{\mathrm{ddim}}_t\, s_t(Y_t))/\sqrt{\alpha_t} §2.
• DDPM-type (stochastic): Y_{t-1} = (Y_t + \eta^{\mathrm{ddpm}}_t\, s_t(Y_t) + \sigma^{\mathrm{ddpm}}_t Z_t)/\sqrt{\alpha_t}, with Z_t \sim \mathcal{N}(0, I_d) i.i.d. §2.

The DDIM coefficient used in the main theorems is the original DDIM choice, \eta^{\mathrm{ddim}}_t = (1-\alpha_t)/\big(1+\sqrt{(\alpha_t-\bar\alpha_t)/(1-\bar\alpha_t)}\big) §2, §3.1. The DDPM coefficients are the original ones, \eta^{\mathrm{ddpm}}_t = 1-\alpha_t and \sigma^{\mathrm{ddpm}}_t = \sqrt{(1-\alpha_t)(\alpha_t-\bar\alpha_t)/(1-\bar\alpha_t)} §2, §3.1. The paper lists other coefficient choices from prior work, which it does not analyse except through the general family in Theorem 5 §2, §3.2.2.

Continuous-time view. The forward process is the SDE dX_t = -\beta(t)X_t\,dt + \sqrt{2\beta(t)}\,dB_t. The probability-flow ODE and a reverse-time SDE both reverse it. A general family with a function \xi(t) \ge 0 interpolates between them: \xi = 0 gives the ODE and \xi = 1 the SDE §2. The paper proves its distributional claims for this family in the appendix app. A.

Assumptions.

1. Polynomially bounded support: \sup_{x \in \mathcal{X}_{\mathrm{data}}}\|x\|_2 \le R_0 with 1 \le R_0 \le T^{c_R} for a universal c_R > 0 §3.1.
2. Intrinsic dimension: for every \epsilon_0 > 0, \log N_{\epsilon_0}(\mathcal{X}_{\mathrm{data}}) \le C_{\mathrm{cover}}\, k \log(R_0/\epsilon_0), where N_{\epsilon_0} is the Euclidean covering number (Definition 1) §3.1.

The paper gives examples: k-dimensional linear subspaces, k-dimensional manifolds with a polynomially bounded support, and sets of doubling dimension k §3.1.

Score-estimation conditions for DDIM (Assumption 3). Each estimated score must be twice continuously differentiable, with \eta^{\mathrm{ddim}}_t\, v^\top \nabla s_t(x)\, v \ge -\tfrac14\|v\|_2^2 for all v, x. In addition, four time-averaged errors weighted by (1-\bar\alpha_t)^2 must be small: the score error, the Jacobian error in Frobenius norm, the trace of the Jacobian error, and the gradient of that trace §3.2.1.

Score-estimation condition for DDPM (Assumption 4). The time average of (1-\bar\alpha_t)\,\varepsilon^2_{\mathrm{score},t} must be at most \varepsilon^2_{\mathrm{ddpm\text{-}sc}}, where \varepsilon^2_{\mathrm{score},t} = \mathbb{E}\|s_t(X_t) - s^\star_t(X_t)\|_2^2 §3.2.2. No Jacobian or Hessian condition is needed §3.2.2.

Coefficient family for DDPM (Theorem 5). Any (\eta_t, \sigma_t) satisfying (1-\bar\alpha_t)(1-\eta_t/(1-\bar\alpha_t))^2 = \alpha_t - \bar\alpha_t - \sigma_t^2, together with \eta_t \le \min\{C_1(1-\alpha_t),\, C_2\sqrt{1-\alpha_t}\,\sigma_t,\, \tfrac12(1-\bar\alpha_t)\} for universal constants C_1, C_2 \ge \tfrac12 §3.2.2. The original DDPM choice is a special case §3.2.2. The paper notes that this family includes the DDIM coefficient as a special case, but its DDPM analysis does not cover the regime \eta_t \gtrsim (1-\alpha_t)\sigma_t^2 §5.

Score estimators. The paper states that estimators with finite-sample guarantees exist for both samplers: a plug-in score from a Gaussian kernel density estimator with a higher-order kernel for DDIM §3.2.1, app. I, and a thresholded kernel estimator for DDPM whose construction depends on whether d is small or large relative to (1-\bar\alpha_t)^{-1} §3.2.2, app. I. Both are constructed in the proofs; the paper does not give a training procedure for neural networks.

Lower bound. Theorem 7 bounds the TV distance after one update from the forward process, \Phi^\star_t(x,z) = (x + \eta_t s^\star_t(x) + \sigma_t z)/\sqrt{\alpha_t}, for the degenerate Gaussian target \mathcal{N}(0, \mathrm{diag}(I_k, 0_{d-k})) with k \le d/2 §3.3. Setting \sigma_t = 0 in the constraint that makes the bound vanish gives the original DDIM coefficient, and any \sigma_t > 0 satisfying the constraint gives a DDPM-type choice §3.3.

Proof structure. The sampling proofs are in the appendix: DDIM in app. C, DDPM in app. D, the differential-equation interpretation in app. A, the training bounds in app. I, and the lower bound in app. G. The main-text remark attributes the low-dimensional adaptivity to the posterior mean of X_0 in the reverse dynamics, via Tweedie's formula §3.2.2.

# DDIM-type sampler, deterministic  [§2] [§3.1]
# Input:  score(t, y) returns s_t(y); T; alphas; alpha_bars
# Output: sample y (approximates Y_0)
def ddim_sample(score, alphas, alpha_bars, T, dim):
    # Start from the Gaussian prior  [§2]
    y = standard_normal(dim)                  # Y_T ~ N(0, I_d)
    for t in range(T, 0, -1):
        # Original DDIM coefficient  [§2] [§3.1]
        eta = (1 - alphas[t]) / (
            1 + sqrt((alphas[t] - alpha_bars[t]) / (1 - alpha_bars[t])))
        # Deterministic update: no injected noise  [§2]
        y = (y + eta * score(t, y)) / sqrt(alphas[t])
    return y

# DDPM-type sampler, stochastic  [§2] [§3.2.2]
# Input:  score(t, y) returns s_t(y); T; alphas; alpha_bars
# Output: sample y (approximates Y_0)
def ddpm_sample(score, alphas, alpha_bars, T, dim):
    # Start from the Gaussian prior  [§2]
    y = standard_normal(dim)                  # Y_T ~ N(0, I_d)
    for t in range(T, 0, -1):
        # Original DDPM coefficients  [§2] [§3.2.2]
        eta = 1 - alphas[t]
        sigma = sqrt((1 - alphas[t]) * (alphas[t] - alpha_bars[t])
                     / (1 - alpha_bars[t]))
        # Fresh Gaussian noise each step  [§2]
        z = standard_normal(dim)              # Z_t ~ N(0, I_d)
        y = (y + eta * score(t, y) + sigma * z) / sqrt(alphas[t])
    return y

Hyperparameters

Universal constants inside the \lesssim bounds are not stated anywhere in the main text §3.

Results

Author-reported. The paper reports no experiments; all results are theorems with the setup stated in each row. Setup in all rows: data with a polynomially bounded support and intrinsic dimension k (Assumptions 1 and 2) §3.1.

Exact scores

Noisy scores

Score estimation (finite sample, adaptive)

Theorem 6 also bounds \varepsilon^2_{\mathrm{ddim\text{-}sc}}, because 1-\bar\alpha_t \le 1 §3.2.2.

Lower bound

Prior work, as compared in the paper. Author-reported comparison; the paper assumes accurate scores and ignores log factors tab. 1 tab. 2.

tab. 1 Prior DDIM theory (rates in TV, accurate scores):

tab. 2 Prior DDPM theory (rates in TV, accurate scores):

Paper vs code

No official code. The paper and its arXiv sources contain no code or repository links. A GitHub repository search for the title's keywords and for the method's terms (intrinsic dimension, diffusion, DDIM) returned no repositories, so no repository was cloned.

Pitfalls

• Unstated constants. c_0, c_1, c_R, C_{\mathrm{cover}}, C_1, C_2 and all universal constants in the \lesssim bounds are "large enough" or unspecified §2 §3. An implementer cannot pick a schedule from the paper alone; the bound says nothing about the constant in front of k\log^3 T/T.
• Log factors dominate at practical T. The rate k\log^3 T/T hides a cubic log, and the training bounds include \log^2(dR_0nT^{c_0}) and powers of R_0. The paper gives no finite-T constant, so the bounds say nothing about the error at, say, 20 steps.
• Exponents grow with k. In the training bounds the power of T is c_0(k^\star/2 + \dots), so it increases with k^\star, and R_0 enters the exponent. The paper does not discuss the size of these exponents for realistic k.
• Bounds are for TV at index 1. Theorems 1, 2, 4 and 5 bound \mathrm{TV}(p_{X_1}, p_{Y_1}). The main text does not state a bound on Y_0 against the data X_0. Treat the final-step bound as unstated.
• Prose and statement disagree in §3.3. The prose says to evaluate the TV distance between Y_t and X_t. Theorem 7 states \mathrm{TV}(\Phi^\star_t(X_t,Z_t), X_{t-1}). Implement the displayed theorem; the two are not the same quantity.
• The lower-bound target is degenerate. \mathcal{N}(0,\mathrm{diag}(I_k,0)) has no density on \mathbb{R}^d, so the standard score \nabla\log p is undefined on the null directions. The main text does not explain how s^\star_t is defined for this example §3.3.
• DDIM coefficient equality. §3.3 writes the DDIM coefficient as "\approx" the constraint solution. Solving the constraint with \sigma = 0 gives exactly \eta = (1-\alpha)/(1+\sqrt{(\alpha-\bar\alpha)/(1-\bar\alpha)}); I checked this algebraically and it is an equality, not an approximation.
• DDIM needs much stronger score accuracy. Assumption 3 requires errors in the Jacobian, the trace of the Jacobian and the gradient of that trace, plus a one-sided Hessian condition. The paper gives no way to check these for a trained network. DDPM needs only the time-averaged \ell_2 score error §3.2.2.
• Weighting differs between the two assumptions. The DDPM condition weights squared \ell_2 errors by (1-\bar\alpha_t) and averages over t. The DDIM condition weights errors by (1-\bar\alpha_t)^2. Neither is a per-step or supremum bound, so a single bad step can be hidden in the average.
• The estimators are existence results. Theorems 3 and 6 say a score estimator exists with these errors; they describe a kernel construction, not a training recipe for a neural score network. The DDPM estimator switches between two regimes depending on d versus (1-\bar\alpha_t)^{-1} §3.2.2, app. I.
• Assumption 2 is about log-covering numbers. k is defined through \log N_{\epsilon_0}, not through a manifold dimension. It can differ from the dimension of a manifold by constant and log factors, through C_{\mathrm{cover}}.
• Open gap. The DDPM analysis does not cover \eta_t \gtrsim (1-\alpha_t)\sigma_t^2, so the DDIM coefficient is not covered by the DDPM theorem in that regime §5.

Lineage

• Builds on: the DDPM update [Ho et al. 2020] and the DDIM update [Song et al. 2020], whose coefficients the paper analyses §2; the noise schedule of Li et al. 2024 (sharp) §2; and the score-based SDE and probability-flow ODE view §2.
• Compared against: prior DDIM and DDPM convergence theory, in tab. 1 and tab. 2. The DDPM comparison includes Li et al. 2024 (adapting), which is the DDPM low-dimensional result the paper improves on §3.1.
• Superseded by: not known from the content of this card.