解析结构化核插值的误差，给出线性时间高斯过程的精度保障条件。
The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
- 基于诱导点插值，理论分析了核矩阵近似误差边界。
- 证明在数据量足够大时，低维下可实现线性时间且误差可控。
- 揭示维度高于3时需权衡误差与计算效率，指导诱导点数量选择。
结构化核插值（SKI）通过在诱导点上插值近似核矩阵，将高斯过程（GP）的计算复杂度降至线性，但缺乏严格的误差分析。本文填补这一空白：我们推导出SKI核矩阵的误差界，并研究其对超参数估计和后验推断的影响。进一步地，针对卷积立方插值，给出实用建议——诱导点数量应随样本数以 $n^{d/3}$ 增长以控制误差。关键发现是：存在两个维度区间决定误差与计算复杂度的权衡。当 $d \leq 3$ 时，对任意误差容忍度，只要样本量足够大，即可实现线性时间；当 $d > 3$ 时，为维持线性时间，误差必须随样本量增加。该分析为实现可控误差的线性时间高斯过程推断提供了精确条件。
原文摘要 · Abstract (English)
Structured Kernel Interpolation (SKI) (Wilson et al. 2015) helps scale Gaussian Processes (GPs) by approximating the kernel matrix via interpolation at inducing points, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges the gap: we prove error bounds for the SKI Gram matrix and examine the error's effect on hyperparameter estimation and posterior inference. We further provide a practical guide to selecting the number of inducing points under convolutional cubic interpolation: they should grow as $n^{d/3}$ for error control. Crucially, we identify two dimensionality regimes governing the trade-off between SKI Gram matrix spectral norm error and computational complexity. For $d \leq 3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d > 3$, the error must increase with sample size to maintain linear time. Our analysis provides key insights into SKI's scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled approximation error.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。