The Initial Search Phase Of Stochastic Gradient Descent For High-Dimensional Inference Tasks

on YouTube ↗30m

" summary

Classifies how much data and time online SGD needs to escape the small‑correlation saddle at the origin: define an information exponent K (first nonzero derivative of the population loss at 0); K=1 gives linear‑time escape, K=2 requires about N log N steps and a logarithmic sample factor, K≥3 produces polynomially long escape times and polynomial sample complexity; analysis uses population ODEs plus perturbative stochastic corrections for SGD under Gaussian‑style noise scaling.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:28Parameter estimation in high dimensions Parametric family of probability distributions Polan
3. 2:42Risk minimization and gradient methods
4. 4:52Some approaches to this problem
5. 9:26First-order methods for parameter estimation
6. 11:28The population dynamics Population dynamics (gradient descent)
7. 13:45Example population losses
8. 15:09Assumption on the size of the noise
9. 16:25Examples falling into this general framework
10. 17:16Stochastic approximation, and limiting ODE approach
11. 18:51The descent phase: where low-dimensional intuition applies
12. 20:17Before the descent phase
13. 20:53The initial search phase: classifying the saddle point
14. 22:32Information exponents for our examples
15. 23:01Computational difficulty of leaving the search phase
16. 24:42Sensitivity to the initialization

" related talks

• 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
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 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