Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems
Mehmet Berk Sahin, Behzad Sharif, Abolfazl Hashemi
Abstract
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 -relative Fisher information, and, under a Poincaré 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Score-Based Diffusion Models as Principled Priors for Inverse Imaging cites Diffusion Posterior Sampling for General Noisy Inverse Problems
- Parallel Diffusion Models of Operator and Image for Blind Inverse Problems cites Diffusion Posterior Sampling for General Noisy Inverse Problems
- InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical Sciences cites Score-Based Diffusion Models as Principled Priors for Inverse Imaging
- InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical Sciences cites Diffusion Posterior Sampling for General Noisy Inverse Problems
Builds on4
- Score-Based Diffusion Models as Principled Priors for Inverse ImagingBerthy T. Feng, Jamie Smith, Michael Rubinstein, Huiwen Chang et al.ICCV 2023 · 153 citations
- Diffusion Posterior Sampling for General Noisy Inverse ProblemsHyungjin Chung, Jeongsol Kim, Michael Thompson McCann, Marc Louis Klasky et al.ICLR 2023 · 152 citations
- Parallel Diffusion Models of Operator and Image for Blind Inverse ProblemsHyungjin Chung, Jeongsol Kim, Sehui Kim, Jong Chul YeCVPR 2023
- InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical SciencesHongkai Zheng, Wenda Chu, Bingliang Zhang, Zihui Wu et al.ICLR 2025
Related papers
- On the Robustness of Langevin Dynamics to Score Function ErrorDaniel Cao, August Chen, Karthik Sridharan, Yuchen WuICML 2026 · 2 citations
- Preconditioned Langevin Dynamics with Score-based Generative Models for Infinite-Dimensional Linear Bayesian Inverse ProblemsLorenzo Baldassari, Josselin Garnier, Knut Solna, Maarten V. de HoopNeurIPS 2025 · 5 citations
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising DiffusionYe He, Kevin Rojas, Molei TaoNeurIPS 2024 · 25 citations
- Posterior Sampling by Combining Diffusion Models with Annealed Langevin DynamicsZhiyang Xun, Shivam Gupta, Eric PriceNeurIPS 2025 · 8 citations
- Batch and match: black-box variational inference with a score-based divergenceDiana Cai, Chirag Modi, Loucas Pillaud-Vivien, Charles Margossian et al.ICML 2024 · 18 citations
