Approximating Statistical Leverage for Large Scale Data Sketching

This direction is split into other directions: importance sampling overhead (leverage score computation overhead). Its last version stays readable and citable here.

Version 1 of 1125 papers136 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

Showing 60 of 125 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_approximating_statistical_leverage_for_l_46ccfa5a,
  title = {Approximating Statistical Leverage for Large Scale Data Sketching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximating-statistical-leverage-for-large-scale-data-sketching/rdr_46ccfa5aa6eb4964b3a6b996a6fb8d13},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_approximating_statistical_leverage_for_l_46ccfa5a_v1,
  title = {Approximating Statistical Leverage for Large Scale Data Sketching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximating-statistical-leverage-for-large-scale-data-sketching/rdr_46ccfa5aa6eb4964b3a6b996a6fb8d13/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}