Optimization Crash Course

on YouTube ↗42m

" summary

Crash course gives concrete guarantees: first/second-order oracle models, step size ≤ 1/L for gradient steps, and a three-line Lyapunov-style proof that function gap decreases for L-smooth convex f. It shows projected and proximal mappings preserve convergence, presents cubic-regularized Newton as a practical second-order tool, and exhibits a tri-diagonal quadratic worst-case that yields a provable 1/K^2 lower bound and explains the resulting square-root condition number gap motivating acceleration and stochastic variants.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 2:50Topics
3. 6:40Motivation
4. 10:05Algorithms
5. 16:41Convexity
6. 20:58Optimality
7. 30:00Projections
8. 35:22Lower Bounds
9. 36:04Explicit Example
10. 38:40Algebra
11. 39:20Quadratic
12. 40:15Gradient Descent

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 58mContinuous Methods 2Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 07mStochastic Second Order Optimization Methods IFred Roosta · Foundations of Data Science Boot Camp 2018
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral AlgorithmsLorenzo Orecchia · Fast Algorithms via Spectral Methods 2014