Feature-distributed sparse regression: a screen-and-clean approach
Most existing approaches to distributed sparse regression assume the data is partitioned by samples. However, for high-dimensional data (D N ), it is more natural to partition the data by features. We propose an algorithm to distributed sparse regression when the data is partitioned by features rather than samples. Our approach allows the user to tailor our general method to various distributed computing platforms by trading-off the total amount of data (in bits) sent over the communication network and the number of rounds of communication. We show that an implementation of our approach is capable of solving 1 -regularized 2 regression problems with millions of features in minutes.
The authors present an approach to distributed sparse regression based on sketching. The proposed method partitions the, high-dimensional, data rather than samples.   The proposed method uses a two-step process called screening and cleaning. In the screening step, the overall number of features is reduced to d=O(N), where N is the number of samples, by removing irrelevant features. By using a screening method that has the sure screening property the authors ensure that relevant features are not removed.  In the cleaning step the reduced regression problem is solved iteratively via a series of regularized quadratic programs (line 96). At each iteration, the current estimate \hat{y} is computed in a distributed manner, each node then sends to the central machine the correlations of the sketched features with current estimate \hat{y}. The central machine then updates the estimate of the regression coefficients \beta. This iterative process terminates after a predetermined number of iterations.  The authors provide a theoretical analysis of the distributed algorithm showing that the prediction error of \beta convergences q-linearly to that of the lasso estimator. The authors further show that the number of iterations of the cleaning stage required to produce an iterate with a prediction error smaller than \epsilon depends on the sketch size n. As the communication costs of the proposed method also depend on n, the authors show that there is a trade-off between "the total rounds of communication with the total amount of data (in bits) sent over the network".  
I find the work very interesting and of high quality. I would agree with the motivation put forward by the authors that data split by features rather than samples is an interesting setting to explore in cases where the data is high-dimensional.    What is not entirely clear is the exact contribution of the paper hence my low score on question 6.  Reading Pilanci and Wainwright's JMLR paper it would seem that the cleaning stage of this work is very close to being an application of the algorithm proposed there (Iterative Hessian Sketching) to a distributed setting. The authors point out some points of difference, lines 52-55, but I am not convinced that these really constitute a novel contribution. I hope the authors can elaborate further on this point. What are the practical differences of applying the proposed method as opposed to IHS, are there tangible advantages to using the proposed method? Obviously IHS would incur a much greater communication cost for the same number of iterations. However how is convergence affected in this case?