# Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 64 references that are in the map.
- First posted on arXiv 8 May 2023.

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

- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Revisiting the central limit theorems for the SGD-type methods](https://mlsanity.com/paper/2207.11755/) (2022)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Nonreversible MCMC from conditional invertible transforms: a complete recipe with convergence guarantees](https://mlsanity.com/paper/2012.15550/) (2020)
- [Dynamic social learning under graph constraints](https://mlsanity.com/paper/2007.03983/) (2020)
- [Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning](https://mlsanity.com/paper/2012.00805/) (2020)

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

- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [Consistency-Aware Padding for Incomplete Multi-Modal Alignment Clustering Based on Self-Repellent Greedy Anchor Search](https://mlsanity.com/paper/2507.03917/) (2025)
- [Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability](https://mlsanity.com/paper/2607.20818/) (2026)
- [Self-Repulsive Sampling for Diffusion Language Models](https://mlsanity.com/paper/2609.39560/) (2026)

## Abstract (arXiv)

We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration in the form of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real α, we prove that the empirical distribution of the process converges almost surely to the the target (stationary) distribution of the underlying Markov chain kernel. We then provide a central limit theorem and derive the exact form of the arising asymptotic co-variance matrix, which allows us to show that the SRRW with a stronger repellence (larger α) always achieves a smaller asymptotic covariance, in the sense of Loewner ordering of co-variance matrices. Especially for SRRW-driven MCMC algorithms, we show that the decrease in the asymptotic sampling variance is of the order O(1/α), eventually going down to zero. Finally, we provide numerical simulations complimentary to our theoretical results, also empirically testing a version of SRRW with α increasing in time to combine the benefits of smaller asymptotic variance due to large α, with empirically observed faster mixing properties of SRRW with smaller α.