Fast kernel methods: Sobolev, physics-informed, and additive models

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 $\mathcal{O}(n \log n)$ complexity, and designed to fully leverage 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. 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, whenever the kernel norm can be efficiently expressed in Fourier space and the ambient dimension $d$ is small. Although the theoretical framework is valid in all dimensions $d$, the fast Sobolev regression package implemented in the paper relies on the CufiNUFFT package, which currently scales exponentially in $d$ and is limited to $d \leq 3$. For similar reasons, the additive model package is only implemented for simple effects without interaction.

Kernel methods are a generalization of the well-known linear regression, from which it inherits closed-form expressions and strong theoretical guarantees. However, naive implementations of kernel methods becomes increasingly slow as the number of data points grows, making them impractical for modern large-scale applications. We address this challenge by developing a new framework that makes kernel-based learning more efficient. We reformulate a vast class of statistical problems as kernel methods, and show that the kernel algorithm can be trained in linear time (it does not take much longer than simply reading the data) while benefitting from the speed-ups of modern GPU hardware. We apply this framework to several common settings, including smooth function estimation, physics-informed learning problems, and additive models. In each case, our method preserves the strong statistical guarantees of classical kernel methods while drastically improving computational efficiency. As a result, our approach can handle datasets with tens of billions of samples in minutes.