The course project is intended as an opportunity to engage in research on machine learning theory. Hence, the project must contain a theoretical component. You are free to pick any topic you like, within reason.

Some examples of suitable project “types” are as follows.

  • Prove a new, interesting theoretical result in a new or existing machine learning model. You can be ambitious, but do also aim for something interesting to show by the end of the semester.

    Example: the theory parts of this paper on Brown clustering. The theory here is actually fairly simple, and could probably be easily elaborated.

  • Simplify an existing but complicated result in a new, non-trivial way.

    Example: Dasgupta and Gupta’s elementary proof of J-L lemma (although producing a proof this miraculous is not required!).
  • Unify and clarify the relationships between several (at least three or four) papers with a common theme or topic in a survey paper. Note that projects of this type will be judged especially critically for clarity and writing quality.

A project that “just” implements an algorithm and runs some experiments is not suitable, even if the algorithm comes from a theory paper.


The final product is a written report. The length of the report will depend on the context. For example, this paper introduces a problem and states the main results in about eight pages, and the proof is in a nine-page appendix. As another example, this paper simplifies the main result of an award-winning PhD thesis in a single page. Quality and clarity are more important than quantity.

There is a tentative plan to hold a poster session during the final exam period for this course (Dec 21). The posters don’t need to be very elaborate (e.g., feel free to draw them by hand), but you should prepare a short oral presentation (about five to seven minutes) that is visually aided by the poster.

Update: there aren’t enough research projects to warrant having a poster session, so we’ll forego this.


  • Oct 12: Submit a project proposal (one or two pages should suffice), describing the project type, the chosen topic, and some preliminary “leg-work”. For instance:
    • If you seek to prove a new result, formally state the problem or conjecture, along with background information explaining why such a result is interesting given the prior art, and why you think you can obtain the result (e.g., possible approaches, high-level ideas why the result should be true).
    • If you seek to simplify an existing result, formally state the existing result and what is unsatisfactory about the existing solution, give evidence that the result remains unsimplified to this date (e.g., by referencing its use as a “black-box” in subsequent works), and explain why you think you can obtain the simplification.
    • If you seek to unify several papers in a survey, formally introduce the common theme or topic of the papers, briefly summarize the high-level ideas of each paper, and explain your unifying thesis and why it transcends the individual papers themselves. You do not have to have read all of the selected papers before submitting the proposal, but you should have a few additional “back-up” papers in case some of the unread selected papers don’t turn out to be relevant.
  • Nov 16: Submit a progress report (one or two pages).
  • Dec 21: Submit the final project report.

If you need to change your project type or topic after submitting the proposal, you must first confirm this with the instructor and submit a new proposal.

Some suggested topics / papers to read

Random linear maps

Learning mixture models

Speeding-up linear algebraic computations