New Bounds for Kernel Sums via Fast Spherical Embeddings

We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\sum_{x\in X}\mathbf{\mathrm{k}}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ up to a prescribed additive error $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+\Delta^2/\varepsilon^2)$, where $\Delta$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilon\Delta^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $\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.

Many machine learning systems need to quickly tell whether a new example looks typical or unusual compared with a large dataset. A common way to do this is to average a smooth similarity score between the query and every stored point, but that becomes expensive when the data has many features and high accuracy is needed. We give a faster theoretical method for this task for a widely used Gaussian similarity function. Our key idea is to map the data onto a sphere in a way that preserves the distinctions that matter: nearby points stay accurate, while faraway points do not accidentally look close. This transformation can be computed quickly using structured random matrices related to the fast Hadamard transform. We then use more fast randomized computations on this new representation to estimate the average similarity. The resulting algorithm improves over several classical methods in important settings, especially when very accurate answers are needed. We also show that the same idea extends to another popular family of similarity functions and to privacy-preserving versions of the problem. More broadly, the new sphere-based embedding we develop could be useful in other learning tasks that involve many variables and depend on fast similarity calculations.