[2603.19633] Alternating Diffusion for Proximal Sampling with Zeroth Order Queries

Computer Science > Machine Learning arXiv:2603.19633 (cs) [Submitted on 20 Mar 2026] Title:Alternating Diffusion for Proximal Sampling with Zeroth Order Queries Authors:Hirohane Takagi, Atsushi Nitanda View a PDF of the paper titled Alternating Diffusion for Proximal Sampling with Zeroth Order Queries, by Hirohane Takagi and 1 other authors View PDF HTML (experimental) 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 interacti...