When dealing with massive datasets, traditional matrix algorithms quickly become computational bottlenecks. A common remedy is to sample a small subset of rows, columns, or features to construct a compressed "sketch" of the data. However, uniform random sampling often fails catastrophically: if a dataset contains a few highly influential data points or unique feature directions, uniform sampling is likely to miss them entirely, destroying the geometric structure of the problem.
Leverage score sampling solves this by providing a principled, data-dependent framework for importance sampling. By biasing selection toward the most structurally significant elements, it allows us to drastically reduce data dimensionality while maintaining provable accuracy guarantees.
The Geometry of Influence
To understand why leverage score sampling works, consider a large matrix $A$. We want to select a small subset of its rows to approximate the full matrix. Geometrically, the rows of $A$ span a vector subspace. If a particular direction in this subspace is only represented by a single row, dropping that row means losing that entire dimension of the data.
The statistical leverage score of a row measures its alignment with the principal components of the matrix. A high leverage score indicates that the row is highly unique or an outlier in the feature space, meaning it exerts significant influence over the matrix's overall structure. Conversely, if many rows are redundant, their individual leverage scores will be low.
As Michael W. Mahoney shows in Randomized algorithms for matrices and data, sampling rows or columns proportional to these leverage scores acts as an automated uniqueness filter. It guarantees that rare but critical directions are preserved with high probability, while highly redundant data points are downsampled. To ensure the final estimate remains unbiased, the selected rows are reweighted inversely proportional to their sampling probabilities. This core mechanism underpins data compression techniques like the Tensor-CUR decomposition introduced by Michael W. Mahoney et al., which extracts actual, highly informative slices of a tensor to preserve human-readable context.
Scaling Kernel Methods and Random Features
The utility of leverage scores extends beyond standard matrix algebra into infinite-dimensional spaces, such as kernel methods. Kernel Ridge Regression (KRR) and Kernel K-Means are powerful but suffer from a notorious $O(n^3)$ computational wall. Two popular scaling techniques—Random Fourier Features (RFF) and Nyström landmark selection—traditionally rely on uniform sampling, which can be highly inefficient.
Data-dependent sampling fundamentally changes this efficiency bound. Alessandro Rudi et al. demonstrate that sampling random features according to a distribution informed by leverage scores drastically reduces the number of features needed to achieve optimal generalization error, breaking the classical requirement where the number of features must scale linearly with the dataset size. Similarly, Haim Avron et al. show that modifying the sampling distribution to prioritize specific frequency ranges based on data geometry optimizes Gaussian kernel approximations.
For Nyström approximations, where a subset of "landmark" points is chosen to represent the kernel matrix, leverage scores are even more critical. Jian Li et al. prove that while uniform sampling suffices for simple scenarios, leverage score sampling is a theoretical necessity to guarantee minimax optimal convergence rates in agnostic learning settings—where the true target function lies outside the model's native hypothesis space. By utilizing Ridge Leverage Scores—a regularized variant of leverage scores—Daniele Calandriello demonstrates in Statistical and Computational Trade-Offs in Kernel K-Means that non-linear clustering can achieve exact statistical accuracy using only a fraction of the full kernel matrix.
Accelerating Optimization and Regression
Leverage score sampling also serves as a powerful tool for accelerating optimization algorithms. In large-scale empirical risk minimization (ERM) and least-squares regression, computing gradients or Hessians over millions of samples is prohibitively expensive.
By constructing a smaller, representative matrix via leverage score sampling, Naman Agarwal et al. combine importance sampling with accelerated coordinate descent. This shifts the computational complexity of regression from a dependency on the number of samples ($n$) to a dependency on the number of features ($d$), providing massive speedups for overdetermined systems.
For second-order optimization methods that require computing the Hessian matrix, Michal Derezinski et al. introduce Newton-LESS. This algorithm uses "LEverage Score Sparsified" embeddings to compress the Hessian sketch. Because leverage scores preserve the most informative rows, the resulting sparse sketch maintains the rapid, problem-independent convergence rates of dense methods at a fraction of the computational cost.
Beyond Least Squares: Lewis Weights for Robust Loss Functions
Standard leverage scores are inherently tied to the $\ell_2$ norm (least-squares geometry). However, many machine learning applications require robust loss functions, such as $\ell_1$ regression (Least Absolute Deviation) or hinge losses in Support Vector Machines (SVMs), which are less sensitive to outliers.
To apply the intuition of leverage scores to these non-Euclidean geometries, researchers use Lewis weights, which generalize statistical leverage scores to $\ell_p$ spaces.
The impact of this generalization is significant:
- Linear Classification: Tung Mai et al. show that sampling data points based on $\ell_1$ Lewis weights yields near-optimal "coresets" (weighted subsets of data) for linear classifiers. This approach identifies influential rows relative to $\ell_1$ geometry, reducing the theoretical sample complexity's dependence on the feature dimension from cubic ($d^3$) to near-linear ($d$).
- Active Learning: In scenarios where data is abundant but labels are expensive, Lewis weights allow for optimal sample selection without knowing the target labels. Xue Chen et al. and Aditya Parulekar et al. leverage this property for active $\ell_1$ regression, proving that a model can achieve high-probability error bounds by labeling only a tiny, structurally significant fraction of the data pool.
By shifting from uniform randomness to geometry-aware importance sampling, leverage scores and Lewis weights bridge the gap between massive data scales and efficient, provably accurate learning.