DECOrrelated feature space partitioning for distributed sparse regression
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 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.
The paper presents a feature-wise partitioning approach for distributed sparse regression. Unfortunately, the results are rather incremental for the level of NIPS, as the result only holds for random design matrices, and the paper in its current form lacks discussion of several lines of related work and experimental baselines.
The paper presents a feature-wise partitioning approach for distributed sparse regression. Unfortunately, the results are rather incremental for the level of NIPS, as the result only holds for random design matrices, and the paper in its current form lacks discussion of several lines of related work and experimental baselines.  While I do definitely like the conceptual idea of the partitioning followed by de-correlation, the presented theory falls short of expectations as it only holds for random design matrices.  The paper however does not clearly explain the novelty and differences over [9]. Also, in addition to [9], relations to related work [B,C] are not sufficiently discussed in the current version. Almost matching upper and lower bounds for the amount of communication are in the meantime well-studied [C]. The approach presented here needs to be set into this relevant context as well.  Clarity of presentation can be improved.  The presented experiments are comprehensive in terms of datasets used, however not comprehensive in term of competing algorithms (many distributed solvers for L1 exist and the most prominent ones should be included in the comparison).    MINOR: - abstract, line 6 "feature space partitioning is more effective when p >> n". This should be supported by a result. Might need to tune down, as most algorithms scale with p*n no matter which of the two possible partitionings is chosen. - conditional number -> condition number      REFERENCES:   [A] Arjevani, Y., & Shamir, O. (2015). Communication Complexity of Distributed Convex Learning and Optimization (pp. 1747–1755). NIPS 2015 - Advances in Neural Information Processing Systems 28.  [B] Heinze, C., McWilliams, B., & Meinshausen, N. (2016). DUAL-LOCO: Distributing Statistical Estimation Using Random Projections (pp. 875–883). Presented at the AISTATS - Proceedings of the th International Conference on Artificial Intelligence and Statistics.  [C] McWilliams, B., Heinze, C., Meinshausen, N., & Krummenacher, G. (2014). LOCO: Distributing Ridge Regression with Random Projections. arXiv   UPDATE AFTER REBUTTAL: I thank the authors for clarifying the relation of the idea to [B,C]. I believe the authors can strengthen the paper for a future submission along the lines suggested.