Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints

on YouTube ↗01h 10m

" summary

Claims that optimization algorithms map to a linear dynamical plant plus a nonlinear gradient block and that stability/rate can be certified by searching for Lyapunov functions via integral quadratic constraints leading to small semidefinite programs. Implements an off-by-one IQC to certify Nesterov‑style accelerated rates (within a constant) by solving tiny LMIs; heavy‑ball shows a surprising limit — a simple 1D counterexample with condition number ~16 produces a limit cycle so it fails certification. Also runs grid synthesis (Julia) to produce noise‑robust accelerated updates.

AI-written summary · about

" chapters (19)

1. 0:00Introduction
2. 0:26Controls and optimization
3. 2:20Controls for optimization
4. 3:59First order methods
5. 7:20Acceleration methods
6. 10:20Nesterov's method
7. 13:03Control theory framework
8. 17:08Modeling algorithms as systems
9. 22:47Analyzing convergence
10. 24:49Linear matrix inequalities
11. 29:40General convex functions
12. 34:53Integral quadratic constraints
13. 38:55Sufficient conditions
14. 41:51Sector inequality proof
15. 44:18Method comparison
16. 49:28Off-by-one IQCs
17. 55:40Heavy ball instability
18. 58:57Synthesis and future work
19. 1:02:53Q&A session

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 41mCompetitive Algorithms for Online ControlYisong Yue · Mathematics of Online Decision Making 2020
• 01h 28mFollow the gradient: an introduction to mathematical optimisationGianluca Campanella · PyData London 2018
• 42mOptimization Crash CourseAshia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 39mPractical Optimization for Stats NerdsRyan J. O'Neil · PyData Seattle 2017
• 51mAre Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?Niao He · Adversarial Approaches in Machine Learning 2022