CSE 291: Statistical Learning Theory

Spring 2017

 

Announcements:

 

·         First day of class April 3rd in CENTR 214.

 

Readings:

 

·         S. Chan, I. Diakonikolas, P. Valiant,  and G. Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In SODA, pages 1193-1203, 2014. (for the L2 tester)

·         Ilias Diakonikolas, Daniel M. Kane, A New Approach for Testing Properties of Discrete Distributions, Foundations Of Computer Science, (FOCS) 2016.

·         Gregory Valiant, and Paul Valiant, An Automatic Inequality Prover and Instance Optimal Identity Testing, FOCS, 2014.

·         Gregory Valiant, and Paul Valiant, A CLT and tight lower bounds for estimating entropy, 2010.

·         Luc Devroye, Gábor Lugosi Combinatorial Methods in Density Estimation (link is table of contents only), Springer-Verlag, New York, 2001. (For chapters 3 and 4)

1.      Vladimir N. Vapnik and Alexey Ya. Chervonenkis On the Uniform Convergence of the Frequencies of Occurrence of Events to Their Probabilities

2.      R. M. Dudley Central Limit Theorems for Empirical Measures

·         Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun Efficient Density Estimation via Piecewise Polynomial Approximation

·         Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Testing Identity of Structured Distributions Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

·         Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin Near-Optimal Closeness Testing of Discrete Histogram Distributions

·         Celement Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart Testing Bayesian Networks (for section 4)

·         Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart, Robust Estimators in High Dimensions, without the Computational Intractability

·         Michael Kerns Efficient Noise-Tolerant Learning from Statistical Queries

·         Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao Statistical Algorithms and a Lower Bound for Detecting Planted Clique (for section 3)

·         Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart Statistical Query Lower Bounds for Robust Estimation of High Dimensional Gaussians and Gaussian Mixtures

 

Homeworks:

 

·         None yet

 

Scribe Notes:

 

Schedule

 

·         Lecture 1

·         Lecture 2 or alternative version of Lecture 2

·         Lecture 4

·         Lecture 6 or alternative version of Lecture 6

·         Lecture 8

·         Lecture 9 or alternative version of Lecture 9

·         Lecture 10

·         Lecture 11 or alternative version of Lecture 11

·         Lecture 12

·         Lecture 16

·         Lecture 17 or alternative version of Lecture 17

·         Lecture 18

·         Lecture 19

·         Lecture 21

·         Lecture 22

·         Lecture 23 or alternative version of Lecture 23

·         Lecture 24

·         Lecture 27

·         Lecture 28

 

Other:

 

·         Course Syllabus

·         Lecture podcasts

·         Piazza signup

·         Reading list for final project

 

Course Description: CSE 291 will focus on covering recent results in computational statistics and machine learning, focusing on problems relating to the learning and testing of distributions.