DUAL-LOCO: Distributing Statistical Estimation Using Random Projections
arXiv:1506.02554
Abstract
We present DUAL-LOCO, a communication-efficient algorithm for distributed statistical estimation. DUAL-LOCO assumes that the data is distributed according to the features rather than the samples. It requires only a single round of communication where low-dimensional random projections are used to approximate the dependences between features available to different workers. We show that DUAL-LOCO has bounded approximation error which only depends weakly on the number of workers. We compare DUAL-LOCO against a state-of-the-art distributed optimization method on a variety of real world datasets and show that it obtains better speedups while retaining good accuracy.
arXiv comment13 pages
References in corpus (5)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
- Randomized algorithms for matrices and data
- Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
- Improved matrix algorithms via the Subsampled Randomized Hadamard Transform