Research map / Learning theory and algorithms / Sample complexity
On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)
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.
Theoretical analysis of latent Diffusion Transformers under a low-dimensional linear latent assumption, giving score approximation, sample complexity, distribution recovery, and SETH-based computational limits with almost-linear-time inference and training criteria.
Problem
Understanding the statistical rates (score approximation, estimation, distribution recovery) and computational limits (quadratic attention cost in forward inference and backward training) of latent diffusion transformers when data lies on an unknown low-dimensional linear subspace.
Approach
Combines the low-dimensional linear latent score decomposition with transformer universal approximation to bound DiT score approximation and estimation error, and uses fine-grained complexity (SETH, tensor trick, low-rank approximation) to give norm-based efficiency thresholds and almost-linear-time forward and backward algorithms.
Key results
- Score approximation error bound for latent DiT score network that is sub-linear in latent dimension, with model size depending on latent dimension d_0 = dL.
- Score estimation sample complexity tilde-O(1/(n^{1/3} T_0 T) * 2^{(1/eps)^{2L}} + ...), with a double exponential factor in the first term.
- Under SETH, no sub-quadratic algorithm exists for approximate DiT inference when entries of W_K A_1, W_Q A_2, W_OV A_3 are bounded by C_b sqrt(log L); almost-linear L^{1+o(1)} inference and training algorithms exist under o(sqrt(log L)) bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a latent DiT score network under the low-dimensional linear latent space assumption | Latent DiT score approximation · Latent DiT score approximation | L2 score approximation error: \epsilon\cdot \sqrt{d_0}/\sigma(t) | Helped |
| Use the learned DiT score estimator for the discretized backward process | Latent DiT · Generated data distribution | total variation distance: \tilde{\mathcal{O}}(\sqrt{\xi(n,\epsilon,L) \cdot \log n}) | Helped |
| Keep the latent/token dimension d=\mathcal{O}(\log L) and norm bound \Gamma=o(\sqrt{\log L}) | DiT gradient computation · ADiTGC | runtime: L^{1+o(1)} | Helped |
| Keep d=\mathcal{O}(\log L) and B=o(\sqrt{\log L}) | DiT inference · ADiTI | runtime: L^{1+o(1)} | Helped |
| Increase the latent dimension d_0 | Latent DiT · Score and distribution estimation | estimation error | Hurt |
Surprising findings
- The sample complexity bound has a double exponential factor 2^{(1/eps)^{2L}}, which prevents balancing approximation and sample error terms, so the rate is not consistent in n.
Limitations
- Double exponential factor in sample complexity suggests a gap in understanding of transformer universality for DiTs.
- Results are theoretical, with no practical implementation or experiments.
- Efficiency results are necessary but not sufficient conditions; hardness is worst-case.
Experimental setup
Builds on: score decomposition under low-dimensional latent space transformer universal approximation via piecewise approximation tensor trick SETH
Closest papers by meaning
- On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimality (ICLR 2025 · similarity 0.92)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.88)
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.88)
- FasterDiT: Towards Faster Diffusion Transformers Training without Architecture Modification (NeurIPS 2024 · similarity 0.88)
- Layer- and Timestep-Adaptive Differentiable Token Compression Ratios for Efficient Diffusion Transformers (CVPR 2025 · similarity 0.88)
- Q-DiT: Accurate Post-Training Quantization for Diffusion Transformers (CVPR 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.