Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares
This work addresses computational bottlenecks in large-scale data analysis for researchers and practitioners, but it is incremental as it builds on prior importance sampling techniques.
The paper tackles the problem of efficiently solving least-squares problems with large datasets by proposing gradient-based sampling, which adaptively selects data points based on both input and output variables, resulting in improved statistical efficiency and computational savings compared to existing methods.
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.