# Dimension-Independent Kernel ε-Covers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 28 Jun 2023.

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

- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Maximum Number of Modes of Gaussian Mixtures](https://mlsanity.com/paper/1702.05066/) (2017)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [Computing Approximate Statistical Discrepancy](https://mlsanity.com/paper/1804.11287/) (2018)
- [Coresets for Kernel Regression](https://mlsanity.com/paper/1702.03644/) (2017)
- [Gaussian Process Subset Scanning for Anomalous Pattern Detection in Non-iid Data](https://mlsanity.com/paper/1804.01466/) (2018)
- [Optimal Approximations Made Easy](https://mlsanity.com/paper/2008.08970/) (2020)
- [The Kernel Spatial Scan Statistic](https://mlsanity.com/paper/1906.09381/) (2019)
- [Sketched MinDist](https://mlsanity.com/paper/1907.02171/) (2019)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)

## Abstract (arXiv)

We introduce the notion of an varepsilon-cover for a kernel range space. A kernel range space concerns a set of points X subset ℝd and the space of all queries by a fixed kernel (e.g., a Gaussian kernel K(p,·) = exp(-|p-·|2), where p ∈ ℝd). For a point set X of size n, a query returns a vector of values Rp ∈ ℝn, where the ith coordinate (Rp)i = K(p,xi) for xi ∈ X. An varepsilon-cover is a subset of points Q subset ℝd so for any p ∈ ℝd that frac1n |Rp - Rq|1≤ varepsilon for some q ∈ Q. This is a smooth analog of Haussler's notion of varepsilon-covers for combinatorial range spaces (e.g., defined by subsets of points within a ball query) where the resulting vectors Rp are in 0,1n instead of [0,1]n. The kernel versions of these range spaces show up in data analysis tasks where the coordinates may be uncertain or imprecise, and hence one wishes to add some flexibility in the notion of inside and outside of a query range. Our main result is that, unlike combinatorial range spaces, the size of kernel varepsilon-covers is independent of the input size n and dimension d. We obtain a bound of 2tilde O(1/varepsilon2), where tildeO(f(1/varepsilon)) hides log factors in (1/varepsilon) that can depend on the kernel. This implies that by relaxing the notion of boundaries in range queries, eventually the curse of dimensionality disappears, and may help explain the success of machine learning in very high-dimensions. We also complement this result with a lower bound of almost (1/varepsilon)Omega(1/varepsilon), showing the exponential dependence on 1/varepsilon is necessary.