# A Statistical Perspective on Algorithmic Leveraging

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2013.

## Built on by (most cited first, 30 of 39)

- [Towards a statistical theory of data selection under weak supervision](https://mlsanity.com/paper/2309.14563/) (2023)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [Model-adapted Fourier sampling for generative compressed sensing](https://mlsanity.com/paper/2310.04984/) (2023)
- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [One Backward from Ten Forward, Subsampling for Large-Scale Deep Learning](https://mlsanity.com/paper/2104.13114/) (2021)
- [An optimal transport approach for selecting a representative subsample with application in efficient kernel density estimation](https://mlsanity.com/paper/2206.01182/) (2022)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Optimal Sample Selection Through Uncertainty Estimation and Its Application in Deep Learning](https://mlsanity.com/paper/2309.02476/) (2023)
- [Model-free Subsampling Method Based on Uniform Designs](https://mlsanity.com/paper/2209.03617/) (2022)
- [Leverage Score Sampling for Complete Mode Coverage in Generative Adversarial Networks](https://mlsanity.com/paper/2104.02373/) (2021)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [General bounds on the quality of Bayesian coresets](https://mlsanity.com/paper/2405.11780/) (2024)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [NoisyCUR: An algorithm for two-cost budgeted matrix completion](https://mlsanity.com/paper/2104.08026/) (2021)
- [Deep Neural Network Based Accelerated Failure Time Models using Rank Loss](https://mlsanity.com/paper/2206.05974/) (2022)
- [Linear Discriminant Analysis with the Randomized Kaczmarz Method](https://mlsanity.com/paper/2211.05749/) (2022)
- [Statistical and Computational Guarantees for Influence Diagnostics](https://mlsanity.com/paper/2212.04014/) (2022)
- [Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data](https://mlsanity.com/paper/2303.08242/) (2023)
- [Efficient and Robust Bayesian Selection of Hyperparameters in Dimension Reduction for Visualization](https://mlsanity.com/paper/2306.00357/) (2023)
- [A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs](https://mlsanity.com/paper/2311.10610/) (2023)
- [Using Low-Discrepancy Points for Data Compression in Machine Learning: An Experimental Comparison](https://mlsanity.com/paper/2407.07450/) (2024)
- [Markov subsampling based Huber Criterion](https://mlsanity.com/paper/2112.06134/) (2021)
- [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024)
- [Online Algorithms with Limited Data Retention](https://mlsanity.com/paper/2404.10997/) (2024)
- [A model-free subdata selection method for classification](https://mlsanity.com/paper/2404.19127/) (2024)
- [Adaptive and Stratified Subsampling for High-Dimensional Robust Estimation](https://mlsanity.com/paper/2410.12367/) (2024)

## Abstract (arXiv)

One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method. In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling. Based on these theoretical results, we propose and analyze two new leveraging algorithms. A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical results indicate that our theory is a good predictor of practical performance of existing and new leverage-based algorithms and that the new algorithms achieve improved performance.