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

arXiv: https://arxiv.org/abs/2509.02649 · HTML: https://mlsanity.com/paper/2509.02649/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 14 references that are in the map.
- First posted on arXiv 2 Sep 2025.

## Builds on (most cited first, 5 of 5)

- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [An elementary analysis of ridge regression with random design](https://mlsanity.com/paper/2203.08564/) (2022)
- [Physics-informed machine learning as a kernel method](https://mlsanity.com/paper/2402.07514/) (2024)
- [cuFINUFFT: a load-balanced GPU library for general-purpose nonuniform FFTs](https://mlsanity.com/paper/2102.08463/) (2021)
- [Forecasting time series with constraints](https://mlsanity.com/paper/2502.10485/) (2025)

## Built on by (most cited first, 3 of 3)

- [Estimating Continuous Treatment Effects with Two-Stage Kernel Ridge Regression](https://mlsanity.com/paper/2604.13410/) (2026)
- [PIKS: Universal Physics-Informed Kernel Methods](https://mlsanity.com/paper/2607.27062/) (2026)
- [Fast Learning Rates for Physics-Informed Kernel Methods](https://mlsanity.com/paper/2609.18901/) (2026)

## Abstract (arXiv)

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.