# Fast Statistical Leverage Score Approximation in Kernel Ridge Regression

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 9 Mar 2021.

## Builds on (most cited first, 13 of 13)

- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Frequentist coverage and sup-norm convergence rate in Gaussian process regression](https://mlsanity.com/paper/1708.04753/) (2017)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [Relating Leverage Scores and Density using Regularized Christoffel Functions](https://mlsanity.com/paper/1805.07943/) (2018)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [Explaining Aggregates for Exploratory Analytics](https://mlsanity.com/paper/1812.11346/) (2018)

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

- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores](https://mlsanity.com/paper/2507.08143/) (2025)
- [Chameleon: A Flexible Data-mixing Framework for Language Model Pretraining and Finetuning](https://mlsanity.com/paper/2505.24844/) (2025)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Inducer-tuning: Connecting Prefix-tuning and Adapter-tuning](https://mlsanity.com/paper/2210.14469/) (2022)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data](https://mlsanity.com/paper/2401.00122/) (2023)
- [Fast Newton method solving KLR based on Multilevel Circulant Matrix with log-linear complexity](https://mlsanity.com/paper/2108.08605/) (2021)
- [Adaptive Quality-Diversity Trade-offs for Large-Scale Batch Recommendation](https://mlsanity.com/paper/2602.02024/) (2026)
- [Spectral Convergence of Random Feature Method in Multiple Dimensions](https://mlsanity.com/paper/2609.03401/) (2026)

## Abstract (arXiv)

Nystr"om approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems through sub-sampling the n-by-n empirical kernel matrix appearing in the objective function. However, the performance of such a sub-sampling method heavily relies on correctly estimating the statistical leverage scores for forming the sampling distribution, which can be as costly as solving the original KRR. In this work, we propose a linear time (modulo poly-log terms) algorithm to accurately approximate the statistical leverage scores in the stationary-kernel-based KRR with theoretical guarantees. Particularly, by analyzing the first-order condition of the KRR objective, we derive an analytic formula, which depends on both the input distribution and the spectral density of stationary kernels, for capturing the non-uniformity of the statistical leverage scores. Numerical experiments demonstrate that with the same prediction accuracy our method is orders of magnitude more efficient than existing methods in selecting the representative sub-samples in the Nystr"om approximation.