Optimization for Machine Learning I

on YouTube ↗01h 05m

" summary

Casts learning as optimization over parameters and proves convex relaxations let local gradient info give global guarantees; uses stochastic gradient descent (one-sample updates) derived from follow-the-regularized-leader and shows expected error/regret scales as 1/sqrt(T), so epsilon accuracy needs O(1/epsilon^2) iterations. Presents FTRL/entropy and Euclidean regularizers (recovering multiplicative weights and GD), explains AdaGrad’s adaptive matrices for sparse data and claims instance-dependent √d improvements in regret.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 3:15Mathematical optimization
3. 5:03Learning - optimization over data laka. Empirical Risk Minimization
4. 7:02Example: linear classification
5. 11:29Convexity
6. 14:11Convex relaxations for linear & kernel
7. 16:16Gradient descent, constrained set
8. 17:50Convergence of gradient descent
9. 24:43Gradient Descent -caveat
10. 27:17Statistical (PAC) learning
11. 32:33Online gradient descent Zinkevich '05
12. 34:31More powerful setting: Online Learning in Games
13. 37:19Analysis
14. 39:18Lower bound
15. 45:10Stochastic gradient descent
16. 47:38Stochastic vs. full gradient descent
17. 53:24Minimize regret: best-in-hindsight
18. 56:30Fixing FTL: Follow-The-Regularized-Leader (FTRL)

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 23mImplicit Regularization IINati Srebro · Deep Learning Boot Camp 2019
• 01h 01mOptimization's Untold Gift to Learning: Implicit RegularizationNathan Srebro Bartom · Optimization, Statistics and Uncertainty
• 01h 03mOverview of Statistical Learning Theory Part 2Nati Srebro · Modern Paradigms in Generalization Boot Camp 2024
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical PrecisionSham Kakade · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp