Reading group: From Euclidean to Geodesic Convex Optimization

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 Generalities (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 GLS Daniel
Apr 17 Mirror descent and acceleration 1712.04581 Nikhil
Apr 24 Interior point methods (perhaps illustrated for LP?) Renegar Sophie
May 1 Zero sum game approach to LPs (+ quantum) 1904.03180 Joran
May 8 Entropy maximization 1711.02036 Michael
May 15 Matrix scaling (analysis, permanents, matchings, and a peek at cutting edge algorithms) LSW, 1609.06349, 1704.02310, 1704.02315 Rafael
  Research discussion    

 

Part 2: Geodesic convex optimization

The below is still only a rough plan which we can refine over the coming weeks.

Date Topic Literature Speaker
  Generalities (geodesics on manifolds, geodesic convexity, examples & applications) 1806.06373, Udriste, AMS? Lukas
  First order algorithms 1602.06053 Harold
  More recent results 1804.10738, …?  
  Operator scaling and applications 1511.03730, 1710.02587, 2002.00071 Cole/Rafael?
  Algebraic algorithms for operator scaling 1512.03531, 1805.11245 Yinan
  Scaling algorithms and geodesic convex optimization 1910.12375 Michael
  Research discussion    

 

A scaling algorithm in action