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.

通过逆扩散过程进行采样的 RS-DMC 算法，利用新颖的递归评分估计方法，设计高效的算法来解决 Diffusion-based Monte Carlo 中高梯度复杂度问题，并在常用耗散条件下证明其比常用 Langevin-based 算法速度更快，为解决采样问题提供了新的方向。