LOCO: Distributing Ridge Regression with Random Projections

2014/06/13 by Christina Heinze, Heinze, Christina, Brian McWilliams +5
Mathematics · #FOS: Computer and information sciences #Machine Learning (stat.ML) #stat.ML

paper · pdf · doi:10.48550/arxiv.1406.3469

37 pages

arxiv created 2015/06/08 · arxiv updated 2015/06/09

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.

Related

• WONDER: Weighted one-shot distributed ridge regression in high dimensions
• ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
• Random Projections For Large-Scale Regression
• Fast Ridge Regression with Randomized Principal Component Analysis and Gradient Descent
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates