Non-asymptotic Convergence of Discrete-time Diffusion Models: New Approach and Improved Rate

• URL: http://arxiv.org/abs/2402.13901v2
• Date: Thu, 30 May 2024 21:18:01 GMT
• Title: Non-asymptotic Convergence of Discrete-time Diffusion Models: New Approach and Improved Rate
• Authors: Yuchen Liang, Peizhong Ju, Yingbin Liang, Ness Shroff,
• Abstract summary: We establish convergence guarantees for substantially larger classes of distributions under DT diffusion processes. We then specialize our results to a number of interesting classes of distributions with explicit parameter dependencies. We propose a novel accelerated sampler and show that it improves the convergence rates of the corresponding regular sampler by orders of magnitude with respect to all system parameters.
• Score: 49.97755400231656
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The denoising diffusion model has recently emerged as a powerful generative technique that converts noise into data. While there are many studies providing theoretical guarantees for diffusion processes based on discretized stochastic differential equation (D-SDE), many generative samplers in real applications directly employ a discrete-time (DT) diffusion process. However, there are very few studies analyzing these DT processes, e.g., convergence for DT diffusion processes has been obtained only for distributions with bounded support. In this paper, we establish the convergence guarantee for substantially larger classes of distributions under DT diffusion processes and further improve the convergence rate for distributions with bounded support. In particular, we first establish the convergence rates for both smooth and general (possibly non-smooth) distributions having a finite second moment. We then specialize our results to a number of interesting classes of distributions with explicit parameter dependencies, including distributions with Lipschitz scores, Gaussian mixture distributions, and any distributions with early-stopping. We further propose a novel accelerated sampler and show that it improves the convergence rates of the corresponding regular sampler by orders of magnitude with respect to all system parameters. Our study features a novel analytical technique that constructs a tilting factor representation of the convergence error and exploits Tweedie's formula for handling Taylor expansion power terms.

Related papers

• Progressive Inference-Time Annealing of Diffusion Models for Sampling from Boltzmann Densities [85.83359661628575]
  We propose Progressive Inference-Time Annealing (PITA) to learn diffusion-based samplers.<n>PITA combines two complementary techniques: Annealing of the Boltzmann distribution and Diffusion smoothing.<n>It enables equilibrium sampling of N-body particle systems, Alanine Dipeptide, and tripeptides in Cartesian coordinates.
  arXiv  Detail & Related papers  (2025-06-19T17:14:22Z)
• Minimax Optimality of the Probability Flow ODE for Diffusion Models [8.15094483029656]
  This work develops the first end-to-end theoretical framework for deterministic ODE-based samplers. We propose a smooth regularized score estimator that simultaneously controls both the $L2$ score error and the associated mean Jacobian error. We demonstrate that the resulting sampler achieves the minimax rate in total variation distance, modulo logarithmic factors.
  arXiv  Detail & Related papers  (2025-03-12T17:51:29Z)
• Low-dimensional adaptation of diffusion models: Convergence in total variation [13.218641525691195]
  We investigate how diffusion generative models leverage (unknown) low-dimensional structure to accelerate sampling. Our findings provide the first rigorous evidence for the adaptivity of the DDIM-type samplers to unknown low-dimensional structure.
  arXiv  Detail & Related papers  (2025-01-22T16:12:33Z)
• Provable Acceleration for Diffusion Models under Minimal Assumptions [8.15094483029656]
  We propose a novel training-free acceleration scheme for score-based samplers. Under minimal assumptions, our scheme achieves $varepsilon$-accuracy in total variation within $widetildeO(d5/4/sqrtvarepsilon)$ iterations.
  arXiv  Detail & Related papers  (2024-10-30T17:59:06Z)
• Straightness of Rectified Flow: A Theoretical Insight into Wasserstein Convergence [54.580605276017096]
  Diffusion models have emerged as a powerful tool for image generation and denoising. Recently, Liu et al. designed a novel alternative generative model Rectified Flow (RF) RF aims to learn straight flow trajectories from noise to data using a sequence of convex optimization problems.
  arXiv  Detail & Related papers  (2024-10-19T02:36:11Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional general score-mismatched diffusion samplers. We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions. This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• $O(d/T)$ Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  We establish a fast convergence theory for a popular SDE-based sampler under minimal assumptions. Our analysis shows that, provided $ell_2$-accurate estimates of the score functions, the total variation distance between the target and generated distributions is upper bounded by $O(d/T)$. This is achieved through a novel set of analytical tools that provides a fine-grained characterization of how the error propagates at each step of the reverse process.
  arXiv  Detail & Related papers  (2024-09-27T17:59:10Z)
• A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models [45.60426164657739]
  We develop non-asymptotic convergence theory for a diffusion-based sampler. We prove that $d/varepsilon$ are sufficient to approximate the target distribution to within $varepsilon$ total-variation distance. Our results also characterize how $ell$ score estimation errors affect the quality of the data generation processes.
  arXiv  Detail & Related papers  (2024-08-05T09:02:24Z)
• Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution [67.9215891673174]
  We propose score entropy as a novel loss that naturally extends score matching to discrete spaces. We test our Score Entropy Discrete Diffusion models on standard language modeling tasks.
  arXiv  Detail & Related papers  (2023-10-25T17:59:12Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• Diffusion Models are Minimax Optimal Distribution Estimators [49.47503258639454]
  We provide the first rigorous analysis on approximation and generalization abilities of diffusion modeling. We show that when the true density function belongs to the Besov space and the empirical score matching loss is properly minimized, the generated data distribution achieves the nearly minimax optimal estimation rates.
  arXiv  Detail & Related papers  (2023-03-03T11:31:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.