2024/07/02 by Josh Alman, Alman, Josh, Yunfeng Guan +1 · 1 citation
Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Industrial Vision Systems and Defect Detection #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2407.02372
openalex publication_date 2024/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In batch Kernel Density Estimation (KDE) for a kernel function f, we are given as input 2n points x(1), ⋯, x(n), y(1), ⋯, y(n) in dimension m, as well as a vector v ∈ ℝn. These inputs implicitly define the n × n kernel matrix K given by K[i,j] = f(x(i), y(j)). The goal is to compute a vector v which approximates K w with || Kw - v||_∞ < ε ||w||1. A recent line of work has proved fine-grained lower bounds conditioned on SETH. Backurs et al. first showed the hardness of KDE for Gaussian-like kernels with high dimension m = Ω(log n) and large scale B = Ω(log n). Alman et al. later developed new reductions in roughly this same parameter regime, leading to lower bounds for more general kernels, but only for very small error ε < 2^- logΩ(1) (n). In this paper, we refine the approach of Alman et al. to show new lower bounds in all parameter regimes, closing gaps between the known algorithms and lower bounds. In the setting where m = Clog n and B = o(log n), we prove Gaussian KDE requires n2-o(1) time to achieve additive error ε < Ω(m/B)-m, matching the performance of the polynomial method up to low-order terms. In the low dimensional setting m = o(log n), we show that Gaussian KDE requires n2-o(1) time to achieve ε such that log log (ε-1) > Ω((log n)/m), matching the error bound achievable by FMM up to low-order terms. To our knowledge, no nontrivial lower bound was previously known in this regime. Our new lower bounds make use of an intricate analysis of a special case of the kernel matrix -- the `counting matrix'. As a key technical lemma, we give a novel approach to bounding the entries of its inverse by using Schur polynomials from algebraic combinatorics.