Chain of Log-Concave Markov Chains

Saeed Saremi, Ji Won Park, Francis R. Bach

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.

The OAT sampling process evolves over time, where the conditional densities become increasingly well-behaved as more measurements are incorporated.

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.

Performance comparison (2-Wasserstein distance) of OAT against AAO and standard MCMC across different dimensions and noise levels.

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

BibTeX
@inproceedings{saremi2024chain,
  author = {Saeed Saremi and Ji Won Park and Francis R. Bach},
  title = {{Chain of Log-Concave Markov Chains}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=yiMB2DOjsR},
}
Figure