True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

2026/05/28 by Qinghua, Ding, Venkat Anantharam · 1 voice
Computer Science · Mathematics · #cs.LG #stat.CO #stat.ML

paper · pdf · doi:10.48550/arxiv.2605.30532

Abstract

We study true self-avoiding walk (TSAW) as a mechanism for improving empirical integral estimation via Markov chain Monte Carlo (MCMC). We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel P on a finite set, with stationary distribution π, in which the transition probabilities are penalized according to empirical overuse. Our main result is that the empirical occupation counts L_t(i) and transition counts N_t(i,j) of the resulting TSAW-based walk satisfy L_t(i)-tπ_i = O(√(log t)) \quadand N_t(i,j)-tπ_iP_ij=O(√(log t)) \qquadalmost surely for every state i and every edge (i,j) with P_ij>0. Consequently, for every bounded function f:V→\mathbb R, the error of our integral estimator converges as |\frac1t∑_s=0^t-1 f(X_s)-∑_{i∈ V}π_i f(i)| = O((√(log t))/(t)) \qquadalmost surely. These results show that, in contrast with the usual t^-1/2 error scaling for empirical averages under standard random-walk-based methods, TSAW-based estimator yields empirical integral errors of order O(√(log t)/t) almost surely, thereby achieving a substantially sharper dependence on the sample size t.

Citations

• Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
• Nonreversible MCMC from conditional invertible transforms: a complete recipe with convergence guarantees
• Self-trapping self-repelling random walks
• Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• On nonlinear Markov chain Monte Carlo
• Interacting Markov chain Monte Carlo methods for solving nonlinear measure-valued equations
• Irreversible Monte Carlo Algorithms for Efficient Sampling
• Self-repelling random walk with directed edges on Z
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better

Discussions

• Qinghua (Devon), Ding, Venkat Anantharam: True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration https://arxiv.org/abs/2605.30532 https://arxiv.org/pdf/2605.30532 https://arxiv. [bsky, 0 points, 0 comments]

Related

• Monte Carlo Methods for the Self-Avoiding Walk
• Noisy Monte Carlo: Convergence of Markov chains with approximate transition kernels
• Quasi Markov Chain Monte Carlo Methods
• A pseudo-marginal sequential Monte Carlo online smoothing algorithm
• Suppressing Random Walks in Markov Chain Monte Carlo Using Ordered Overrelaxation