CSE 519T Advanced Machine Learning

Fall 2019: Robust learning and statistics
Instructor: Brendan Juba
Tuesday/Thursday 1pm-2:20pm, Cupples I 115

Course Piazza board. Please ask all questions that are not of a personal nature in a public post to the Piazza board.

Description: An introduction to the problems of learning and inference when some portion of the data consists of arbitrary "outliers," including an introduction to task formulations that allow the "inliers" (data of interest) to comprise a minority fraction. We will examine both tractable algorithms for these problems and their statistical requirements. Mathematical maturity and general familiarity with machine learning is required.

Prerequisite: CSE 517A, mathematical maturity

Grades and assignments: Students will each present one of the papers from the list below, and grades will be based on these presentations. It is expected that students will attend others' presentations and participate in discussion of the presentations/Q&A.

Schedule

To be filled in as the semester progresses:

8/27: Introduction to robust estimation problems; statistical optimality of Tukey medians (Prof. Juba) notes
8/29: Introduction to robust estimation with a minority of inliers (list learning and conditional learning); RANSAC (Prof. Juba) notes
9/3: Hai S. Le - Juba ITCS 2017
9/5: Zihao Deng - Charikar Steinhardt Valiant STOC 2017 (full version)
9/10: Sijia Wang - Lai Rao Vempala FOCS 2016
9/12: Xiaojian Xu - Diakonikolas Kamath Kane Li Moitra Stewart FOCS 2016 (full version)
9/17: (rescheduled to 9/26)
9/19: Jin Yang - Kothari Steinhardt Steurer STOC 2018
9/24: Sebastian Foeller - Diakonikolas Kamath Kane Li Moitra Stewart ICML 2017
9/26: Rui Qiu - Steinhardt Charikar Valiant ITCS 2018
10/1: Leifu Zhang - Balakrishnan Du Li Singh COLT 2017
10/3: Jerry Kong - Hardt Moitra COLT 2013
10/8: Jizhou Huang - Klivans Kothari Meka COLT 2018
10/10: Hanrui Zou - Diakonikolas Kong Stewart SODA 2019
10/15: FALL BREAK (no meeting)
10/17: Yuanguang Ming - Cheng Diakonikolas Kane Stewart NeurIPS 2018 (full version)
10/22: Matt Gleeson - Diakonikolas Kane Li Steinhardt Stewart ICML 2019
10/24: Ray Wu - Prasad Suggala Balakrishnan Ravikumar arXiv 2018
10/29: Yifan Yu - Hopkins Li STOC 2018 (full version)
10/31: Zhuangyu Han - Cheng Diakonikolas Ge SODA 2019
11/5: Wei Tang - Despersin-Lecue arXiv 2019/ Dong Hopkins Li arXiv 2019
11/7: Chuan Tang - Liu Shen Li Caramanis arXiv 2018
11/12, 11/14: no meeting (Prof. Juba traveling)
11/19: Zhihao Xia - Diakonikolas Kane Stewart STOC 2018 (full version)
11/21: Hai S. Le - Hainline Juba Le Woodruff AISTATS 2019 (supplemental)
11/26, 11/28: THANKSGIVING BREAK (no meeting)
12/3: Prof. Juba - Calderon Juba Li Li Ruan arXiv 2018
12/5: Wrap up - what we didn't see

List of Papers

unsupervised (subspace recovery)

Hardt Moitra COLT 2013 (JK)

mean/covariance estimation, etc.

mixture of Gaussians

Li Schmidt COLT 2017

sparse models

Balakrishnan Du Li Singh COLT 2017 (LZ)
Liu Shen Li Caramanis arXiv 2018 (CT)

fast estimators

convex/stochastic optimization

regression

Klivans Kothari Meka COLT 2018 (JH)
Diakonikolas Kong Stewart SODA 2019 (HZ)

Bayesian networks

Cheng Diakonikolas Kane Stewart NeurIPS 2018 (full version) (YM)

hardness

minority inliers

Charikar Steinhardt Valiant STOC 2017 (full version) (ZD)
Steinhardt Charikar Valiant ITCS 2018 (RQ)
Kothari Steinhardt Steurer STOC 2018 (JY)
Diakonikolas Kane Stewart STOC 2018 (full version) (ZX)
Hopkins Li STOC 2018 (full version) (YY)
Karmalkar Kothari Klivans arXiv 2019/Raghavendra Yau arXiv 2019
Juba ITCS 2017 (HSL)
Hainline Juba Le Woodruff AISTATS 2019 (supplemental) (HSL)
Calderon Juba Li Li Ruan arXiv 2018 (BJ)