  This paper considers the problem of sampling from non-logconcave
distribution, based on queries of its unnormalized density. It first describes
a framework, Diffusion Monte Carlo (DMC), based on the simulation of a
denoising diffusion process with its score function approximated by a generic
Monte Carlo estimator. DMC is an oracle-based meta-algorithm, where its oracle
is the assumed access to samples that generate a Monte Carlo score estimator.
Then we provide an implementation of this oracle, based on rejection sampling,
and this turns DMC into a true algorithm, termed Zeroth-Order Diffusion Monte
Carlo (ZOD-MC). We provide convergence analyses by first constructing a general
framework, i.e. a performance guarantee for DMC, without assuming the target
distribution to be log-concave or satisfying any isoperimetric inequality. Then
we prove that ZOD-MC admits an inverse polynomial dependence on the desired
sampling accuracy, albeit still suffering from the curse of dimensionality.
Consequently, for low dimensional distributions, ZOD-MC is a very efficient
sampler, with performance exceeding latest samplers, including
also-denoising-diffusion-based RDMC and RS-DMC. Last, we experimentally
demonstrate the insensitivity of ZOD-MC to increasingly higher barriers between
modes or discontinuity in non-convex potential.
