Parallel Coordinate Descent Methods for Big Data Optimization
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Presents a concrete parallel coordinate-descent framework built around an ESO (expected separable over-approximation) that produces algorithm parameters beta and W, shows beta scales with data sparsity (omega) and update batch size (tau), and gives a distributed implementation called Hydra. Proves iteration bounds ~beta·N/(tau·C), demonstrates nearly linear speedups on sparse problems (24 cores → ~20× faster), and solves a 3 TB LASSO instance with 512 MPI processes on 128 nodes in roughly 15–20 minutes.
AI-written summary · about
chapters (26)
- 0:00Intro
- 1:482D Optimization
- 4:45Convergence of Randomized Coordinate Descent
- 5:49Parallelization Dream
- 7:18"Naive" parallelization
- 9:05Failure of naive parallelization
- 13:14Problem
- 13:45Regularizer: examples
- 14:12Loss: examples
- 15:243 models for f with small B
- 20:16Randomized Parallel Coordinate Descent Method
- 22:05ESO: Expected Separable Overapproximation
- 24:57Convergence rate: convex f
- 27:08Serial uniform sampling
- 33:41Theoretical speedup
- 36:24Practice
- 37:08Optimization with Big Data
- 37:30Coordinate Updates
- 38:46Wall Time
- 39:50Distributed T-nice sampling
- 42:26ESO: Distributed setting
- 43:53Bad partitioning at most doubles # of iterations
- 46:14LASSO with a 3TB data matrix
- 47:41Conclusions
- 48:19References: serial coordinate descent
- 48:45References: parallel coordinate descent
related talks
01h 05mTutorial: Federated Optimization, Part III
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
01h 18mOptimization I
17mZEN: Empowering Distributed Training with Sparsity-driven Data Synchronization
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
18m(De/Re)-Composition of Data-Parallel Computations via Multi-Dimensional(…)
51mExploiting Similarity in Federated Learning
31mNearest Neighbor Based Greedy Coordinate Descent