HEXAGONbeta

Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.NA — Numerical Analysismath.PR — Probability

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 15, 2026 / CC BY 4.0

Abstract

Wagner asked whether Gaussian kernel density estimation in Rd\mathbb R^d admits query time O~(d+ε−2)\widetilde O(d+\varepsilon^{-2}) without dependence on the diameter of the data. We answer this affirmatively for each fixed query: a randomized data structure answers a query to additive error ε\varepsilon with probability 1−δ1-\delta in time O((d+ε−2)log⁡(d+1)log⁡(2/δ))O((d+\varepsilon^{-2})\log(d+1)\log(2/\delta)), independently of the number of data points and of their diameter. The key ingredient is a variance bound for a Fastfood-type structured Fourier block that holds uniformly in the norm of the displacement.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. Tal Wagner. New bounds for kernel sums via fast spherical embeddings. In Proceedings of the 43rd International Conference on Machine Learning , PMLR 306:124205--124223, 2026. Published version (https://proceedings.mlr.press/v306/wagner26a.html). The open question is in Section 6; references to Section 7 use the preprint. arXiv:2605.01263v1 [cs.DS] (https://arxiv.org/abs/2605.01263), 2 May 2026.arXiv
  2. Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski. Efficiently computing similarities to private datasets. In The Twelfth International Conference on Learning Representations , 2024. OpenReview:HMe5CJv9dQ (https://openreview.net/forum?id=HMe5CJv9dQ).link
  3. Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems , volume 20, pages 1177--1184, 2007. NeurIPS proceedings record (https://proceedings.neurips.cc/paper_files/paper/2007/hash/013a006f03dbc5392effeb8f18fda755-Abstract.html).link
  4. L. Greengard and J. Strain. The fast G auss transform. SIAM J. Sci. Stat. Comput. , 12(1):79--94, 1991. https://doi.org/10.1137/0912004.DOI
  5. M. Charikar and P. Siminelakis. Hashing-based-estimators for kernel density in high dimensions. In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS) , 1032--1043, 2017. https://doi.org/10.1109/FOCS.2017.99.DOI
  6. M. Charikar, M. Kapralov, N. Nouri, and P. Siminelakis. Kernel density estimation through density constrained near neighbor search. In Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS) , 172--183, 2020. https://doi.org/10.1109/FOCS46700.2020.00025.DOI
  7. N. Ailon and B. Chazelle. The fast J ohnson-- L indenstrauss transform and approximate nearest neighbors. SIAM J. Comput. , 39(1):302--322, 2009. https://doi.org/10.1137/060673096.DOI
  8. Quoc V. Le, Tamás Sarlós, and Alexander J. Smola. Fastfood---computing Hilbert space expansions in loglinear time. In Proceedings of the 30th International Conference on Machine Learning , PMLR 28(3):244--252, 2013. PMLR:v28/le13 (https://proceedings.mlr.press/v28/le13.html).link
  9. Chang Feng, Qinghua Hu, and Shizhong Liao. Random feature mapping with signed circulant matrix projection. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence , pp. 3490--3496, 2015. IJCAI proceedings record (https://www.ijcai.org/Abstract/15/491).link
  10. Krzysztof Choromanski and Vikas Sindhwani. Recycling randomness with structure for sublinear time kernel expansions. In Proceedings of the 33rd International Conference on Machine Learning , PMLR 48:2502--2510, 2016. PMLR:v48/choromanski16 (https://proceedings.mlr.press/v48/choromanski16.html).link
Show all 18 referencesShow fewer references
  1. Quoc Viet Le, Tamás Sarlós, and Alexander J. Smola. Fastfood: approximate kernel expansions in loglinear time. Expanded version, arXiv:1408.3060v1 (https://arxiv.org/abs/1408.3060v1), 2014.arXiv
  2. Nizar Demni and Hachem Kadri. Orthogonal random features: explicit forms and sharp inequalities. Transactions on Machine Learning Research , September 2024. OpenReview:FMtRZ4xzSi (https://openreview.net/forum?id=FMtRZ4xzSi).link
  3. Felix Xinnan Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmann-Rice, and Sanjiv Kumar. Orthogonal random features. In Advances in Neural Information Processing Systems , volume 29, 2016. NeurIPS proceedings record (https://proceedings.neurips.cc/paper/2016/hash/53adaf494dc89ef7196d73636eb2451b-Abstract.html).link
  4. Krzysztof Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effectiveness of structured random orthogonal embeddings. In Advances in Neural Information Processing Systems , volume 30, 2017. NeurIPS proceedings record (https://papers.nips.cc/paper_files/paper/2017/hash/bf8229696f7a3bb4700cfddef19fa23f-Abstract.html).link
  5. Krzysztof Choromanski, Mark Rowland, Tamás Sarlós, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. The geometry of random features. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics , PMLR 84:1--9, 2018. PMLR:v84/choromanski18a (https://proceedings.mlr.press/v84/choromanski18a.html).link
  6. Jeff M. Phillips and Wai Ming Tai. Improved coresets for kernel density estimates. In Proceedings of the 29th Annual ACM--SIAM Symposium on Discrete Algorithms , pages 2718--2727, 2018. doi:10.1137/1.9781611975031.173 (https://doi.org/10.1137/1.9781611975031.173).DOI
  7. Wai Ming Tai. Optimal coreset for Gaussian kernel density estimation. In 38th International Symposium on Computational Geometry , LIPIcs 224, pages 63:1--63:15, 2022. doi:10.4230/LIPIcs.SoCG.2022.63 (https://doi.org/10.4230/LIPIcs.SoCG.2022.63).DOI
  8. Ofek I. Cohen. Query-oblivious coresets for softmax attention: improved bounds and efficient constructions. arXiv:2609.06327v2 (https://arxiv.org/abs/2609.06327v2), 13 September 2026.arXiv

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 15, 2026