[Theory] Topics Course in Optimization: Fast Algorithms via Continuous Optimization and Combinatorial Preconditioning

[Lorenzo Orecchia]

Hi all,

Following up on Aaron’s magnificent lead, this quarter I am teaching the following topics course. Prerequisites are undergraduate algorithms and a working knowledge of convex optimization and linear algebra. Feel free to contact me with any questions.

Best wishes for a great quarter,
Lorenzo

CMSC 35480 Fall 2021: Topics in Optimization: Fast Algorithms via Continuous Optimization and Combinatorial Preconditioning

Instructor: Lorenzo Orecchia
Hours: TR 9.30-10.50am
Location: JCL 354

Note: Meeting times and location may change by consensus of all the course takers and the instructor.

Topic Area: In the last decade, techniques from continuous optimization have led to faster (approximation) algorithms for classical graph problems in combinatorial optimization. Many of these results have relied on the use of a novel framework for algorithm design, based on first-order iterative methods, such as gradient and mirror descent. Contrary to popular intuition, this is actually a very rich algorithmic class, as all such methods require a choice of underlying, possibly non-Euclidean, geometry (aka preconditioning). Indeed, we will see how to interpret the new algorithms as judicious combination of the right first-order methods and the right geometry, whose choice often requires an elegant mix of geometric and combinatorial arguments.

In this class, we will explore this novel algorithmic design framework through the lens of minimum-cost maximum-flow tasks, a general family of problems including s-t maximum flow and s-t shortest paths. We will also take small detours to touch on open problems and current projects in my research group.

For an introduction to the topic, I recommend the 2018 ICM presentation here<https://eta.impa.br/dl/028.pdf.>.

Course Type: Seminar on current research topics. The instructor and students, working in groups when possible, will present papers in the topic area. This course does not feature an objectively graded component, so it will not fulfill the Theory requirement for CS PhD students. Ask the instructor about possible projects to complete in conjunction with the course, if you are interested in having the course count towards requirements.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210927/cbbaf17e/attachment.html>