Pith. sign in

REVIEW 2 major objections 1 minor 1 cited by

Fast-Mixing Markov Chains without Gradients

T0 review · 2 major / 1 minor · reviewed 2026-06-29 · grok-4.3

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

Pith's one-line read A surrogate-based MCMC algorithm matches MALA mixing times for strongly log-concave targets without ever evaluating gradients.

desk verdict DART claims the first mixing-time bound for a surrogate MCMC method that matches MALA rates in some regimes without gradients, but the localization argument needs the full derivation to check. read the letter →

arxiv 2606.27564 v1 pith:EZ6WMP4N submitted 2026-06-25 math.ST stat.COstat.MLstat.TH

Robert Kutri , Robert Scheichl This is my paper · ORCID
classification math.STstat.COstat.MLstat.TH
keywords MCMCmixingtimesurrogatemethodslog-concavedensitiesMetropolis-HastingsLangevindynamicsMarkovchainsdelayedacceptance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces a localisation principle that lets a surrogate Metropolis-Hastings proposal capture the directional effect of the target gradient through regularisation and tempering alone. The resulting DART method produces an expected proposal displacement that matches the Langevin drift up to controlled error. For targets that are strongly log-concave with condition number κ in d dimensions, DART mixes in O(κ max{κ, d}) steps from a warm start. The bound recovers the known O(κ d) rate of MALA when d is at least κ and improves to a dimension-free O(κ²) rate otherwise. The analysis supplies the first mixing-time guarantee for any MCMC method that relies on surrogate transitions rather than direct gradient information.

What carries the argument

The localisation principle, which equates expected proposal displacement to the Langevin drift via regularisation and tempering of the surrogate measure without gradient evaluations.

What would settle it

A numerical experiment on a strongly log-concave Gaussian in which the measured mixing time of DART exceeds O(κ max{κ, d}) by more than a small constant factor, or a direct calculation showing that the expected proposal displacement deviates from the Langevin drift by an amount larger than the controlled error term.

Watch

Extended reading notes

Core claim

By regularising and tempering the proposal measure, a surrogate-based Metropolis-Hastings step can be constructed so that its expected displacement coincides with the Langevin drift up to controlled error; the resulting Delayed Acceptance with Regularisation and Tempering (DART) algorithm therefore inherits an O(κ max{κ, d}) mixing time from warm start for strongly log-concave densities.

Load-bearing premise

The regularised and tempered surrogate proposal produces an expected displacement that stays close to the Langevin drift of the target.

Editorial extensions

If this is right

  • DART recovers the optimal known rate of MALA when dimension d is at least as large as the condition number κ.
  • When κ exceeds d the mixing time becomes O(κ²) and independent of dimension.
  • The first rigorous mixing guarantee is obtained for any MCMC algorithm whose transitions are built from surrogate densities.
  • The Dirichlet-Neumann averaging parametrisation supplies a surrogate whose linear memory and log-linear arithmetic cost carry over to the inference problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same localisation construction could be applied to other gradient-free proposals such as random-walk or Hamiltonian Monte Carlo variants.
  • If the error control in the localisation principle can be verified for non-log-concave targets, the mixing analysis might extend beyond the strongly convex setting.
  • Parameter choices for the regularisation and tempering strengths could be tuned automatically by monitoring the observed displacement error during a short pilot run.
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 / 1 minor

Summary. The paper proposes a 'localisation principle' based on regularisation and tempering that lets a surrogate-based Metropolis-Hastings proposal capture the expected displacement of the Langevin drift without evaluating either the target or surrogate gradient. The resulting Delayed Acceptance with Regularisation and Tempering (DART) algorithm is claimed to achieve an O(κ max{κ, d}) mixing time from a warm start for strongly log-concave targets with condition number κ in d dimensions; this matches the known MALA rate when d ≥ κ and becomes dimension-free O(κ²) otherwise. The paper asserts this is the first mixing-time guarantee for any surrogate-transition MCMC method and illustrates the method on a hierarchical spatial GLM using Dirichlet-Neumann averaging as the surrogate.

Significance. If the mixing-time claim is rigorously established, the result would be significant: it supplies the first non-asymptotic guarantee for a surrogate-based MCMC transition and shows that gradient-level geometry can be exploited without gradient evaluations. The dimension-independent regime (when κ ≫ d) would be particularly useful for high-dimensional but well-conditioned problems where standard gradient-based methods pay an unnecessary d factor.

major comments (2)
  1. [Abstract] The central mixing-time claim O(κ max{κ, d}) is stated in the abstract but no theorem statement, proof outline, or error bound on the localisation principle is supplied in the provided text. Without the derivation it is impossible to verify whether the regularisation/tempering construction indeed produces a controlled bias relative to the Langevin drift or whether hidden dependence on surrogate parameters appears.
  2. [Abstract] The paper asserts that the expected proposal displacement coincides with the Langevin drift 'up to controlled error,' yet no quantitative bound on that error (in terms of κ, d, or surrogate accuracy) is given. This error term is load-bearing for the subsequent mixing-time analysis.
minor comments (1)
  1. [Abstract] The abstract mentions a demonstration on a hierarchical spatial GLM but supplies no numerical results, comparison baselines, or scaling plots, making it impossible to assess practical performance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful comments on our paper. We respond to the major comments below and will revise the manuscript accordingly to improve clarity.

read point-by-point responses

  1. Referee: [Abstract] The central mixing-time claim O(κ max{κ, d}) is stated in the abstract but no theorem statement, proof outline, or error bound on the localisation principle is supplied in the provided text. Without the derivation it is impossible to verify whether the regularisation/tempering construction indeed produces a controlled bias relative to the Langevin drift or whether hidden dependence on surrogate parameters appears.

    Authors: The provided text consists of the abstract, which is necessarily concise. The full manuscript states the mixing-time result as Theorem 3.1 and derives the localisation principle, including verification that the bias is controlled with no hidden dependence on surrogate parameters, in Sections 3–4. We will add a short proof outline and the formal theorem statement to the introduction in the revised version. revision: partial

  2. Referee: [Abstract] The paper asserts that the expected proposal displacement coincides with the Langevin drift 'up to controlled error,' yet no quantitative bound on that error (in terms of κ, d, or surrogate accuracy) is given. This error term is load-bearing for the subsequent mixing-time analysis.

    Authors: We agree that making the quantitative error bound explicit would strengthen the presentation. The manuscript controls the error via the regularisation and tempering parameters in the proof of Theorem 3.1, but we will extract this into a standalone lemma in the revised version, stating the bound explicitly in terms of κ (with the leading term O(κ^{-1})) and confirming independence from d and surrogate accuracy under the paper's assumptions. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation self-contained against external benchmarks

full rationale

The provided abstract and context describe a new localisation principle and DART framework whose mixing-time bound O(κ max{κ, d}) is presented as derived from the regularisation/tempering construction that matches Langevin drift up to controlled error. No equations, proof steps, or self-citations are supplied that reduce the central claim to a fitted parameter, renamed input, or load-bearing self-reference. The result is positioned as the first such guarantee for surrogate MCMC and is compared to the known MALA rate, indicating an independent theoretical argument rather than a definitional or fitted-input reduction. Absent any quoted reduction of the form 'prediction equals input by construction,' the derivation chain is treated as self-contained.

Assumptions & free parameters 0 free parameters · 2 assumptions · 1 invented entities

The central claim rests on the domain assumption of strong log-concavity and on the existence of a surrogate satisfying the localization property; no free parameters or new entities with independent evidence are stated in the abstract.

assumptions (2)
  • domain assumption Targets are strongly log-concave with finite condition number κ
    Required to obtain the stated mixing-time bound.
  • domain assumption A surrogate exists whose regularized and tempered version produces expected displacement matching the Langevin drift up to controlled error
    This is the localization principle invoked to justify gradient-free behavior.
invented entities (1)
  • DART framework
    purpose: Gradient-free fast-mixing MCMC
    New algorithmic construction introduced by the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast-Mixing Markov Chains without Gradients." pith.science (2026). https://pith.science/paper/EZ6WMP4N

@misc{pith2026260627564,
  author       = {Pith},
  title        = {Pith review of: Fast-Mixing Markov Chains without Gradients},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZ6WMP4N}},
  note         = {Machine review of arXiv:2606.27564}
}
abstract

Most approaches for accelerating Markov chain mixing either rely on incorporating expensive geometric information in the proposals, or reduce the per-step cost of sampling via surrogate densities. We propose a localisation principle that allows a surrogate-based Metropolis-Hastings proposal to exploit gradient-level geometric information of the target density, without evaluating either the target gradient or the surrogate gradient. The construction relies on regularisation and tempering of the proposal measure. We show that the expected proposal displacement coincides with the Langevin drift up to controlled error. The resulting framework, Delayed Acceptance with Regularisation and Tempering (DART), achieves an $O(\kappa \max\{\kappa, d\})$ mixing time from warm start for strongly log-concave targets with condition number $\kappa$ in $d$ dimensions. This matches the known $O(\kappa d)$ rate for MALA when $d \ge \kappa$, and scales as $O(\kappa^2)$, independent of dimension, otherwise. This is, to our knowledge, the first mixing time guarantee for a surrogate-transition-based MCMC method. We demonstrate DART on a hierarchical spatial generalised linear mixed model. In this setting, the Dirichlet-Neumann averaging parametrisation, originally introduced for the efficient simulation of Gaussian processes, is repurposed to supply the surrogate, and its linear memory and log-linear arithmetic scaling in the number of observation sites carry over to inference.

Figures

Figures reproduced from arXiv: 2606.27564 by the authors.

Figure 1
Figure 1. Median absolute error in log(𝑁𝑧/𝑁𝑥 ), with interquartile range over 10 000 independent runs, for 𝑅̂ IS (dashed) and 𝑅̂ G (solid) as a function of root chain length 𝑛. The mixture has weights (0.7, 0.3), means ±𝑎 with 𝑎 = 0.5, common covariance 𝜎 2 𝕀 with 𝜎 = 1, and 𝜃 = 1. The root chain is MALA on Π𝑥 initialised at 𝜇𝑥 = 𝛿𝑥 , burn-in fraction 0.3, no thinning. 4.2. The Quadratic Surrogate Regime We now test the full … view at source ↗
Figure 2
Figure 2. Bayesian logistic regression with a Laplace surrogate (𝑛obs = 240, 𝛼 = 3, giving 𝜅 = 21; 𝜃 = 1/2). (a) Running mean error 𝑒𝑘 at 𝑑 = 16 for MALA, MRW, MLDA, and DART at 𝛾 = 0.2 𝐿, averaged over 𝑛est = 500 independent runs from prior initialisations. (b) ESS per iteration of DART along the slowest target direction, as a function of 𝛾/𝐿 for dimensions 𝑑 ∈ {2, 4, 8, 16}, estimated from 𝑀 = 8 replicate chains. Horizontal… view at source ↗
Figure 3
Figure 3. Trace plots (first 5 000 post-burn-in iterations) for MRW, MALA, two-level DART, and three-level DART on bimodal Gaussian mixture targets with (Δ, 𝜎2 ) = (4, 0.4) (left) and (Δ, 𝜎2 ) = (8, 0.2) (right). Side panels show the target density (grey) and, for the DART variants, the localised surrogate densities at each tempering level (dashed, coloured), evaluated at 𝑥 = 0. Each trace is annotated with its IAT (estimated… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Good-surrogate regime. Ground truth is generated once at high resolution (𝑞gt = 500) and held fixed. 𝑁 = 100 observation sites are drawn uniformly on (0, 1) and Poisson counts are simulated from (5.1) with intercept 𝛽0 = 1.5. DNA methods use fine resolution 𝑞 = 100 and…
Figure 5
Figure 5. Figure 5: shows, for each smoothness, the ground-truth field, the DART posterior mean and the posterior standard deviation. The posterior mean recovers the truth in both cases. The posterior mean is slightly more regular than the truth. We attribute this to the penalised￾complex…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Gradient-free Riemannian Langevin Sampler

    cs.LG 2026-07 conditional novelty 6.0 of 10

    GRiLS is a gradient-free MCMC proposal derived via a Lamperti transform of Riemannian Langevin dynamics, using a Gaussian approximation of the target to enable mode-hopping without gradient evaluations.

Reference graph

Works this paper leans on

57 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [1]

    and Yu, Bin , journal =

    Dwivedi, Raaz and Chen, Yuansi and Wainwright, Martin J. and Yu, Bin , journal =. Log-Concave Sampling:

  2. [2]

    High-dimensional Bayesian inference via the unadjusted Langevin algorithm , author =

  3. [3]

    MCMC methods for functions: modifying old algorithms to make them faster , author =

  4. [4]

    Random structures & algorithms , volume =

    Random walks in a convex body and an improved volume algorithm , author =. Random structures & algorithms , volume =. 1993 , publisher =

    1993

  5. [5]

    Meyn, Sean P and Tweedie, Richard L , year =

  6. [6]

    Biometrika , volume =

    Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms , author =. Biometrika , volume =. 1996 , publisher =

    1996

  7. [7]

    Acta numerica , volume =

    Inverse problems: a Bayesian perspective , author =. Acta numerica , volume =. 2010 , publisher =

    2010

  8. [8]

    Probability theory and related fields , volume =

    A convex/log-concave correlation inequality for Gaussian measure and an application to abstract Wiener spaces , author =. Probability theory and related fields , volume =. 2004 , publisher =

    2004

Show all 57 references
  1. [9]

    SIAM/ASA journal on uncertainty quantification , volume =

    Multilevel delayed acceptance MCMC , author =. SIAM/ASA journal on uncertainty quantification , volume =. 2023 , publisher =

    2023

  2. [10]

    Handbook of markov chain monte carlo , volume =

    MCMC using Hamiltonian dynamics , author =. Handbook of markov chain monte carlo , volume =. 2011 , publisher =

    2011

  3. [11]

    2001 , publisher =

    Monte Carlo strategies in scientific computing , author =. 2001 , publisher =

    2001

  4. [12]

    The journal of chemical physics , volume =

    Equation of state calculations by fast computing machines , author =. The journal of chemical physics , volume =. 1953 , publisher =

    1953

  5. [13]

    Monte Carlo sampling methods using Markov chains and their applications , journal =

    Hastings, W Keith , year =. Monte Carlo sampling methods using Markov chains and their applications , journal =

  6. [14]

    Philosophical Transactions of the Royal Society A , volume =

    On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions , author =. Philosophical Transactions of the Royal Society A , volume =. 2023 , publisher =

    2023

  7. [15]

    Mathematical programming , volume =

    Hit-and-run mixes fast , author =. Mathematical programming , volume =. 1999 , publisher =

    1999

  8. [16]

    Journal of Machine Learning Research , volume =

    Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients , author =. Journal of Machine Learning Research , volume =

  9. [17]

    science , volume =

    Optimization by simulated annealing , author =. science , volume =. 1983 , publisher =

    1983

  10. [18]

    Europhysics letters , volume =

    Simulated tempering: a new Monte Carlo scheme , author =. Europhysics letters , volume =. 1992 , publisher =

    1992

  11. [19]

    Journal of the American Statistical Association , volume =

    Annealing Markov chain Monte Carlo with applications to ancestral inference , author =. Journal of the American Statistical Association , volume =. 1995 , publisher =

    1995

  12. [20]

    Journal of Computational and Graphical statistics , volume =

    Markov chain Monte Carlo using an approximation , author =. Journal of Computational and Graphical statistics , volume =. 2005 , publisher =

    2005

  13. [21]

    2009 , journal =

    The pseudo-marginal approach for efficient Monte Carlo computations , author =. 2009 , journal =

    2009

  14. [22]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Particle markov chain monte carlo methods , author =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2010 , publisher =

    2010

  15. [23]

    Roberts and Richard L

    Gareth O. Roberts and Richard L. Tweedie , title =. Bernoulli , number =

  16. [24]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Theoretical guarantees for approximate sampling from smooth and log-concave densities , author =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2017 , publisher =

    2017

  17. [25]

    IMA Journal of Numerical Analysis , volume =

    Nonasymptotic mixing of the MALA algorithm , author =. IMA Journal of Numerical Analysis , volume =. 2013 , publisher =

    2013

  18. [26]

    SIAM Journal on Scientific Computing , volume =

    A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion , author =. SIAM Journal on Scientific Computing , volume =. 2012 , publisher =

    2012

  19. [27]

    Physics letters B , volume =

    Hybrid monte carlo , author =. Physics letters B , volume =. 1987 , publisher =

    1987

  20. [28]

    , author =

    The No-U-Turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. , author =. J. Mach. Learn. Res. , volume =

  21. [29]

    arXiv preprint arXiv:1705.00166 , year =

    On the convergence of hamiltonian monte carlo , author =. arXiv preprint arXiv:1705.00166 , year =

    arXiv

  22. [30]

    2014 , journal =

    Error bounds for Metropolis--Hastings algorithms applied to perturbations of Gaussian measures in high dimensions , author =. 2014 , journal =

    2014

  23. [31]

    2020 , publisher =

    Surrogates: Gaussian process modeling, design, and optimization for the applied sciences , author =. 2020 , publisher =

    2020

  24. [32]

    Mathematics of Computation , volume =

    Posterior consistency for Gaussian process approximations of Bayesian posterior distributions , author =. Mathematics of Computation , volume =

  25. [33]

    The SMAI journal of computational mathematics , volume =

    Model reduction and neural networks for parametric PDEs , author =. The SMAI journal of computational mathematics , volume =

  26. [34]

    Nature machine intelligence , volume =

    Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators , author =. Nature machine intelligence , volume =. 2021 , publisher =

    2021

  27. [35]

    ICLR 2023 workshop on physics for machine learning , year =

    Convolutional neural operators , author =. ICLR 2023 workshop on physics for machine learning , year =

    2023

  28. [36]

    arXiv preprint arXiv:2311.04172 , year =

    Measure transport via polynomial density surrogates , author =. arXiv preprint arXiv:2311.04172 , year =

  29. [37]

    Water Resources Research , volume =

    Bayesian calibration of a large-scale geothermal reservoir model by a new adaptive delayed acceptance Metropolis Hastings algorithm , author =. Water Resources Research , volume =. 2011 , publisher =

    2011

  30. [38]

    arXiv preprint arXiv:2012.05668 , year =

    Multilevel delayed acceptance MCMC with an adaptive error model in PyMC3 , author =. arXiv preprint arXiv:2012.05668 , year =

    2012

  31. [39]

    2023 , publisher =

    Bayesian non-linear statistical inverse problems , author =. 2023 , publisher =

    2023

  32. [40]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    The Barker proposal: Combining robustness and efficiency in gradient-based MCMC , author =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2022 , publisher =

    2022

  33. [41]

    Journal of the Royal Statistical Society Series C: Applied Statistics , volume =

    Model-based geostatistics , author =. Journal of the Royal Statistical Society Series C: Applied Statistics , volume =. 1998 , publisher =

    1998

  34. [42]

    Statistica Sinica , pages =

    Simulating ratios of normalizing constants via a simple identity: a theoretical exploration , author =. Statistica Sinica , pages =. 1996 , publisher =

    1996

  35. [43]

    Journal of the American statistical Association , volume =

    Approximate inference in generalized linear mixed models , author =. Journal of the American statistical Association , volume =. 1993 , publisher =

    1993

  36. [44]

    SIAM Journal on Numerical Analysis , volume =

    Analysis of circulant embedding methods for sampling stationary random fields , author =. SIAM Journal on Numerical Analysis , volume =. 2018 , publisher =

    2018

  37. [45]

    SIAM/ASA Journal on Uncertainty Quantification , volume =

    Dirichlet--Neumann Averaging: The DNA of Efficient Gaussian Process Simulation , author =. SIAM/ASA Journal on Uncertainty Quantification , volume =. 2026 , publisher =

    2026

  38. [46]

    Numerische Mathematik , volume =

    Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients , author =. Numerische Mathematik , volume =. 2015 , publisher =

    2015

  39. [47]

    Journal of the American Statistical Association , volume =

    Accelerating asymptotically exact MCMC for computationally intensive models via local approximations , author =. Journal of the American Statistical Association , volume =. 2016 , publisher =

    2016

  40. [48]

    Journal of Machine Learning Research , volume =

    Minimax mixing time of the Metropolis-adjusted Langevin algorithm for log-concave sampling , author =. Journal of Machine Learning Research , volume =

  41. [49]

    The Annals of Mathematical Statistics , year =

    Robbins, Herbert and Monro, Sutton , title =. The Annals of Mathematical Statistics , year =

  42. [50]

    Penalising Model Component Complexity: A Principled, Practical Approach to Constructing Priors , journal =

    Simpson, Daniel and Rue, H. Penalising Model Component Complexity: A Principled, Practical Approach to Constructing Priors , journal =. 2017 , volume =

    2017

  43. [51]

    arXiv preprint arXiv:2604.00689 , year =

    Performance of neural and polynomial operator surrogates , author =. arXiv preprint arXiv:2604.00689 , year =

  44. [52]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Auxiliary gradient-based sampling algorithms , author =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2018 , publisher =

    2018

  45. [53]

    Conference on Learning Theory , pages =

    Structured logconcave sampling with a restricted Gaussian oracle , author =. Conference on Learning Theory , pages =. 2021 , organization =

    2021

  46. [54]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =

    Approximate Bayesian inference for latent Gaussian models by using integrated nested Laplace approximations , author =. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume =. 2009 , publisher =

    2009

  47. [55]

    Journal of statistical software , volume =

    Stan: A probabilistic programming language , author =. Journal of statistical software , volume =

  48. [56]

    Statistical science , volume=

    Inference from iterative simulation using multiple sequences , author=. Statistical science , volume=. 1992 , publisher=

    1992

  49. [57]

    arXiv preprint arXiv:1405.0182 , year=

    Ergodicity of approximate MCMC chains with applications to large data sets , author=. arXiv preprint arXiv:1405.0182 , year=

    arXiv

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.