提出新方法加速核函数求和，小误差下更高效。
New Bounds for Kernel Sums via Fast Spherical Embeddings
- 用快速球面嵌入保持局部距离，避免远距离失真。
- 新界为 $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$，优于旧方法。
- 适合高维数据中小误差场景的核计算任务。
研究在有限数据集 $X\subset\mathbb{R}^d$ 中，对查询点 $y$ 估计核均值 $\frac1{|X|}\sum_{x\in X}\mathbf{k}(x,y)$ 的查询时间界，要求误差不超过 $\varepsilon$。已知高斯核的最佳界为 $O(d/\varepsilon^2)$、$\widetilde O(d+1/\varepsilon^4)$、$\widetilde O(d+Δ^2/\varepsilon^2)$，其中 $Δ$ 为点集所在区域直径。本文证明新界 $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$，在小误差 $\varepsilon$ 和中等直径 $Δ$ 的情况下优于前人结果。核心是提出一种新的快速球面嵌入定理，由 Bartal 等（2011）引入，能控制嵌入后数据直径，同时保留局部欧氏距离，避免大尺度距离坍缩。该嵌入定理本身可能具有独立价值。
原文摘要 · Abstract (English)
We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\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 $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+Δ^2/\varepsilon^2)$, where $Δ$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $Δ$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。