2019-06-25-jain19b.md

abstract	section	title	layout	series	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	publisher	container-title	volume	genre	issued	pdf	extras
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.	contributed	Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation	inproceedings	Proceedings of Machine Learning Research	jain19b	0	Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation	1756	1771	1756-1771	1756	false	Jain, Vishesh and Koehler, Frederic and Liu, Jingbo and Mossel, Elchanan	given family Vishesh Jain given family Frederic Koehler given family Jingbo Liu given family Elchanan Mossel	2019-06-25		PMLR	Proceedings of the Thirty-Second Conference on Learning Theory	99	inproceedings	date-parts 2019 6 25	http://proceedings.mlr.press/v99/jain19b/jain19b.pdf