Qian Yu “Ising Model on Locally Tree-like Graphs: Uniqueness of Solutions to Cavity Equations”

Thursday, March 9
10:00 am - 11:00 am

Grier B - 34-401B

Add to Calendar
FacebookTwitterLinkedInEmailShare

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 distributional recursions and its fixed points. We prove that there is at most one non-trivial fixed point for Ising models with zero or certain random external fields. Previously this was only known for sufficiently “low-temperature” models. 

Our result simultaneously closes the following 6 conjectures in the literature: 1) independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly’16); 2) uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm’16); 3) optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu’16); 4) uniqueness of BP fixed point in broadcasting on trees in the Gaussian (large degree) limit (ibid); 5) boundary irrelevance in broadcasting on trees (Abbe-Cornacchia-Gu-P.’21); 6) characterization of entropy (and mutual information) of community labels given the graph in 2-SBM (ibid). 

This is a joint work with Yury Polyanskiy. Near the end of the talk, I’ll also provide a brief overview of my work on machine learning theory and coded computing. 

Paper link: https://arxiv.org/abs/2211.15242

Bio:
Qian Yu received his Ph.D. degree from the Department of Electrical and Computer Engineering at University of Southern California (USC). He received an M.Eng. degree in Electrical Engineering and a B.S. degree in Physics and EECS, both from Massachusetts Institute of Technology (MIT). He completed two postdoctoral appointments, the first at University of Southern California, and the second at the Department of Electrical and Computer Engineering at Princeton University. His interests span information theory, learning theory, distributed computing, and many other problems math-related. Qian is the recipient of the Thomas M. Cover Dissertation Award in 2022. He received the Google PhD Fellowship in 2018, and the Jack Keil Wolf ISIT Student Paper Award in 2017.

Details

  • Date: Thursday, March 9
  • Time: 10:00 am - 11:00 am
  • Category:
  • Location: Grier B - 34-401B

Host