提出O(n log n)快速核方法，支持大规模数据精确计算
Fast kernel methods: Sobolev, physics-informed, and additive models
- 用傅里叶表示+非均匀FFT实现核回归加速
- 处理数十亿样本仅需数分钟，保持统计最优收敛率
- 适合需要高精度的大规模学习任务
核方法在统计学习中表现强大，但其样本量n的立方复杂度限制了在大规模数据上的应用。本文提出一种可扩展的核回归框架，复杂度降至O(n log n)，充分借助GPU加速。该方法基于核的傅里叶表示与非均匀快速傅里叶变换（NUFFT），实现精确、快速且内存高效的计算。我们在三种场景中实例化：Sobolev核回归、物理信息回归和加性模型。当已知时，所提估计器达到经典核理论中的极小极大收敛率。实证结果表明，该方法可在数分钟内处理多达数十亿样本，兼具统计准确性和计算可扩展性。这些贡献建立了一种灵活的方法，为核方法在大规模学习任务中的常规应用铺平道路。
原文摘要 · Abstract (English)
Kernel methods are powerful tools in statistical learning, but their cubic complexity in the sample size n limits their use on large-scale datasets. In this work, we introduce a scalable framework for kernel regression with O(n log n) complexity, fully leveraging GPU acceleration. The approach is based on a Fourier representation of kernels combined with non-uniform fast Fourier transforms (NUFFT), enabling exact, fast, and memory-efficient computations. We instantiate our framework in three settings: Sobolev kernel regression, physics-informed regression, and additive models. When known, the proposed estimators are shown to achieve minimax convergence rates, consistent with classical kernel theory. Empirical results demonstrate that our methods can process up to tens of billions of samples within minutes, providing both statistical accuracy and computational scalability. These contributions establish a flexible approach, paving the way for the routine application of kernel methods in large-scale learning tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。