IE598. Statistical Learning
This website is for IE598AI. Algorithms for Inference.
Announcements
We meet at 243 Mechanical Engineering Building on Tuesdays and Thursdays 12:301:50.
The first lecture is on Tuesday Jan 19th, 2016.
Related papers
Concentration inequalities and tail bounds
Userfriendly tail bounds for sums of random matrices, Joel A. Tropp, 2010
Matrix completion
Exact matrix completion via convex optimization, Emmanuel J. Candes, Benjamin Recht, 2008
The power of convex relaxation: nearoptmial matrix completion, Emmanuel J. Candes, Terence Tao, 2009
Matrix completion from a few entries, Raghunandan Keshavan, Andrea Montanari, Sewoong Oh, 2009
Matrix completion from noisy entries, Raghunandan Keshavan, Andrea Montanari, Sewoong Oh, 2009
Lowrank matrix completion using alternating minimization, Preteek Jain, Praneeth Netrapalli, Sujay Sanghavi, 2012
Spectral techniques applied to sparse random graphs, Uriel Feige, Eran Ofek, 2005
Crowdsourcing
Budgetoptimal Task Allocation for Reliable Crowdsourcing Systems, David R. Karger, Sewoong Oh and Devavrat Shah, 2014
Reliable Crowdsourcing under the Generalized DawidSkene Model, Ashish Khetan, Sewoong Oh, 2016
Optimality of Belief Propagation for Crowdsourced Classification, Jungseul Ok, Sewoong Oh, Jinwoo Shin, Yung Yi, 2016
Minimax Lower Bound
‘‘Assouad, fano, and le cam’’, Bin Yu, Festschrift for Lucien Le Cam, 1997
Project
The project for this course is to write 46 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.
Spectral methods in matrix completion by Amish Goel
On the provable convergence of alternating minimization for matrix completion, Moritz Hardt, 2014
Guaranteed matrix completion via nonconvex factorization, Ruoyu Sun, ZhiQuan Luo, 2014
Matrix completion with strong guarantees
Provable inductive matrix completion, Prateek Jain, Inderjit S. Dhillon
Nonconvex robust PCA, P Netrapalli, UN Niranjan, S Sanghavi, A Anandkumar, P Jain
Ranking from pairwise comparisons by Joseph Lubars
Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues, Nihar B. Shah, Sivaraman Balakrishnan, Adityanand Guntuboyina and Martin J. Wainwright, 2015
Simple, Robust and Optimal Ranking from Pairwise Comparisons, Nihar B. Shah and Martin J. Wainwright 2015
Computational lower bound
Computational Lower Bounds for Sparse PCA, Berther, Rigollet
Lower bounds on the performance of polynomialtime algorithms for sparse linear regression, Zhang, Wainwright, Jordan
Tensor completion by Shiyu Liang
Tensor Prediction, Rademacher Complexity, and Random 3XOR, Ankur Moitra, Boaz Barak, 2015
On Tensor Completion via Nuclear Norm Minimization, Yuan, Zhang, 2014
Approximate gradient descent
Phase Retrieval using Alternating Minimization", Netrapalli, Jain, Sanghavi.
Statistical Guarantees for the EM Algorithm: From Population to Samplebased Analysis, Balakrishnan, Wainwright, Yu.
Crowdsourcing by Siddhartha Satpathi
Spectral methods meet EM: A provably optimal algorithm for crowdsourcing, Y Zhang, X Chen, D Zhou, MI Jordan 2014
On the Impossibility of Convex Inference in Human Computation, NB Shah, D Zhou, 2014
Nonbacktraking operator by Ashish Khetan
Spectral redemption in clustering sparse networks, F Krzakala, C Moore, E Mossel, et al. 2013
Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, C Bordenave, M Lelarge, L Massoulie, 2015
