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

• URL: http://arxiv.org/abs/2605.30573v1
• Date: Thu, 28 May 2026 21:07:14 GMT
• Title: Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems
• Abstract summary: Langevin dynamics provides a principled framework for sampling when gradients are accessible.<n>It suffers from high variance and lacks non-asymptotic convergence guarantees for non-log-concave sampling.<n>We propose a variance-reduced zeroth-order Langevin sampling method.<n>We establish the first non-asymptotic convergence guarantees for zeroth-order non-log-concave sampling.
• Score: 7.692336118507715
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\varepsilon$-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.

Related papers

• Variance Reduction for Non-Log-Concave Sampling with Applications to Inverse Problems [7.041502953437834]
  We show that we can approximate gradients that exhibit high variance under a fixed-reduction iteration.<n>We extend our theory to solve inverse priors problems in twodimensional imaging.
  arXiv  Detail & Related papers  (2026-06-15T06:01:05Z)
• Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives [48.91820744387913]
  We develop preconditioned gradient methods with a focus on Muon and Scions.<n>We introduce a family of algorithms that can handle a wide variety of convex and non-reduced constraints.
  arXiv  Detail & Related papers  (2026-05-12T09:36:13Z)
• Dual-space posterior sampling for Bayesian inference in constrained inverse problems [5.739708455652395]
  Inverse problems constrained by partial differential equations are often ill-conditioned due to noisy and incomplete data or inherent non-uniqueness.<n>We develop a new technique for translating hard physical constraints, such as the wave equation, into prior distributions amenable to existing sampling techniques.
  arXiv  Detail & Related papers  (2026-02-28T00:34:31Z)
• On the Sample Complexity of Learning for Blind Inverse Problems [8.091533689145908]
  Blind inverse problems arise in many experimental settings where the forward operator is partially or entirely unknown.<n>Data-driven approaches have been proposed to address blind inverse problems, demonstrating strong empirical performance and adaptability.<n>We shed light on learning in blind inverse problems within the simplified yet insightful framework of Linear Minimum Mean Square Estimators.
  arXiv  Detail & Related papers  (2025-12-29T11:53:37Z)
• Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms [2.860608352191896]
  We consider random instances of non- numerically weights perceptron problems in the high-dimensional limit.<n>We develop a formalism based on replica theory to predict Approximate sampling space using generative algorithms.
  arXiv  Detail & Related papers  (2025-02-22T16:43:01Z)
• Taming Score-Based Diffusion Priors for Infinite-Dimensional Nonlinear Inverse Problems [4.42498215122234]
  This work introduces a sampling method capable of solving Bayesian inverse problems in function space. It does not assume the log-concavity of the likelihood, meaning that it is compatible with nonlinear inverse problems. A novel convergence analysis is conducted, inspired by the fixed-point methods established for traditional regularization-by-denoising algorithms.
  arXiv  Detail & Related papers  (2024-05-24T16:17:01Z)
• Sobolev Space Regularised Pre Density Models [51.558848491038916]
  We propose a new approach to non-parametric density estimation that is based on regularizing a Sobolev norm of the density. This method is statistically consistent, and makes the inductive validation model clear and consistent.
  arXiv  Detail & Related papers  (2023-07-25T18:47:53Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
  We develop a framework for non-asymptotic analysis of deterministic samplers used for diffusion generative modeling. We show that one step along the probability flow ODE can be expressed as two steps: 1) a restoration step that runs ascent on the conditional log-likelihood at some infinitesimally previous time, and 2) a degradation step that runs the forward process using noise pointing back towards the current gradient.
  arXiv  Detail & Related papers  (2023-03-06T18:59:19Z)
• An adjoint-free algorithm for conditional nonlinear optimal perturbations (CNOPs) via sampling [5.758073912084367]
  We propose a sampling algorithm based on state-of-the-art statistical machine learning techniques to obtain conditional nonlinear optimal perturbations (CNOPs) The sampling approach directly reduces the gradient to the objective function value (zeroth-order information) We demonstrate the CNOPs obtained with their spatial patterns, objective values, quantifying computation times, and nonlinear error growth.
  arXiv  Detail & Related papers  (2022-08-01T16:07:22Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck [14.309243378538012]
  We propose an online compression scheme that fixes an error neighborhood with respect to the Hellinger metric centered at the current posterior. For constant error radius, POG converges to a neighborhood of the population posterior (Theorem 1(ii))but with finite memory at-worst determined by the metric entropy of the feature space.
  arXiv  Detail & Related papers  (2020-04-23T11:52:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.