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

• Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Models [59.331993845831946]
  Diffusion models benefit from instillation of task-specific information into the score function to steer the sample generation towards desired properties. This paper provides the first theoretical study towards understanding the influence of guidance on diffusion models in the context of Gaussian mixture models.
  arXiv  Detail & Related papers  (2024-03-03T23:15:48Z)
• Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization [17.535229185525353]
  We introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Our results align with state-of-the-art achievements for diffusion models in $mathbbRd$ and further underscore the advantages of discrete diffusion models in comparison to the $mathbbRd$ setting.
  arXiv  Detail & Related papers  (2024-02-12T22:26:52Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Semi-Implicit Denoising Diffusion Models (SIDDMs) [50.30163684539586]
  Existing models such as Denoising Diffusion Probabilistic Models (DDPM) deliver high-quality, diverse samples but are slowed by an inherently high number of iterative steps. We introduce a novel approach that tackles the problem by matching implicit and explicit factors. We demonstrate that our proposed method obtains comparable generative performance to diffusion-based models and vastly superior results to models with a small number of sampling steps.
  arXiv  Detail & Related papers  (2023-06-21T18:49:22Z)
• 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)
• Blackout Diffusion: Generative Diffusion Models in Discrete-State Spaces [0.0]
  We develop a theoretical formulation for arbitrary discrete-state Markov processes in the forward diffusion process. As an example, we introduce Blackout Diffusion'', which learns to produce samples from an empty image instead of from noise.
  arXiv  Detail & Related papers  (2023-05-18T16:24:12Z)
• 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)
• Denoising Diffusion Samplers [41.796349001299156]
  Denoising diffusion models are a popular class of generative models providing state-of-the-art results in many domains. We explore a similar idea to sample approximately from unnormalized probability density functions and estimate their normalizing constants. While score matching is not applicable in this context, we can leverage many of the ideas introduced in generative modeling for Monte Carlo sampling.
  arXiv  Detail & Related papers  (2023-02-27T14:37:16Z)
• An optimal control perspective on diffusion-based generative modeling [9.806130366152194]
  We establish a connection between optimal control and generative models based on differential equations (SDEs) In particular, we derive a Hamilton-Jacobi-Bellman equation that governs the evolution of the log-densities of the underlying SDE marginals. We develop a novel diffusion-based method for sampling from unnormalized densities.
  arXiv  Detail & Related papers  (2022-11-02T17:59:09Z)

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.