Non-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient Descent

on YouTube ↗13m

" summary

Proves that plain vanilla SGD—single-pass, unregularized, fixed step size—achieves nonparametric excess-risk bounds in infinite-dimensional linear/kernel regression where rates depend on two regularities: alpha_opt (target) and alpha_feat (features). Convergence shows a polynomial decay with exponent set by min(alpha_opt+1, alpha_feat) until a step size plateau where excess risk is proportional to the step size and the optimal risk. Kernel example gives best choice S = R and matches known minimax-style behaviors.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 1:20Linear regression
3. 2:58Complexity in RKHS
4. 4:53Non-parametric rates for ridge regression
5. 5:38Limitations of the previous analyses
6. 6:58Convergence rates under the noiseless assumption
7. 7:56Toy example: interpolation of a function in Sobolev spaces
8. 10:25Take-home message

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 05mNon-monotonic convergence of gradient descent with large stepsizeJingfeng Wu · 9th Annual Simons Institute Industry Day
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical PrecisionSham Kakade · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 23mImplicit Regularization IINati Srebro · Deep Learning Boot Camp 2019
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 29mImplicit Regularization in Nonconvex Statistical EstimationYuxin Chen · Optimization, Statistics and Uncertainty