cs.LGMar 20, 2026

Alternating Diffusion for Proximal Sampling with Zeroth Order Queries

Authors: Hirohane Takagi, Atsushi Nitanda

Organizations: Graduate School of Information Science and Technology, The University of Tokyo, Japan · Institute of High Performance Computing, Agency for Science, Technology and Research, Singapore · Centre for Frontier AI Research, Agency for Science, Technology and Research, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Illustration of the ideal proximal sampling (left) and our approximation (right). Heat flow and reverse dynamics are defined between πX\pi^{X} and πY\pi^{Y} , but applied to intermediate ρ\rho . Although these do not reach their targets in one step, the ideal version attains exponential convergence. Compared to the rejection sampling-based implementation of proximal samplers, our approach allows for larger step sizes (i.e., stronger convolution), which reduce the iterations to reach the target distribution.
Figure 2: Convergence of estimated KL divergence, averaged over 10 random seeds with shaded areas indicating variances. Our method (orange) outperforms both the proximal sampler with RGO (blue) and an ablated variant of our algorithm without particle interactions (green). It achieves the same accuracy as RGO in about 10×10\times fewer iterations ( 100×100\times faster when accounting for thinning).
Figure 3: One-dimensional marginals of πX\pi^{X} along the third coordinate. The red curve is the ground-truth. Our method around 100 iterations (left, orange) already matches the RGO-based sampler at ∼\sim 1000 iterations (left, blue), and with only 200–300 iterations (right, orange) it closely aligns with the reference obtained from a sufficiently long run following Liang and Chen (2023b) (right, blue).
Figure 4: Empirical distributions at k=3,10,200k=3,10,200 iterations with seed =0=0 on the two-tori domain. In-and-Out (top row) finds T1T_{1} , which overlaps with the initial standard Gaussian distribution, but fails to reach T2T_{2} . Our method (bottom row) generates some particles outside the domain but gradually drives particles toward T2T_{2} , demonstrating its ability to explore both components.
Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

MethodParameters
Proximal Sampler with RGOInitial distribution: y1/2(j)∼N(0,Id)y^{(j)}_{1/2}\sim\mathcal{N}(0,I_{d})
 Step size: η=1/135\eta=1/135
 Number of independent chains: 100100
 Thinning: 1010
OursInitial distribution: x0(i)∼N(0,Id)x^{(i)}_{0}\sim\mathcal{N}(0,I_{d})
 Step size: h=1/10h=1/10
Appendix
Table 1: Parameter setting for the experiment in Section 5.1 .
MethodParameters
In-and-OutInitial distribution: x0(i)∼N(0,Id)x^{(i)}_{0}\sim\mathcal{N}(0,I_{d})
 Step size: h=1h=1
 Number of proposals for rejection sampling: 1000010000
 (Particles are discarded if not accepted)
 Number of independent chains: 10001000
OursInitial distribution: x0(i)∼N(0,Id)x^{(i)}_{0}\sim\mathcal{N}(0,I_{d})
Appendix
Table 2: Parameter setting for the experiment in Section 5.2 .
Figure 5: Convergence of KL divergence for different step sizes hh , with all other parameters set as Ours in Table 1 . Each curve shows the mean over 10 random seeds, with shaded areas indicating variances. Larger step sizes lead to faster convergence.
Figure 6: Comparison of hyperparameter tuning while keeping the number of particles used during the algorithm’s execution (i.e., M×NM\times N ). For readability, the first iteration has been omitted. While increasing the number of particles N used for approximating the target distribution stabilizes the KL divergence, changing both M and N results in very similar convergence patterns.

Explore similar work

CardsList

  1. Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler

    Sep 7, 2026Fan Chen, Sinho Chewi, Jianfeng Lu +1Markov Chain Monte CarloLog-Concave Sampling

    Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1

  2. Decentralized Proximal Stochastic Gradient Langevin Dynamics

    May 1, 2026Mohammad Rafiqul Islam, Lingjiong ZhuMarkov Chain Monte CarloStochastic Gradient Langevin Dynamics

    Department of Mathematics, Florida State University, Tallahassee, Florida, United States of America

  3. Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling

    Oct 12, 2026Bo Yuan, Wei Guo, Yongxin ChenLog-Concave SamplingLangevin Dynamics

    Georgia Institute of Technology