CMSC 34500: Optimization

This is a webpage for the Spring 2010 course at TTIC and the University of Chicago (known as CMSC 34500 at the University).

Tuesdays and Thursdays 3-4:30pm at TTIC 530 (located at 6045 S. Kenwood Ave, fifth floor)

Lecturer: Nati Srebro.
TAs: Karthik Sridharan and Andy Cotter.
Homework Submissions: .

Course Description

The course will cover techniques in unconstrained and constrained convex optimization and a practical introduction to convex duality. The course will focus on (1) formulating and understanding convex optimization problems and studying their properties; (2) presenting and understanding optimization approaches; and (3) understanding the dual problem. Limited theoretical analysis of convergence properties of methods will be presented. Examples will be mostly from data fitting, statistics and machine learning.

Specific Topics:

Text Books

The required textbook for the class is: The book is available online here. About 75% of the material covered in the class can be found in the above book.

Supplemental recommended books:

Requirements and Grading:

There will be roughly bi-weekly homework assignments, counting toward 30% of the grade. Assignments must be typed (not handwritten) and submitted electronically in PDF. Collaborative work on the homeworks is encouraged, but each student must eventually write up the solution independently.

There will also be several MATLAB programming and experimentation assignments, counting toward another 30% of the grade.

The remaining 40% of the grade will be based on a final exam.

Students may also choose to do an optional project, which could replace some of the above requirements.

Lectures and Required Reading:

Lecture 0: Tuesday March 30th
(lecture by Ambuj Tewari) Required Reading: Boyd and Vandenberghe Sections 2.1-2.3,2.5,3.1-3.3
Homework 1 out (due April 12th)
Lecture I: Thursday April 1st
Boyd and Vandenberghe Sections 1.1-1.4,4.1-4.2,9.1
Lecture II: Tuesday April 6th
Boyd and Vandenberghe Sections 9.1-9.3,9.5
Lecture III: Thursday April 8th
Boyd and Vandenberghe Sections 9.5-9.6; Bertsekas Sections 1.6-1.7
Programming assignment 1 out (source code) (due May 3rd)
Written Assignment 1 (due April 26th)
Lecture IV: Teusday April 13th
Boyd and Vandenberghe Sections 4.2-4.3,5.1,5.2,5.4,5.5.1
Lecture V: Thursday April 15th
Lecture VI: Tuesday April 20th
Lecture VII: Thursday April 22nd
Lecture VIII: Tuesday April 27th
Lecture IX: Thursday April 29th
Lecture X: Tuesday May 4th
Lecture XI: Thursday May 6th
Lecture XII: Tuesday May 11th
Lecture XIII: Thursday May 13th
Lecture XIV: Tuesday May 18th
  • Review and limitations of methods with polynomial convergence.
  • Large-scale, slowly converging, first order methods.
  • Sub-gradient descent with projection, step size and analysis for Lipschitz functions over a bounded domain (Section 5.3.1 of Nemirovksi's "Lectures on Modern Convex Optimization").
    Lecture XV: Thursday May 20th
    • More about sub-gradient descent, step-size selection and constraints.
    • Gradient descent as a proximal point method.
    • From gradient descent to bundle methods (more information in Section 5.3.2 of Nemirovksi's "Lectures on Modern Convex Optimization").
    • Mirror Descent formulation and basic concepts: strong convexity with respect to a norm, dual norm, distance generating function and Bergman divergence (Section 5.4.1 of Nemirovksi's "Lectures on Modern Convex Optimization").
    Lecture XVI: Tuesday May 25th
    • Mirror Descent: Analyzis (Section 5.4.2 of Nemirovksi's "Lectures on Modern Convex Optimization").
    • Optimization over the simplex using Mirror Descent. (Sections 5.5.1 of above))
    • Partial linarization.
    Lecture XVII: Thursday May 27th
    • Stochastic Gradient Descent and Stochastic Optimization. (Section 14.1 of Nemirovksi's "Efficient Methods in Convex Programming")
    • Overview of further results for first order methods: robustness, faster rates with strong convexity, faster rates with smoothness, acceleration with smoothness.
    Lecture XVIII: Tuesday June 1st
    • Course Summary
  • Assignments:

    Last modified: Tue Jun 01 01:46:24 Central Daylight Time 2010