High-accuracy log-concave sampling with stochastic queries

Fan Chen, Sinho Chewi, Rocco A. Servedio, Alexander Rakhlin

TL;DR

This paper reveals a surprising fundamental difference between optimization and sampling: while noisy gradients prevent high-precision convex optimization, high-accuracy sampling (reaching error $\delta$ in $\text{polylog}(1/\delta)$ steps) is entirely possible even with stochastic gradients, provided the noise has "light" (subexponential) tails. The authors provide both the algorithms to achieve this and information-theoretic lower bounds proving that light tails are a necessary requirement for such high-precision results.

What Problem Does This Paper Address?

In the world of machine learning, we often draw parallels between convex optimization (finding the minimum of a function $f$) and log-concave sampling (drawing a point from a distribution $\mu \propto e^{-f}$).

For optimization, it is a well-known "hard truth" that if your gradient measurements are noisy, you cannot reach a high-accuracy solution quickly. Even with simple Gaussian noise, the number of queries needed scales as $1/\delta$ or $1/\delta^2$. To get ten times more precision, you need ten to a hundred times more data.

The researchers asked: Does sampling suffer from the same "noise tax"? Specifically, can we generate a sample with error $\delta$ using only $\text{polylog}(1/\delta)$ queries to a stochastic (noisy) oracle? Prior to this work, most popular stochastic samplers like Stochastic Gradient Langevin Dynamics (SGLD) were known to be "inexact," meaning they couldn't reach high accuracy without decreasing the step size to zero, which ruins efficiency.

Methods

The authors achieve high-accuracy sampling by combining two powerful frameworks:

  1. First-Order Rejection Sampling (FORS): This is a "meta-algorithm" recently developed by some of the same authors. It uses a "Bernoulli factory" approach—a mathematical trick that allows one to perform exact rejection sampling using only unbiased estimators of the target density, rather than the exact density values.
  2. The Proximal Sampler: This is a high-level algorithm that breaks down the difficult task of sampling from a complex distribution into a series of simpler "Gaussian tilt" sampling problems.

The core technical contribution is showing that the FORS framework is robust to noise. By using a path-integral representation of the log-density ratio and replacing exact gradients with stochastic ones, the authors show they can still implement the "rejection" step of the algorithm accurately. They extend this logic to both stochastic gradient oracles (where you get a noisy slope) and stochastic zeroth-order oracles (where you only get noisy function values).

Datasets

As a theoretical paper focused on proving complexity bounds and algorithmic guarantees, no empirical datasets were used. The "evaluation" consists of mathematical proofs of convergence rates and information-theoretic lower bounds.

Key Insights and Ideas

  • The Sampling-Optimization Gap: The most striking insight is that sampling is fundamentally more robust to gradient noise than optimization. In optimization, noise pushes you away from the unique global minimum. In sampling, you are looking for a distribution; the inherent "randomness" of sampling can, in a sense, absorb certain types of external noise.
  • Tails Matter: The paper identifies "tail behavior" as the decider of efficiency.
  • If noise is subexponential (light-tailed), you get high accuracy: $\text{polylog}(1/\delta)$.
  • If noise only has bounded variance (heavy-tailed), you are stuck with: $\Theta(1/\delta)$.
  • Bernoulli Factory Power: The paper demonstrates that the "Bernoulli factory" (turning unbiased estimates into exact probabilities) is the right tool for making MCMC methods robust to stochasticity. It bridges the gap between "exact" MCMC (which is usually too slow) and "stochastic" MCMC (which is usually too inaccurate).

Key Results

  • Upper Bounds: For a distribution that is "well-behaved" (satisfying a Log-Sobolev or Poincaré inequality), the authors prove that a $\delta$-accurate sample can be obtained in $\text{polylog}(1/\delta)$ queries using stochastic gradients with subexponential tails.
  • Lower Bounds: They prove a new lower bound showing that if the stochastic gradient only has a bounded $s$-th moment, the complexity must scale as $(1/\delta)^{1/(s-1)}$. For the common "bounded variance" assumption ($s=2$), this means $1/\delta$ queries are mandatory.
  • Zeroth-Order Sampling: They provide the first high-accuracy guarantees for sampling using only noisy function evaluations, showing that you don't even need gradients to achieve $\text{polylog}(1/\delta)$ accuracy, though the dependence on the dimension $d$ becomes worse.

Limitations and Future Work

  • Dimension Dependence: While the paper optimizes for the accuracy parameter $\delta$, the scaling with respect to the dimension $d$ and the "condition number" $\kappa$ may not yet be optimal. The authors suggest that further refinements could improve these factors.
  • Finite-Sum Setting: The current work focuses on a "black-box" stochastic oracle. In many ML applications, the function $f$ is a sum of $n$ individual data points. The authors note that extending these results to specifically leverage the finite-sum structure (like SVRG does for optimization) is a promising next step.
  • Warm Starts: The complexity results often depend on how "good" the initial starting point is. Exploring how to achieve "warm starts" in the presence of noise is left for future research.

Summary updated

Abstract

We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/δ)$, where $δ$ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/δ)$ queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as $Θ(1/δ)$. Our framework also provides similar high accuracy guarantees under stochastic zeroth order (value) queries.
BibTeX
@misc{chen2026high,
  author = {Fan Chen and Sinho Chewi and Rocco A. Servedio and Alexander Rakhlin},
  title = {{High-accuracy log-concave sampling with stochastic queries}},
  year = {2026},
  eprint = {2602.14342},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.14342},
}
Figure