Reading group: From Euclidean to Geodesic Convex Optimization
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
|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|
Part 2: Geodesic convex optimization
The below is still only a rough plan which we can refine over the coming weeks.
|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|