Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
Xunpeng Huang Difan Zou Hanze Dong Yian Ma Tong Zhang
To sample from a general target distribution $p_*\propto e^{-f_*}$ beyond the
isoperimetric condition, Huang et al. (2023) proposed to perform sampling
through reverse diffusion, giving rise to Diffusion-based Monte Carlo (DMC).
Specifically, DMC follows the reverse SDE of a diffusion process that
transforms the target distribution to the standard Gaussian, utilizing a
non-parametric score estimation. However, the original DMC algorithm
encountered high gradient complexity, resulting in an exponential dependency on
the error tolerance $\epsilon$ of the obtained samples. In this paper, we
demonstrate that the high complexity of DMC originates from its redundant
design of score estimation, and proposed a more efficient algorithm, called
RS-DMC, based on a novel recursive score estimation method. In particular, we
first divide the entire diffusion process into multiple segments and then
formulate the score estimation step (at any time step) as a series of
interconnected mean estimation and sampling subproblems accordingly, which are
correlated in a recursive manner. Importantly, we show that with a proper
design of the segment decomposition, all sampling subproblems will only need to
tackle a strongly log-concave distribution, which can be very efficient to
solve using the Langevin-based samplers with a provably rapid convergence rate.
As a result, we prove that the gradient complexity of RS-DMC only has a
quasi-polynomial dependency on $\epsilon$, which significantly improves
exponential gradient complexity in Huang et al. (2023). Furthermore, under
commonly used dissipative conditions, our algorithm is provably much faster
than the popular Langevin-based algorithms. Our algorithm design and
theoretical framework illuminate a novel direction for addressing sampling
problems, which could be of broader applicability in the community.