Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 496: Learning in Networks


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

Instructor consent

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.

  • This course fulfills CS Technical Elective area
REQUIRED TEXTBOOK: N/A
REFERENCE TEXTBOOKS: There are no required textbooks. 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. Lecture notes, 2023. — lecture notes for similar courses at Duke and Yale
  • Miklos Z. Racz and Sebastien Bubeck. Basic models and questions in statistical network analysis. Statistics Surveys, 11:1–47, 2017.
  • Gabor Lugosi. Lectures on Combinatorial Statistics. Saint-Flour lecture notes, 2017.
  • Emmanuel Abbe. Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research, 18:1–86, 2018.

COURSE COORDINATORS: Prof. Miklos Z. Racz

COURSE INSTRUCTOR: Prof. Miklos Z. Racz

COURSE 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.