CSE 599: Interplay between Convex Optimization and Geometry

In this course, we cover several frameworks for convex optimization, including, first-order methods, cutting plane methods and interior point methods. Besides covering some basic algorithms in those frameworks, we explain the geometry picture behind many of these algorithms.

Administrative Information:

  • Instructor: Yin Tat Lee
  • Office Hours: By appointment, email me at yintat at uw dot edu.
  • Lectures: WF 3:00-4:20 at EEB 037
  • Course evaluation: 2 homework (50%), final project (50%)
  • Mailing list: https://mailman1.u.washington.edu/mailman/listinfo/cse599s_wi18

Assignments:

Announcements

  • Jan 15: Assignment 1 is posted.
  • Jan 3: I corrected the statement of the open problem in the lecture note 1.
  • Jan 1: The schedule is updated. Due to time constraints, the sampling part is removed and replaced by an optional reading. Feel free to ask me any question on the survey.

Tentative Schedule:

Remark: Some lecture notes are updated after the class.

Cutting Plane Methods

  • Jan 05: Ellipsoid Method and Reductions Between Convex Oracles (Note)
  • Jan 10: Composite Problem via Duality (Note)
  • Jan 12: Marginal of Convex Set (Note)
  • Jan 17: John Ellipsoid (Note)
  • Jan 19: Geometric Descent (Note)

First Order Methods

  • Jan 24: Gradient Descent, Mirror Descent, and Accelerated Gradient Descent
  • Jan 26: Coordinate Descent and Stochastic Descent
  • Jan 31: Preconditioning
  • Feb 02: Example: Maximum Flow Problem

Algorithms for Linear Systems

  • Feb 07: Leverage Score & Uniform Sampling Method
  • Feb 09: Lewis Weight
  • Feb 14: How does MATLAB solve Ax=b?
  • Feb 16: Sparse Cholesky Decomposition

Interior Point Methods

  • Feb 21: Homotopy Method
  • Feb 23: Newton Method & Self-Concordant Barrier
  • Feb 28: Entropic Barrier
  • Mar 02: Lee-Sidford Barrier

Other Methods

  • Mar 07: Quasi-Newton Method
  • Mar 09: ???

Related CS Theory Courses: