S&DS 684: Statistical inference on graphs

An emerging research thread in statistics and machine learning deals with finding latent structures from data represented by graphs or matrices. This course will provide an introduction to mathematical and algorithmic tools for studying such problems. We will discuss information-theoretic methods for determining the fundamental limits, as well as methodologies for attaining these limits, including spectral methods, semidefinite programming relaxations, message passing algorithms, etc. Specific topics will include spectral clustering, planted clique and partition problem, sparse PCA, community detection on stochastic block models, broadcasting on trees, statistical-computational tradeoffs.

Complementing this objective of understanding the fundamental limits, another significant direction is to develop computationally efficient procedures that attain the statistical optimality, or to understand the lack thereof. We will discuss the recent trend of combining the statistical and algorithmic perspectives and the computational barriers in a series of statistical problems on large matrices and random graphs.

Announcements

• Welcome to S&DS 684. The first lecture is Aug 29.

• Lectures 2-4 have been posted.

• The first homework has been posted. Due Oct 10.