Self-Repellent Random Walks on General Graphs - Achieving Minimal Sampling Variance via Nonlinear Markov Chains (Extended Abstract)

Vishwaraj Doshi, Jie Hu, Do Young Eun, Yuhang Tian, Changzhi Zhou, Jing Xu, Ziyi Yang, Shuhao Zhang

This blog-style summary covers the research presented in the paper "Self-Repellent Random Walks on General Graphs - Achieving Minimal Sampling Variance via Nonlinear Markov Chains," an extended abstract of award-winning work presented at IJCAI-24.

TL;DR

The authors introduce a "Self-Repellent Random Walk" (SRRW) that uses its entire history to avoid frequently visited nodes, effectively "pushing" the walker toward unexplored areas of a graph. This nonlinear Markov chain approach significantly reduces sampling variance compared to standard random walks, achieving a performance boost that is even more pronounced in distributed stochastic optimization tasks.

What Problem Does This Paper Address?

Many algorithms in statistics and machine learning rely on Markov Chain Monte Carlo (MCMC) sampling. In these scenarios, a "random walker" moves across a network (graph) to estimate a target quantity. However, standard random walks are often "lazy"—they can get trapped in local clusters of the graph due to the underlying topology, leading to highly correlated samples and high variance in the final estimate.

While existing techniques like "non-backtracking" random walks try to fix this by preventing the walker from immediately returning to its previous step, they only look at the very recent past. This paper addresses the challenge of how to use the entire history of the walker to speed up diffusion and achieve the lowest possible sampling variance.

Methods

The core innovation is the Self-Repellent Random Walk (SRRW). Unlike a standard Markov chain where transition probabilities are fixed, the SRRW is a nonlinear Markov chain.

Key technical components include:

  • The Transition Kernel: The probability of moving to a neighbor is weighted by a "repellence" function. If a neighbor has been visited many times in the past (high "occupational measure"), the walker is less likely to go there.
  • The $\alpha$ Parameter: The authors parameterize the repellence using a power law: $r(x) \propto x^{-\alpha}$. Here, $\alpha$ represents the "strength" of the repellence. When $\alpha = 0$, it reverts to a standard random walk.
  • Scale Invariance: The authors prove that their specific polynomial form is the only one that maintains "scale invariance," meaning the algorithm only needs local information (neighboring nodes) and doesn't require knowledge of global graph constants to work.
  • Stochastic Approximation (SA): To prove convergence, the authors treat the random walk as a stochastic approximation problem, linking the discrete jumps of the walker to a continuous deterministic system (Ordinary Differential Equations).

Datasets

As a theoretical paper focused on algorithmic foundations, the authors evaluate their method using:

  • Synthetic General Graphs: Used to prove the "Almost Sure Convergence" to target distributions (like the Uniform distribution).
  • Distributed Optimization Simulations: The authors tested an "SA-SRRW" version on an $L_2$-regularized binary classification problem using Stochastic Gradient Descent (SGD).
  • Target Distributions: They specifically demonstrate effectiveness on the Metropolis-Hastings Random Walk (MHRW) kernel.

Key Insights and Ideas

  • The "Push" Effect: By avoiding the past, the walker is forced to explore the graph more aggressively. This leads to a "Loewner ordering" of covariance matrices, which is a fancy way of saying that for any $\alpha_1 > \alpha_2$, the variance with $\alpha_1$ is guaranteed to be lower.
  • Surpassing i.i.d. Sampling: Remarkably, for large enough $\alpha$, the SRRW can achieve lower sampling variance than an independent and identically distributed (i.i.d.) sampler. This is counter-intuitive because i.i.d. samples are usually considered the "gold standard," but the SRRW’s active avoidance of its own history makes it even more efficient at covering the state space.
  • The Optimization Amplification: The benefit of using SRRW is "amplified" when applied to distributed optimization. While the sampling variance decreases at a rate of $O(1/\alpha)$, the optimization error (asymptotic co-variance of iterates) decreases at a much faster rate of $O(1/\alpha^2)$.

Key Results

  • Convergence: The authors provide a formal proof that the empirical distribution of the SRRW converges "almost surely" to the target distribution for any $\alpha \geq 0$.
  • Variance Reduction: They derive a Central Limit Theorem (CLT) for the SRRW, showing that as $\alpha$ increases, the asymptotic variance goes down to zero.
  • Empirical Validation: Simulations (Figure 3 in the paper) confirm the theoretical $O(1/\alpha^2)$ speedup in Mean Squared Error (MSE) for optimization tasks, showing a clear performance ordering where higher $\alpha$ values result in faster, more stable convergence.

Limitations and Future Work

  • Numerical Stability: While higher $\alpha$ is theoretically better, the authors note that very large values of $\alpha$ might lead to numerical or computational stability issues in real-world implementations.
  • Local vs. Global: The algorithm relies on local visit counts. In extremely large or dynamic graphs, maintaining and communicating these counts accurately could introduce overhead.
  • Wider Adoption: The authors advocate for the "wider adoption" of nonlinear Markov chains, suggesting that future work could explore these "unconventional noise sequences" in other areas of reinforcement learning and decentralized AI.

Summary updated

BibTeX
@inproceedings{doshi2024self,
  author = {Vishwaraj Doshi and Jie Hu and Do Young Eun and Yuhang Tian and Changzhi Zhou and Jing Xu and Ziyi Yang and Shuhao Zhang},
  title = {{Self-Repellent Random Walks on General Graphs - Achieving Minimal Sampling Variance via Nonlinear Markov Chains (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=9t8FTdULAa},
}
Figure