# Compressed Empirical Measures (in finite dimensions)

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 42 references that are in the map.
- First posted on arXiv 19 Apr 2022.

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

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)

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

- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)

## Abstract (arXiv)

We study approaches for compressing the empirical measure in the context of finite dimensional reproducing kernel Hilbert spaces (RKHSs). In this context, the empirical measure is contained within a natural convex set and can be approximated using convex optimization methods. Such an approximation gives rise to a coreset of data points. A key quantity that controls how large such a coreset has to be is the size of the largest ball around the empirical measure that is contained within the empirical convex set. The bulk of our work is concerned with deriving high probability lower bounds on the size of such a ball under various conditions and in various settings: we show how conditions on the density of the data and the kernel function can be used to infer such lower bounds; we further develop an approach that uses a lower bound on the smallest eigenvalue of a covariance operator to provide lower bounds on the size of such a ball; we extend the approach to approximate covariance operators and we show how it can be used in the context of kernel ridge regression. We also derive compression guarantees when standard algorithms like the conditional gradient method are used and we discuss variations of such algorithms to improve the runtime of these standard algorithms. We conclude with a construction of an infinite dimensional RKHS for which the compression is poor, highlighting some of the difficulties one faces when trying to move to infinite dimensional RKHSs.