Group-averaged Markov chains II: tuning of group action in finite state space

Abstract

We study group-averaged Markov chains obtained by augmenting a $π$-stationary transition kernel $P$ with a group action on the state space via orbit kernels. Given a group $\mathcal{G}$ with orbits $(\mathcal{O}_i)_{i=1}^k$, we analyse three canonical orbit kernels: namely the Gibbs $(G)$, Metropolis-Hastings $(M)$, and Barker $(B)$ kernels, as well as their multiplicative sandwiches $QPQ$ and the additive mixtures $\frac{1}{2}(P+Q)$ where $Q\in\{G,M,B\}$. We show that $M^t, B^t \to G$ blockwise as $t \to \infty$ under suitable conditions, that the projection chains induced by $(\mathcal{O}_i)_{i=1}^k$ coincide for $GPG$ and $P$, and that orbit averaging never deteriorates the absolute spectral gap or asymptotic variance when $P$ is reversible. We give a direct and simple proof of Pythagorean identity under the Kullback-Leibler (KL) divergence, showing that $GPG$ arises naturally as an information projection of $P$ onto the set of $G$-invariant transition matrices. For a given $P$, we characterise the optimal choice of $G$ with a fixed number of orbits that minimises the one-step KL divergence to stationarity. Analogously, for a given $G$, we characterise the optimal choice of $P$ and give sufficient conditions under which $GPG = Π$. We further show that alternating projections over multiple group actions converge at a rate governed by the singular values of an overlap matrix, and that in structured cases, this yields exact sampling where the number of group actions grows logarithmically with the size of the state space. Based on the theory, we propose two heuristics to tune $G$ in practice. We also illustrate the results on discrete uniform and multimodal examples, including the Curie-Weiss model where $GPG$ achieves polynomial (in inverse temperature and dimension) mixing while Glauber dynamics remains exponentially slow.

Summary

This paper introduces a novel framework for improving Markov Chain Monte Carlo (MCMC) methods by augmenting Markov chains with group actions on the state space. By systematically incorporating group actions to create group-averaged Markov chains, the authors demonstrate improved mixing properties and provide a theoretical foundation for accelerating sampling from complex distributions.

Key Insights

• •The paper introduces group-averaged Markov chains, a method that leverages group actions to enhance the mixing of Markov chains, offering a more flexible approach than previous methods relying on equi-probability jumps.
• •The authors analyze three canonical "orbit kernels" (Gibbs, Metropolis-Hastings, and Barker) and prove that repeated application of Metropolis-Hastings or Barker kernels converges to the Gibbs kernel under certain conditions.
• •The paper demonstrates that orbit averaging, using the proposed techniques, never deteriorates the absolute spectral gap when the original chain is reversible, and can lead to significant improvements in mixing properties, as shown by the theoretical guarantees on the spectral gap of the group-averaged kernels.
• •They show the connection between group-averaged kernels and information projection, proving that GPG is the closest G-invariant transition matrix to P in terms of Kullback-Leibler divergence.
• •The paper addresses the inverse problem of identifying the optimal group action and demonstrates that the optimal choice aggregates high-mass states into a single orbit while leaving the remainder as singletons, suggesting a strategy for identifying effective group actions.

Practical Implications

• •The framework provides a theoretical basis for improving MCMC sampling in various fields by strategically incorporating group actions, offering potential for faster convergence and more efficient exploration of complex probability distributions.
• •The heuristics for tuning and selecting appropriate group actions, particularly in settings without obvious symmetry, offer practical guidance for implementing group-averaged Markov chains in real-world applications.
• •Future research can extend the framework to continuous state spaces and develop more efficient algorithms for implementing group-averaged Markov chains, further broadening the applicability of this approach.
• •The Curie-Weiss model example highlights the potential for overcoming ergodicity challenges in complex systems, illustrating the benefits of exploiting symmetries to improve sampling efficiency.

Links & Resources

Authors

Cite This Paper