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 gradient- based 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.
