Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation

Vishesh Jain, Frederic Koehler, Jingbo Liu, Elchanan Mossel
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1756-1771, 2019.

Abstract

The analysis of Belief Propagation and other algorithms for the {\em reconstruction problem} plays a key role in the analysis of community detection in inference on graphs, phylogenetic reconstruction in bioinformatics, and the cavity method in statistical physics. We prove a conjecture of Evans, Kenyon, Peres, and Schulman (2000) which states that any bounded memory message passing algorithm is statistically much weaker than Belief Propagation for the reconstruction problem. More formally, any recursive algorithm with bounded memory for the reconstruction problem on the trees with the binary symmetric channel has a phase transition strictly below the Belief Propagation threshold, also known as the Kesten-Stigum bound. The proof combines in novel fashion tools from recursive reconstruction, information theory, and optimal transport, and also establishes an asymptotic normality result for BP and other message-passing algorithms near the critical threshold.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-jain19b, title = {Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation}, author = {Jain, Vishesh and Koehler, Frederic and Liu, Jingbo and Mossel, Elchanan}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {1756--1771}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/jain19b/jain19b.pdf}, url = {https://proceedings.mlr.press/v99/jain19b.html}, abstract = {The analysis of Belief Propagation and other algorithms for the {\em reconstruction problem} plays a key role in the analysis of community detection in inference on graphs, phylogenetic reconstruction in bioinformatics, and the cavity method in statistical physics. We prove a conjecture of Evans, Kenyon, Peres, and Schulman (2000) which states that any bounded memory message passing algorithm is statistically much weaker than Belief Propagation for the reconstruction problem. More formally, any recursive algorithm with bounded memory for the reconstruction problem on the trees with the binary symmetric channel has a phase transition strictly below the Belief Propagation threshold, also known as the Kesten-Stigum bound. The proof combines in novel fashion tools from recursive reconstruction, information theory, and optimal transport, and also establishes an asymptotic normality result for BP and other message-passing algorithms near the critical threshold.} }
Endnote
%0 Conference Paper %T Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation %A Vishesh Jain %A Frederic Koehler %A Jingbo Liu %A Elchanan Mossel %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-jain19b %I PMLR %P 1756--1771 %U https://proceedings.mlr.press/v99/jain19b.html %V 99 %X The analysis of Belief Propagation and other algorithms for the {\em reconstruction problem} plays a key role in the analysis of community detection in inference on graphs, phylogenetic reconstruction in bioinformatics, and the cavity method in statistical physics. We prove a conjecture of Evans, Kenyon, Peres, and Schulman (2000) which states that any bounded memory message passing algorithm is statistically much weaker than Belief Propagation for the reconstruction problem. More formally, any recursive algorithm with bounded memory for the reconstruction problem on the trees with the binary symmetric channel has a phase transition strictly below the Belief Propagation threshold, also known as the Kesten-Stigum bound. The proof combines in novel fashion tools from recursive reconstruction, information theory, and optimal transport, and also establishes an asymptotic normality result for BP and other message-passing algorithms near the critical threshold.
APA
Jain, V., Koehler, F., Liu, J. & Mossel, E.. (2019). Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:1756-1771 Available from https://proceedings.mlr.press/v99/jain19b.html.

Related Material