Continuous Methods 1

on YouTube ↗01h 02m

" summary

Asserts that designing first-order algorithms from continuous dynamics plus conjugate duality yields a mechanical recipe: pick mirror map via conjugate, maintain primal/dual averages, preserve an alpha(t)·gap invariant, then discretize. Builds the continuous ODE, uses forward Euler to discretize, and recovers Frank–Wolfe: linear oracle + gradient yields O(L·diameter^2/ε) iterations because discretization error on the smooth term dominates. Notes acceleration requires different discretization (approximate backward Euler) and the method matches known rates.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 4:53Gradient Flow
3. 12:07Algorithm
4. 25:07Composite Optimization
5. 33:37Upper Bounds
6. 36:57Lower Bounds
7. 40:52Dual Objective
8. 44:48Raft
9. 54:36Practice
10. 58:19Smoothness

" related talks

• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 01h 03mSampling Crash CourseAndreas Eberle · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...Ermin Wei · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 42mOptimization Crash CourseAshia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 34mFast Algorithms for Multivariate ODEs arising in Sampling and LearningSantosh Vempala · Randomized Numerical Linear Algebra and Applications 2018
• 01h 31mIncremental Approximate Message PassingAhmed El Alaoui · Computational Phase Transitions (Simons Institute, 2020)