Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference Article Swipe

MAKE IMPACT

Xunpeng Huang , Difan Zou , Hanze Dong , Yi Zhang , Yi-An Ma , Tong Zhang · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2405.16387

To generate data from trained diffusion models, most inference algorithms, such as DDPM, DDIM, and other variants, rely on discretizing the reverse SDEs or their equivalent ODEs. In this paper, we view such approaches as decomposing the entire denoising diffusion process into several segments, each corresponding to a reverse transition kernel (RTK) sampling subproblem. Specifically, DDPM uses a Gaussian approximation for the RTK, resulting in low per-subproblem complexity but requiring a large number of segments (i.e., subproblems), which is conjectured to be inefficient. To address this, we develop a general RTK framework that enables a more balanced subproblem decomposition, resulting in $\tilde O(1)$ subproblems, each with strongly log-concave targets. We then propose leveraging two fast sampling algorithms, the Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD), for solving these strongly log-concave subproblems. This gives rise to the RTK-MALA and RTK-ULD algorithms for diffusion inference. In theory, we further develop the convergence guarantees for RTK-MALA and RTK-ULD in total variation (TV) distance: RTK-ULD can achieve $ε$ target error within $\tilde{\mathcal O}(d^{1/2}ε^{-1})$ under mild conditions, and RTK-MALA enjoys a $\mathcal{O}(d^{2}\log(d/ε))$ convergence rate under slightly stricter conditions. These theoretical results surpass the state-of-the-art convergence rates for diffusion inference and are well supported by numerical experiments.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2405.16387

PDF

https://arxiv.org/pdf/2405.16387

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4399115588

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4399115588

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2405.16387

Digital Object Identifier

Title

Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-05-26

Full publication date if available

Authors

Xunpeng Huang, Difan Zou, Hanze Dong, Yi Zhang, Yi-An Ma, Tong Zhang

List of authors in order

Landing page

https://arxiv.org/abs/2405.16387

Publisher landing page

PDF URL

https://arxiv.org/pdf/2405.16387

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2405.16387

Direct OA link when available

Concepts

Inference, Kernel (algebra), Diffusion, Computer science, Transition (genetics), Kernel smoother, Statistical physics, Kernel method, Mathematics, Artificial intelligence, Chemistry, Physics, Thermodynamics, Discrete mathematics, Radial basis function kernel, Biochemistry, Support vector machine, Gene

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload