Alternating Diffusion for Proximal Sampling with Zeroth Order Queries
This provides a more efficient sampling method for machine learning and statistics, avoiding rejection sampling and enabling deterministic runtime, though it is incremental in improving upon existing proximal sampling techniques.
The paper tackles the problem of sampling from complex distributions without requiring gradient information, introducing a new proximal sampler that uses only zeroth-order queries and achieves exponential convergence under isoperimetric conditions.
This work introduces a new approximate proximal sampler that operates solely with zeroth-order information of the potential function. Prior theoretical analyses have revealed that proximal sampling corresponds to alternating forward and backward iterations of the heat flow. The backward step was originally implemented by rejection sampling, whereas we directly simulate the dynamics. Unlike diffusion-based sampling methods that estimate scores via learned models or by invoking auxiliary samplers, our method treats the intermediate particle distribution as a Gaussian mixture, thereby yielding a Monte Carlo score estimator from directly samplable distributions. Theoretically, when the score estimation error is sufficiently controlled, our method inherits the exponential convergence of proximal sampling under isoperimetric conditions on the target distribution. In practice, the algorithm avoids rejection sampling, permits flexible step sizes, and runs with a deterministic runtime budget. Numerical experiments demonstrate that our approach converges rapidly to the target distribution, driven by interactions among multiple particles and by exploiting parallel computation.