On additive averaging kernels for finite Markov chains

1. Problem Statement

The paper addresses the challenge of accelerating the convergence of Markov Chain Monte Carlo (MCMC) samplers to their stationary distribution $\pi$. While recent work has shown that group-averaged (composition-based) kernels, such as $GPG$ (where $G$ is a Gibbs kernel and $P$ is a baseline sampler), significantly improve mixing times and spectral gaps, these constructions introduce computational overhead and structural complexity.

The authors investigate whether similar improvements can be achieved through a simpler, additive construction. Specifically, they study the additive mixture kernel:
$$A_\alpha = \alpha P + (1 - \alpha)G$$
where:

• $P$ is a baseline $\pi$-stationary Markov kernel (e.g., Glauber dynamics).
• $G$ is a Gibbs kernel induced by a partition of the state space $\mathcal{X} = \bigcup_{i=1}^k O_i$.
• $\alpha \in [0, 1]$ is a mixing parameter controlling the trade-off between local updates ($P$) and global averaging within blocks ($G$).

The core research questions are:

1. How to interpret $A_\alpha$ theoretically?
2. How to optimally choose the partition $(O_i)$ and the parameter $\alpha$ to minimize the distance to stationarity?
3. How does $A_\alpha$ compare to composition-based kernels in terms of convergence speed and computational cost?

2. Methodology and Theoretical Framework

2.1 Lifted Chain Interpretation

The authors establish that $A_\alpha$ can be interpreted as the projection of a lifted Markov chain $Q_\alpha$ defined on an augmented state space $\tilde{\mathcal{X}} = \mathcal{X} \times \{-1, +1\}$.

• In the lifted chain, an auxiliary variable $\sigma$ determines whether to apply $P$ (if $\sigma = -1$) or $G$ (if $\sigma = +1$).
• Projecting $Q_\alpha$ back onto the original state space $\mathcal{X}$ recovers the additive kernel $A_\alpha$. This provides a rigorous probabilistic foundation for the mixture.

2.2 Optimization Objectives

The paper analyzes the convergence of $A_\alpha$ using two distinct objective functions:

A. Squared Frobenius Norm
The authors minimize $\|A_\alpha - \Pi\|_{F, \pi}^2$, where $\Pi$ is the rank-1 matrix with rows equal to $\pi$.

• Trace Formulas: They derive explicit formulas relating the Frobenius distance to the trace of the projection chain $\bar{P}$ induced by the partition.
• Cheeger-type Functional: For two-block partitions ($S \cup S'$), minimizing the distance is equivalent to maximizing a functional $g(S)$ related to the symmetrized Cheeger constant.
• Combinatorial Optimization: The problem is shown to admit a difference-of-submodular (DS) decomposition. This allows the use of efficient approximation algorithms, specifically Majorisation-Minimisation (MM), to find near-optimal partitions without exhaustive search.
• Singleton Approximation: A computationally efficient approximation is proposed where the optimal set $S$ is restricted to a singleton, reducing the search complexity from exponential to linear in the state space size.
• Spectral Bounds: They derive geometric decay rates governed by the absolute spectral gap of $P$, showing that $\|A_\alpha^l - \Pi\| \leq (1 - \alpha \gamma^*(P))^{2(l-1)} \|A_\alpha - \Pi\|$.

B. Kullback-Leibler (KL) Divergence
The authors analyze $D_{KL}(A_\alpha \| \Pi)$.

• Convexity Bounds: Using the convexity of $x \log x$, they prove that the KL divergence of the mixture is bounded by the convex combination of the KL divergences of $P$ and $G$.
• Partition Independence: Crucially, the bound depends on the partition only through the Gibbs component $G$. The optimal partition for minimizing the KL divergence is explicitly characterized as grouping the $k-1$ smallest probability masses into singletons and the remainder into one large block.

3. Key Contributions

1. Theoretical Unification: Provided a lifted chain interpretation for additive mixtures, linking them to projection chains and offering a new perspective on how randomization between local and global moves affects convergence.
2. Optimization Algorithms: Developed a structured approach to partition selection for the Frobenius objective. By identifying the problem as a difference-of-submodular optimization, they enabled the use of MM algorithms for scalable partition selection.
3. Explicit Bounds: Established geometric decay rates for the Frobenius norm and convexity-based upper bounds for the KL divergence, clarifying the theoretical limits of the additive approach.
4. Parameter Sensitivity: Demonstrated that the mixing parameter $\alpha$ is critical. The study reveals a "Goldilocks" zone where intermediate values of $\alpha$ (typically $\approx 0.5$) outperform both pure local dynamics ($\alpha=1$) and pure averaging ($\alpha=0$).

4. Numerical Results

The authors validated their theory using the Curie-Weiss model (a mean-field Ising model) with Glauber dynamics as the baseline $P$.

• Comparison with Composition Kernels:

  • They compared $A_{1/2}$ against the baseline $P$ and composition-based kernels ($GPG$, $GPGS$).
  • Hierarchy: In terms of raw mixing speed (Total Variation distance), the hierarchy was consistently: $GPGS > GPG > A_{1/2} > P$.
  • Cost vs. Performance: While composition kernels were faster, they require multiple Gibbs steps per iteration. $A_\alpha$ offers a computationally cheaper alternative that still significantly outperforms the baseline $P$.

• Optimal Partitions:

  • When partitions were optimized via the Frobenius objective, composition-based kernels ($GPG$, $GPGS$) tended to select highly unbalanced cuts (concentrating mass in one block).
  • In contrast, the additive kernel $A_\alpha$ favored more balanced partitions (e.g., $\pi(S) \approx 0.5$), suggesting different structural requirements for optimality between additive and multiplicative schemes.

• Role of $\alpha$:

  • Experiments showed a consistent U-shaped curve for Total Variation distance vs. $\alpha$.
  • $\alpha = 0$ (Pure $G$) fails to explore the full state space (no inter-block transitions).
  • $\alpha = 1$ (Pure $P$) suffers from slow mixing due to metastability.
  • Intermediate $\alpha$ (e.g., 0.5 to 0.75) achieved the best performance by balancing local exploration with global averaging.

5. Significance

This work provides a computationally efficient alternative to complex composition-based MCMC accelerators.

• Practicality: The additive kernel $A_\alpha$ is easier to implement and cheaper per iteration than $GPG$ or $GPGS$, making it attractive for high-dimensional problems where Gibbs sampling is expensive.
• Design Principles: The paper offers concrete guidelines for practitioners:
  1. Use additive mixtures when computational budget per step is constrained.
  2. Do not rely on extreme values of $\alpha$; tune $\alpha$ to balance local and global moves.
  3. Partition selection should be guided by the specific objective (Frobenius vs. KL), as they yield different optimal structures (balanced vs. unbalanced cuts).
• Theoretical Insight: The connection between additive mixtures, lifted chains, and submodular optimization opens new avenues for designing and analyzing MCMC algorithms that leverage structural information of the state space without the complexity of non-reversible or fully lifted constructions.