LOCO: Distributing Ridge Regression with Random Projections. arXiv stat.ML

We propose LOCO, a distributed algorithm which solves large-scale ridge reg-ression. LOCO randomly assigns variables to different processing units which do not communicate. Important dependencies between variables are preserved us-ing random projections which are cheap to compute. We show that LOCO has bounded approximation error compared to the exact ridge regression solution in the fixed design setting. Experimentally, in addition to obtaining significant speedups LOCO achieves good predictive accuracy on a variety of large-scale reg-ression problems. Notably LOCO is able to solve a regression problem with 5 billion non-zeros distributed across 128 workers in 25 seconds.