Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

on YouTube ↗30m

" summary

Introduces a concrete condition called relative Lipschitzness between operator G and regularizer R and proves that standard extragradient (Mirror Prox) achieves the usual 1/T and linear rates under this weaker, verifiable condition. Rewrites convex minimization as a Fenchel game, shows the RL constant is 1+√(L/μ) so extragradient recovers Nesterov’s √(L/μ) acceleration, and gives an expected RL and local variance reduction recipe that (a) makes stochastic 1/T rates possible and (b) recovers Schurman/Sherman area-convex maxflow analyses.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 0:22Outline
3. 2:18How to watch this talk
4. 3:31Vis in monotone operators
5. 5:48Algorithms for solving Vis
6. 9:46Proximal point: an idealized algorithm
7. 18:43A direct recipe for acceleration Goal minimize convex function : XR Assumptions gradient is L-Lipschitz, function is pl-strongly convex (Euclidean norm)
8. 21:46Relative Lipschitzness for the Fenchel game
9. 24:17More applications!