The main purpose of CPSC 531H is to bring students closer to the research frontier in the theory of machine learning. Towards that goal, students must complete a course project, which is an in-depth study on a topic relevant to the coursework.
· Read at least one research paper
· Possible activities:
o implement the paper's method and perform some small experiments
o try to generalize the paper’s results, or apply their techniques in a new context
o compare the results of multiple research papers
A brief description of the topic that you plan to study and the paper(s) that you plan to read. The length should be between one-half and one page in length.
Due: Thursday February 27th, in class.
A 4-5-page written report, say 2000-2500 words, typeset in Latex. Word processors are not acceptable.
Due: Tuesday April 8th, in class.
A 10-15 minute presentation with slides discussing the context and contributions of your project.
Presentation Date: TBD, probably sometime around April 10th.
Some suggested topics
· Mukherjee, Schapire. A Theory of Multiclass Boosting. JMLR 2013.
· Kalai, Servedio. Boosting in the presence of noise. JCSS 2005.
· Long, Servedio. Random Classification Noise Defeats All Convex Potential Boosters. Machine Learning 2010.
· Kleinberg. An Impossibility Theorem for Clustering. NIPS 2002.
· Balcan, Blum, Vempala. A Discriminative Framework for Clustering via Similarity Functions. STOC 2008.
· Balcan, Gupta. Robust Hierarchical Clustering. COLT 2010.
Boolean Functions and Fourier Analysis
· De Wolf. A Brief Introduction to Fourier Analysis on the Boolean Cube. ToC 2008.
· Linial, Mansour, Nisan. Constant Depth Circuits, Fourier Transform, and Learnability. JACM 1993.
· Kushilevitz, Mansour. Learning decision trees using the Fourier spectrum. SICOMP 1993.
· Mansour. Learning Boolean Functions via the Fourier Transform. 1994.
Mixtures of Gaussians
· Dasgupta. Learning mixtures of Gaussians. FOCS 1999.
· Vempala, Wang. A spectral algorithm for learning mixture models. JCSS 2004.
· Feldman, Servedio, O'Donnell. PAC Learning Mixtures of Gaussians with No Separation Assumption. COLT 2006.
· Achlioptas, McSherry. On Spectral Learning Mixtures of Distributions. COLT 2005.
· Kannan, Salmasian, Vempala. The spectral method for general mixture models. SICOMP 2008.
· Brubaker, Vempala. Isotropic PCA and Affine-invariant Clustering. FOCS 2008.
· Belkin, Sinha. Toward Learning Gaussian Mixtures with Arbitrary Separation. COLT 2010
· Kalai, Moitra, Valiant. Efficiently learning mixtures of two Gaussians. FOCS 2010.
· Kalai, Moitra, Valiant. Disentangling Gaussians. CACM 2012.
· Feldman, Kothari, Vondrak. Representation, Approximation, and Learning of Submodular Functions Using Low-rank Decision Trees. COLT 2013.
· Feldman, Vondrak. Optimal bounds on Approximation of Submodular and XOS Functions by Juntas. FOCS 2013.
· Cheraghchi, Klivans, Kothari, Lee. Submodular Functions Are Noise Stable. SODA 2012.
· Balcan, Harvey. Submodular Functions: Learnability, Structure, and Optimization. STOC 2011.
· Balcan, Constantin, Iwata, Wang. Learning Valuation Functions. COLT 2012.
· Iyer, Jegelka, Bilmes. Fast Semidifferential-based Submodular Function Optimization. ICML 2013, Best Paper Award.
· Iyer, Bilmes. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints. NIPS 2013, Outstanding Paper Award.
· Bilmes. Deep Mathematical Properties of Submodularity with Applications to Machine Learning. NIPS 2013 Tutorial.
· Soma, Kakimura, Inaba, Kawarabayashi. Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm. ICML 2014.
Sparse / Noisy Recovery
· Recht, Fazel, Parrilo. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Rev 2010.
· Candes, Recht. Exact Matrix Completion via Convex Optimization. FCM 2009.
· Candes, Li, Ma, Wright. Robust Principal Component Analysis?. JACM 2011.
· Recht. A Simpler Approach to Matrix Completion. JMLR 2011.
· Hardt, Moitra. Algorithms and Hardness for Robust Subspace Recovery. COLT 2013.
· Sarlos. Improved approximation algorithms for large matrices via random projections. FOCS 2006.
· Chin, Madry, Miller, Peng. Runtime Guarantees for Regression Problems. ITCS 2013.
· Woodruff, Zhang. Subspace Embeddings and L_p-Regression Using Exponential Random Variables. COLT 2013.
Johnson-Lindenstrauss Dimensionality Reduction
Classification and Random Projection
· Balcan, Blum, Vempala. Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings. Machine Learning 2006.
· Rahimi, Recht. Random Features for Large-Scale Kernel Machines. NIPS 2007.
· Rahimi, Recht. Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning. NIPS 2008.
· Zhang, Mahdavi, Jin, Yang, Zhu. Recovering the Optimal Solution by Dual Random Projection. COLT 2013.
· Le, Sarlos, Smola. Fastfood – Approximating Kernel Expansions in Loglinear Time. ICML 2013.
· Chandrasekaran, Jordan. Computational and Statistical Tradeoﬀs via Convex Relaxation. PNAS 2013.