Lecture: Tuesday 11:00am-12:30pm, 310 Soda
Instructor: Prasad Raghavendra
Office hours: Tuesday 2:30-3:30pm
In this course, we will explore the tractability of computational problems arising in high-dimensional statistics. Specifically, we will study
General techniques for designing efficient (i.e., polynomial-time) algorithms for these problems.
Conjectured computational barriers that arise among these problems and broad approaches to provide evidence of computational intractability.
A tentative list of topics include the following:
Problems:
Robust and heavy-tailed statistics: mean estimation and linear regression.
Mixture models, learning mixtures of Gaussians.
Stochastic block models, community detection.
Sparse PCA.
Matrix and tensor completion.
Algorithmic Tools:
Spectral methods & filtering.
Sums-of-squares semi-definite programming
Belief propagation
Approximate message passing
Evidence of intractability
Computational-statistical gaps.
Low degree hardness
Overlap gap property
Statistical query lower bounds.
Ideas from statistical physics:
Cavity Method
The class is aimed at graduate students specializing in theoretical computer science,statistics or related areas. A solid background in probability and linear algebra is an absolute must.
Scribing: one or two lectures 40%
Project: In groups of 2 or 3, write a survey on a topic of your choice : 40%
Class participation 20%
If you are interested in taking the class, please drop me an email with the subject line 'CS294 Enrollment’ along with details of what graduate program and research group you belong to, and relevant course/research experience if any.