Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching
summary
Introduces JacSketch, a variance-reduced stochastic optimizer that maintains cheap, sketched estimates of the full Jacobian and uses a sketch-and-project update plus a bias-correcting multiplier to produce an unbiased estimator of the gradient. Claims linear convergence (Lyapunov combining parameter error and Jacobian error), recovers SAGA as a special case (random column submatrix of the identity), improves mini-batch SAGA and importance-sampling bounds, resolves a conjecture about SAGA sampling, and shows faster practical per-epoch progress on ridge and logistic regression.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:42Outline
- 2:38Finite Sum Minimization Problem
- 4:18Stochastic Gradient Methods
- 5:42Variance Reduction
- 7:37Lift and Sketch
- 10:42Introducing General Sketches
- 14:10Sketch and Project
- 16:21Gradient Estimate
- 22:10Adding Control Variate to Reduce Variance
- 23:40Variance of the Stochastic Gradient
- 25:58First Main Result (Theorem 3.6)
- 28:35Minibatch Partition Sketch
- 29:39Ridge Regression
- 30:00Minibatch SAGA
- 30:23JacSketch vs Other Methods
related talks
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 03mSketching as a Tool for Numerical Linear Algebra
53mSketching and Projecting
01h 07mStochastic Second Order Optimization Methods I
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 04mSketching and Randomized Linear Algebra
33mStochastic Optimization for Big Data Machine Learning Problems
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II