What (Doesn't) Make Learning Algorithms Generalize?

on YouTube ↗42m

" summary

Shows that empirical risk minimization needs dimension-dependent samples (at least log D) while adding regularization yields 1/ε^2 sample complexity for stochastic convex optimization; full gradient descent can require m^2 steps to be stable and generalize, but stochastic gradient descent generalizes with only m steps despite producing predictors that fail conventional simplicity or stability tests. Proofs use a max-coordinate construction and assume a first-order oracle (value and gradient) to build explicit counterexamples and bounds.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:21Hardness of learning
3. 2:55Common practice in machine learning
4. 9:00Resolving Conundrum: Non uniform rates
5. 10:35Example: Linear optimization
6. 15:03Stochastic Convex Optimization as a case study
7. 23:21Case Study1: Gradient Descent
8. 26:35Implicit regularization?
9. 28:19Case Study1.5: Regularized Gradient Descent
10. 29:36Case Study 1.75: Any type regularized GD?
11. 30:22Proof idea of ALK'21
12. 31:41Case Study2: Stochastic Gradient Descent
13. 33:05Proof (ignoring projections)
14. 36:50SGD doesn't minimize the empirical risk

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical PrecisionSham Kakade · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 03mOverview of Statistical Learning Theory Part 2Nati Srebro · Modern Paradigms in Generalization Boot Camp 2024
• 01h 05mOptimization for Machine Learning IElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 01h 02mPrediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 2Ryan Tibshirani · Modern Paradigms in Generalization Boot Camp 2024