# Fast-Mixing Markov Chains without Gradients

arXiv: https://arxiv.org/abs/2606.27564 · HTML: https://mlsanity.com/paper/2606.27564/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 25 Jun 2026.

## Builds on (most cited first, 14 of 14)

- [DeepONet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators](https://mlsanity.com/paper/1910.03193/) (2019)
- [Model Reduction and Neural Networks for Parametric PDEs](https://mlsanity.com/paper/2005.03180/) (2020)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Auxiliary gradient-based sampling algorithms](https://mlsanity.com/paper/1610.09641/) (2016)
- [Accelerating Asymptotically Exact MCMC for Computationally Intensive Models via Local Approximations](https://mlsanity.com/paper/1402.1694/) (2014)
- [Penalising model component complexity: A principled, practical approach to constructing priors](https://mlsanity.com/paper/1403.4630/) (2014)
- [Multilevel Delayed Acceptance MCMC](https://mlsanity.com/paper/2202.03876/) (2022)
- [Performance of Neural and Polynomial Operator Surrogates](https://mlsanity.com/paper/2604.00689/) (2026)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Dirichlet-Neumann Averaging: The DNA of Efficient Gaussian Process Simulation](https://mlsanity.com/paper/2412.07929/) (2024)

## Built on by (most cited first, 1 of 1)

- [Gradient-free Riemannian Langevin Sampler](https://mlsanity.com/paper/2607.07519/) (2026)

## Abstract (arXiv)

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 maxkappa, 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 ≥ kappa, and scales as O(kappa2), 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.