AlgStats - 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](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 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)<details> <summary>SQ lower bound for 3XOR via SQ dimension</summary> ![image](https://hackmd.io/_uploads/r1AkmMMr6.png) </details> 22. (Nov. 28) low degree versus SQ, start planted clique reductions 23. (Nov. 30) more reductions 24. (Dec. 5) finish complexity 25. (Dec. 7) student presentations 1 26. (Dec. 12) student presentations 2 ### Assignments [Homework problems](https://www.overleaf.com/read/kxmvnydbmysq) [Course project](https://www.overleaf.com/read/zfvkmpgswqgn)