COMS 4995-004 Optimization for Machine Learning (Fall 2019)

Time & venue
Tuesdays and Thursdays 8:40 am-9:55 am in Kent Hall 413
Instructor
Satyen Kale
Course email
teaching at satyenkale dot com [NOTE: I will not be checking my Columbia email, nor respond to course inquiries sent to my personal email]
Office hours
Tuesdays/Thursdays right after class by appointment only, please email me at least a day in advance to set up a meeting. Location: CEPSR 7th floor, room 7LW1A (across from room 724).
TAs
Gurpreet Singh. Office hours: Mondays 12:00 - 1:00 pm. Location: Mudd 1st floor TA room.
Victor Dong. Office hours: Wednesdays 3:30 - 4:30 pm. Location: Mudd 1st floor TA room.
Chao Qin. Office hours: Thursdays 2:00 - 3:00 pm. Location: Uris Hall 4N.
Online forum
All class discussion will be held on Piazza.

Announcements

Sep 16
Office hours have been posted.
Sep 12
Homework 1 is out.
Aug 27
Sign-up for Piazza using this link.

Schedule

9/3 Administrivia, ML basics, ML as optimization Read: BCN {Chapters 1, 2}, EH {Chapter 1}, CPA {Intro slides}
9/5 ML as optimization, Convexity Read: BCN {Chapters 1, 2}, EH {Chapter 1}, CPA {Intro slides}
9/10 Convexity Read: MJ {Chapter 1}, EH {Chapter 2, till Section 2.1}
9/12 Convexity Read: MJ {Chapter 1}, EH {Chapter 2, till Section 2.1}
9/17 Convexity Read: MJ {Chapter 1}, EH {Chapter 2, till Section 2.1}
9/19 Gradient descent Read: MJ {Chapter 2}
9/24 Projected gradient descent Read: MJ {Chapter 3, till Section 3.4}

Course information

Description
The course covers the theory of optimization for problems arising in machine learning. The course will be highly mathematical and will involve analysis of optimization algorithms. Topics covered will be a subset of the following: convex analysis, first-order methods (cutting plane, gradient descent, stochastic gradient methods, and variants), second order methods (Newton, quasi-Newton such as LBFGS, etc.), acceleration techniques for gradient methods (Nesterov, adaptive preconditioning, variance reduction, etc.), projection-free methods (Frank-Wolfe/conditional gradient), non-convex optimization, online learning, regularization, generalization, and zero-order optimization.
Prerequisites
Introductory machine learning: course similar to COMS 4771.
Multivariate calculus: textbook by Marsden and Weinstein; MIT open courseware.
Linear algebra: immersive linear algebra; lecture notes from UC Davis; MIT open courseware; book chapter by Goodfellow, Bengio, and Courville; additional review notes
Probability: textbook by Grinstead and Snell; book chapter by Goodfellow, Bengio, and Courville; review notes by Arian Maleki and Tom Do
Algorithms: Chapter 0 of textbook by Dasgupta, Papadimitriou, and Vazirani (with discussion of asymptotic notation); "booksite" by Sedgewick and Wayne
Mathematical maturity: notes on writing math in paragraph style from SJSU; notes on writing proofs from SJSU.
Python: You must be comfortable writing code to process and analyze data in Python. Some Python tips are available here.
Course work
Homework assignments: 20%.
Implementation project based on research paper: 30%. Details TBD.
Midterm exam: 20%. Covers topics from the first half of the course.
Final exam: 30%. Covers topics from the entire course, but with an emphasis on the second part of the course.
Lecture notes
All lectures will be on the board and no slides or lecture notes will be provided; you are strongly advised to take your own notes during the lecture. In lieu of slides or lecture notes, pointers will be provided to materials available online, from the textbooks and related courses listed below.
Textbooks
Convex Optimization: Algorithms and Complexity (SB) by Sébastien Bubeck
Convex Optimization (BV) Stephen Boyd and Lieven Vandenberghe
Introductory Lectures on Convex Optimization (YN) by Yurii Nesterov
Lecture notes on Optimization for Machine Learning (EH) by Elad Hazan
Lecture notes on Optimization for Machine Learning (MJ) by Martin Jaggi and Bernd Gärtner
Optimization Methods for Large-Scale Machine Learning (BCN) by Léon Bottou, Frank E. Curtis and Jorge Nocedal
Related courses
Optimization for Machine Learning (CEH) by Elad Hazan
Optimization for Machine Learning (CMJ) by Martin Jaggi
Convex Optimization and Approximation (CMH) by Moritz Hardt
Convex Optimization (CPA) by Pradeep Ravikumar and Aarti Singh
Course materials
Copyright for course materials (e.g., lecture slides, homeworks, exams, solutions) is owned by their respective authors; course materials may not be redistributed without explicit permission.
Getting help
You are encouraged to use office hours and Piazza to discuss and ask questions about course material and reading assignments, and to ask for high-level clarification on and possible approaches to homework problems. If you need to ask a detailed question specific to your solution, please do so on Piazza and mark the post as "private" so only the instructors can see it.
Questions, of course, are also welcome during lecture. If something is not clear to you during lecture, there is a chance it may also not be clear to other students. So please raise your hand to ask for clarification during lecture. Some questions may need to be handled "off-line"; we'll do our best to handle these questions in office hours or on Piazza.

Homework assignments

Formatting policy
Your write-up must be neatly typeset as a PDF document.
It is strongly recommended that you prepare your write-up as a LaTeX document (intro, wikibook). If you do not use LaTeX, you must ensure that the mathematical typesetting is of equal quality and legibility. (Microsoft Office 2013 or later seem to do a reasonable job.)
If you use LaTeX, you should use the following template: homework.tex, homework.cls, homework.pdf. If you do not use LaTeX, you must use an equivalent template: in particular, ensure that your name, your UNI, and the UNI's of students you discussed the homework with appear on the first page.
Submission policy
You must submit your write-up as a single PDF file, called uni.pdf where uni is replaced with your UNI (e.g., abc1234.pdf), on Courseworks by 1:00 pm of the specified due date. If any code is required, separate instructions will be provided.
Late policy
Late assignments will not be accepted.
9/12 Homework 1 Due: 9/26 by 1:00 pm.

Academic Rules of Conduct

Academic honesty
You are expected to adhere to the Academic Honesty policy of the Computer Science Department, as well as the following course-specific policies.
Collaboration
You are welcome and encouraged to discuss course materials and reading assignments, and homework assignments with each other in small groups (two to three people). You must list all discussants in your homework write-up. Discussion about homework assignments may include brainstorming and verbally discussing possible solution approaches, but must not go as far as one person telling others how to solve a problem. In addition, you must write-up your solutions by yourself, and you may not look at another student's homework write-up/solutions (whether partial or complete).
Collaboration of any kind on exams is not permitted.
Outside references
Outside reference materials and sources (i.e., texts and sources beyond the assigned reading materials for the course) may be used on homework assignments only if given explicit written permission from the instructor. Such references must be appropriately acknowledged in the homework write-up. You must always write up your solutions in your own words.
Sources obtained by searching the internet for answers or hints on homework assignments are never permitted.
You are permitted to use texts and sources on course prerequisites (e.g., your linear algebra textbook). If you need to look up a result in such a source, provide a citation in your homework write-up.
If you inadvertently come across the solution to a homework problem: you must acknowledge this source and document the circumstance in your homework write-up, and then do your best to produce a solution without looking at the source. You must, as always, write your solution in your own words.
Violations
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. Such students are also reported to the relevant Deans' offices that handle cases of academic dishonesty.
Credits: Website design by Daniel Hsu, and policies and LaTeX template are by Rocco Servedio.