Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares
In modern data analysis, random sampling is an efficient and widely-used strategy to overcome the computational difficulties brought by large sample size. In previous studies, researchers conducted random sampling which is according to the input data but independent on the response variable, however the response variable may also be informative for sampling. In this paper we propose an adaptive sampling called the gradient-based sampling which is dependent on both the input data and the output for fast solving of least-square (LS) problems. We draw the data points by random sampling from the full data according to their gradient values. This sampling is computationally saving, since the running time of computing the sampling probabilities is reduced to O(nd) where n is the full sample size and d is the dimension of the input. Theoretically, we establish an error bound analysis of the general importance sampling with respect to LS solution from full data. The result establishes an improved performance of the use of our gradientbased sampling. Synthetic and real data sets are used to empirically argue that the gradient-based sampling has an obvious advantage over existing sampling methods from two aspects of statistical efficiency and computational saving.
The authors propose a sub-sampling algorithm for least squares regression, where the weights depend on the magnitude of the gradient. They argue that by using these weights, rather than uniform weights or weights based on leverage, the resulting regression estimates are more accurate. They bound the error of the resulting regression coefficients and they show that their method is optimal, in the sense that it minimizes a constant. They illustrate the performance of the method using a simulated example and two real datasets. 
I don't think that the paper provides convincing arguments as to why using the gradient to determine the sub-sampling probabilities is a good idea. In particular, I worry that selecting mostly points characterised by big residuals will lead to un-robust  regression estimates. In addition, are the weights invariant to the scale of the covariates? The quadratic form used to calculate the leverage is invariant, but I don't think that the gradient is. Hence, the results might depend on the scale used.  Looking at Example 1: notice that the errors are homoscedastic here. I guess that under  heteroscedasticity gradient-based sampling would do quite badly. Under heteroscedasticity one typically wants to down-weight observations where the variance is large. On the contrary, gradient-based sampling will give large weights to these points, because they have big residuals. This issue should be particularly problematic when the number of sub-samples (r) is small. Hence, before using the proposed strategy one has to be quite sure that the errors are homoscedastic.  The title might be a bit misleading at the moment: I don't see in which sense the proposed approach is adaptive and I also don't see where the importance sampling part comes from (there seems to be no notion of an importance and a target distribution here). I would say that the paper focuses simply on gradient-based sub-sampling.  In Theorem 1: I find a bit puzzling that if we plug r = n in formula (6) we do not get zero that the error is zero, as we should.   In Section 5.1. How large is d here? The number of covariates is not reported.  MINOR POINTS:  L 15: "has obvious advantage" use either "has obvious advantages" or "has an obvious advantage".  L18: "Modern data analysis always meets enormous data sets in recent years." maybe "meets" is not the correct word here.   L22: "uniform sampling is simple but trivial way" maybe better "uniform sampling is a simple but trivial way".  L28-29: "Another shortcoming is that it needs to cost much time" better "Another shortcoming is that it costs much time".  L46: "we establishes"  L64: "with d-dimensional predictors" here there are d predictors, but they are not d-dimensional  L114: "and argue that choosing the initial size of r 0 to get a pilot estimate may not be careful" do you mean that one does not need to be careful when choosing r0?  L116: Poisson should be have capital P.  L128: ", we do simulation studies and command that it is an efficient sampling method from the algorithmic perspective." maybe you mean "find" rather than "command".  L211: "we compare the performance of various sampling on two" add "algorithms" after "sampling".  Table 3: what are the TS-PS entries in the CASP table?  L223: "which supply a rationality for the algorithm" maybe "justification" rather than "rationality". Also, "supplies" rather than "supply".  L225: "since the gradient-based sampling algorithm is implied without linear model assumption" maybe "justified" rather than "implied"  L231: "since gradient is considered a steepest way to go to the (local) optima." This sentence needs to be re-written.  L231: "optimzation".  L231: "Thus, applying this idea into other" use "to" rather than "into".