Improved Estimation of Relaxation Time in Non-reversible Markov Chains

Geoffrey Wolfer, Aryeh Kontorovich

Abstract

We establish that the minimax sample complexity for estimating the pseudo-spectral gap $\gamma_{\mathsf{ps}}$ of an ergodic Markov chain within a constant multiplicative error is $\tilde{\Theta}\left( \frac{1}{\gamma_{\mathsf{ps}} \pi_{\star}} \right)$, where $\pi_{\star}$ denotes the minimum stationary probability. This result recovers the known bound for the reversible setting and resolves a significant open problem. Our approach introduces a fully-adaptive empirical procedure that utilizes a novel "reversible dilation" technique, leading to tighter confidence intervals and reduced computational complexity compared to previous methods.

Introduction: The Challenge of Non-Reversibility

Markov chains are fundamental to modern computational science, powering everything from MCMC sampling to reinforcement learning. A central question for practitioners is determining the "relaxation time"—the time required for a chain to converge to its stationary distribution. This time is inversely proportional to the spectral gap.

While the estimation of the spectral gap for reversible Markov chains is well-understood, many efficient modern algorithms rely on non-reversible chains. Historically, theoretical bounds for non-reversible chains were loose and often scaled with the state space size $|X|$, making them impractical for large-scale systems. This work bridges that gap, proving that non-reversibility does not inherently increase the difficulty of relaxation time estimation.

Methodology: Reversible Dilation and Adaptive Estimation

The authors employ several innovative techniques to achieve these optimal bounds:

  1. Minimax Analysis: By deriving a new upper bound for the sample complexity of estimating the pseudo-spectral gap ($\gamma_{\mathsf{ps}}$), the paper proves that a trajectory of length $\tilde{\Theta}(1/(\gamma_{\mathsf{ps}} \pi_{\star}))$ is sufficient for constant multiplicative error.
  2. Reversible Dilation: A key innovation is the introduction of a reversible dilation $\mathcal{S}_\pi(P)$. Unlike traditional "multiplicative reversiblization" ($P^*P$), which is computationally expensive, this $2|X| \times 2|X|$ matrix preserves spectral properties while being significantly cheaper to compute.
  3. Fully-Adaptive Estimator: The proposed algorithm does not require prior knowledge of chain parameters. It employs a "doubling trick" to automatically determine the optimal skipping rate, making the estimation process entirely data-driven.

Key Results and Comparison

The primary contribution is the establishment of an optimal sample complexity that matches the reversible case, effectively removing the dependency on the state-space size $|X|$ found in earlier literature.

Comparison of sample complexity bounds for estimating spectral gaps in reversible and non-reversible Markov chains.

The use of reversible dilation allows for the application of symmetric matrix concentration tools, such as Matrix Bernstein inequalities, which were previously inaccessible for non-reversible operators. Furthermore, the authors prove a new sub-multiplicativity property for the $\ell_2(\pi)$ norm, which was the technical breakthrough needed to eliminate the $|X|$ dependency. This leads to an estimator that is not only theoretically optimal but also computationally more efficient and provides tighter, data-adaptive confidence intervals.

Conclusion and Future Directions

This work provides a definitive answer to the sample complexity of estimating relaxation time in non-reversible chains for constant multiplicative error. By showing that non-reversibility is not a penalty, it opens the door for more robust analysis of modern sampling and learning algorithms.

While the paper closes the gap for constant multiplicative error, there remains an open problem regarding the exact dependency on the precision parameter $\epsilon$ and minimum probability $\pi_{\star}$ for arbitrarily small errors. Future work could also explore even more lightweight uncertainty guarantees for massive state spaces.

Summary updated

Abstract

We show that the minimax sample complexity for estimating the pseudo-spectral gap $γ_{\mathsf{ps}}$ of an ergodic Markov chain in constant multiplicative error is of the order of $$\tildeΘ\left( \frac{1}{γ_{\mathsf{ps}} π_{\star}} \right),$$ where $π_\star$ is the minimum stationary probability, recovering the known bound in the reversible setting for estimating the absolute spectral gap [Hsu et al., 2019], and resolving an open problem of Wolfer and Kontorovich [2019]. Furthermore, we strengthen the known empirical procedure by making it fully-adaptive to the data, thinning the confidence intervals and reducing the computational complexity. Along the way, we derive new properties of the pseudo-spectral gap and introduce the notion of a reversible dilation of a stochastic matrix.
BibTeX
@article{wolfer2024improved,
  author = {Geoffrey Wolfer and Aryeh Kontorovich},
  title = {{Improved Estimation of Relaxation Time in Non-reversible Markov Chains}},
  journal = {The Annals of Applied Probability},
  year = {2024},
  doi = {10.1214/23-aap1963},
}

Loading related content...

Figure