# Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares

arXiv: https://arxiv.org/abs/1803.00841 · HTML: https://mlsanity.com/paper/1803.00841/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2018.

## Built on by (most cited first, 8 of 8)

- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [TASER: Temporal Adaptive Sampling for Fast and Accurate Dynamic Graph Representation Learning](https://mlsanity.com/paper/2402.05396/) (2024)
- [Gradient Shaping Beyond Clipping: A Functional Perspective on Update Magnitude Control](https://mlsanity.com/paper/2510.01578/) (2025)
- [Markov subsampling based Huber Criterion](https://mlsanity.com/paper/2112.06134/) (2021)
- [Online Algorithms with Limited Data Retention](https://mlsanity.com/paper/2404.10997/) (2024)
- [Gradient-based Sample Selection for Faster Bayesian Optimization](https://mlsanity.com/paper/2504.07742/) (2025)
- [ASSS: A Differentiable Adversarial Framework for Task-Aware Data Reduction](https://mlsanity.com/paper/2601.02081/) (2026)

## Abstract (arXiv)

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.