CS 496: Learning in Networks, Fall 2023
Basic info
Course description: This is a graduate topics course on learning in networks, focusing in particular on fundamental statistical and computational limits. Topics include the planted clique problem, community detection, high-dimensional random geometric graphs, root-finding algorithms, graph matching, information-computation gaps, and more. While exploring these topics, we will discuss several general techniques that are applicable more broadly, such as the first and second moment methods, concentration inequalities, martingales, branching processes, information-theoretic methods, spectral algorithms, and more.
Goals: The goals of the course are three-fold: (1) to give an overview of recent research progress in the area; (2) to highlight ideas and techniques that are broadly useful, enriching students' technical tool box; and (3) to highlight open problems and create excitement about future research in the area.
Prerequisites: General mathematical maturity. More specifically, familiarity with probability, linear algebra, statistics, and algorithms. Please contact the instructor with questions.
Instructor: Miklos Z. Racz
Lecture time and location: MW 11:00 am - 12:20 pm, Tech LG66
Office hours: M 2 - 4 pm, 2006 Sheridan Rd, Room 108
Grading and course policies
Grading: The course grade will be based on the following breakdown:
- participation 20%
- HW 30%
- paper presentation 50%
Paper presentation: Every student will pick a recent research paper and prepare a 20 minute presentation on it. The last couple of weeks of the course will be devoted to student presentations. A large list of possible papers will be provided before the start of the course.
Resources
The course will combine material from a number of recent lecture notes and surveys, as well as recent research papers. These include (all freely available online):
- Yihong Wu and Jiaming Xu, Statistical inference on graphs: Selected Topics, 2023. Lecture notes for similar courses at Duke and Yale. [ online ]
- Miklos Z. Racz and Sebastien Bubeck, Basic models and questions in statistical network analysis, Statistics Surveys, 11:1--47, 2017. [ online ]
- Gabor Lugosi, Lectures on Combinatorial Statistics, Saint-Flour lecture notes, 2017. [ online ]
- Emmanuel Abbe, Community Detection and Stochastic Block Models: Recent Developments, Journal of Machine Learning Research, 18:1--86, 2018. [ online ]
- Sebastien Roch, Modern Discrete Probability: An Essential Toolkit, 2023. [ online ]
Back to Teaching Home