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

• URL: http://arxiv.org/abs/2509.02649v1
• Date: Tue, 02 Sep 2025 12:07:48 GMT
• Title: Fast kernel methods: Sobolev, physics-informed, and additive models
• Authors: Nathan Doumèche, Francis Bach, Gérard Biau, Claire Boyer,
• Abstract summary: We introduce a scalable framework for kernel regression with O(n log n) complexity.<n>We instantiate our framework in three settings: Sobolev kernel regression, physics-informed regression, and additive models.<n> Empirical results demonstrate that our methods can process up to tens of billions of samples within minutes.
• Score: 9.003833238370122
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. We propose a quantum approach to defining Betti kernels, which is based on constructing Betti curves with increasing order.
  arXiv  Detail & Related papers  (2023-07-14T14:48:52Z)
• Snacks: a fast large-scale kernel SVM solver [0.8602553195689513]
  Snacks is a new large-scale solver for Kernel Support Vector Machines. Snacks relies on a Nystr"om approximation of the kernel matrix and an accelerated variant of the subgradient method.
  arXiv  Detail & Related papers  (2023-04-17T04:19:20Z)
• RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features [3.0079490585515347]
  We introduce RFFNet, a scalable method that learns the kernel relevances' on the fly via first-order optimization. We show that our approach has a small memory footprint and run-time, low prediction error, and effectively identifies relevant features. We supply users with an efficient, PyTorch-based library, that adheres to the scikit-learn standard API and code for fully reproducing our results.
  arXiv  Detail & Related papers  (2022-11-11T18:50:34Z)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support. The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG) Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
  arXiv  Detail & Related papers  (2022-10-10T12:35:02Z)
• Neural Fields as Learnable Kernels for 3D Reconstruction [101.54431372685018]
  We present a novel method for reconstructing implicit 3D shapes based on a learned kernel ridge regression. Our technique achieves state-of-the-art results when reconstructing 3D objects and large scenes from sparse oriented points.
  arXiv  Detail & Related papers  (2021-11-26T18:59:04Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• The Fast Kernel Transform [21.001203328543006]
  We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications for datasets in moderate dimensions with quasilinear complexity. The FKT is easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Green's functions. We illustrate the efficacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets.
  arXiv  Detail & Related papers  (2021-06-08T16:15:47Z)
• Gauss-Legendre Features for Gaussian Process Regression [7.37712470421917]
  We present a Gauss-Legendre quadrature based approach for scaling up Gaussian process regression via a low rank approximation of the kernel matrix. Our method is very much inspired by the well-known random Fourier features approach, which also builds low-rank approximations via numerical integration.
  arXiv  Detail & Related papers  (2021-01-04T18:09:25Z)
• Learning Compositional Sparse Gaussian Processes with a Shrinkage Prior [26.52863547394537]
  We present a novel probabilistic algorithm to learn a kernel composition by handling the sparsity in the kernel selection with Horseshoe prior. Our model can capture characteristics of time series with significant reductions in computational time and have competitive regression performance on real-world data sets.
  arXiv  Detail & Related papers  (2020-12-21T13:41:15Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.