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 | - | 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
- Sophie Huiberts (CWI): an alternative cutting plane method based on polar geometry
- Rafael Oliveira (Waterloo): hyperbolic polynomials and optimization
- Daniel Dadush (CWI): circuits for LP
- Tushant Mittal (Chicago): scaling and singularity testing
- Harold Nieuwboer (Amsterdam): unconstrained geometric programs and scaling problems
- Quentin Paris (HSE Moscow): barycenter problem & convex optimisation in geodesic metric spaces
- Philipp Reichenbach (TU Berlin): computational invariant theory I
- Mahmut Levent Doğan (TU Berlin): computational invariant theory II
- Jeroen Zuiddam (IAS): subrank of tensors and optimization
