Testing Non-Reversible Chain Theory on Real Graph Random Walks

Many Markov chain samplers run faster when they are made non-reversible, meaning probability flows around loops in the state space instead of balancing equally in both directions. The theory behind these chains has grown quickly. There are now minimax-optimal estimators of how fast a non-reversible chain mixes, proofs that adding "vortices" (circulating flow) never increases estimator variance, and orderings of samplers by asymptotic variance. Almost none of these results has been checked on anything larger than a toy. The relaxation-time estimator of Improved estimation of relaxation time in nonreversible Markov chains has no experiments at all. The vortex theorem of Improving the Asymptotic Performance of Markov Chain Monte-Carlo by Inserting Vortices was tested only on a 128-state ring. This note proposes to close that gap in one setting where the theory can be checked exactly. In decentralized optimization, a single "token" carrying the model does a random walk over a real network, updating on local data at each node it visits. The transition matrix of that walk is known, it has a few hundred to a few thousand states, and its quality is measured downstream by optimization error.

The proposal has three parts. We build non-reversible token walks by adding vortices on real graphs, using only local information at each node. We measure every theoretical quantity exactly, because the matrix is small enough to handle directly. We then ask two questions: does the minimax estimator recover these quantities from a single trajectory at the predicted sample sizes, and which theoretical quantity actually predicts finite-time optimization error? The second question is open because the theory separates two things. Vortices provably reduce asymptotic variance, but nothing guarantees they improve the pseudo-spectral gap, which governs how fast the walk mixes. Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario states explicitly that its variance ordering says nothing about mixing speed.

Core Claim

Token walks on real graphs are the first realistic testbed where non-reversible chain theory can be checked against ground truth rather than against other estimates. We hypothesize two things. First, vortex insertion on real graphs gives a finite-time reduction in optimization error that matches its exact reduction in asymptotic variance. Second, there is a measurable regime of strong vortices where asymptotic variance keeps falling while the pseudo-spectral gap shrinks, and in that regime finite-horizon error gets worse. If both hold, practitioners need both quantities, and the data-adaptive estimator becomes the tool for telling the two regimes apart when no node knows the full matrix.

Research Program

The base chain $T$ is the Metropolis–Hastings random walk on a network, with stationary distribution $\pi$ set by the optimization target. Following the vortex paper, the non-reversible chain is $A = T + Q^{-1}H$. Here $Q = \mathrm{diag}(\pi)$, and $H$ is skew-symmetric with zero row and column sums, supported on graph edges, and scaled by a strength $\epsilon$ that is kept small enough for every entry of $A$ to stay nonnegative. These conditions keep $\pi$ stationary. The vortex paper leaves the choice of $H$ open as a combinatorial problem.

We use a cheap, local construction: a unit circulation around each triangle (or each element of a short-cycle basis) of the graph, with a random but fixed orientation. Each node then needs only its own triangle memberships, which is what decentralized deployment requires. A second, greedy construction picks cycles by their exactly computed effect on the asymptotic variance of the target gradient. This serves as an oracle upper bound on what a smarter design could achieve.

For every chain in the family (indexed by $\epsilon$ and the construction), we compute three quantities directly. The first is the pseudo-spectral gap $\gamma_{ps}$, defined through multiplicative reversibilizations of powers of $A$. The second is the exact asymptotic variance of the stochastic gradient noise, obtained from the fundamental matrix. The third is $\pi_* = \min_x \pi(x)$. We then run the data-adaptive confidence-interval procedure of Wolfer and Kontorovich on single trajectories of increasing length. We record relative error, interval coverage, wall-clock time and memory, and how these compare with the $\tilde{\Theta}(1/(\pi_*\gamma_{ps}\epsilon^2))$ rate they prove. Here $\epsilon$ means the target relative error, not vortex strength.

This directly tests whether the hidden constants are benign, which is the central concern of the empirical-validation literature. Examples of guarantees that turned out conservative in practice include A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. Finally, we run token-based stochastic approximation on each chain and measure parameter mean square error over time.

Baselines

The naive reference point is the reversible Metropolis–Hastings token walk, which is the baseline used in Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks. Every vortex chain is a perturbation of exactly this walk, so the comparison isolates the effect of circulation.

The strongest existing competitor is that paper's self-repellent random walk (SA-SRRW). It adapts transitions using visit counts and proves that asymptotic covariance shrinks as $O(1/\alpha^2)$ in the repulsion strength $\alpha$. It was evaluated on wikiVote (889 nodes) and Dolphins, on ijcnn1 and a9a. The file reports only qualitative results: lower mean square error than Metropolis–Hastings walks, and confirmation of the $O(1/\alpha^2)$ decay on Dolphins. There is no reported numerical value on Lacuna for SA-SRRW mean square error on wikiVote, ijcnn1 or a9a, so we will reproduce it.

All methods will run on the same graphs, datasets and number of token steps. Each gets the same step-size schedule family, and each gets an equal grid-search budget over its own knob: $\alpha$ for SRRW, $\epsilon$ for vortices. Beating SRRW means lower final mean square error at a matched step budget, averaged over seeds, with confidence intervals that do not overlap. We also test the composition of the two, SRRW running on top of a vortex base chain. This is natural because the two methods act on different parts of the chain: SRRW changes the visit-dependent reweighting, while vortices add circulation.

The ablation that isolates the key ingredient keeps the same perturbation magnitude but makes $H$ symmetric. That chain is reversible and is not stationary-preserving in the same way. We also compare against randomly oriented circulations versus greedily chosen ones. For the estimation question, the baselines are the plug-in spectral estimate from the empirical transition matrix and batch-means effective sample size. Computationally Efficient Estimation of the Spectral Gap of a Markov Chain (UCPI) is included as a reversible-only reference. It requires real positive spectra, so we expect it to fail or be inapplicable on the vortex chains, and we report that as a finding rather than a tuning failure.

Why not just…?

Why not just use the self-repellent walk, which already has a quadratic variance gain? SRRW is a real threat on the downstream metric, and the experiments compare against it directly. However, it is history-dependent and nonlinear, so none of the linear-chain theory (pseudo-spectral gap, vortex variance ordering) applies to it. It also does not answer whether that theory transfers to practice. If SRRW alone dominates every vortex chain and the composition adds nothing, we will report that circulation is redundant once repulsion is present.

Why not just compute the exact quantities, since the matrix is known? For the chain-design question we do exactly that, and that is what makes this setting a testbed. In deployment, though, no single node holds the full matrix, and graphs change over time. The estimator matters only if it works from one trajectory at realistic lengths. Exact computation is what lets us grade it.

Why not just tune $\epsilon$ by grid search on downstream error? On a fixed graph, grid search will find a good $\epsilon$, and it is included as a baseline. The open question is whether it is needed. If the measured $\gamma_{ps}$ and asymptotic variance predict the downstream ranking of chains, then a cheap trajectory diagnostic can replace costly optimization runs when choosing $\epsilon$ on a new graph. If they do not predict it, the theory fails a practical test, and that is worth knowing.

Proposed Experiments and Decisive Checks

The graphs are wikiVote and Dolphins, with ijcnn1 and a9a data distributed across nodes as in the SRRW paper. The 128-state ring is included only to reproduce the vortex paper's report that the reversible chain "reached only about 20-30% of the states within 1,000 steps." That reproduction checks that our implementation is correct.

There are three decisive checks. The first is estimator validity. If the data-adaptive intervals for $\gamma_{ps}$ undercover by more than a few points at trajectory lengths near the minimax rate, or if constants push the required length beyond $10\times$ that rate, the estimator is not yet practical on real chains. The second is transfer. Across the chain family, we compute the rank correlation between the exact asymptotic variance and the finite-horizon mean square error, and between $\gamma_{ps}$ and early-phase error. The gap hypothesis is falsified if asymptotic variance alone predicts error at every horizon. The third is regime detection. We look for strong vortex strengths where asymptotic variance improves but $\gamma_{ps}$ drops, and test whether the single-trajectory estimator flags those settings before optimization error reveals them. This would give the theory a concrete diagnostic role in practice.