On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions

Kai Brügge, Asja Fischer, Christian Igel

Introduction

The Metropolis algorithm is a cornerstone of Markov Chain Monte Carlo (MCMC) methods. In practical applications, such as training Restricted Boltzmann Machines or simulating Ising models, variables are often updated in a fixed, deterministic order (a "fixed scan") rather than a random one. While computationally efficient, fixed-order updates for multivariate binary distributions can lead to a lack of ergodicity, where the Markov chain becomes reducible and fails to converge to the target distribution. This paper addresses this theoretical gap by proposing a simple modification to the Metropolis transition operator.

The Modified Metropolis Operator

The standard Metropolis algorithm for binary variables accepts a proposed state flip with probability 1 if the new state is more or equally probable. The authors identify that the deterministic acceptance of equally probable states is the root cause of reducibility in fixed-order scans. They propose a modified operator:

  1. If the proposed state is more probable, accept with probability 1.
  2. If the proposed state is less probable, accept with the standard probability ratio.
  3. If the proposed state has the exact same probability, accept with a probability of 0.5.
State transition graph for a 3-bit system illustrating potential cycles and the mapping of state transitions to directed graphs.

By introducing this stochasticity for equal-probability transitions, the authors use graph theory to prove that the resulting Markov chain is irreducible and aperiodic for any multivariate binary distribution, regardless of the update order. This seemingly minor change allows the Markov chain to occasionally stay in its current state, breaking the deterministic loops that plague the standard algorithm.

Empirical Evaluation and Results

The authors evaluate the algorithm using $3 \times 3$ ferromagnetic Ising models, comparing the spectral gaps of Gibbs sampling, standard Metropolis, and the modified Metropolis algorithm. The spectral gap is a direct measure of convergence speed; a gap of zero indicates a failure to converge.

Spectral gap comparison for periodic (top) and non-periodic (bottom) Ising models across coupling strengths J.

As shown in the results, the standard Metropolis algorithm fails completely (spectral gap = 0) on the periodic Ising model due to the "equal probability trap." The modified algorithm, however, ensures convergence across all tested scenarios. In cases where the standard algorithm does converge (e.g., non-periodic boundaries), the modified version maintains comparable performance, even outperforming standard Metropolis at moderate coupling strengths ($J$).

Conclusion

This work provides a robust theoretical foundation for fixed-order Metropolis updates in binary systems. The proposed modification is computationally trivial to implement and guarantees convergence without sacrificing the efficiency of fixed scans. The authors suggest this modified operator should become the standard implementation for Metropolis MCMC in multivariate binary settings, closing a long-standing gap between MCMC theory and practice.

Summary updated

Abstract

The Metropolis algorithm is arguably the most fundamental Markov chain Monte Carlo (MCMC) method. But the algorithm is not guaranteed to converge to the desired distribution in the case of multivariate binary distributions (e.g., Ising models or stochastic neural networks such as Boltzmann machines) if the variables (sites or neurons) are updated in a fixed order, a setting commonly used in practice. The reason is that the corresponding Markov chain may not be irreducible. We propose a modified Metropolis transition operator that behaves almost always identically to the standard Metropolis operator and prove that it ensures irreducibility and convergence to the limiting distribution in the multivariate binary case with fixed-order updates. The result provides an explanation for the behaviour of Metropolis MCMC in that setting and closes a long-standing theoretical gap. We experimentally studied the standard and modified Metropolis operator for models were they actually behave differently. If the standard algorithm also converges, the modified operator exhibits similar (if not better) performance in terms of convergence speed.
BibTeX
@inproceedings{brugge2021convergence,
  author = {Kai Brügge and Asja Fischer and Christian Igel},
  title = {{On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}
Figure