HackMD
Algorithmic Statistics (6.S896), Fall '23, MIT
Prerequisites: Mathematical maturity is the main prerequisite. Familiarity with linear algebra, probability, discrete math, and algorithms at the advanced undergraduate level will be assumed.
Meeting time: Tuesdays and Thursdays, 2:30pm-4:00pm
Location: 32-124
Instructors: Costis Daskalakis and Sam Hopkins
Office Hours: Thursday 4-6 pm (after class) 32-G5 Lounge or by appointment
Evaluation: Students will be expected to complete two problem sets and a research-oriented course project, which may consist of original research (theoretical and/or experimental!) and/or an exposition of 1 or 2 recent research papers. Tentatively, weight for your final grade will be split as follows: 25% pset 1, 25% pset 2, 50% course project.
Problem Set Partners: We have activated problem set partner matching for this course. See this website
Lectures + Lecture Notes
- (Sept. 7) introduction, uniformity testing on the hypercube. costis's notes
- (Sept. 12) learning high-dimensional gaussians. sam's notes, O'Donnell's lecture on Gaussians
- (Sept. 14) undirected graphical models. costis's notes
- (Sept. 19) graphical model examples, chow-liu, lower bound for learning trees. sam's notes
- (Sept. 21) continuation of lecture 4.
- (Sept. 26) learning parameters of non-tree Ising models via logistic regression. costis's notes
- (Sept. 28) learning non-tree Ising models in total variation distance using tournaments. costis's notes
- (Oct. 3) course overview. part 1 costis part 2 sam
- (Oct. 5) the role of temperature I: Reconstruction problem on the tree; the Kesten-Stigum Bound. costis's notes
- (Oct. 12) the role of temperature II: mixing time of Glauber dynamics; log-Sobolev inequalities. costis's notes
- (Oct. 17) introduction to Bayesian Networks; conditional independence; d-separation. costis's notes
- (Oct 19) learning and testing Bayesian networks; subadditivity of distances over Bayesian networks costis's notes
- (Oct. 24) introduction to causal inference: interventional distributions, causal models, do calculus; guest speaker: Chris Harshaw Chris's notes
- (Oct. 26) causal inference, part 2: adjustment sets, backdoor and frontdoor criteria; guest speaker: Chris Harshaw Chris's notes
- (A) (Oct. 31) causal inference, part 3: Inverse Propensity Weighting estimator; guest speaker: Chris Harshaw Chris's notes
(B) (Oct. 31) heavy tails, median of means in one dimension. sam's notes - (Nov. 2) finish heavy tails, start robust mean estimation. Tselil Schramm's notes on robust mean estimation
- (Nov. 7) finite-sample, infinite-time algorithm for robust mean estimation, start of SoS. Tselil Schramm's notes on SoS and SDP
- (Nov. 9) SoS proofs, finish robust mean estimation (notes above)
- (Nov. 14) robustly learning Ising models, transition from algorithms to complexity sam's notes
- (Nov. 16) low-degree model Sidhanth's notes
- (Nov. 21) statistical query model Diakonikolas-Kane book, chapter 8 sam's notes
- (Nov. 28) low degree versus SQ (notes above), start planted clique reductions sam's notes
- (Nov. 30) finish planted clique reductions (notes above)
- (Dec. 5) sos and planted clique sam's notes
- (Dec. 7) student presentations 1
- (Dec. 12) student presentations 2
