Theoretical Machine Learning

CSCI 699, Fall 2019

Haipeng Luo

Final Project

The final project is to conduct a short survey on a specific topic on learning theory. Each of you has been assigned 1-2 papers (around 25-35 pages in total including appendix), based on alphabetical order of last names (see below). The project includes two parts
  • (20%) one 35-minute presentation on the assigned date. More concrete instructions can be found below.
  • (40%) one final survey report, due on 12/16 (no late day is allowed). More concrete instructions can be found below.
Important: The order of the presentation topics is fixed. So if you happen to have schedule conflict and cannot present on the assigned date, please first try to find a classmate to swap the topics and the presentation dates with you (and inform me the change). If you cannot find anyone to swap with you, talk to me and I will make other arrangements. But in any case, this should be done as early as possible, no later than 11/07.

Assigned papers and schedule

Name Papers Date
Liyu Chen Learnability, Stability and Uniform Convergence 11/14
Dongsheng Ding Multiclass Learnability and the ERM Principle
Daniil Feldman PAC-learning in the Presence of Evasion Adversaries
VC Classes are Adversarially Robustly Learnable, but Only Improperly
Hrayr Harutyunyan Spectrally-normalized Margin Bounds for Neural Networks
Zhiyun Lu The Isotron Algorithm: High-Dimensional Isotonic Regression
Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
Tiancheng Jin Competing With Strategies 11/21
Zimo Li Blackwell Approachability and No-Regret Learning are Equivalent
Hexiang Hu Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Chuizheng Meng Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback
Ravi Lanka Subrahmanya Online Learning: Sufficient Statistics and the Burkholder Method 12/05
Heramb Nemlekar Contextual Bandits with Linear Payoff Functions
Improved Algorithms for Linear Stochastic Bandits
James Preiss Exploration by Optimisation in Partial Monitoring
Bowen Zhang Minimax Regret Bounds for Reinforcement Learning

Some guidance on reading these papers:
  • Note that they are all closely related to the lectures. So when reading these papers, try to find the connections with what you have learned from this course.
  • Some papers could be notation-heavy and get rather technical at some parts. You are by no mean required to understand every single detail of the papers. Instead, try to focus on the key ideas/messages. It is fine that you only skim some parts of the paper, as long as you spend time in carefully reading and understanding some other main parts.
  • If you need further help understanding the papers, feel free to ask on Piazza or schedule an appointment with me.

Instructions on presentation

The goal of having this component in the final project is to give you an opportunity to practice the skill of giving talks, which is an extremely important part of your PhD training (but is often overlooked). Follow the instructions below to make sure you give a smooth talk.

Each presentation is 35 minute long. I suggest you to roughly break it down into following parts:

  • (3-5 minutes) introduction: what is the topic you are presenting? how is this related to the lectures? what are the main results of the assigned paper(s)? why are they significant? what will you cover in the rest of the talk?
  • (5-10 minutes) setting up: describe the problem in detail and introduce necessary notations.
  • (~15 minutes) main results: describe the main algorithms and/or theorems. Try to put more emphasis on explaining the key ideas.
  • (2-3 minutes) conclusion: conclude you talk and highlight the key take-home message.
In addition, keep the following in mind when preparing the talks:
  • It is recommended that you give a board talk, just like our regular lectures. In this case, think carefully about how you are going to use the board: how much space do I need? what should I put in each part of the board? how do I avoid erasing stuffs that I need later? You can also prepare slides if you prefer, in which case please let me know before the lecture so we can make sure there is no problem in setting up the projector.
  • Anticipate questions from the audience. Just like the regular lectures, everyone is encouraged to ask questions during the talk. Make sure you understand the question before answering, and try to answer it concisely if you can so you can finish the talk in time. It is perfectly fine if you do not know the answer for tough questions -- simply acknowledge it in this case and move on. But make sure you address simple clarification questions, especially in the beginning of the talk when setting up the problems.
  • By no mean you need to cover everything in your assigned papers! In fact, most likely you will only have time to cover one or two main results. If you have two assigned papers, you could also choose to present results from only one of them (although in the report you do need to cover both).
  • Even if the paper is notation-heavy, it does not mean your talk has to be so. Try to use a minimum amount of notation to convey what you want to say. It is common to make simplification in talks even if that means sacrificing generality or even rigorousness.
If you have any other questions, feel free to ask on Piazza!

Instructions on writing the report

The final report has to be written in Latex and must be 8-9 page long, excluding references. You can use the NeurIPS format that we have been using for lecture notes and homework, or some other similar styles. The report summarizes and distills the main results of your assigned papers, and should include the following components:
  • A short abstract, summarizing the entire survey.
  • Introduction: Introduce the main topic of you assigned paper(s). Try to put it into the context of general learning theory and explain how it relates to topics covered in our lectures. Briefly mention the high-level results and explain the significance of the results (such as improvement over prior work).
  • Problem setup: For this and the next two parts ("Main results" and "Proofs"), you can use the lecture notes as examples. For problem setup, you should describe the problems in detail using necessary notation. Once again, you are not asked to cover everything in the papers, so only describe in detail what you plan to cover in this short survey.
  • Main results: Describe the main algorithms/theorems. For algorithms, describe what they are doing at each step and what the key idea is behind it. For theorems, after the formal statement, try to explain in words what the statement really means and what the implications are.
  • Proofs: Try to distill some proofs from the paper and reproduce them in the report. Due to space limit, most likely you can only fit 1-3 proofs into the report, so pick the ones that you think are most important. If the original proofs are long and complicated, try to break it down into several parts (in the form of lemmas for example), and only present the proofs for some of these parts. Again, use the lecture notes as examples.
  • A short conclusion, highlighting the main message again.
  • References.
The following two are optional and considered as bonus tasks. You can use up to 1 extra page for each of these two extra components:
  • Open questions: Identify interesting and concrete open questions in the same direction that are not mentioned in the papers already. Mention briefly what you think the potential approaches are to tackle these open questions and/or why you think these are hard problems that require new techniques beyond what the papers present.
  • More papers in the same direction: Read more related papers of the same topic and include an extended related work section that summarizes what the other papers you read are about and how they are compared to your assigned papers. To find these other papers, you can use the reference list of your assigned papers, use Google Scholar to see which papers cite your assigned papers, or do a general online search of the related topic.
If you have any other questions, feel free to ask on Piazza!