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

arXiv: https://arxiv.org/abs/2605.30573 · HTML: https://mlsanity.com/paper/2605.30573/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 65 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 30 of 32)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Elucidating the Design Space of Diffusion-Based Generative Models](https://mlsanity.com/paper/2206.00364/) (2022)
- [Diffusion Posterior Sampling for General Noisy Inverse Problems](https://mlsanity.com/paper/2209.14687/) (2022)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Zero-Shot Image Restoration Using Denoising Diffusion Null-Space Model](https://mlsanity.com/paper/2212.00490/) (2022)
- [Solving Inverse Problems in Medical Imaging with Score-Based Generative Models](https://mlsanity.com/paper/2111.08005/) (2021)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [SNIPS: Solving Noisy Inverse Problems Stochastically](https://mlsanity.com/paper/2105.14951/) (2021)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models](https://mlsanity.com/paper/2307.00619/) (2023)
- [Score-Based Diffusion Models as Principled Priors for Inverse Imaging](https://mlsanity.com/paper/2304.11751/) (2023)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Parallel Diffusion Models of Operator and Image for Blind Inverse Problems](https://mlsanity.com/paper/2211.10656/) (2022)
- [Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie](https://mlsanity.com/paper/2103.04715/) (2021)
- [Principled Probabilistic Imaging using Diffusion Models as Plug-and-Play Priors](https://mlsanity.com/paper/2405.18782/) (2024)
- [DOLCE: A Model-Based Probabilistic Diffusion Framework for Limited-Angle CT Reconstruction](https://mlsanity.com/paper/2211.12340/) (2022)
- [InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical Sciences](https://mlsanity.com/paper/2503.11043/) (2025)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Deep Probabilistic Imaging: Uncertainty Quantification and Multi-modal Solution Characterization for Computational Imaging](https://mlsanity.com/paper/2010.14462/) (2020)
- [Symbolic Music Generation with Non-Differentiable Rule Guided Diffusion](https://mlsanity.com/paper/2402.14285/) (2024)
- [Provable Probabilistic Imaging using Score-Based Generative Priors](https://mlsanity.com/paper/2310.10835/) (2023)
- [Plug-and-Play split Gibbs sampler: embedding deep generative priors in Bayesian inference](https://mlsanity.com/paper/2304.11134/) (2023)
- [Generative Plug and Play: Posterior Sampling for Inverse Problems](https://mlsanity.com/paper/2306.07233/) (2023)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)

## Built on by (most cited first, 1 of 1)

- [Variance Reduction for Non-Log-Concave Sampling with Applications to Inverse Problems](https://mlsanity.com/paper/2606.16257/) (2026)

## Abstract (arXiv)

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.