## 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](http://people.csail.mit.edu/costis/) and [Sam Hopkins](http://www.samuelbhopkins.com/)

**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](https://psetpartners.mit.edu/)

### Lectures + Lecture Notes

1. (Sept. 7) introduction, uniformity testing on the hypercube. [costis's notes](https://www.dropbox.com/scl/fi/sp52o6sc4upezz1ar3mee/Lecture-1-Intro-Uniformity-Testing.pdf?rlkey=n8r4mc9lk344jgvlz96vwqqwg&dl=0)
2. (Sept. 12) learning high-dimensional gaussians. [sam's notes](https://www.dropbox.com/scl/fi/5jyamqr5s8ek97l8xktqh/Lecture-2-Learning-a-Gaussian.pdf?rlkey=ddf8kqjq10xx8kfm9kc61p98q&dl=0), [O'Donnell's lecture on Gaussians](https://www.youtube.com/watch?v=hRqhf1edVIo)
3. (Sept. 14) undirected graphical models. [costis's notes](https://www.dropbox.com/scl/fi/ka2uas3prwr27fx207aa9/Lecture-3.pdf?rlkey=zxaei54se7syq2h1rk5432d2a&dl=0)
4. (Sept. 19) graphical model examples, chow-liu, lower bound for learning trees. [sam's notes](https://www.dropbox.com/scl/fi/eznah0xtvmzv5y3pw8qdb/Lecture-4-5.pdf?rlkey=d6nh7si2fo5lvjwl9e3lwaou8&dl=0)
5. (Sept. 21) continuation of lecture 4.
6. (Sept. 26) learning parameters of non-tree Ising models via logistic regression. [costis's notes](https://www.dropbox.com/scl/fi/wmi18jj8kcq07w9b5jyd4/Lecture-6.pdf?rlkey=tm9jzo2c6pa815kd8fr4bzgpi&dl=0)
7. (Sept. 28) learning non-tree Ising models in total variation distance using tournaments. [costis's notes](https://www.dropbox.com/scl/fi/vqircxnptrfi7pcvprp2v/Lecture-7-MRFs-learning-in-TV.pdf?rlkey=j6m3mb8tjratuwepi1cl6bin8&dl=0)
8. (Oct. 3) course overview. [part 1 costis](https://www.dropbox.com/scl/fi/zycla554kw5snggfv2xug/Lecture-8-Overview.pdf?rlkey=k4d81rlhlu5i69uwjr35isexe&dl=0) [part 2 sam](https://hackmd.io/@QkEI9EXuQp2xal2TYj7T2w/B1th8v_xa/edit)
9. (Oct. 5) the role of temperature I: Reconstruction problem on the tree; the Kesten-Stigum Bound. [costis's notes](https://www.dropbox.com/scl/fi/w5xzjvop5jqz1qkupc7c4/Lecture-9-Kesten-Stigum-Bound.pdf?rlkey=30sz8i4kg1dyub7h5mng7pfwe&dl=0)
10. (Oct. 12) the role of temperature II: mixing time of Glauber dynamics; log-Sobolev inequalities. [costis's notes](https://www.dropbox.com/scl/fi/8q38ugx36wqlg0ub9l2dk/Lecture-10-Log-Sobolev.pdf?rlkey=wc73ish3cfz9dolurtfb9rbfd&dl=0)
11. (Oct. 17) introduction to Bayesian Networks; conditional independence; d-separation. [costis's notes](https://www.dropbox.com/scl/fi/3wyoky2zxvcu277e18p4r/Lecture-11-Bayesnets-Introduction.pdf?rlkey=w2p35ui75mwrzkn1u4lwh2640&dl=0)
12. (Oct 19) learning and testing Bayesian networks; subadditivity of distances over Bayesian networks [costis's notes](https://www.dropbox.com/scl/fi/stbg4scypefrpjsgwyjee/Lecture-12-Learning-And-Testing-Bayesnets.pdf?rlkey=o59s2juph6tbv1f2bw778ql7b&dl=0)
13. (Oct. 24) introduction to causal inference: interventional distributions, causal models, do calculus; guest speaker: Chris Harshaw [Chris's notes](https://www.dropbox.com/scl/fi/p9beol0hldqndl1r6wkvb/Lecture-13-Causal-Inference-1-Introduction.pdf?rlkey=0vntldn0rgyqkhjtzmzpkm53f&dl=0)
14. (Oct. 26) causal inference, part 2: adjustment sets, backdoor and frontdoor criteria; guest speaker: Chris Harshaw [Chris's notes](https://www.dropbox.com/scl/fi/iuqryo7oun4km8slnd5i0/Lecture-14-Causal-Inference-2-adjustment-sets.pdf?rlkey=l84ko9opzoay0ri8ra5qve73x&dl=0)
15. (A) (Oct. 31) causal inference, part 3: Inverse Propensity Weighting estimator; guest speaker: Chris Harshaw [Chris's notes](https://www.dropbox.com/scl/fi/tgw6sa580gev2ajv4kxxc/Lecture-15-Causal-Inference-3-IPW-and-AIPW-estimator.pdf?rlkey=srzzovvh9dpr15cnp2pl7en8o&dl=0)
(B) (Oct. 31) heavy tails, median of means in one dimension. [sam's notes](https://www.dropbox.com/scl/fi/hdgr5djwqz3rayu7lb4r0/Lecture15-19-robustness-heavy-tails-SoS.pdf?rlkey=u88x37n7ky465a5f333w0ynh4&dl=0)
16. (Nov. 2) finish heavy tails, start robust mean estimation. [Tselil Schramm's notes on robust mean estimation](https://tselilschramm.org/sos-paradigm/notes22/00-proofs-to-algs.pdf)
17. (Nov. 7) finite-sample, infinite-time algorithm for robust mean estimation, start of SoS. [Tselil Schramm's notes on SoS and SDP](https://tselilschramm.org/sos-paradigm/notes22/01-implementing-sos-with-SDPs.pdf)
18. (Nov. 9) SoS proofs, finish robust mean estimation (notes above)
19. (Nov. 14) robustly learning Ising models, transition from algorithms to complexity [sam's notes](https://www.dropbox.com/scl/fi/f5acep9rzu5jatbi5zpvi/Lecture19-robustly-learning-ising.pdf?rlkey=hmjxi8rywm73c09bxa9hw66f9&dl=0)
20. (Nov. 16) low-degree model [Sidhanth's notes](https://www.dropbox.com/scl/fi/010zup4uv33jbjx2boigx/Lecture-20-Low-Degree.pdf?rlkey=ctmuqdtt25x17bn4j9iz71y30&dl=0)
21. (Nov. 21) statistical query model [Diakonikolas-Kane book, chapter 8](http://www.iliasdiakonikolas.org/ars-book.pdf) [sam's notes](https://www.dropbox.com/scl/fi/5972kc1ld0m4it13ey9pe/Lecture21-22-SQ.pdf?rlkey=177igulxksrs2scu2ur4teksg&dl=0)
23. (Nov. 28) low degree versus SQ (notes above), start planted clique reductions [sam's notes](https://www.dropbox.com/scl/fi/2qciz66hzs14bzuvdtpq6/Lecture22-23-planted-clique-reduction.pdf?rlkey=bzcn9vr8s5bgb0jakv22z2j4n&dl=0)
24. (Nov. 30) finish planted clique reductions (notes above)
25. (Dec. 5) sos and planted clique [sam's notes](https://www.dropbox.com/scl/fi/o5gz0t0wc7kq7bzc5remb/Lecture24-planted-clique-sos.pdf?rlkey=7voljzjc4rt9pvcq4ll01qke9&dl=0)
26. (Dec. 7) student presentations 1
27. (Dec. 12) student presentations 2

### Assignments

[Homework problems](https://www.overleaf.com/read/kxmvnydbmysq)

[Course project](https://www.overleaf.com/read/zfvkmpgswqgn)