Here are some papers you can choose from. You are welcome to pick any other recent paper on learning theory, but please check with me to see if it is suitable for this class. You can also present more than one paper so long as they are on the same topic and your presentation forms a coherent story.
Large Scale Learning
A reliable effective terascale linear learning system. Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, John Langford, JMLR 2014.
- Communication-Efficient Algorithms for Statistical Optimization. Yuchen Zhang, John C. Duchi, Martin Wainwright, JMLR 2013.
- Distributed Learning, Communication Complexity, and Privacy. Nina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. COLT 2012.
- Communication Complexity of Distributed Convex Learning and Optimization
Yossi Arjevani and Ohad Shamir, NIPS 2015.
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method. Ohad Shamir, Nathan Srebro and Tong Zhang, ICML 2014.
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
Ohad Shamir, Arxiv 2015.
- Optimal Learners for Multiclass Problems. Amit Daniely and Shai Shalev-Shwartz. COLT, 2014.
- Multiclass Learnability and the ERM principle. Amit Daniely, Sivan Sabato, Shai Ben-David and Shai Shalev-Shwartz. COLT, 2011
- Multiclass Learning Approaches: A Theoretical Comparison with Implications. Amit Daniely, Sivan Sabato and Shai Shalev-Shwartz. NIPS, 2012
- Error-Correcting Tournaments. Alina Beygelzimer, John Langford and Pradeep Ravikumar. ALT 2009.
- Logarithmic time online multiclass prediction. Anna Choromanska and John Langford. NIPS 2013.
Non-Convex Optimization and Spectral Learning
- Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods. Majid Janzamin, Hanie Sedghi and Anima Anandkumar, Arxiv 2015.
- Intersecting Faces: Non-negative Matrix Factorization With New Guarantees, Rong Ge and James Zou, ICML 2015.
- Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition. Rong Ge, Furong Huang, Chi Jin and Yang Yuan. COLT 2015.
- Rich Component Analysis. Rong Ge and James Zou. Arxiv 2015.
- Computing Matrix Squareroot via Non Convex Local Search. Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli. Arxiv, 2015.
- Fourier PCA and Robust Tensor Decomposition. Navin Goyal, Santosh Vempala, Ying Xiao, STOC 2014.
- Robust Interactive Learning. Nina Balcan and Steve Hanneke. COLT 2012.
- Convergence Rates of Active Learning for Maximum Likelihood Estimation. Kamalika Chaudhuri, Sham Kakade, Praneeth Netrapalli and Sujay Sanghavi, NIPS 2015.
- An Efficient Algorithm for Graph-based Active Learning. Gautam Dasarathy, Rob Nowak and Xiaojin Zhu.
- Efficient and Parsimonious Agnostic Active Learning. Tzu-Kuo Huang, Alekh Agarwal, Daniel J. Hsu, John Langford, Robert E. Schapire, NIPS 2015.
- Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities. Brian Eriksson and Gautam Dassarathy and Aarti Singh and Rob Nowak, AISTATS 2011.
- PLAL: CLuster-based active learning. Ruth Urner, Sharon Wulff and Shai Ben-David, COLT 2013.