Reading group: From Euclidean to Geodesic Convex Optimization (Spring-Fall 2020)

Schedule: Fri 16:00-17:30 (10:00 Eastern = 7:00 Pacific)
Organizers: Michael Walter, Yinan Li, Harold Nieuwboer

Our goal of is to review standard techniques in convex optimization, give an overview of recent work on quantum algorithms, and learn about geodesic convex optimization on manifolds, motivated by and connecting to recent developments in matrix, operator, tensor scaling etc.

This reading group is a joint event of QuSoft, the N&O group at CWI, and the KdVI at UvA. We warmly invite participants from other institutions – if you are interested in participating please let us know by email. The reading group is run online via Zoom. Video recording and notes are available here.

Part 1: Convex optimization

Date Topic Literature Speaker
Mar 27 Introduction (convexity, duality, gradient descent for strongly convex & smooth functions) 1712.04581 Samarth
Apr 3 Membership vs separation vs optimization, reduction of separation to membership (+ quantum) 1706.07357, 1809.00643 Sander
Apr 10 Optimization from separation, ellipsoid Daniel’s notes Daniel
Apr 17 Mirror descent and acceleration 1712.04581 Nikhil
Apr 24 Interior point methods Renegar Sophie
May 1 Zero sum game approach to LPs (+ quantum) 1904.03180 Joran
May 8 Entropy maximization 1711.02036 Nisheeth
May 15 Matrix scaling (analysis, permanents, matchings, and a peek at cutting edge algorithms) LSW, 1609.06349, 1704.02310, 1704.02315 Rafael
May 22
May 29 Estimating volumes of convex bodies (+ quantum) 1908.03903 Andras
June 5 Rump session - see below

 

Part 2: Geodesic convex optimization

Date Topic Literature Speaker
Jun 12 Geodesically convex optimization (or, can we prove P != NP using gradient descent) video Avi
Jun 19 Manifolds, geodesics, convexity 1806.06373, Udriste, AMS Lucas
Jun 26 Examples: R_+^n and PD(n) 1806.06373, Bhatia Lucas/Harold/Michael
Jul 3 First order algorithms 1602.06053, LSCCJ Harold
Jul 10 - - -
Jul 17 Cutting plane methods on manifolds 1804.10738 Cole
Jul 24 Curvature, Alexandrov spaces, optimal transport TBD Quentin
Sept 11 Scaling problems & geodesic convex optimization I 1910.12375 Michael
Sept 18 Scaling problems & geodesic convex optimization II 1910.12375 Michael
Sept 25 Continuous scaling by gradient flow (Paulsen, spectral analysis) 1710.02587, 1904.03213, 2002.00071 Akshay
Oct 2 Extremal combinatorics, tensor scaling, moment polytopes 1709.07851, 1804.04739 Jeroen

 

Rump session speakers

 

A scaling algorithm in action