Course Project

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

Project Proposal

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.

Written report

A 4-5-page written report, say 2000-2500 words, typeset in Latex. Word processors are not acceptable.

Due: Tuesday April 8th, in class.

Oral presentation

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.

Submodular Functions

·         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.

Nearest Neighbors


·         Chandrasekaran, Jordan. Computational and Statistical Tradeos via Convex Relaxation. PNAS 2013.