A new arXiv preprint argues that a gradient-free random-walk Metropolis sampler can retain a positive worst-case acceptance probability for certain steep mathematical target distributions, even as the dimension grows, when its proposal scale satisfies a curvature-based condition. Under the paper’s concrete criterion K ≤ 1/4, the lower bound exceeds one-sixth of (1−δ), uniformly over the starting state and the dimension. The criterion is sufficient, not necessarily sharp for every target.
Here, a target is a mathematical probability distribution of the form π(dx) ∝ exp(−U(x))dx on R^d, rather than an empirical participant sample. The sampler proposes a new point with a Gaussian random walk, Y = x + σZ, where Z∼N(0,I_d). The analysis asks whether that proposal can be accepted uniformly across states; it does not use participants or a real-world dataset.
A condition on the landscape
The key assumption lets the allowed curvature depend on local force. More precisely, it bounds the Hessian’s operator norm—roughly, the largest local change in slope—by a nondecreasing function of the gradient norm. The acceptance analysis also exploits symmetry: for two opposite proposal increments, it is enough for one of them to be favorable.
An accepted move is not by itself a guarantee of fast mixing. With additional isoperimetric conditions on the target’s global geometry, uniform acceptance and suitable initialization, the paper invokes lower bounds of order σκ for conductance and σ²κ² for the spectral gap. The authors say these conditional bounds can support polynomial-in-dimension mixing guarantees when the extra assumptions hold.
Examples show why scale matters
In a radial power example, the proposed scale is σ = ηₚ,꜀((p−1)d)^{−(p−1)/p}, for sufficiently small ηₚ,꜀. At that scale, worst-case acceptance is bounded away from zero uniformly over states and dimensions.
The same example also shows why scaling matters. At the paper’s specified test point, if the rescaled proposal strength tends to a finite value τ as d grows, acceptance tends to 2Φ(−τ/2). If the rescaled strength instead diverges, acceptance at that point tends to zero, so worst-case acceptance does too.
For a separable product power example, the analysis gives, at σ = ℓd^{−1/2}, a lower bound of the form c exp(−Cₚℓᵖ); the supplied analysis does not specify the numerical constants. In a separate (1,1)-smooth example, the paper reports uniform positive acceptance at σ = η/d for η≤η꜀, stable acceptance at scale (log d)/d, but not at scale d^{−(1−ε)}.
A nonconvex perturbation example also retains uniform positive acceptance at a scale of order d^{−(p−1)/p} for fixed p and a, provided the stated perturbation bounds and a sufficiently small proposal constant are met.
The evidence stops at the mathematics
The document is arXiv version 1, posted on 20 Aug 2026. Its analyzed population is the mathematical class π(dx) ∝ exp(−U(x))dx on R^d, not an empirical participant sample or dataset.
Because the analysis controls the worst case uniformly over states, its bounds can be conservative and do not show that every proposed scale is optimal. The mixing conclusions remain conditional on target-specific geometry and initialization, and the paper’s sharpness results cover selected examples rather than the full class of steep potentials.
Paper data and sources
Original title: Robustness of random-walk Metropolis for steep potentials
Authors: Sam Power
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text