STSCI6940: Topics in high-dimensional inference

Instructor: Ahmed El Alaoui
Email: elalaoui at cornell dot edu
Meeting time: Tuesday-Thursday 2:45pm-4pm (virtual)
Office hours: Wednesday 3-5pm, or by appointment.

Description: We will be interested in the mathematics behind the problem of detecting and extracting a low-dimensional structure embedded in large amounts of noise. We will consider a few instructive models, and try to understand when this problem is feasible, first information-theoretically, and then algorithmically via an efficient procedure. We will see that these questions admit sharp characterizations, often reflected in phase transition phenomena in the high-dimensional limit. Our main goal will be to understand the mathematical techniques allowing such precise characterizations and get a view of the outstanding open problems. We will devote the first half of the course to an exposition of the foundations. We will cover some research papers in the second half through presentations by students.
The format of this class is inspired by a class taught by Nike Sun at MIT.

A tentative list of topics includes:

Evaluation: Students will be asked to work on a small project in groups of at most two, present in one of the lectures, and return a graded homework. A successful project can either consist in understanding and distilling the main ideas behind a particular result, applying a known method to a new problem, or attempting to push the limits of a particular technique.

Prerequisites: A graduate or advanced undergraduate level course in probability and real analysis is highly recommended.


Notes in tex (so far).

Student presentation:


You can use the following list to pick a project and a subject for your talk.

The rank-one spiked Wigner model - estimation:

The rank-one spiked Wigner model - detection:

Behavior of eigenvalues and eigenvectors:

Approximate message passing:

Pinning, simple decompositions of measures, and accuracy of the mean-field approximation:

Sampling from log-concave measures:

Sampling from the SK measure:

Evidence of hardness: the low-degree likelihood ratio method and overlap gaps:

The stochastic block model and broadcasting / reconstruction on trees:

Beyond locally tree-like graphs, and information-percolation bounds: