CSE 291: Statistical Learning Theory

Spring 2017

Final Project suggestions


         Distribution testing from Conditional Samples (i.e. algorithms that can ask for samples conditioned on lying in some subset):

o   Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah On the Power of Conditional Samples in Distribution Testing

o   Clement Canonne, Dana Ron, Rocco A. Servedio Testing probability distributions using conditional samples

         Instance Optimality:

o   Gregory Valiant, Paul Valiant Instance Optimal Learning (learning the distribution up to permutations of the indices)

o   Alon Orlitsky, Ananda Theertha Suresh Competitive Distribution Estimation (being competitive against learners with limited extra information)

         Graphical Models

o   Guy Bresler Efficiently learning Ising models on arbitrary graphs

o   Celement Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart Testing Bayesian Networks

o   Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart Robust Learning of Fixed-Structure Bayesian Networks

o   Constantinos Daskalakis and Qinxuan Pan Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

         Learning Topic Models

o   Sanjeev Arora, Rong Ge, Ankur Moitra Learning Topic Models - Going beyond SVD

         Expectation Maximization Algorithms

o   Balakrishnan, Wainright and Yu Statistical guarantees for the EM algorithm: From population to sample-based analysis

         Stochastic Block Models (learning graph partitioning)

o   Elchanan Mossel, Joe Neeman, Allan Sly Stochastic Block Models and Reconstruction

o   Ankur Moitra, William Perry, Alexander S. Wein How Robust are Reconstruction Thresholds for Community Detection?

         SQ Lower Bounds

o   Vitaly Feldman, Homin Lee, Rocco Servedio Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

o   J. Steinhardt, G. Valiant, and S. Wager Memory, Communication, and Statistical Queries

         Population Recovery

o   Shachar Lovett, Jiapeng Zhang Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

         Robust Statistics

o   Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

o   Moses Charikar, Jacob Steinhardt, Gregory Valiant Learning from Untrusted Data

         Learning SIRVs

o   Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables

o   Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

o   Constantinos Daskalakis, Anindya De, Gautam Kamath and Christos Tzamos A Size-Free CLT for Poisson Multinomials and its Applications

o   Constantinos Daskalakis, Gautam Kamath and Christos Tzamos On the Structure, Covering, and Learning of Poisson Multinomial Distributions


o   Weihao Kong, Gregory Valiant Spectrum Estimation from Samples

o   Jayadev Acharya, Constantinos Daskalakis and Gautam Kamath Optimal Testing for Properties of Distributions

o   Gregory Valiant, and Paul Valiant Estimating the unseen: a sublinear-sample canonical estimator of distributions