Tradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision

on YouTube ↗33m

" summary

Claims an algorithm based on variance-reduced gradient ideas drives the excess risk to the empirical-risk-minimizer rate sigma^2/n while using one-pass streaming access and O(1) memory per sample. Method alternates cheap correction updates with occasional larger gradient estimates whose sample size doubles, killing initial error quickly, is trivially parallelizable, and avoids dimension/condition-number blowup. Targets linear, logistic and other GLMs; theoretical guarantees show constant-factor optimality, practical tuning is robust though no large-scale benchmarks are given.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:09Statistical estimation involves optimization
3. 2:09Statistics vs. Computation
4. 3:00Machine learning at scale!
5. 5:35The Stochastic Optimization Problem
6. 7:40Without Computational Constraints...
7. 12:34Outline
8. 13:05(just) Statistics
9. 15:11(just) Computation
10. 16:50Stochastic Gradient Descent (SGD)
11. 19:32Stochastic Variance Reduced Gradient (SVRG)
12. 25:28Computation + Statistics
13. 28:09Single Pass Least Squares Estimation

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 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)
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 01h 05mOptimization for Machine Learning IElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 01h 04mOptimization for Machine Learning IIElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 01h 07mLarge-Scale Private Learning, Part IIKunal Talwar · Data Privacy: Foundations and Applications Boot Camp