# Diversity sampling is an implicit regularization for kernel methods

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

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

- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Deep Kernel Principal Component Analysis for Multi-level Feature Learning](https://mlsanity.com/paper/2302.11220/) (2023)
- [On sampling determinantal and Pfaffian point processes on a quantum computer](https://mlsanity.com/paper/2305.15851/) (2023)
- [Deep Adaptive Bayesian Screening](https://mlsanity.com/paper/2607.16927/) (2026)

## Abstract (arXiv)

Kernel methods have achieved very good performance on large scale regression and classification problems, by using the Nystr"om method and preconditioning techniques. The Nystr"om approximation -- based on a subset of landmarks -- gives a low rank approximation of the kernel matrix, and is known to provide a form of implicit regularization. We further elaborate on the impact of sampling diverse landmarks for constructing the Nystr"om approximation in supervised as well as unsupervised kernel methods. By using Determinantal Point Processes for sampling, we obtain additional theoretical results concerning the interplay between diversity and regularization. Empirically, we demonstrate the advantages of training kernel methods based on subsets made of diverse points. In particular, if the dataset has a dense bulk and a sparser tail, we show that Nystr"om kernel regression with diverse landmarks increases the accuracy of the regression in sparser regions of the dataset, with respect to a uniform landmark sampling. A greedy heuristic is also proposed to select diverse samples of significant size within large datasets when exact DPP sampling is not practically feasible.