CS 798 - Convexity and Optimization

CS 798: Convexity and Optimization

Lecture:	Wednesdays and Fridays, 10:30-11:50, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Fridays, 2-3, DC 3120.
Tutor:	Tsz Chiu Kwok
Piazza:	piazza.com/uwaterloo.ca/winter2017/cs798a

In this course, we will study some recent developments in theoretical computer science using tools from convex optimization and convex geometry. Towards this goal, we will cover the fundamentals required in these areas. The following is a tentative syllabus.

convex sets, convex functions, examples, inequalities.
duality, separating hyperplane, optimality conditions, John ellipsoid.
gradient descent algorithms, approximating min-cut.
multiplicative update, mirror descent, approximate Caratheodory.
Newton method, interior point method, maximum flow.
ellipsoid method, cutting plane method, matroid intersection, geometric descent.
volume, Brunn-Minkowski's inequality, Grunbaum's theorem.
isoperimetric inequalities, concentration of measure, discrepancy minimization.
random sampling in convex bodies.
semidefinite programming, Grothendieck's inequality, log-rank conjecture.

References: Notes will be provided. The following is a list of primary references.

Convex Optimization, by Boyd and Vandenberghe.
Convex Optimization: Algorithms and Complexity, by Bubeck.
An Elementary Introduction to Modern Convex Geometry, by Ball.
Algorithmic Convex Geometry, by Vempala.

The recent results are extracted from papers. See the project page for further references.

Site menu: