First-Order Stochastic Optimization

on YouTube ↗58m

" summary

Proves that under smooth, (strongly) convex finite-sum assumptions SGD with a constant step size < 1/L converges exponentially to a neighborhood whose radius depends on per-component gradient variance, and that importance sampling by Lipschitz weights (row-norm squared for linear problems) can cut required iterations by up to factor n in worst cases; shows experiments match theory and points to AdaGrad-style adaptive learning rates to avoid hand-tuning step sizes.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 3:20Support Vector Machine
3. 4:55Deep Learning
4. 8:26Gradient Descent
5. 25:55Questions
6. 29:10Theorem
7. 33:40Proof
8. 39:00Important Sampling
9. 42:36Convergence Rate
10. 44:40Adaptive Learning
11. 52:38Dynamic Updates

" related talks

• 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
• 01h 04mOptimization for Machine Learning IIElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 47mThe Importance of Better Models in Stochastic Optimization...John Duchi · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 33mStochastic Optimization for Big Data Machine Learning ProblemsTong Zhang · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017