In large-scale machine learning, we are often forced to choose between two extremes: processing every data point at immense computational cost, or sampling a small subset and risking the loss of critical, "rare" information. Uniform sampling is fast but "blind"—it treats an outlier with massive influence the same as a redundant, average point.
To solve this, researchers use importance sampling, where data points are weighted by their "influence" on the final model. The gold standard for this influence is the statistical leverage score. However, a fundamental paradox emerges: calculating exact leverage scores often requires as much work as solving the original problem.
Recent research has focused on breaking this circular dependency, developing randomized and recursive techniques to approximate these scores in a fraction of the time.
The Leverage Score Paradox
In a linear system $Ax = b$, the leverage score of a row in $A$ measures how much that specific observation "pulls" the solution. Rows with high leverage are unique and indispensable; if you miss them during sampling, your model fails.
As Petros Drineas and Michael W. Mahoney point out in Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving, these scores are the key to "nearly linear-time" solvers. But there is a catch: calculating them exactly usually involves a Singular Value Decomposition (SVD), which scales cubically with the data dimensions. This creates a bottleneck where the cost of identifying which data to keep negates the efficiency gains of the subsequent solver.
This "chicken and egg" problem appears across domains:
- Matrix Completion: Yudong Chen and Rachel Ward showed in Completing Any Low-rank Matrix, Provably that leverage-based sampling allows for the recovery of "spiky" matrices that uniform sampling would miss, but the overhead of estimating those scores remains a barrier.
- Kernel Methods: In Fast Randomized Kernel Methods With Statistical Guarantees, Ahmed El Alaoui and Michael W. Mahoney note that importance sampling for kernels creates a circular dependency, as the "importance" depends on the very kernel matrix you are trying to approximate.
Sketching as a Shortcut
To bypass the SVD bottleneck, researchers use sketching—applying a random projection to the data to create a smaller "proxy" matrix. Because random projections (like the Johnson-Lindenstrauss transform) roughly preserve the geometry of the data, the leverage scores of the small proxy matrix are excellent approximations of the scores in the original massive matrix.
David Woodruff has been a central figure in refining these techniques. In Single Pass Entrywise-Transformed Low Rank Approximation, Yi Li and Woodruff introduced the H-Sketch, a data structure that allows for high-quality approximations in a single pass over the data, achieving speeds 1,000x faster than traditional multi-pass methods.
Recursive and Sequential Refinement
For even more complex structures, like tensors or time series, a single sketch might not be enough. Instead, researchers are turning to recursive algorithms that refine their importance estimates as they go.
In SALSA: Sequential Approximate Leverage-Score Algorithm, Ali Eshragh and Fred Roosta demonstrate how to approximate leverage scores for massive time series data up to 30x faster than exact methods. By updating estimates sequentially, they avoid the need to ever load the full dataset into memory.
A similar logic applies to high-dimensional tensors. Vivek Bharadwaj and Guillaume Rabusseau developed rTT-ALS in Efficient Leverage Score Sampling for Tensor Train Decomposition. They leverage the "canonical form" of tensor cores to compute leverage scores efficiently, overcoming the "exponential curse" that usually makes tensor sampling impossible.
Beyond Linear Models
The intuition of leverage is now expanding into nonlinear domains. While traditional leverage is a linear algebraic concept, Prakash Palanivelu Rajmohan and Fred Roosta recently introduced a framework for Importance Sampling for Nonlinear Models. By using a "nonlinear adjoint operator," they generalize leverage scores to neural networks, allowing for faster training and better outlier detection in models that don't follow simple linear rules.
Even in generative modeling, these scores are proving vital. Joachim Schreurs showed in Leverage Score Sampling for Complete Mode Coverage in GANs that biasing training toward high-leverage (unique) points prevents "mode collapse," ensuring that GANs learn to represent rare subpopulations rather than just the most common examples.
Why It Works
The success of these methods rests on a single insight: statistical influence is a structural property, not a numerical one. You don't need the exact value of a leverage score to benefit from it; you only need to know which points are relatively more important than others. By using randomized sketches and recursive updates, we can capture the "skeleton" of the data's importance without ever having to solve the full, heavy system. This shift from exact computation to "good enough" approximation is what enables modern algorithms to scale to datasets that were previously untouchable.