LOCO: Distributing Ridge Regression with Random Projections

Abstract

We propose LOCO, an algorithm for large-scale ridge regression which distributes the features across workers on a cluster. Important dependencies between variables are preserved using structured random projections which are cheap to compute and must only be communicated once. We show that LOCO obtains a solution which is close to the exact ridge regression solution in the fixed design setting. We verify this experimentally in a simulation study as well as an application to climate prediction. Furthermore, we show that LOCO achieves significant speedups compared with a state-of-the-art distributed algorithm on a large-scale regression problem.

37 pages

References in corpus (4)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Distributed Coordinate Descent Method for Learning with Big Data

Cited by in corpus (5)

• Adding vs. Averaging in Distributed Primal-Dual Optimization
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Localized sketching for matrix multiplication and ridge regression
• Streaming regularization parameter selection via stochastic gradient descent
• Adaptive regularization for Lasso models in the context of non-stationary data streams