Instructor: Frederic Koehler
Tuesday and Thursday, 12:30 PM - 1:50 PM
Location: Jones 303
This is a class on the precise analysis of high-dimensional optimization problems arising from statistics, learning, and other areas using probabilistic tools. A main conceptual focus is the relationship between computational/constructive vs statistical/existential tractability. Techniques related to statistical physics (e.g. AMP), combinatorial and nonconvex optimization, and gaussian processes will be covered.
Subject to revision.
Week 1: Intro
Week 2: Replica trick
Week 3: REM and concentration
Weeks 4-5: Optimization with random matrices
Weeks 6-7: Message passing and more Gaussian processes
Weeks 8-9: Random graphs, average-case hardness/predictions
Every student enrolled for credit should scribe a class. Scribe notes should aim to be high quality, mathematically correct, and intelligible to someone who missed the class. They are due within 9 days of when the class occurred. I might ask for edits to the scribe notes if I observe areas for improvement. They will be posted on the course webpage.
Scribing template: scribetemplate.tex Please send tex and pdf when completed with scribing.
These are some sample course notes,books,etc which cover many interesting topics. They have some overlapping content with this course and are useful references.
There will be a course project with a written report for all students enrolled for a grade. You may either write a survey of at least 2 papers, or do original research of some kind. The ideal goal is to make a novel intellectual contribution, so do not just reproduce the contents of an existing paper. For example, if you are doing a survey try to identify important open problems and whether the techniques in the paper have limitations, try to simplify the proofs, etc. You could also try to do something more experimental, find new domains of application, connect with theory, etc. Please send a half-page project proposal by end of Friday, Nov 7. Your proposal should include a sentence explicitly explaining why the topic you are interested in should be considered related to this class. Some example topics and papers of interest: Google doc
If you are auditing the class, please email me to ensure you receive relevant announcements.