Stochastic Optimization for Big Data Machine Learning Problems
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Claims that SVRG and SDCA fix SGD by eliminating gradient variance and deliver linear convergence while touching one example per iteration, so per-iteration cost stays cheap. Algorithms prove complexity roughly N + κ rather than N·κ, giving large-N speedups. Mini-batch with acceleration yields near-linear processor scaling until batch approaches N. A parallel SVRG variant coordinates only a few global epochs (convex ~2, nonconvex ~5) to synchronize W̃ and preserves fast convergence in practice. variance reduction is the core technique enabling these gains.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:31Outline
- 1:24Mathematical Problem
- 2:16Optimization Problem Complexity
- 3:50Batch Optimization Method: Gradient Descent
- 5:17Stochastic Approximate Gradient Computation
- 7:30SGD versus GD
- 10:39Improving SGD via variance reduction
- 12:32Stochastic Variance Reduced Gradient (SVRG)
- 17:22SVRG: variance
- 17:52SVRG: convergence
- 21:51Benefit of SDCA
- 22:37Parallelization: MiniBatch SDCA
- 25:11Example: MiniBatch SDCA with Acceleration
- 26:58From Synchronized update to Loose Synchronization
- 28:28Improvement
- 28:57Distribution Scheme
- 29:08Distributed SVRG
- 30:39Summary
related talks
01h 07mOptimization Crash Course (continued)
58mFirst-Order Stochastic Optimization
01h 18mOptimization I
33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision
01h 04mOptimization for Machine Learning II
01h 01mRobustness, Stochastics, Uncertainty 2
01h 12mStochastic Second Order Optimization Methods II
36mA Generalization Bound for Online Variational Inference