# New Bounds for Kernel Sums via Fast Spherical Embeddings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 2 May 2026.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [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)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [The Bernstein Mechanism: Function Release under Differential Privacy](https://mlsanity.com/paper/1507.04499/) (2015)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions](https://mlsanity.com/paper/2507.23539/) (2025)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform](https://mlsanity.com/paper/2601.09477/) (2026)

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

- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)

## Abstract (arXiv)

We study query time bounds for the fundamental problem of estimating the kernel mean frac1|X|sumx∈ Xk(x,y) of a query y in a finite dataset Xsubsetℝd up to a prescribed additive error varepsilon. The best known bounds for the Gaussian kernel are O(d/varepsilon2), widetilde O(d+1/varepsilon4), and widetilde O(d+Delta2/varepsilon2), where Delta is the diameter of a region containing the points. We prove the new bound tilde O(d+varepsilonDelta2+1/varepsilon3), 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.