A1223
Title: Group-averaged Markov chains II: Tuning of group action in finite state space
Authors: Michael Choi - National University of Singapore (Singapore) [presenting]
Abstract: Group-averaged Markov chains obtained by augmenting a $\pi$-stationary transition kernel $P$ with a group action on the state space via orbit kernels are studied. Given a group $\mathcal G$ with orbits $(\mathcal O_i)_{i=1}^k$, three canonical orbit kernels are analysed: 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\}$. It is shown that orbit averaging never deteriorates the absolute spectral gap or asymptotic variance when $P$ is reversible. A direct and simple proof of pythagorean identity under the Kullback-Leibler (KL) divergence is given, showing that $GPG$ arises naturally as an information projection of $P$ onto the set of $G$-invariant transition matrices. For a given $P$, the optimal choice of $G$ with a fixed number of orbits that minimises the one-step KL divergence to stationarity is characterised. Analogously, for a given $G$, the optimal choice of $P$ is characterised and sufficient conditions under which $GPG = \Pi$ are given. It is further shown 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.
