IE598. Statistical Learning

This website is for IE598AI. Algorithms for Inference.

Announcements

• We meet at 243 Mechanical Engineering Building on Tuesdays and Thursdays 12:30-1:50.

• The first lecture is on Tuesday Jan 19th, 2016.

Related papers

1. Concentration inequalities and tail bounds

   1. User-friendly tail bounds for sums of random matrices, Joel A. Tropp, 2010

2. Matrix completion

   1. Exact matrix completion via convex optimization, Emmanuel J. Candes, Benjamin Recht, 2008

   2. The power of convex relaxation: near-optmial matrix completion, Emmanuel J. Candes, Terence Tao, 2009

   3. Matrix completion from a few entries, Raghunandan Keshavan, Andrea Montanari, Sewoong Oh, 2009

   4. Matrix completion from noisy entries, Raghunandan Keshavan, Andrea Montanari, Sewoong Oh, 2009

   5. Low-rank matrix completion using alternating minimization, Preteek Jain, Praneeth Netrapalli, Sujay Sanghavi, 2012

   6. Spectral techniques applied to sparse random graphs, Uriel Feige, Eran Ofek, 2005

3. Crowdsourcing

   1. Budget-optimal Task Allocation for Reliable Crowdsourcing Systems, David R. Karger, Sewoong Oh and Devavrat Shah, 2014

   2. Reliable Crowdsourcing under the Generalized Dawid-Skene Model, Ashish Khetan, Sewoong Oh, 2016

   3. Optimality of Belief Propagation for Crowdsourced Classification, Jungseul Ok, Sewoong Oh, Jinwoo Shin, Yung Yi, 2016

4. Minimax Lower Bound

   1. ‘‘Assouad, fano, and le cam’’, Bin Yu, Festschrift for Lucien Le Cam, 1997

Project

The project for this course is to write 4-6 page final paper, and present it in class. You can work in groups or you can work alone. There are two optios:

• You can write a literature review on some topic related to the materials we covered in class.

• You can do original research. This is a more challenging type of a project, and it is the most open ended.

Here are the topics and related papers.

1. Spectral methods in matrix completion by Amish Goel

   1. On the provable convergence of alternating minimization for matrix completion, Moritz Hardt, 2014

   2. Guaranteed matrix completion via non-convex factorization, Ruoyu Sun, Zhi-Quan Luo, 2014

2. Matrix completion with strong guarantees

   1. Provable inductive matrix completion, Prateek Jain, Inderjit S. Dhillon

   2. Non-convex robust PCA, P Netrapalli, UN Niranjan, S Sanghavi, A Anandkumar, P Jain

3. Ranking from pairwise comparisons by Joseph Lubars

   1. Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues, Nihar B. Shah, Sivaraman Balakrishnan, Adityanand Guntuboyina and Martin J. Wainwright, 2015

   2. Simple, Robust and Optimal Ranking from Pairwise Comparisons, Nihar B. Shah and Martin J. Wainwright 2015

4. Computational lower bound

   1. Computational Lower Bounds for Sparse PCA, Berther, Rigollet

   2. Lower bounds on the performance of polynomial-time algorithms for sparse linear regression, Zhang, Wainwright, Jordan

5. Tensor completion by Shiyu Liang

   1. Tensor Prediction, Rademacher Complexity, and Random 3-XOR, Ankur Moitra, Boaz Barak, 2015

   2. On Tensor Completion via Nuclear Norm Minimization, Yuan, Zhang, 2014

6. Approximate gradient descent

   1. Phase Retrieval using Alternating Minimization", Netrapalli, Jain, Sanghavi.

   2. Statistical Guarantees for the EM Algorithm: From Population to Sample-based Analysis, Balakrishnan, Wainwright, Yu.

7. Crowdsourcing by Siddhartha Satpathi

   1. Spectral methods meet EM: A provably optimal algorithm for crowdsourcing, Y Zhang, X Chen, D Zhou, MI Jordan 2014

   2. On the Impossibility of Convex Inference in Human Computation, NB Shah, D Zhou, 2014

8. Non-backtraking operator by Ashish Khetan

   1. Spectral redemption in clustering sparse networks, F Krzakala, C Moore, E Mossel, et al. 2013

   2. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs, C Bordenave, M Lelarge, L Massoulie, 2015