Continuous Methods 2
summary
Claims that continuous-time gap invariants plus two discretization recipes produce accelerated O(1/T^2) convergence for convex problems, with concrete algorithms: a Nesterov "trick" (explicit forward step plus a corrective gradient step) and a midpoint / backward Euler approximation (implicit-like discretization via one iterative correction). Shows how a time-varying mirror regularizer (a homotopy smoothing / regularizer) handles nonsmooth objectives, and reports a surprising application: a positive packing LP solver whose iteration count becomes independent of the magnitude of matrix entries.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:00Primal averaging
- 1:50Nonsmooth gradient
- 3:40Gradient descent
- 4:55Dual averaging
- 22:12Dynamic acceleration
- 24:28Nesterov
- 28:42Ramirez
- 32:04Backward Euler
- 35:34Open Questions
- 42:04Discretization
- 50:29Composite Optimization
related talks
01h 18mOptimization I
42mOptimization Crash Course
27mTalk by Ali Kavis (UT Austin)
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 07mOptimization Crash Course (continued)
46mSmooth Nonconvex Min-Max Optimization
28mStability and Convergence Trade-Off of Iterative Optimization Algorithms
01h 04mLast-Iterate Convergence in Constrained Min-Max Optimization: SOS to the Rescue