The Work You Do

---

Late Policy

Late submissions will NOT be accepted, but to allow for flexibility in case of issues for any reason to submit solutions in time, 10% of the mark can be shifted from any component to the midterm.

Course Project

Deadlines

• Proposal: October 29, 2023 11:55pm
• Presentations: December 5 and 7, 2023, in class
• Report: December 10, 2023 11:55pm

Objective and evaluation

The project should be done individually or in a group of two (maximum group size of two).

The goal is for everyone to get a taste of how it is to work on theoretical aspects of machine learning. In the project, you do not actually need to produce research paper quality results (although if you do, no one will complain!). It is sufficient to demonstrate a thorough understanding of some aspect of the theory literature, such as:

• What are the interesting questions to ask (and what are less interesting questions?)
• What is known about a given topic (and what is not known)?
• Sorting out whether some assumption is critical for some result (or not).

When evaluating the reports, we will not care that much about originality (new results) than coherence, soundness and the quality of writing. In fact, a typical report is expected to be a readable (and possibly entertaining) summary of a topic in the area. Reports that contain original results are also welcome, just to earn full grade, originality is absolutely not required.

We strongly recommend to start small: Aim for writing a review of some results of interest. If time permits and as you feel fit, add new results.

Having said this, if you score a new result early on, it is also OK to start on writing that result down.

How to choose a topic?

1. Choose a theory paper and rewrite it to make it better. Choose and pick of what you include in your report. It may be better proofs. It may be better exposition of the results. Be critical about assumptions (but not overly critical). It may be putting the results into a perspective. Aim for readable (but technically correct) writeups.
2. Choose a problem that you care about in the area. Ask what is known. Write a summary about it. Be specific about what problems you are writing about. If time permits and with some luck, add new results. Aim for small things, like, such and such is known in topic A but only under condition B. Do these results extend to condition C? What conditions are necessary? How about slightly changing the problem, adding or removing a condition?
3. Choose an open question and try to answer it. When there is an upper bound, ask whether there is a matching lower bound. If not quite, try to reduce the gap. Ditto for lower bounds. Any time you see a bound you can ask: Is this tight?
4. It is a bit more risky, but possibly more rewarding, is to choose a non-theory paper and look at it through the eyes of a theoretician. Are there any hard claims that could be formulated (and possibly proved) in the context of the paper? If the paper is proposing algorithms, are there any conditions when the algorithm proposed will work “well”? How well? Put the results into the context of what is known.

Formatting

The reports should be typeset in latex and sent as a pdf document. The template is available here. The report should be maximum 9 pages long, the proposal maximum 2 pages long. They should have the standard structure:

• Introduction (what is the problem studied, why do we study it)
• Results (the “meat”)
• Conclusions/summary (what did we learn? what is the short take-away from all of this? what’s next if anything?)

Examples of topics

TBA

---