DECOrrelated feature space partitioning for distributed sparse regression

Abstract

Fitting statistical models is computationally challenging when the sample size or the dimension of the dataset is huge. An attractive approach for down-scaling the problem size is to first partition the dataset into subsets and then fit using distributed algorithms. The dataset can be partitioned either horizontally (in the sample space) or vertically (in the feature space). While the majority of the literature focuses on sample space partitioning, feature space partitioning is more effective when $p\gg n$. Existing methods for partitioning features, however, are either vulnerable to high correlations or inefficient in reducing the model dimension. In this paper, we solve these problems through a new embarrassingly parallel framework named DECO for distributed variable selection and parameter estimation. In DECO, variables are first partitioned and allocated to $m$ distributed workers. The decorrelated subset data within each worker are then fitted via any algorithm designed for high-dimensional problems. We show that by incorporating the decorrelation step, DECO can achieve consistent variable selection and parameter estimation on each subset with (almost) no assumptions. In addition, the convergence rate is nearly minimax optimal for both sparse and weakly sparse models and does NOT depend on the partition number $m$. Extensive numerical experiments are provided to illustrate the performance of the new framework.

arXiv commentCorrect legend errors in Figure 3

References in corpus (8)

• Simultaneous analysis of Lasso and Dantzig selector
• Piecewise linear regularized solution paths
• Geometric median and robust estimation in Banach spaces
• Parallelizing MCMC via Weierstrass Sampler
• Complexity Analysis of the Lasso Regularization Path
• Parallelizing MCMC with Random Partition Trees
• Preconditioning to comply with the Irrepresentable Condition
• On the consistency theory of high dimensional variable screening

Cited by in corpus (7)

• Debiased distributed learning for sparse partial linear models in high dimensions
• High-dimensional variable selection via low-dimensional adaptive learning
• The Backbone Method for Ultra-High Dimensional Sparse Machine Learning
• Paired-move multiple-try stochastic search for Bayesian variable selection
• An Overview of Multi-Processor Approximate Message Passing
• Multiprocessor Approximate Message Passing with Column-Wise Partitioning
• Scalable Bayesian variable selection and model averaging under block orthogonal design