Optimization I

on YouTube ↗01h 18m

" summary

Covers concrete algorithms and rates: plain gradient descent converges linearly at a rate governed by condition number κ (example κ≈100 needs ~40 steps), momentum (Polyak/“heavy ball”) cuts dependence to ~√κ (≈10× fewer steps), Nesterov acceleration achieves the provable optimal worst‑case rate (1/K^2 for convex), and stochastic gradient yields O(1/K) in expectation but is robust and disk‑friendly (used successfully for Netflix‑style matrix completion). Also shows constraints via proximal mapping (soft‑thresholding/L1 shrinkage) and simple projected steps; proofs reuse the same contraction/variance recursions.

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 1:20Optimization
3. 3:40Logistic Regression
4. 5:32L1 Norm
5. 8:03Why Optimization
6. 10:58Duality
7. 14:16Minimize
8. 16:57Contractility
9. 18:41Convexity
10. 22:15Line Search
11. 25:53Acceleration
12. 31:06Analysis
13. 37:45Extra Gradient
14. 47:26NonConcave
15. 49:30Stochastic Gradient
16. 54:03Robinson Munroe Example

" related talks

• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 42mOptimization Crash CourseAshia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral AlgorithmsLorenzo Orecchia · Fast Algorithms via Spectral Methods 2014
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 46mGradient Descent: The Ultimate OptimizerErik Meijer · KotlinConf 2019