CSC 581B Project Details

As part of this course, every graduate student will complete a solo project with a significant theoretical component.

Types of projects

Below are suggestions for types of projects you could complete. The first set are research-oriented projects, which could involve:

Making progress toward an open problem in learning theory; you don't necessarily have to solve the problem, but you have to show an honest effort;
Posing a new, interesting problem and beginning to work on it;
Showing connections between several problems or techniques;
Developing a new, elegant understanding of a complicated result;
A re-working of an existing, significant paper that significantly simplies the authors' analysis/solution.

The second set are survey-oriented, such as:

A synthesis of several related papers that distills the main ideas and presents them more simply and very concisely;
Providing a new understanding/connections between several papers within some theme.

Initial meeting to green-light your project

Sometime in early March, I'll meet with each of you to ensure that you have a sensible project that is at the right scale. For ideas/themes for projects, take a look at the "Project ideas" section below.

Presentation

For each project, there will be a 15 to 20 minute presentation (depending on the time available) displaying your findings, plus a few minutes for questions. These presentations will happen in the last few lectures of class or possibly within a few days of the last lecture.

Submission

Each of you also will submit a 2-5 page report, not including references. The maximum length is flexible depending on your project; for instance, if you engage in an interesting research topic that could lead to a paper, a longer writeup may be ideal. For your report, please use the LaTeX style file and template below (this is just to get the geometry right, e.g. margins, font size, line spacing):

Your project writeups are due (via email) by Friday April 12th, 11:59pm PDT.

Project ideas

Below are some papers in various areas to help you think about project ideas; I may update these soon to include a few other areas.

Deep learning and generalization

Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Trans. on Information Theory, 1998.
Neyshabur, Tomioka, and Srebro. Norm-based capacity control in neural networks. COLT, 2015.
Neyshabur, Bhojanapalli, McAllester, and Srebro. Exploring generalization in deep learning. NIPS, 2017.
Dziugaite and Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. UAI, 2017.

Active learning

Beygelzimer, Dasgupta, and Langford. Importance weighted active learning. ICML, 2009.
Beygelzimer, Hsu, Langford, and Zhang. Agnostic active learning without constraints. NIPS, 2010.
Balcan, Hanneke, and Wortman Vaughan. The true sample complexity of active learning. Machine learning, 2010.

Transfer learning and lifelong learning

Fully online lifelong learning:

Alquier, Mai, and Pontil. Regret bounds for lifelong learning. AISTATS, 2017.

Lifelong learning of PAC learning tasks:

Balcan, Blum, and Vempala. Efficient representations for lifelong learning and autoencoding. COLT, 2015
Pentina and Urner. Lifelong learning with weighted majority votes. NIPS, 2016.

Learning under corruption

Awasthi, Balcan, and Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM, 2017

PAC-Bayesian bounds

Margin bounds:

McAllester. Simplified PAC-Bayesian margin bounds. COLT, 2003.

Generalized PAC-Bayesian bounds:

Bégin, Germain, Laviolette, and Roy. PAC-Bayesian bounds based on the Rényi divergence. AISTATS, 2016.

PAC-Bayesian bounds with faster rates and unbounded losses:

Grünwald and Mehta. Fast rates for general unbounded loss functions: from ERM to generalized Bayes. arXiv, 2017.

Compression bounds

Moran and Yehudayoff. Sample compression schemes for VC classes. Journal of the ACM, 2016. (see also the references within)

Learning at faster rates

Massart and Tsybakov noise:

Massart and Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 2006.
Van Erven, Grünwald, Mehta, Reid, and Williamson. Fast rates in statistical and online learning. JMLR, 2015.
Grünwald and Mehta. Fast rates for general unbounded loss functions: from ERM to generalized Bayes. arXiv, 2017.
Grünwald and Mehta. A tight excess risk bound via a unified PAC-Bayesian-Rademacher-Shtarkov-MDL complexity. arXiv, 2017.

Efficient learning:

Awasthi, Balcan, Haghtalab, and Urner. Efficient learning of linear separators under bounded noise. COLT, 2015

Algorithmic stability

Bousquet and Elisseeff. Stability and generalization. JMLR, 2002.
Shalev-Shwartz, Shamir, Srebro, and Sridharan. Learnability, stability and uniform convergence. JMLR, 2010.

Connection to cross-validation:

Kearns and Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural computation, 1999.

Privacy and Adaptive data analysis

This is a rapidly developing space that interfaces heavily with machine learning. If you are interested, I can try to provide guidance for a problem here.

Online learning

Topics in online learning are possible; however, since online learning occupies the last third of the course, I have not specified options here, as you likely will not yet have received sufficient exposure to online learning yet. That said, if you are interested, I can try and provide some references.