# Distributed Adaptive Sampling for Kernel Matrix Approximation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2018.

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

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Computational Efficiency under Covariate Shift in Kernel Ridge Regression](https://mlsanity.com/paper/2505.14083/) (2025)
- [Generalized Leverage Scores: Geometric Interpretation and Applications](https://mlsanity.com/paper/2206.08054/) (2022)
- [AQKA: Active Quantum Kernel Acquisition Under a Shot Budget](https://mlsanity.com/paper/2605.14672/) (2026)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)
- [Certified Approximation for Interpretable Representer Landmarks](https://mlsanity.com/paper/2609.38901/) (2026)

## Abstract (arXiv)

Most kernel-based methods, such as kernel or Gaussian process regression, kernel PCA, ICA, or k-means clustering, do not scale to large datasets, because constructing and storing the kernel matrix Kn requires at least O(n2) time and space for n samples. Recent works show that sampling points with replacement according to their ridge leverage scores (RLS) generates small dictionaries of relevant points with strong spectral approximation guarantees for Kn. The drawback of RLS-based methods is that computing exact RLS requires constructing and storing the whole kernel matrix. In this paper, we introduce SQUEAK, a new algorithm for kernel approximation based on RLS sampling that sequentially processes the dataset, storing a dictionary which creates accurate kernel matrix approximations with a number of points that only depends on the effective dimension deff(γ) of the dataset. Moreover since all the RLS estimations are efficiently performed using only the small dictionary, SQUEAK is the first RLS sampling algorithm that never constructs the whole matrix Kn, runs in linear time widetildeO(ndeff(γ)3) w.r.t. n, and requires only a single pass over the dataset. We also propose a parallel and distributed version of SQUEAK that linearly scales across multiple machines, achieving similar accuracy in as little as widetildeO(log(n)deff(γ)3) time.