COMS 4772 Advanced Machine Learning (Fall 2014)

Time & venue
Wednesday 4:10–6:00 PM in 633 Mudd
Daniel Hsu
Office hours
Monday 1:00–3:00 PM in 702 CEPSR
TA office hours
Monday 6:00–7:00 PM (Zhongyu Wang)
Thursday 4:00–5:00 PM (Xiaohan Liu)
Thursday 5:30–6:30 PM (Anirban Gangopadhyay)
TA office hours are in the TA room.
E-mail (replace #### with course number)
Include "coms4772" (without quote marks, as a separate token) at the start of the e-mail subject.
Online forum


Dec 5
Office hours for week of Dec. 8th.
By appointment only: send a message to the course e-mail.
Note that I (Daniel) will be out-of-town all week.
Office hours for week of Dec. 15th.
Monday (Dec. 15) 1:00–3:00 PM (Daniel)


9/3 introduction [notes] Homework 1 (due Sep 10).
9/10 experts [notes] Homework 2 (due Sep 24).
9/17 bandits and games [notes]
9/24 perceptron and winnow [notes]
10/1 online-to-batch [notes],
large feature spaces [notes]
Homework 3 (due Oct 15).
Project proposal submission open.
10/8 random linear maps [notes],
introduction to convexity [notes]
Read B&V (2.1-2.3, 3.1-3.2)
10/15 follow the leader [notes] Homework 4 (due Nov 5).
Project proposal submission closed.
10/22 online gradient descent [notes],
duality [notes]
10/29 strong convexity [notes],
primal-dual algorithms [notes]
11/5 Bregman divergences, [notes]
exp-concave losses [notes]
11/12 composite losses, [notes]
tradeoffs, batch vs. online
Project status update due.
Read The Tradeoffs of Large Scale Learning.
11/19 boosting [notes] Homework 5 (last updated Nov. 17).
11/26 review [slides]
12/3 in-class exam [notes]

Course information

Online learning and online optimization
Machine learning (e.g., COMS W4771)
Algorithms (e.g., CSOR W4231)
Linear algebra (e.g., MATH V2020)
Multivariable calculus (e.g., MATH V110{1,2,3,4} or MATH V120{7,8})
Probability theory (e.g., STAT W4109 or SIEO W4150)
Ability to analyze and evaluate algorithms
Ability to write clear and concise proofs
Proficiency in and regular access to a modern programming environment
Course work
Homework (50%)
In-class exam, during the 12/3 lecture (25%)
Final project (25%)
Optional text
Prediction, Learning, and Games by Cesa-Bianchi and Lugosi [On (e-)reserve]

Homework assignments

[Policies and LaTeX template shamelessly stolen from Rocco Servedio.]

Formatting policy
You must prepare your write-up as a LaTeX document.
If you're unfamiliar with with LaTeX, click here for an introduction.
Furthermore, you must use the following template: homework.tex, homework.cls.
Your name and UNI should appear on every page. The UNI's of students you discussed the homework with should appear on the first page.
Submission policy
You must submit your write-up on Courseworks as a single PDF document by 4:00 PM of the specified due date.
You must also submit a hard-copy of your write-up in the next lecture following the specified due date (which might be the same day, at 4:10 PM).
Please staple all pages together.
If you use more than one sheet of paper for any given problem, these sheets must be stapled together. Pages for different problems must not be stapled together.
Late policy
Each student is allowed three unpenalized late days for the entire semester. All late days beyond the first three are penalized. Each (penalized or unpenalized) late day is exactly 24 hours and cannot be subdivided (e.g., five minutes late counts as one late day). Each penalized late day deducts 10% of the (unpenalized) earned score. For instance, if you earn 100 points on an assignment but hand it in three penalized days late, then you will actually only earn 70 points. Exceptions are only granted under exceptional circumstances which I deem reasonable; to qualify you must have your undergraduate or graduate advisor contact me explaining the exceptional circumstance. (If I am your advisor, you must find another faculty member to serve as a proxy for this matter.)
Collaboration policy
You are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people), but you must list all discussion partners in your write-up. Discussion of homework problems may include brainstorming and verbally discussing possible solution approaches, but must not go as far as one person telling the others how to solve the problem. In addition, each person must write up her/his solutions independently; you may not look at another student's written solutions. All outside reference materials used must be appropriately acknowledged in the write-up, and you must always write up your solutions in your own words.
Academic honesty
Students are expected to adhere to the Academic Honesty policy of the Computer Science Department; this policy can be found in full here.
Violation of any portion of these policies will result in a penalty to be assessed at the instructor's discretion. This may include receiving a zero grade for the assignment in question AND a failing grade for the whole course, even for the first infraction.

Final project

Projects are to be done in groups of two or three students (no exceptions).

Possible project types

  1. Literature synthesis. Pick a subtopic of online learning or online optimization in consultation with me, read at least three relevant and distinct papers on the subtopic, and write a report that synthesizes these papers to produce some new insight or understanding about the subtopic. You must do more than simply summarize the papers. Rather, you should try to find new connections between the works, relate different settings and assumptions, and find interesting open problems on the subtopic. The exposition should demonstrate a solid understanding of the main ideas from the papers.
  2. Original research. Propose a research project on a specific topic related to online learning or online optimization in consultation with me, carry out the plan as far as possible, and write a report describing the results. The project must have a substantial theoretical component; simply conducting an empirical evaluation of an algorithm is not sufficient (although that could be single part of a larger project). The report should clearly describe the motivation for the project, demonstrate a solid understanding of prior work, and detail the results of the project (and/or any partial progress). In case things don't work out as planned, you should be prepared to convert the research project into a literature synthesis project (exactly as described above).

I suggest looking at past ICML, COLT, and NIPS conference proceedings for ideas.

Project components

  1. Project proposal (submit any time between 10/1–10/15). Write a one-page description of your plans for the project, and submit it as a PDF file on Courseworks.
    • Decide on a project group (two or three students).
    • Pick a concrete project topic.
    • Pick at least three relevant and distinct papers on the topic (for a literature synthesis project), or pick at least three relevant papers on prior work or background material (for an original research project).
    • Briefly explain, without going into details, how each paper relates to your proposed project.
    I will post the project proposals on the website as I receive them on Courseworks. If your proposed project is too similar to one already proposed by another group, I will ask you to suitably revise it.
  2. Status update (due 11/12) Write a one-page description of the current status of your project, and submit it as a PDF file on Courseworks.
    • For a literature synthesis project, you should briefly describe what the main ideas in most (e.g., at least two) of the chosen papers are, and briefly describe how they relate.
    • For an original research project, you should briefly describe partial progress on the project, and/or describe current obstacles you are facing.
  3. Final report (due 12/17) Submit the final report as a PDF file on Courseworks (no hard-copy necessary). The report should be around six to eight pages, single-spaced and single-column, 11 points font, with one inch margins. (Longer reports are okay provided that you really do have more than eight pages of real content.) The report will be evaluated on the basis of both presentation and technical quality, so please proofread for clarity of exposition (e.g., make sure everything is unambiguously defined) and accuracy/completeness of results/arguments. Also, make it very clear which contributions in the report are original (if any), and properly cite any works you reference throughout the report.