Optimization Crash Course (continued)

on YouTube ↗01h 07m

" summary

Discrete acceleration closes the classic GD vs lower‑bound gap to a √κ dependence (Polyak/Nesterov ODE viewpoint and energy/Lyapunov proofs) but needs knowledge of L and µ or uses adaptive restarting to avoid destructive oscillation. For large sums, SVRG and SAGA trade memory or occasional full gradients to achieve an n+κ oracle complexity (vs SGD’s n‑independent 1/√K or strongly‑convex κ/K bounds), and Catalyst can inject momentum to recover √κ speedups. Mirror descent is natural gradient on a Hessian manifold using Bregman projections; choosing the right geometry (entropy on the simplex) yields dramatically faster LP/robust‑regression solves.

AI-written summary · about

" chapters (31)

1. 0:00Optimization recap
2. 1:09Acceleration concepts
3. 3:47Nesterov's acceleration
4. 6:18Acceleration frameworks
5. 8:25Algebraic construction
6. 11:19Rates of convergence
7. 15:04Universal acceleration
8. 16:23ODE perspective
9. 19:00Stochastic methods
10. 20:54SGD performance
11. 22:34Accelerating SGD
12. 23:35Variance reduction
13. 25:47SVRG and SAGA details
14. 29:01Practical performance
15. 30:07Accelerated SGD
16. 32:23Accelerated plots and robust
17. 34:43Manifold optimization
18. 36:57Tangent spaces
19. 39:13Hessian manifolds
20. 41:04Gradients and flow
21. 42:55Natural gradient descent
22. 44:51Mirror descent introduction
23. 47:11Mirror descent derivation
24. 48:55Discretizing mirror descent
25. 50:52Mirror descent vs SGD
26. 53:20Bregman distances
27. 55:49Proximal Bregman method
28. 57:37Bregman projections
29. 59:31Projected mirror descent
30. 1:01:57Geometry impact
31. 1:03:37Q&A and conclusion

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 33mStochastic Optimization for Big Data Machine Learning ProblemsTong Zhang · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 04mOptimization for Machine Learning IIElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral AlgorithmsLorenzo Orecchia · Fast Algorithms via Spectral Methods 2014
• 46mGradient Descent: The Ultimate OptimizerErik Meijer · KotlinConf 2019