Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
arXiv:1905.10031
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.
arXiv commentTo be presented on COLT 2019
References in corpus (8)
- Spectral redemption: clustering sparse networks
- Statistical physics of inference: Thresholds and algorithms
- Phase transition in the detection of modules in sparse networks
- Optimal detection of sparse principal components in high dimension
- Computational barriers in minimax submatrix detection
- Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
- The critical Ising model on trees, concave recursions and nonlinear capacity
- Key Capacity with Limited One-Way Communication for Product Sources