On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions.
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions. / Brügge, Kai; Fischer, Asja; Igel, Christian.
Proceedings of The 24th International Conference on Artificial Intelligence and Statistic. PMLR, 2021. p. 469-477 (Proceedings of Machine Learning Research, Vol. 130).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions.
AU - Brügge, Kai
AU - Fischer, Asja
AU - Igel, Christian
PY - 2021
Y1 - 2021
N2 - 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 where they actually behave differently. If the standard algorithm also converges, the modified operator exhibits similar (if not better) performance in terms of convergence speed.
AB - 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 where they actually behave differently. If the standard algorithm also converges, the modified operator exhibits similar (if not better) performance in terms of convergence speed.
M3 - Article in proceedings
T3 - Proceedings of Machine Learning Research
SP - 469
EP - 477
BT - Proceedings of The 24th International Conference on Artificial Intelligence and Statistic
PB - PMLR
T2 - 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
Y2 - 13 April 2021 through 15 April 2021
ER -
ID: 287826148