12 Jan 2024 | Xunpeng Huang*,†, Difan Zou*§, Hanze Dong†, Yian Ma‡, and Tong Zhang‡
This paper addresses the challenge of sampling from general target distributions that do not satisfy the isoperimetric condition. The authors propose a novel method called Recursive Score Diffusion-based Monte Carlo (RS-DMC), which is an extension of the original Diffusion-based Monte Carlo (DMC) algorithm introduced by Huang et al. (2023). The key innovation in RS-DMC is a recursive score estimation method that divides the entire diffusion process into multiple segments, allowing for more efficient sampling of intermediate distributions.
The original DMC algorithm suffered from high gradient complexity due to its redundant design of score estimation. RS-DMC overcomes this issue by dividing the diffusion process into segments and formulating the score estimation step as a series of interconnected mean estimation and sampling subproblems. This recursive structure ensures that all sampling subproblems only need to handle strongly log-concave distributions, which can be efficiently sampled using standard Markov Chain Monte Carlo (MCMC) methods like Langevin Monte Carlo (LMC).
The authors prove that the gradient complexity of RS-DMC is quasi-polynomial in the error tolerance \(\epsilon\), significantly improving the exponential complexity of the original DMC algorithm. Under mild assumptions on the target distribution, RS-DMC is shown to converge to the target distribution in KL divergence with quasi-polynomial gradient complexity. This makes RS-DMC more efficient than Langevin-based algorithms, which typically require additional isoperimetric conditions or have exponential complexity in the dimension \(d\).
The paper also includes empirical results demonstrating the effectiveness of RS-DMC compared to other sampling methods, such as ULA and RDS. The experimental results show that RS-DMC can cover multiple modes and achieve balanced particle distribution, while maintaining fast local convergence. Overall, RS-DMC provides a novel and efficient approach to sampling from general non-log-concave distributions, with theoretical guarantees and practical performance.This paper addresses the challenge of sampling from general target distributions that do not satisfy the isoperimetric condition. The authors propose a novel method called Recursive Score Diffusion-based Monte Carlo (RS-DMC), which is an extension of the original Diffusion-based Monte Carlo (DMC) algorithm introduced by Huang et al. (2023). The key innovation in RS-DMC is a recursive score estimation method that divides the entire diffusion process into multiple segments, allowing for more efficient sampling of intermediate distributions.
The original DMC algorithm suffered from high gradient complexity due to its redundant design of score estimation. RS-DMC overcomes this issue by dividing the diffusion process into segments and formulating the score estimation step as a series of interconnected mean estimation and sampling subproblems. This recursive structure ensures that all sampling subproblems only need to handle strongly log-concave distributions, which can be efficiently sampled using standard Markov Chain Monte Carlo (MCMC) methods like Langevin Monte Carlo (LMC).
The authors prove that the gradient complexity of RS-DMC is quasi-polynomial in the error tolerance \(\epsilon\), significantly improving the exponential complexity of the original DMC algorithm. Under mild assumptions on the target distribution, RS-DMC is shown to converge to the target distribution in KL divergence with quasi-polynomial gradient complexity. This makes RS-DMC more efficient than Langevin-based algorithms, which typically require additional isoperimetric conditions or have exponential complexity in the dimension \(d\).
The paper also includes empirical results demonstrating the effectiveness of RS-DMC compared to other sampling methods, such as ULA and RDS. The experimental results show that RS-DMC can cover multiple modes and achieve balanced particle distribution, while maintaining fast local convergence. Overall, RS-DMC provides a novel and efficient approach to sampling from general non-log-concave distributions, with theoretical guarantees and practical performance.