2021-03-18-brugge21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	brugge21a	0	On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions	469	477	469-477	469	false	Br{\"u}gge, Kai and Fischer, Asja and Igel, Christian	given family Kai Brügge given family Asja Fischer given family Christian Igel	2021-03-18		Proceedings of The 24th International Conference on Artificial Intelligence and Statistics	130	inproceedings	date-parts 2021 3 18	http://proceedings.mlr.press/v130/brugge21a/brugge21a.pdf