Talk info 12/01/22

Abstract: In the study of Ising models on large locally tree-like graphs, in both rigorous and non-rigorous methods one is often led to understanding the so-called belief propagation (BP) distributional recursion and its fixed point (also known as Bethe fixed point, cavity equation, 1RSB). In this work we prove there is at most one non-trivial fixed point for Ising models for both zero and certain random external fields. This long sought-after result simultaneously resolves 6 conjectures formulated over the last 10+ years in the literature on stochastic block models and Ising models. Interestingly, our proof is based on information-theoretic ideas of channel comparison and is rather simple. 

A machine learning application is in the area of community detection in which n vertices are assigned equiprobable hidden binary labels and the adjacent vertices are connected with probability a/n or b/n depending on whether they have the same label or not. The goal is to reconstruct the latent community structure based on observation of the graph only. BP-uniqueness implies that a simple efficient algorithm—BP initialized by the sign of the second eigenvector—achieves optimal recovery rate, exactly matching performance of the exponential-time maximum likelihood estimator.

Joint work with Qian Yu (Princeton).

Bio: Yury Polyanskiy is a Professor of Electrical Engineering and Computer Science and a member of LIDS, IDSS and the Center of Statistics. Yury received M.S. degree in applied mathematics and physics from the Moscow Institute of Physics and Technology, Moscow, Russia in 2005 and Ph.D. degree in electrical engineering from Princeton University, Princeton, NJ in 2010. His research interests span information theory, statistical machine learning, error-correcting codes, wireless communication and fault tolerance. Dr. Polyanskiy won the 2020 IEEE Information Theory Society James Massey Award, 2013 NSF CAREER award and 2011 IEEE Information Theory Society Paper Award.