Advanced Optimization and Randomized Methods

Organizational Information

  • Lectures: Monday and Wednesday, 3:00PM–4:30PM

  • Location: Gates Hillman Center 4307

  • Recitations: Tuesdays 5:30-6:30pm

  • Location: GHC 4307

  • Instructors: Alex Smola and Suvrit Sra

  • TAs: Madalina Fiterau (ina.fiterau@gmail.com) and Yu-Xiang Wang (luke.yxwang@gmail.com)

  • Grading Policy: Homeworks (50%), Project (48%), Scribing (2%)

  • Office hours for Suvrit: email me.

ANNOUNCEMENTS

[13 Jan 2014] SIGN UP FOR THE GOOGLE GROUP
[15 Jan 2014] Start looking for project partners
[22 Jan 2014] HW1 is out; due on Feb 03, 2014 (beginning of class)
[05 Feb 2014] HW2 is out; due on Feb 12, 2014, 11:59PM EST
[12 Feb 2014] HW3 is out; due on Feb 24, 2014, 11:59PM EST
[24 Feb 2014] HW4 is out; due on Mar 12, 2014, 11:59PM EST
[24 Mar 2014] Midterm project report due
[31 Mar 2014] Reviews of midterm reports due
[29 Apr 2014] Project presentations, part I
[30 Apr 2014] Project presentations, part II
[02 May 2014] Final project reports due
[09 May 2014] Project report reviews due
[14 May 2014] Grades are out

Goals

This course will cover a variety of topics from optimization (convex, nonconvex, continuous and combinatorial) as well as streaming algorithms. The key aim of the course is to make the students aware of powerful algorithmic tools that are used for tackling large-scale data intesive problems. The topics covered are chosen to give the students a solid footing for research in machine learning and optimization, while strengthening their practical grasp. In addition to foundational classical theory, the course will also cover some cutting-edge material due to the rapidly evolving nature of large-scale optimization.

Prerequisites

Students entering the course are expected to have prior exposure to convex optimization and algorithms at a graduate level. It will be very useful to have a strong working knowledge of linear algebra, analysis, and to some extent probability and statistics. Programming in a couple of high-level languages will be of advantage.

Lectures and related material

Date Topic Notes and Reading Material Video Lecturer
1 13 Jan 2014 Convex Sets Notes; [1]; [Video] Suvrit
2 15 Jan 2014 Convex Functions Scribed notes; Scanned notes; [1]; [2]; [Video] Suvrit
3 22 Jan 2014 Conjugates, Subdifferentials, Optimization Problems Scribed notes; Scanned notes; [1]; [2]; [Video]; Recitation Suvrit
4 27 Jan 2014 SDP relaxations, MaxCUT, Goemans-Williamson Papers; Scanned notes; [Video] Alex
5 29 Jan 2014 Hash functions, LSH, Simhash et al. Papers; Scanned notes; [Video] Alex
6 03 Feb 2014 Weak duality, strong duality, minimax Slides; [1] [2] [Video]; Recitation Suvrit
7 05 Feb 2014 Duality, KKT, conic duality Scribed notes; Scanned notes; [1]; [Video]; Recitation Suvrit
8 10 Feb 2014 Simhash, Minwise Hash Properties Scan; [Video] Alex
9 12 Feb 2014 Concentration inequalities [Video]; Alex
10 17 Feb 2014 Flajolet-Martin counter, heavy-hitters Slides [Video]; Alex
11 19 Feb 2014 Bloom filters [Video] Alex
12 24 Feb 2014 Descent methods, CCCP [1] [2]; Scan; [Video]; Suvrit
13 26 Feb 2014 Prox-operators [1] [2] Yaoliang notes [Video]; Yaoliang
14 03 Mar 2014 Countmin sketch, Counter braids, LSH [Video] Alex
15 05 Mar 2014 Hash Kernels, Sketching, Randomized mult Slides; Notes 1; Notes 2; Notes 3 [Video]; Alex
16 17 Mar 2014 Compressed matrix mult; random kitchen sinks Notes [Video]; Ina
17 19 Mar 2014 Random function classes [Video]; Alex
18 24 Mar 2014 Proximal methods, monotone operators, splitting Slides; Notes [Video]; Suvrit
19 26 Mar 2014 Parallel proximal; Incremental gradient Slides; Papers [Video]; Suvrit
20 31 Mar 2014 Conditional gradient methods Slides [Video]; Yaoliang
21 02 Apr 2014 Incremental methods; Stochastic Optimization Slides; [Video]; Suvrit
22 07 Apr 2014 Fixed-point theory; Nonlinear conic optimization Slides; Suvrit
23 09 Apr 2014 Complexity theory of optimization Notes [Video]; Aaditya
24 14 Apr 2014 Random projection methods I [Video]; Alex
25 16 Apr 2014 Random projection methods II; Linear systems [Video]; Alex
26 21 Apr 2014 Random projection methods III; Matrix decompositions [Video]; Alex
27 23 Apr 2014 Randomized matrix algorithms; matrix functions [Video]; Alex
28 28 Apr 2014 Derivative free optimization Slides; [Video]; Suvrit
29 30 Apr 2014 Project presentations Remarks; Suvrit