CS 69000-SML: Statistical Machine Learning II

Semester:	Fall 2021, also offered on Spring 2019 and Spring 2017
Time and place:	Tuesday and Thursday, 10.30am-11.45am, Hampton Hall 2117
Instructors:	Jean Honorio
Office hours:	(Please send an e-mail for appointments)

Continuous and combinatorial optimization are at the heart of every machine learning algorithm. This course is an introduction to the theoretical aspects of continuous and combinatorial optimization, relevant to machine learning problems. By using continuous optimization, we will answer questions relevant to classification, such as "where does the dual form of support vector machines come from and why does it work?". By using combinatorial optimization, we will answer questions relevant to influence maximization in networks, such as "why does the greedy approach allows for maximizing influence within a factor of 1-1/e?".

Learning Objectives

During the course, students will:

learn the theoretical aspects of continuous and combinatorial optimization, relevant to machine learning problems.
learn how to transform those problems into problems that are simpler to understand, analyze and/or solve.
present recent papers from the leading machine learning conferences and journals.

Prerequisites

Basic knowledge from calculus and linear algebra is required. Some knowledge from machine learning, data mining or artificial intelligence is also required (CS57300, CS57800 or CS5900-AI0). Necessary concepts from optimization will be provided during the course.

Textbooks

For convex continuous optimization, we will use Convex Optimization by Boyd and Vandenberghe.
For nonconvex continuous optimization, we will use papers from the leading machine learning conferences and journals.
For combinatorial optimization, we will use lecture notes.

Assignments

There will be up to six homeworks, one paper presentation, one midterm exam and one final exam (dates posted on the schedule). The homeworks are to be done individually.

Grading

Homeworks: 40%
Paper presentation: 10%
Midterm exam: 25%
Final exam: 25%

Late policy

Assignments are to be submitted by the due date listed. Each person will be allowed seven days of extensions which can be applied to any combination of assignments during the semester. Use of a partial day will be counted as a full day. Extensions cannot be used after the final day of classes. Please, use the extension days wisely!

Assignments will NOT BE accepted if they are more than five days late.

Academic Honesty

Please read the departmental academic integrity policy here. This will be followed unless we provide written documentation of exceptions. We encourage you to interact amongst yourselves: you may discuss and obtain help with basic concepts covered in lectures and homework specification (but not solution). However, unless otherwise noted, work turned in should reflect your own efforts and knowledge. Sharing or copying solutions is unacceptable and could result in failure. You are expected to take reasonable precautions to prevent others from using your work.

Additional course policies

Please read the general course policies here.

Schedule

We will start by covering chapters 1-5,9-11 in Convex Optimization by Boyd and Vandenberghe (B&V).

Date	Topic (Tentative)	Notes
Tue, Aug 24	B&V Chapter 1: introduction	Identities on matrix calculus
Thu, Aug 26	B&V Chapter 2: convex sets
Tue, Aug 31	B&V Chapter 3: convex functions Examples: equation 1 in [1], section 3 in [2] (not mandatory to be read)	Homework 1: due on Sep 7, 11.59pm EST
Thu, Sep 2	(lecture continues)
Tue, Sep 7	B&V Chapter 4: convex optimization problems Examples: equation 6 in [1], equation 8 in [2] (not mandatory to be read)	Homework 1 due
Thu, Sep 9	(lecture continues)
Tue, Sep 14	(lecture continues)	Homework 1 solution Homework 2: due on Sep 21, 11.59pm EST
Thu, Sep 16	B&V Chapter 5: duality Example: [1] (not mandatory to be read)
Tue, Sep 21	(lecture continues)	Homework 2 due
Thu, Sep 23	(lecture continues)
Tue, Sep 28	(lecture continues)	Homework 2 solution Homework 3: due on Oct 5, 11.59pm EST
Thu, Sep 30	—
Tue, Oct 5	B&V Chapter 9: unconstrained optimization	Homework 3 due Send me an e-mail with a link to the paper you plan to present
Thu, Oct 7	(lecture continues) B&V Chapter 10: equality constrained optimization
Tue, Oct 12	OCTOBER BREAK	Homework 3 solution
Thu, Oct 14	MIDTERM (Chapters 1-4)	10.30am-11.45am at Hampton Hall 2117 Midterm solution
Tue, Oct 19	(lecture continues) B&V Chapter 11: interior-point methods
Thu, Oct 21	—	Presentation slides due (see email for directions)
Tue, Oct 26	(lecture continues)
Thu, Oct 28	Student presentations: Abhijeet [1], Jiajun [2], Shuang [3], Xinyi [4]	Homework 4: due on Nov 4, 11.59pm EST
Tue, Nov 2	Student presentations: Zhanyu [1], Shanyun [2], Sehwan [3], Qiuling [4]
Thu, Nov 4	Student presentations: Hanbyul [1], Huiming [2], Mingxuan [3], Xiaochen [4], Zihan [5]	Homework 4 due
Tue, Nov 9	Student presentations: Jinwon [1], Yao [2], Austin [3], Eunhan [4], Hyeong [5]	Homework 4 solution Homework 5: due on Nov 16, 11.59pm EST
Thu, Nov 11	Student presentations: Tian [1], Muye [2], Wenjie [3], Pramith [4]	Student presentation slides
Tue, Nov 16	Matroids and the greedy algorithm	Homework 5 due
Thu, Nov 18	Submodular optimization Greedy algorithms for submodular maximization
Tue, Nov 23	FINAL EXAM (Chapters 5, 9-11, matroids, submodularity)	10.30am-11.45am at Hampton Hall 2117 Final exam solution
Thu, Nov 25	THANKSGIVING VACATION
Tue, Nov 30	Convergence rates of gradient descent for constrained optimization
Thu, Dec 2	(lecture continues)