Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Randomizing a Metropolis–Hastings step size converts exponential mixing collapse under misspecified tuning into polynomial decay.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Randomizing the Metropolis-Hastings step size preserves spectral gaps and algorithmic complexity while making mixing degrade polynomially, not exponentially, when the step size is mis-tuned.

T0 review reviewed 2026-08-03 challenge →

load-bearing objection A solid robustness result for randomized step sizes, with a narrower scope than the abstract claims and a concrete error in one motivating example. the 2 major comments →

arxiv 2601.19710 v2 pith:MENPATLE submitted 2026-01-27 stat.CO math.STstat.MEstat.TH

On randomized step sizes in Metropolis-Hastings algorithms

Sebastiano Grazzi , Samuel Livingstone , Lionel Riou-Durand This is my paper
classification stat.CO math.STstat.MEstat.TH MSC 60J0565C0562F15
keywords Metropolis–Hastingsrandomized step sizesspectral gaprobustness to tuningscaling limitsMALAHamiltonian Monte CarloMarkov chain Monte Carlo
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Metropolis–Hastings samplers are highly sensitive to their step size: for gradient-based proposals, choosing h too large makes the spectral gap collapse quickly, while choosing it too small wastes computation. This paper argues that a simple modification—drawing the step size from a fixed distribution at every iteration—removes that fragility. The main result states that if the fixed-step kernel has any spectral gap at h=1 and the randomizing distribution retains non-negligible mass near zero, then both the auxiliary-variable and marginalized randomized kernels have spectral gaps decaying at worst as 1/h as h grows. Since the argument only needs a spectral gap for the base kernel, it makes nearly any Metropolis–Hastings family robust to oversizing. The same randomization preserves the high-dimensional scaling limits of the underlying algorithm, and shifts the optimal acceptance rate upward for MALA and HMC.

Core claim

The paper's central claim is that randomizing the step size is a general robustness device for reversible Metropolis–Hastings kernels. Given a family of kernels indexed by h, define the auxiliary-variable kernel by averaging the base kernel over z drawn from a randomizing distribution μ, and define the marginalized kernel by averaging the proposal density before applying the Metropolis acceptance step. Theorem 4 shows: if the base kernel at h=1 has a positive spectral gap and μ satisfies Assumption 1, then both randomized kernels have spectral gaps of order Ω(h^{-1}) as h→∞. In other words, no matter how badly the step size overshoots the scale of the target, the randomized chain mixes at mo

What carries the argument

The key machinery is the mixture representation of the auxiliary kernel combined with the Dirichlet-form identity E(P̄_h, f) = ∫ E(P_{h z}, f) μ(dz). Under Assumption 1—which requires μ(z/h) ≥ C μ(z) for all h≥1 and z>0, i.e. non-negligible mass near zero—a change of variables gives E(P̄_h, f) ≥ (C/h) E(P_1, f). Thus a spectral gap for P_1 at h=1 is inherited as a polynomial-in-h gap for every larger h. The marginalized kernel, built from the averaged proposal density Q̄_h(x,y)=∫ μ(z)Q_{hz}(x,y)dz plus Metropolis acceptance based on that density, is π-reversible and satisfies E(M_h,f) ≥ E(P̄_h,f), which yields the same robustness by a single comparison.

Load-bearing premise

The result stands or falls on whether the randomizing distribution still gives non-negligible probability to very small effective step sizes as h grows; without that, the polynomial gap bound in Theorem 4 has no proof.

What would settle it

Estimate the spectral gap of the auxiliary-variable kernel for a Gaussian target with a jitter distribution whose support is bounded away from zero, such as Uniform on [1,2], as h→∞; if the gap decays exponentially, that confirms Assumption 1 is essential. For a covered case, numerically diagonalize the auxiliary kernel with half-Normal jitter on a product Gaussian target and check whether the gap decays like 1/h rather than exponentially.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any Metropolis–Hastings family whose kernel at h=1 has a positive spectral gap becomes robust to oversized steps: both randomized kernels have gaps Ω(h^{-1}).
  • When the marginalized kernel is implementable, it is never worse than the auxiliary-variable version in asymptotic variance, so it should be the default choice.
  • Randomizing the step size preserves the base algorithm's dimension-scaling complexity while raising the optimal acceptance rate—to roughly 0.68 for MALA and 0.75 for HMC with Uniform or Exponential jitter.
  • The analytic results apply to any one-dimensional indexing parameter of a reversible kernel family, so the robustness guarantee extends beyond step size to other tuning parameters.
  • Numerically, randomized MALA explores the tails of funnel- and banana-shaped targets and reaches the bulk of a heavy-tailed posterior faster than standard MALA.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because Assumption 1 is a local condition near zero, a practical design rule for the jitter distribution is to give it positive density at zero; distributions bounded away from zero, such as Uniform on [1,2], fall outside the theorem and could still suffer exponential collapse.
  • The proof of Theorem 4 is dimension-free and depends on the base kernel only through Gap(P_1), suggesting that explicit bounds in terms of C and Gap(P_1) could be extracted to quantify worst-case mixing as a function of misspecification.
  • The scaling-limit theorem gives a concrete mechanism to optimize over the jitter distribution beyond the given Uniform and Exponential examples; heavier-tailed choices may trade additional robustness for more efficiency loss near the optimum.
  • The robustness guarantee is stated for h→∞, and the numerical work shows improvements from tail initialization, but undersizing behavior is essentially unchanged—so the practical benefit of jitter is specifically protection against too-large steps.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies Metropolis–Hastings algorithms with randomized step sizes, in both an auxiliary-variable construction (P_h) and a marginalized construction (M_h). It proves that M_h dominates P_h in Dirichlet form (Prop. 1), that both randomized kernels inherit weak Poincaré inequalities or spectral gaps from the fixed-step family under suitable conditions (Prop. 2, Cor. 1), and that both kernels have spectral gaps decaying at most polynomially in h when the step size is misspecified, provided the randomized kernel at h=1 has a positive gap and μ satisfies Assumption 1 (Thm. 4). It also gives scaling-limit results for the auxiliary kernel (Thm. 5, Prop. 6), reports increased optimal acceptance rates for randomized MALA and HMC, and presents numerical experiments on Neal's funnel, the Rosenbrock distribution, and Poisson regression.

Significance. If the main results hold, the paper is a valuable contribution to the robustness-to-tuning literature. The Dirichlet-form comparison and the polynomial spectral-gap theorem provide a rigorous justification for the common heuristic of jittering the step size. The paper also contributes concrete implementable marginalized kernels (e.g., with Bessel-function proposal densities), a scaling-limit framework, and reproducible numerics. The central Dirichlet-form argument in Section 3 is transparent and likely correct. However, the reach of Theorem 4 is narrower than the abstract and the surrounding discussion suggest: the theorem requires a spectral gap of the randomized kernel at h=1, not merely of the fixed-step kernel, and it depends on Assumption 1. There is also a concrete incorrect claim in Section 2.3. These issues are correctable but need attention.

major comments (2)
  1. [§3.3, Theorem 4] Theorem 4 is correct as stated, but its logical reach is narrower than the claims made around it. The hypothesis Gap(P_1)>0 is a spectral gap of the randomized auxiliary kernel at h=1, not of the fixed-step kernel P_1. The sentence immediately before Theorem 4 ('for any MH algorithm P_h ... randomizing h imposes a level of robustness, even if this is not the case for the original kernel P_h') and the abstract's unqualified 'both types of randomization make an algorithm robust' invite the stronger reading that a gap of the fixed-step kernel P_1 suffices. It does not: one must additionally establish Gap(P_1)>0, e.g. via Proposition 2/Corollary 1 requiring μ to charge the set H where the base family has a gap. Assumption 1 is also load-bearing: for μ with no mass near zero (e.g. Uniform[1,2]) the polynomial bound is not proved, and the gap can still collapse exponentially. Please qualify th
  2. [§2.3, after Eq. (4)] The statement that half-Normal μ in the Rademacher random walk makes M_h a Gaussian random-walk Metropolis proposal with variance h is incorrect. For U=(Y-X)/√h, the marginalized proposal density is f_U(u)=|u|√(2/π)e^{-u^4/2}, not the standard normal density. (Equivalently, Q_h(x,y) has a quartic exponent rather than the Gaussian quadratic exponent.) This error does not affect Theorem 4, but it is a wrong example and should be corrected; the analogous Barker claim in the same paragraph should also be checked.
minor comments (3)
  1. [§2.2, Corollary 1] The statement 'density μ(z)>0 for all z∈R' should be z>0, and 'for any h∈R' should be h>0.
  2. [§4, after Theorem 5] The overline notation for the randomized ESJD is missing in several displays (e.g., the display beginning 'Note that for all ℓ>0'), making the comparison between the randomized and base efficiency functions hard to follow.
  3. [§4, Table 1] The text says 'the randomized algorithms have a loss of asymptotic efficiency when ℓ is optimally tuned.' This is correct only when comparing the maxima of eff and the randomized efficiency; please make the comparison explicit in the text to avoid confusion.

Circularity Check

0 steps flagged

No significant circularity: the main spectral-gap and scaling-limit results follow from explicit assumptions via direct Dirichlet-form calculations and prior external results.

full rationale

The derivation chain is not circular. The randomized kernels P_h and M_h are defined explicitly in Section 2.2 as mixtures/integrated Metropolis-Hastings kernels; Lemma 1 (E(P_h,f)=∫E(P_hz,f)μ(dz)) is a direct calculation from that definition. Proposition 2 and Corollary 1 inherit weak Poincaré inequalities/spectral gaps from the base family under Assumption 2 and a positive-mass condition on μ; these are genuine inheritance results, not predictions built from fitted values. Proposition 3 derives the polynomial lower bound E(P_h,f)≥(C/h)E(P_1,f) from Assumption 1, and Theorem 4 then follows by combining this with Gap(P_1)>0 and Proposition 1's ordering; the conclusion is not equivalent to the assumptions by construction. The citations to Titsias and Papaspiliopoulos (2018), Storvik (2011), Andrieu et al. (2022) and Livingstone and Zanella (2022) are used as explicit external foundations; even where authors overlap (Livingstone), the cited results are not used to assume the paper's own conclusion. The main caveat is that Theorem 4's premise is a spectral gap of the randomized kernel at h=1, Gap(P_1)>0, and Assumption 1 requires μ to retain mass near zero; thus the abstract's 'robust to tuning' claim is conditional on these explicit assumptions rather than universal. That limits reach but is not circularity. The Section 2.3 half-Normal/Rademacher Gaussian identification appears questionable, but it is not load-bearing for the spectral-gap theorems and is better treated as a correctness risk than a circular-input issue.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No new particles, forces, or entities are postulated. The central machinery is standard spectral theory and MCMC ordering arguments, plus two domain assumptions about the randomizing distribution and the base kernels. No fitted constants appear; the paper's numbers are derived from these assumptions and from numerical integration for the optimal acceptance rates.

axioms (5)
  • domain assumption Assumption 1: μ(z/h) ≥ C μ(z) for all h≥1 and z>0
    Used in Proposition 3 and Theorem 4 to guarantee non-negligible mass near zero; without it the Ω(h^{-1}) spectral-gap bound can fail. Many common distributions (half-Normal, Exponential, Uniform[0,1]) satisfy it for C=1.
  • domain assumption Assumption 2: base kernel P_h has a weak Poincaré inequality / spectral gap for h in some set H
    Used in Proposition 2 to transfer a gap/weak PI from P_{hz} to Pbar_h; for targets like Gaussian MALA/HMC this is known only for small h, which is exactly the setting where the randomized kernels gain robustness.
  • standard math Known optimal scaling limits (11)-(12) for RWM, MALA, and HMC from Roberts et al. (1997), Roberts and Rosenthal (1998), Beskos et al. (2013)
    Invoked in Theorem 5 and in the derivation of Table 1; the randomized scaling limit is an average of these base limits.
  • domain assumption Uniform integrability of f_d(z)=ESJD(d,P_{h_d z})
    Needed for the second part of Theorem 5 to swap limit and integral. Proven for RWM and MALA under product-form targets in Proposition 6, but not verified for HMC or general targets.
  • standard math Peskun-Tierney ordering and the Titsias-Papaspiliopoulos ordering imply asymptotic-variance domination via Dirichlet forms
    Used in Proposition 1 to conclude Gap(M_h) ≥ Gap(Pbar_h) and lower asymptotic variance for the marginalized kernel.

reviewed 2026-08-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of On randomized step sizes in Metropolis-Hastings algorithms." pith.science (2026). https://pith.science/paper/MENPATLE

@misc{pith2026260119710,
  author       = {Pith},
  title        = {Pith review of: On randomized step sizes in Metropolis-Hastings algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MENPATLE}},
  note         = {Machine review of arXiv:2601.19710}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The performance of Metropolis-Hastings algorithms is highly sensitive to the choice of step size, and miss-specification can lead to severe loss of efficiency. We study algorithms with randomized step sizes, considering both auxiliary-variable and marginalized constructions. We show that algorithms with a randomized step size inherit weak Poincar\'e inequalities/spectral gaps from their fixed-step-size counterparts under minimal conditions, and that the marginalized kernel should always be preferred in terms of asymptotic variance to the auxiliary-variable choice if it is implementable. In addition we show that both types of randomization make an algorithm robust to tuning, meaning that spectral gaps decay polynomially as the step size is increasingly poorly chosen. We further show that step-size randomization often preserves high-dimensional scaling limits and algorithmic complexity, while increasing the optimal acceptance rate for Langevin and Hamiltonian samplers when an Exponential or Uniform distribution is chosen to randomize the step size. Theoretical results are complemented with a numerical study on challenging benchmarks such as Poisson regression, Neal's funnel and the Rosenbrock (banana) distribution.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling

    cs.LG 2026-05 unverdicted novelty 8.0

    Establishes measure-theoretic foundations for NML in regular non-smooth models and introduces the PDL-PPMH geometric MCMC sampler to compute stochastic complexity exactly.

Reference graph

Works this paper leans on

3 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ann Statist 49(4):1958–1981

    Andrieu C, Livingstone S (2021) Peskun-Tierney ordering for Markovian Monte Carlo: beyond the reversible scenario. Ann Statist 49(4):1958–1981. https://doi.org/10. 1214/20-aos2008, URL https://doi.org/10.1214/20-aos2008 Andrieu C, Thoms J (2008) A tutorial on adaptive mcmc. Statistics and computing 18:343–373 Andrieu C, Lee A, Vihola M (2018) Uniform ergo...

    work page doi:10.1214/20-aos2008 2021

  2. [3]

    Bernoulli 19(5A):1501–1534

    Cambridge University Press Beskos A, Pillai N, Roberts G, et al (2013) Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli 19(5A):1501–1534. https://doi.org/10.3150/12-BEJ414, URL https://doi.org/10.3150/12-BEJ414 20 Durmus A, Moulines E, Saksman E (2020) Irreducibility and geometric ergodicity of Hamiltonian Monte Carlo. Ann Statist 48(6):3545–...

    doi:10.3150/12-bej414 2013

  3. [9]

    Springer Science & Business Media Livingstone S, Zanella G (2022) The barker proposal: Combining robustness and effi- ciency in gradient-based mcmc. Journal of the Royal Statistical Society Series B: Statistical Methodology 84(2):496–523 Livingstone S, Betancourt M, Byrne S, et al (2019a) On the geometric ergodicity of Hamiltonian Monte Carlo. Bernoulli 2...

    arXiv 2022

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.