Unverified 2026

Two-query SPSA Langevin sampler for black-box neural energies

Implementation & benchmark of arXiv:2608.07837 — Zeroth-Order Langevin Monte Carlo via SPSA under Noisy Function Measurements

Usefulness6/10
Difficulty5/10
Novelty8/10

Source paper: Zeroth-Order Langevin Monte Carlo via SPSA under Noisy Function Measurements arXiv:2608.07837 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace backpropagated gradients in a Langevin sampler with a simultaneous-perturbation estimate obtained from two noisy evaluations of a neural energy or simulator-defined negative log-density. This enables posterior or latent-space sampling when the energy contains nondifferentiable code, stochastic simulation, discrete operations, or an inaccessible neural-network gradient.

Formulas

$$\tilde{f}(x)=f(x)+\varepsilon,\qquad \pi(x)\propto e^{-f(x)}.$$
$$dL_t=-\nabla f(L_t)\,dt+\sqrt{2}\,dB_t.$$
$$\widehat g_c(x)=\frac{\tilde f(x+c\Delta)-\tilde f(x-c\Delta)}{2c}\,\Delta,\qquad \Delta_i\stackrel{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}\{-1,+1\}.$$
$$x_{k+1}=x_k-h_k\widehat g_{c_k}(x_k)+\sqrt{2h_k}\,\xi_k,\qquad \xi_k\sim\mathcal N(0,I_p).$$

Mathematical statement

The target density is $\pi(x)\propto e^{-f(x)}$ for $x\in\mathbb{R}^{p}$, and the available oracle is $\tilde f(x)=f(x)+\varepsilon$, where $\varepsilon$ is additive measurement noise. The continuous reference process is the overdamped Langevin diffusion $dL_t=-\nabla f(L_t)\,dt+\sqrt{2}\,dB_t$, with invariant density $\pi$; $B_t$ is standard $p$-dimensional Brownian motion. Use a Rademacher perturbation vector $\Delta\in\{-1,+1\}^{p}$ with independent coordinates and estimate the gradient from two noisy evaluations: $\widehat g_c(x;\Delta,\varepsilon^+,\varepsilon^-)=[\tilde f(x+c\Delta)-\tilde f(x-c\Delta)](2c)^{-1}\Delta$, where multiplication by $\Delta$ is coordinatewise and equals division because $\Delta_i^{-1}=\Delta_i$. The paired oracle noise enters as the difference $\varepsilon^+-\varepsilon^-$. The discrete sampler is $x_{k+1}=x_k-h_k\widehat g_{c_k}(x_k)+\sqrt{2h_k}\,\xi_k$, with $\xi_k\sim\mathcal N(0,I_p)$ independently. Use diminishing $h_k$ and $c_k$ so discretization, finite-difference bias, and oracle-noise effects vanish asymptotically. A practical power-law schedule is $h_k=h_0(k+1)^{-\alpha}$ and $c_k=c_0(k+1)^{-\beta}$ with $0<\alpha\le1$ and $\beta>0$, tuned empirically. The reported noisy-oracle complexity is $O(p/\epsilon^{2}+\delta^{2}p^{3}/\epsilon^{3})$ for $W_2$ accuracy $\epsilon$, where $p$ is dimension and $\delta$ is the paired-noise level.

Implementation notes

Integrate this at the transition kernel of a latent-variable or parameter sampler, rather than inside ordinary supervised backpropagation. Let $x$ be a latent vector, simulator state, or Bayesian neural-network parameter vector, and let energy(x) return a noisy scalar $\tilde f(x)$; it may execute a neural decoder, renderer, simulator, or black-box validation score. At iteration $k$, draw a fresh Rademacher vector Delta, evaluate y_plus = energy(x + c_k*Delta) and y_minus = energy(x - c_k*Delta), and form g_hat = ((y_plus-y_minus)/(2*c_k))*Delta. Draw standard Gaussian xi and update x = x - h_k*g_hat + sqrt(2*h_k)*xi. Use h_k=h0/(k+1)^alpha and c_k=c0/(k+1)^beta; initialize with alpha=0.6, beta=0.1, and tune h0 using a short pilot run. Clip updates whose norm exceeds a fixed multiple of the running median, while recording clipping frequency. Estimate oracle noise by repeated calls at one point: delta_hat^2 = 0.5*Var(energy(x)), and tune c0 so the finite-difference signal exceeds this noise. First test on a 2D or 10D Gaussian-mixture energy, then on a 32D VAE latent posterior whose decoder contains a nondifferentiable simulator. Compare against random-walk Metropolis, one-sided zeroth-order Langevin, and exact-gradient ULA when available, matching total energy evaluations. Measure MMD or $W_2$ distance to reference samples, effective sample size per oracle call, and divergence rate. Success means lower sampling error at equal two-query budgets and stable chains as $k$ increases; failure is SPSA variance overwhelming the drift in moderate dimension.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.