Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems

Sampling from high-dimensional, non-log-concave distributions with unnormalized densities remains a fundamental challenge in machine learning, particularly in black-box settings where gradient information is inaccessible or computationally prohibitive. While Langevin dynamics provides a principled framework for sampling when gradients are accessible, its extension to the black-box settings suffers from high variance and lacks non-asymptotic convergence guarantees for non-log-concave sampling. To address these limitations, we propose a variance-reduced zeroth-order Langevin sampling method. Our method employs a gradient estimator that substantially reduces the variance of the classical batched zeroth-order estimator and eliminates the unfavorable dimensional dependence of the batch size required for accurate estimation, enabling practical and stable sampling. We establish the first non-asymptotic convergence guarantees for zeroth-order non-log-concave sampling in terms of $\varepsilon$-relative Fisher information, and, under a Poincar\'e inequality assumption, squared total variation distance. We further propose ZO-APMC, a posterior sampling algorithm for black-box inverse problems with pre-trained score-based generative priors, establishing the first non-asymptotic convergence guarantees for such methods. We validate our theory through synthetic experiments and demonstrate strong empirical performance on practical linear and nonlinear inverse problems.

Many machine learning problems require drawing samples from complicated probability distributions, for example when estimating uncertainty or solving inverse problems such as image reconstruction. Existing methods often rely on gradient information, but there are many practical settings where these gradients are unavailable, unreliable, or too expensive to compute. We develop a new sampling method designed for these "black-box" settings. Our approach uses only function evaluations while greatly reducing the noise that typically makes gradient-free sampling unstable and inefficient, especially in high-dimensions. We also provide the first rigorous mathematical guarantees showing that this type of method can reliably sample from challenging non-convex distributions within a finite number of steps. We further apply our framework to inverse problems that use modern generative AI models as priors, enabling uncertainty-aware posterior sampling even when the underlying system is treated as a black-box. Our experiments on synthetic examples and practical imaging problems show strong empirical performance. This work expands the toolbox for reliable uncertainty quantification and Bayesian inference in machine learning problems where gradient information is inaccessible.