# Supervised Kernel Thinning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 17 Oct 2024.

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

- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Large Scale Kernel Learning using Block Coordinate Descent](https://mlsanity.com/paper/1602.05310/) (2016)
- [Improved Coresets for Kernel Density Estimates](https://mlsanity.com/paper/1710.04325/) (2017)
- [Debiased Distribution Compression](https://mlsanity.com/paper/2404.12290/) (2024)
- [NYTRO: When Subsampling Meets Early Stopping](https://mlsanity.com/paper/1510.05684/) (2015)
- [Sequential Kernel Embedding for Mediated and Time-Varying Dose Response Curves](https://mlsanity.com/paper/2111.03950/) (2021)
- [Coresets for Kernel Regression](https://mlsanity.com/paper/1702.03644/) (2017)
- [Robust inference of conditional average treatment effects using dimension reduction](https://mlsanity.com/paper/2008.13137/) (2020)
- [Compressed Empirical Measures (in finite dimensions)](https://mlsanity.com/paper/2204.08847/) (2022)

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

- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [Local EGOP for Continuous Index Learning](https://mlsanity.com/paper/2601.07061/) (2026)
- [Revisiting Thinning Methods for Kernel Learning Problems](https://mlsanity.com/paper/2609.07432/) (2026)

## Abstract (arXiv)

The kernel thinning algorithm of Dwivedi & Mackey (2024) provides a better-than-i.i.d. compression of a generic set of points. By generating high-fidelity coresets of size significantly smaller than the input points, KT is known to speed up unsupervised tasks like Monte Carlo integration, uncertainty quantification, and non-parametric hypothesis testing, with minimal loss in statistical accuracy. In this work, we generalize the KT algorithm to speed up supervised learning problems involving kernel methods. Specifically, we combine two classical algorithms--Nadaraya-Watson (NW) regression or kernel smoothing, and kernel ridge regression (KRR)--with KT to provide a quadratic speed-up in both training and inference times. We show how distribution compression with KT in each setting reduces to constructing an appropriate kernel, and introduce the Kernel-Thinned NW and Kernel-Thinned KRR estimators. We prove that KT-based regression estimators enjoy significantly superior computational efficiency over the full-data estimators and improved statistical efficiency over i.i.d. subsampling of the training data. En route, we also provide a novel multiplicative error guarantee for compressing with KT. We validate our design choices with both simulations and real data experiments.