S&DS 684: Statistical inference on graphsYihong Wu, Yale University, Spring 2023
An emerging research thread in statistics and machine learning deals with recovering latent structures from combinatorial data represented by graphs or matrices. This graduate-level course provides an introduction to the mathematical and algorithmic tools for studying such problems. We will discuss information-theoretic methods for determining the fundamental limits of various detection and recovery problems on random graphs. Complementing the objective of characterizing the information-theoretical limits, another significant direction is to develop computationally efficient algorithms (such as spectral methods, convex relaxation, and belief propagation) that attain the statistical optimality, or to understand the lack thereof (computational barriers). Specific topics will include spectral clustering, planted clique and partition problem, community detection on stochastic block models, broadcasting on trees, planted matching problem (linear and quadratic assignment problems), statistical-computational tradeoffs. We will be following this set of lecture notes co-developed by Yihong Wu and Jiaming Xu.
Announcements |