Provable Acceleration for Diffusion Models under Minimal Assumptions

• URL: http://arxiv.org/abs/2410.23285v2
• Date: Sun, 03 Nov 2024 14:56:22 GMT
• Title: Provable Acceleration for Diffusion Models under Minimal Assumptions
• Authors: Gen Li, Changxiao Cai,
• Abstract summary: 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.
• Score: 8.15094483029656
• License:
• Abstract: While score-based diffusion models have achieved exceptional sampling quality, their sampling speeds are often limited by the high computational burden of score function evaluations. Despite the recent remarkable empirical advances in speeding up the score-based samplers, theoretical understanding of acceleration techniques remains largely limited. To bridge this gap, we propose a novel training-free acceleration scheme for stochastic samplers. Under minimal assumptions -- namely, $L^2$-accurate score estimates and a finite second-moment condition on the target distribution -- our accelerated sampler provably achieves $\varepsilon$-accuracy in total variation within $\widetilde{O}(d^{5/4}/\sqrt{\varepsilon})$ iterations, thereby significantly improving upon the $\widetilde{O}(d/\varepsilon)$ iteration complexity of standard score-based samplers. Notably, our convergence theory does not rely on restrictive assumptions on the target distribution or higher-order score estimation guarantees.

Related papers

• 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)
• Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models [21.961189407928853]
  We propose and analyze a training-free acceleration algorithm for SDE-style diffusion samplers, based on the KL Runge-Kutta method. The proposed sampler provably attains $varepsilon2$ error -- measured in divergence -- using $widetilde O(d3/2 / varepsilon)$ score function evaluations.
  arXiv  Detail & Related papers  (2024-10-07T05:34:51Z)
• $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)
• Accelerating Convergence of Score-Based Diffusion Models, Provably [44.11766377798812]
  Score-based diffusion models often suffer from low sampling speed due to extensive function evaluations needed during the sampling phase. We design novel training-free algorithms to accelerate popular deterministic (i.e., DDIM) and (i.e., DDPM) samplers. Our theory accommodates $ell$-accurate score estimates, and does not require log-concavity or smoothness on the target distribution.
  arXiv  Detail & Related papers  (2024-03-06T17:02:39Z)
• Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
  We show that a novel accelerated DDPM sampler achieves accelerated performance for three broad distribution classes not considered before. Our results show an improved dependency on the data dimension $d$ among accelerated DDPM type samplers.
  arXiv  Detail & Related papers  (2024-02-21T16:11:47Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• 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)
• Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints [29.227720674726413]
  We propose a fast minimum-norm (FMN) attack that works with different $ell_p$-norm perturbation models. Experiments show that FMN significantly outperforms existing attacks in terms of convergence speed and time.
  arXiv  Detail & Related papers  (2021-02-25T12:56:26Z)

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.