New Bounds for Kernel Sums via Fast Spherical Embeddings

We study query time bounds for the fundamental problem of estimating the kernel mean $\frac{1}{\mathrm{\mid }X\mathrm{\mid }}{\sum }_{x\in X}\mathbf{k}(x,y)$ of a query $y$ in a finite dataset $X\subset {\mathbb{R}}^d$ up to a prescribed additive error $\epsilon$. The best known bounds for the Gaussian kernel are $O(d\mathrm{/}{\epsilon }^2)$, $\tilde{O}(d+1\mathrm{/}{\epsilon }^4)$, and $\tilde{O}(d+{\mathrm{\Delta }}^2\mathrm{/}{\epsilon }^2)$, where $\mathrm{\Delta }$ is the diameter of a region containing the points. We prove the new bound $\tilde{O}(d+\epsilon {\mathrm{\Delta }}^2+1\mathrm{/}{\epsilon }^3)$, which improves over the previous ones in regimes with small error $\epsilon$ and intermediate diameter $\mathrm{\Delta }$. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse’’ at larger scales. This fast embedding theorem may be of independent interest.