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:


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.


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.


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.


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.


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
Tue, Nov 30 Convergence rates of gradient descent for constrained optimization
Thu, Dec 2     (lecture continues)