Introduction
Sampling from complex, unnormalized probability densities is a fundamental challenge in statistics and machine learning. Traditional Markov Chain Monte Carlo (MCMC) methods often fail when distributions are non-log-concave (multi-modal) or ill-conditioned (highly elongated). This paper introduces a novel framework that transforms these difficult sampling problems into a sequence of manageable ones by smoothing the target distribution with Gaussian noise.
The One-At-A-Time (OAT) Sampling Framework
The proposed method builds on Walk-Jump Sampling, which involves a "Walk" phase (sampling from a smoothed distribution $p(y)$) and a "Jump" phase (denoising back to the target distribution $p(x)$). The innovation lies in the One-At-A-Time (OAT) scheme, where noisy measurements are generated sequentially.
In this scheme, the history of samples is efficiently summarized by a running empirical mean, making the process computationally lightweight despite its non-Markovian nature. Underdamped Langevin MCMC serves as the inner-loop engine, benefiting from the improved mathematical properties of these conditional densities.
Theoretical Insights: Persistence of Log-Concavity
A key theoretical contribution is the "Once Log-Concave, Always Log-Concave" property. The authors prove that if the initial smoothing is sufficient to make the first noisy measurement log-concave, every subsequent conditional distribution in the OAT sequence remains log-concave. Furthermore, the condition number of these distributions improves monotonically as more measurements are added, contrasting with "All-At-Once" (AAO) approaches where conditioning typically degrades.
Experimental Results and Performance
The OAT algorithm was tested on challenging synthetic densities, including high-dimensional Elliptical Gaussians and multi-modal Mixtures of Gaussians.
As illustrated in Figure 4, OAT consistently outperforms standard Langevin MCMC and All-At-Once (AAO) sampling. Notably, in multi-modal settings, OAT demonstrates the ability to "tunnel" between isolated modes, accurately capturing the distribution's mass even when modes are separated by regions of near-zero probability. The method shows remarkable stability in optimal noise levels even as dimensionality increases.
Conclusion
This work establishes a robust theoretical link between smoothing-based generative models and classical MCMC. By leveraging sequential measurements and the persistence of log-concavity, the OAT framework provides a scalable and accurate path for sampling from the difficult distributions encountered in physics and Bayesian inference. Future work will focus on optimizing inner-loop algorithms and refining score estimation for complex real-world data.
Summary updated