Proximal SCOPE for Distributed Sparse Learning
Distributed sparse learning with a cluster of multiple machines has attracted much attention in machine learning, especially for large-scale applications with high-dimensional data. One popular way to implement sparse learning is to use L 1 regularization. In this paper, we propose a novel method, called proximal SCOPE (pSCOPE), for distributed sparse learning with L 1 regularization. pSCOPE is based on a cooperative autonomous local learning (CALL) framework. In the CALL framework of pSCOPE, we find that the data partition affects the convergence of the learning procedure, and subsequently we define a metric to measure the goodness of a data partition. Based on the defined metric, we theoretically prove that pSCOPE is convergent with a linear convergence rate if the data partition is good enough. We also prove that better data partition implies faster convergence rate. Furthermore, pSCOPE is also communication efficient. Experimental results on real data sets show that pSCOPE can outperform other state-of-the-art distributed methods for sparse learning.
This paper mainly focused on solving regularized finite-sum problem in distributed setting. The first contribution is that it developed pSCOPE, which is an improvement over an existing SCOPE by combining proximal mapping to deal with non-smooth regularization term. Then a new measure to determine the quality of data partition is introduced, and the convergence of pSCOPE is analyzed with this measure. Furthermore, a trick for dealing with sparse data efficiently for pSCOPE is also proposed. Finally, some numerical comparisons were conducted to show the efficiency of pSCOPE method.  I do not think turning an existing method SCOPE into the proximal version is quite interesting or has great contribution. Though the authors listed several differences between SCOPE and pSCOPE, I still think these differences are tiny. On the other hand, I personally prefer the part about how to measure the quality of data partition and how it affects convergence rate, which should be novel. However, it is pity that such theory was not be utilized to guide the data partition in the paper.  The convergence rate is in fact poor, which has a quadratic dependence on the condition number. I do not agree this quadratic dependence is due to distributed computation. The effect of distribution should be reflected through $\xi$ instead of $\kappa$ (note that even for p=1, you still have $\kappa^2$). While most SVRG variants, no matter distributed or non-distributed, do have linear dependence on condition number.   Some experiment results look strange for me. But the convergence behavior of the baselines in some figures are really weird. Some of them seem not convergent at all. I am not challenging authors’ experiment here. I sincerely suggest the authors can recheck their experiments carefully, especially the implementation of these baselines.  There also exist several formatting issues in the paper. For example, the math equation should be more professional, especially the proximal mapping operator. And The figures are really too small for publishing.  I believe in line 162 that the square of the norm is missing.  Based on the above facts, I mainly remain neutral but slightly tent to accept this paper.   *********************************************************************** I have read authors’ feedback. The explanation to why the convergence has quadratic dependence on condition number is reasonable now. However, I still prefer a bound with linear dependence on condition number, since in most applications we do have individual convexity. Hence, I do not plan to change the score.