Kernel Methods

Follow this topic Ask about this topic

Momentum

18 papers in the last four weeks, up 125% on the four weeks before. 0.2% of all new papers.

Jul 13Week of Sep 28

Latest papers 168

Oct 16, 2025cs.LG

Predicting kernel regression learning curves from only raw data statistics

We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet. We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function

f_*

. The key new idea is an analytical approximation of a kernel's eigenvalues and eigenfunctions with respect to an anisotropic data distribution. The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the Hermite eigenstructure ansatz (HEA). We prove the HEA for Gaussian data, but we find that real image data is often "Gaussian enough" for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk. Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA. Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.

Dhruva Karkada, Joseph Turnbull, Yuxi Liu +1

UC Berkeley · Imbue

Kernel Regression Kernel Methods Statistical Learning Theory

Sep 21, 2025math.NA

Data-efficient Kernel Methods for Learning Hamiltonian Systems

Hamiltonian dynamics describe a wide range of physical systems. As such, data-driven simulations of Hamiltonian systems are important for many scientific and engineering problems. In this work, we propose kernel-based methods for identifying and forecasting Hamiltonian systems directly from trajectory data. We present two approaches: a 2-step method that reconstructs trajectories before learning the Hamiltonian, and a 1-step method that jointly infers both. Across several benchmark systems, including mass-spring dynamics, a nonlinear pendulum, and the Henon-Heiles system, we demonstrate that our framework achieves accurate, data-efficient predictions and outperforms 2-step kernel-based baselines, particularly in scarce-data regimes, while preserving the Hamiltonian structure. Moreover, we prove a priori error estimates, ensuring reliability of the learned models. We also provide a more general, problem-agnostic numerical framework that goes beyond Hamiltonian systems and can be used for data-driven learning of arbitrary dynamical systems.

Yasamin Jalalian, Mostafa Samir, Boumediene Hamzi +2

Department of Computing and Mathematical Sciences, Caltech, CA, USA. · Beyond Limits, CA, USA. · The Alan Turing Institute, London, UK. +1

Dynamical Systems Nonlinear System Identification System Identification Kernel Methods Hamiltonian Dynamics

Sep 17, 2025cs.LG

A Compositional Kernel Model for Feature Learning

We study a compositional variant of kernel ridge regression in which the predictor is applied to a coordinate-wise reweighting of the inputs. Formulated as a variational problem, this model provides a tractable setting for studying feature learning in compositional architectures. From the perspective of variable selection, we show how relevant variables are recovered while noise variables are eliminated. We prove that both global minimizers and stationary points discard noise coordinates when the noise variables are Gaussian distributed. A central finding is that

\ell_1

-type kernels, such as the Laplace kernel, succeed in recovering features contributing to nonlinear effects at stationary points, whereas Gaussian kernels recover only linear ones.

Feng Ruan, Keli Liu, Michael Jordan

*Department of Statistics and Data Science, Northwestern University. · *Company E · *Department of Statistics and Computer Science, University of California, Berkeley.

Kernel Ridge Regression Kernel Regression Kernel Methods Feature Selection

Sep 14, 2025stat.ML

A Kernel-based Stochastic Approximation Framework for Nonlinear Operator Learning

We develop a stochastic approximation framework for learning nonlinear operators between infinite-dimensional spaces utilizing general Mercer operator-valued kernels. Our framework encompasses two key classes: (i) operator-valued kernels whose associated integral operators are compact and hence admit discrete spectral decompositions, and (ii) separable kernels of the form

K(x,x')=k(x,x')T

, where

k

is a scalar-valued kernel and

T

is a positive operator on the output space. This broad setting induces expressive vector-valued reproducing kernel Hilbert spaces (RKHSs) that generalize the classical

K=kI

paradigm, thereby enabling rich structural modeling with rigorous theoretical guarantees. To address target operators lying outside the RKHS, we introduce vector-valued interpolation spaces to precisely quantify misspecification error. Within this framework, we establish non-asymptotic convergence rates for prediction, estimation, and misspecification errors in the online and finite-horizon settings. Importantly, the framework also accommodates a range of operator learning settings, from Fredholm integral operators to encoder--decoder architectures. Numerical experiments on the two-dimensional Navier--Stokes equations illustrate the proposed approach.

Jia-Qi Yang, Lei Shi

School of Mathematical Sciences and Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China.

Stochastic Approximation Reproducing Kernel Hilbert Spaces Kernel Methods Operator Learning Statistical Learning Theory

Jun 25, 2025cs.LG

The kernel of graph indices for vector search

The most popular graph indices for vector search use principles from computational geometry to build the graph. Hence, their formal graph navigability guarantees are only valid in Euclidean space. In this work, we show that machine learning can be used to build graph indices for vector search in metric and non-metric vector spaces (e.g., for inner product similarity). From this novel perspective, we introduce the Support Vector Graph (SVG), a new type of graph index that leverages kernel methods to establish the graph connectivity and that comes with formal navigability guarantees valid in metric and non-metric vector spaces. In addition, we interpret the most popular graph indices, including HNSW and DiskANN, as particular specializations of SVG and show that new navigable indices can be derived from the principles behind this specialization. Finally, we propose SVG-L0 that incorporates an

\ell_0

sparsity constraint into the SVG kernel method to build graphs with a bounded out-degree. This yields a principled way of implementing this practical requirement, in contrast to the traditional heuristic of simply truncating the out edges of each node. Additionally, we show that SVG-L0 has a self-tuning property that avoids the heuristic of using a set of candidates to find the out-edges of each node and that keeps its computational complexity in check.

Mariano Tepper, Ted Willke

IBM WatsonX

Graph-Based Retrieval Kernel Methods Approximate Nearest Neighbor Search

Jun 20, 2025stat.ML

Gaussian Processes and Reproducing Kernel Hilbert Spaces: Connections and Equivalences

This monograph studies the relations between two approaches using positive definite kernels: probabilistic methods using Gaussian processes, and non-probabilistic methods using reproducing kernel Hilbert spaces (RKHS). They are widely studied and used in machine learning, statistics, and numerical analysis. We study connections and equivalences for fundamental topics such as regression, interpolation, numerical integration, distributional discrepancies, and statistical dependence, as well as sample path properties of Gaussian processes. A unifying perspective for these equivalences is established, based on the equivalence between the Gaussian Hilbert space and the RKHS. The monograph serves as a basis to bridge many other methods based on Gaussian processes and reproducing kernels, which are developed in parallel by the two research communities.

Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic +1

EURECOM · University of Tübingen, Tübingen AI Center Max Planck Institute for Intelligent Systems · Adelaide University Australian Institute for Machine Learning +1

Gaussian Processes Reproducing Kernel Hilbert Spaces Kernel Methods Gaussian Process Regression

May 21, 2025cs.LG

Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selection and Approximation

Out-of-Distribution (OoD) detection is vital for the reliability of deep neural networks, the key of which lies in effectively characterizing the disparities between OoD and In-Distribution (InD) data. In this work, such disparities are exploited through a fresh perspective of non-linear feature subspace. That is, a discriminative non-linear subspace is learned from InD features to capture representative patterns of InD, while informative patterns of OoD features cannot be well captured in such a subspace due to their different distribution. Grounded on this perspective, we exploit the deviations of InD and OoD features in such a non-linear subspace for effective OoD detection. To be specific, we leverage the framework of Kernel Principal Component Analysis (KPCA) to attain the discriminative non-linear subspace and deploy the reconstruction error on such subspace to distinguish InD and OoD data. Two challenges emerge: (i) the learning of an effective non-linear subspace, i.e., the selection of kernel function in KPCA, and (ii) the computation of the kernel matrix with large-scale InD data. For the former, we reveal two vital non-linear patterns that closely relate to the InD-OoD disparity, leading to the establishment of a Cosine-Gaussian kernel for constructing the subspace. For the latter, we introduce two techniques to approximate the Cosine-Gaussian kernel with significantly cheap computations. In particular, our approximation is further tailored by incorporating the InD data confidence, which is demonstrated to promote the learning of discriminative subspaces for OoD data. Our study presents new insights into the non-linear feature subspace for OoD detection and contributes practical explorations on the associated kernel design and efficient computations, yielding a KPCA detection method with distinctively improved efficacy and efficiency.

Kun Fang, Qinghua Tao, Mingzhen He +6

Department of Automation, Shanghai Jiao Tong University · Department of Electrical and Electronic Engineering, The Hong Kong Polytechnic University · School of Automation, Beijing Institute of Technology +2

Principal Component Analysis Kernel Methods OOD Detection

May 10, 2025stat.ML

Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction

The problem of using proximity (similarity or dissimilarity) data for the purpose of "adding a point to a vector diagram" was first studied by J.C. Gower in 1968. Since then, a number of methods -- mostly kernel methods -- have been proposed for solving what has come to be called the problem of out-of-sample embedding. We survey the various kernel methods that we have encountered and show that each can be derived from one or the other of two competing strategies: projection or restricted reconstruction. Projection can be analogized to a well-known formula for adding a point to a principal component analysis. Restricted reconstruction poses a different challenge: how to best approximate redoing the entire multivariate analysis while holding fixed the vector diagram that was previously obtained. This strategy results in a nonlinear optimization problem that can be simplified to a unidimensional search. Various circumstances may warrant either projection or restricted reconstruction.

Michael W. Trosset, Kaiyi Tan, Minh Tang +1

Department of Statistics, Indiana University. · Department of Statistics, North Carolina State University. · Department of Applied Mathematics & Statistics, Johns Hopkins University.

Kernel Methods Dimensionality Reduction

Mar 21, 2025quant-ph

Benign Overfitting with Quantum Kernels

Kernel methods compare inputs through feature maps. Quantum kernels follow the same principle: input data are encoded into quantum states, which define quantum feature representations in Hilbert spaces. Kernel values are then obtained by estimating inner products between these states using suitable quantum circuit measurements. As a result, quantum kernels may be intractable to compute classically while remaining efficiently computable on quantum hardware, potentially leading to a quantum advantage. However, designing effective quantum kernels remains a major challenge. Many quantum kernels, such as the fidelity kernel, suffer from exponential concentration. This results in near-identity kernel matrices that fail to capture meaningful data correlations and lead to overfitting and poor generalization. In this paper, we propose a novel strategy for constructing quantum kernels that achieve good generalization performance, drawing inspiration from benign overfitting in classical machine learning. We introduce the concept of Local-Global quantum kernels, which combine two components: a local quantum kernel based on measurements of small subsystems, and a global quantum kernel derived from full-system measurements. To support the effectiveness of the proposed construction, we show theoretically and empirically that Local-Global quantum kernels exhibit benign overfitting.

Joachim Tomasi, Sandrine Anthoine, Hachem Kadri

Aix-Marseille Univ, CNRS, LIS, Marseille, France. · Aix Marseille Univ, CNRS, I2M, Marseille, France.

Benign Overfitting Quantum Machine Learning Quantum Kernel Methods Kernel Methods

Feb 16, 2025quant-ph

Physics-Informed Support Vector Kernels via Green-Function Analogies and Jackson-Chebyshev Spectral Design

Kernel selection for regression of physical observables is often heuristic. We investigate a physics-informed strategy in which functional forms and spectral structures associated with Green's functions motivate kernel selection without requiring an exact identification between a machine-learning kernel and a physical propagator. The principal construction is a Jackson-damped Chebyshev kernel inspired by the kernel polynomial method (KPM); its explicit feature map yields a positive-semidefinite Gram matrix by construction and provides an inspectable spectral prior for structured observables. We evaluate standard and custom SVR models on copper-conductivity proxies, local Dirac-like band dispersion, quartic-oscillator energy levels, photonic-crystal transmission, and Fibonacci-chain transmission using repeated nested validation, learning curves, random-forest and multilayer-perceptron baselines, and low-rank Nyström tests where relevant. The framework is intended for finite-data regression of precomputed observables while boundary conditions remain part of the physical model that generates those observables.

Nan-Hong Kuo, Renata Wong

Department of Physics, National Taiwan University, Taipei, Taiwan · Department of Artificial Intelligence, Chang Gung University, Taoyuan, Taiwan · Department of Neurology, Chang Gung Memorial Hospital, Keelung, Taiwan +1

Support Vector Machines Kernel Methods Physics-Informed ML Spectral Methods

Jan 18, 2025stat.ML

Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer

The principal objective of this work is twofold within nonparametric regression settings: (1) to establish the minimax optimal convergence rates for fixed-bandwidth Gaussian kernel spectral algorithms when the true regression function resides in a Sobolev space, and (2) to apply Gaussian spectral algorithms for achieving robust and adaptive transfer learning under concept shift. While minimax optimality of misspecified spectral algorithms has been established, existing guarantees are typically restricted to the non-saturation regime. We demonstrate that the infinite smoothness of fixed-bandwidth Gaussian kernels provides universal robustness to model misspecification by showing that this kernel choice enables any spectral algorithm to attain minimax optimal rates, provided the regularization parameter decays exponentially. This result effectively decouples optimality from the algorithm's inherent qualification. Building on this, we then advocate Gaussian spectral algorithms as powerful components in a learning framework for robust and adaptive transfer. Specifically, we derive the adaptive convergence rate of the excess risk for this framework and show that the rates are optimal up to logarithmic factors. Our results also reveal the impact of the magnitude of the concept shift and the sample size on the generalization error.

Haotian Lin, Matthew Reimherr

Department of Statistics, The Pennsylvania State University.

Spectral Regularization Concept Drift Transfer Learning Kernel Methods Spectral Methods Statistical Learning Theory

Oct 14, 2024math.NA

Which Spaces can be Embedded in $L_p$ -type Reproducing Kernel Banach Space? A Characterization via Metric Entropy

In this paper, we establish a novel connection between the metric entropy growth and the embeddability of function spaces into reproducing kernel Hilbert/Banach spaces. Metric entropy characterizes the information complexity of function spaces and has implications for their approximability and learnability. Classical results show that embedding a function space into a reproducing kernel Hilbert space (RKHS) implies a bound on its metric entropy growth. Surprisingly, we prove a \textbf{converse}: a bound on the metric entropy growth of a function space allows its embedding to a

L_p-

type Reproducing Kernel Banach Space (RKBS). This shows that the

{L}_p-

type RKBS provides a broad modeling framework for learnable function classes with controlled metric entropies. Our results shed new light on the power and limitations of kernel methods for learning complex function spaces.

Yiping Lu, Daozhe Lin, Qiang Du

Industrial Engineering & Management Sciences, Northwestern University · Department of Applied Physics & Applied Mathematics, Columbia University

Reproducing Kernel Hilbert Spaces Kernel Methods Statistical Learning Theory

Sep 13, 2024math.ST

Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent

We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy (

\mathsf{KSD}

) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of

N

particle locations and the

N

-fold product target measure, starting from a regular initial distribution, splits into a dominant negative part' proportional to $N$ times the expected $\mathsf{KSD}^2$ and a smaller positive part'. This observation leads to

\mathsf{KSD}

rates of order

1/\sqrt{N}

, in both continuous and discrete time, providing a near optimal (in the sense of matching the corresponding i.i.d. rates) double exponential improvement over the recent result by Shi and Mackey (2024). Under mild assumptions on the kernel and potential, these bounds also grow polynomially in the dimension

d

. By adding a bilinear component to the kernel, the above approach is used to further obtain Wasserstein-2 convergence in continuous time. For the case of `bilinear + Matérn' kernels, we derive Wasserstein-2 rates that exhibit a curse-of-dimensionality similar to the i.i.d. setting. We also obtain marginal convergence and long-time propagation of chaos results for the time-averaged particle laws.

Sayan Banerjee, Krishnakumar Balasubramanian, Promit Ghosal

Department of Statistics and Operations Research, University of North Carolina, Chapel Hill. · Department of Statistics, University of California, Davis. · Department of Statistics, University of Chicago.

Kernel Methods Variational Inference Stein Variational Gradient Descent Wasserstein Distance

May 12, 2024eess.SY

Nonparametric Control Koopman Operators

This paper presents a novel Koopman composition operator representation framework for control systems in reproducing kernel Hilbert spaces (RKHSs) that is free of explicit dictionary or input parametrizations. By establishing fundamental equivalences between different model representations, we are able to close the gap of control system operator learning and infinite-dimensional regression, enabling various empirical estimators and the connection to the well-understood learning theory in RKHSs under one unified framework. Consequently, our proposed framework allows for arbitrarily accurate finite-rank approximations in infinite-dimensional spaces and leads to finite-dimensional predictors without a priori restrictions to a finite span of functions or inputs. To enable applications to high-dimensional control systems, we improve the scalability of our proposed control Koopman operator estimates by utilizing sketching techniques. Numerical experiments demonstrate superior prediction accuracy compared to bilinear EDMD, especially in high dimensions. Finally, we show that our learned models are readily interfaced with linear-parameter-varying techniques for model predictive control.

Petar Bevanda, Bas Driessen, Lucian Cristian Iacob +3

Chair of Information-oriented Control, TU München, Germany · Control Systems Group, TU/e, Eindhoven, The Netherlands · Systems and Control Laboratory, HUNREN Institute for Computer Science and Control, Budapest, Hungary +2

Koopman Operator Learning System Identification Kernel Methods

Oct 18, 2023cs.LG

Consistent Distributed Ranking of Generative Models via Kernel Distances

Ranking generative models based on the fidelity and diversity of their outputs is required to identify the best generator in a group of candidate generative AI models. To rank a group of models in a conventional centralized setting, a standard score is commonly evaluated for each involved model. The selection and design of reference-based evaluation scores have been extensively studied in centralized settings, where the reference samples are drawn from a single probability distribution. However, in practical scenarios including distributed learning contexts, reference samples are distributed across multiple clients, each potentially with a heterogeneous data distribution. In this work, we investigate the ranking of generative models in such distributed settings with heterogeneous data distributions across clients. We focus on the widely used family of kernel distance (KD) evaluation metrics. We prove that, for every kernel function, ranking models by the averaged KD scores of individual clients yields the same ordering as a centralized KD evaluation using the combined reference data from all the clients. We further extend our analysis to other popular metrics, including the Fréchet Distance (FD), for which the individual client scores could be insufficient for accurate model ranking. We present the numerical results of several experiments on standard image datasets and generative models to validate our theoretical findings regarding distributed ranking using various evaluation scores.

Zixiao Wang, Farzan Farnia, Zhenghao Lin +2

Kernel Methods Image Generation Evaluation Generative AI Evaluation

Dec 23, 2018cs.LG

Distribution-Free Uncertainty Quantification for Kernel Methods by Gradient Perturbations

We propose a data-driven approach to quantify the uncertainty of models constructed by kernel methods. Our approach minimizes the needed distributional assumptions, hence, instead of working with, for example, Gaussian processes or exponential families, it only requires knowledge about some mild regularity of the measurement noise, such as it is being symmetric or exchangeable. We show, by building on recent results from finite-sample system identification, that by perturbing the residuals in the gradient of the objective function, information can be extracted about the amount of uncertainty our model has. Particularly, we provide an algorithm to build exact, non-asymptotically guaranteed, distribution-free confidence regions for ideal, noise-free representations of the function we try to estimate. For the typical convex quadratic problems and symmetric noises, the regions are star convex centered around a given nominal estimate, and have efficient ellipsoidal outer approximations. Finally, we illustrate the ideas on typical kernel methods, such as LS-SVC, KRR,

\varepsilon

-SVR and kernelized LASSO.

Balázs Csanád Csáji, Krisztián Balázs Kis

EPIC Centre of Excellence MTA SZTAKI: Institute for Computer Science and Control Hungarian Academy of Sciences, Budapest, Hungary

Confidence Region Estimation Uncertainty Quantification Kernel Methods

Date pendingquant-ph

Classical and quantum kernel fusion for two-sample testing

Two-sample tests have been extensively employed in various scientific fields and machine learning to discriminate whether two sets of samples come from the same distribution or not. Kernel-based procedures for hypothetical testing have been proposed to efficiently disentangle high-dimensional complex structures in data to obtain accurate results in a model-free way by embedding the data into the reproducing kernel Hilbert space (RKHS). While the choice of kernels plays a crucial role for their performance, little is understood about how to choose kernel especially for small datasets. Here we construct a hypothetical test which can be effective even for small datasets, based on the theoretical foundation of kernel-based tests using maximum mean discrepancy, which is called MMD-FUSE. We enhance the MMD-FUSE framework by incorporating quantum kernels and propose a novel hybrid testing strategy that fuses classical and quantum kernels. This approach creates a powerful and adaptive test by combining the domain-specific inductive biases of classical kernels with the unique expressive power of quantum kernels. We evaluate our method on various synthetic and real-world clinical datasets, and our experiments reveal two key findings: 1) With appropriate hyperparameter tuning, MMD-FUSE with quantum kernels consistently improves test power over classical counterparts, especially for small and high-dimensional data. 2) The proposed hybrid framework demonstrates remarkable robustness, adapting to different data characteristics and achieving high test power across diverse scenarios. These results highlight the potential of quantum-inspired and hybrid kernel strategies to build more effective statistical tests, offering versatile tools for data analysis where sample sizes are limited.

Yu Terada, Yugo Ogio, Ken Arai +2

Advanced Research Laboratory, Sony Group Corporation, 1-7-1 Konan, Minato-ku, Tokyo 108-0075, Japan · Deloitte Tohmatsu Consulting LLC.

Two-Sample Testing Maximum Mean Discrepancy Hybrid Quantum-Classical ML Quantum Kernel Methods Kernel Methods

Date pendingcs.LG

When do cheap embeddings beat protein language models? A theoretically-grounded hashing sketch for biological sequence classification

\textbf{Motivation:} Pre-trained protein language models (PLMs) such as ESM-2 have become the default representation for biological sequence tasks, but they are computationally heavy and require GPUs both for embedding and for fine-tuning. Whether they are actually necessary for sequence \emph{classification}, as opposed to structure prediction, is rarely tested against strong, principled, lightweight alternatives. This question has direct practical stakes for large-scale genomic surveillance, where embedding millions of sequences on commodity hardware is a recurring bottleneck.\ \textbf{Results:} We introduce Murmur2Vec, an alignment-free, training-free embedding that aggregates

k

-mer counts into a small hash table via the deterministic MurmurHash function, and we cast it as a randomized sketch of the classical

k

-mer spectrum kernel. We provide a complete theoretical treatment: closed-form bias/variance of the inner product, an unbiased signed variant with a Johnson--Lindenstrauss-type concentration bound, an excess-risk bound for downstream linear classifiers that makes the bias--variance trade-off in the hash-table size explicit, and an implicit-regularization mechanism by which collisions damage frequent non-discriminative

k

-mers more than rare lineage-defining ones. Across four classification tasks, SARS-CoV-2 spike lineage (22 classes), HIV-1 Env subtype (8 classes), and two protein-family benchmarks (8 and 6 classes), Murmur2Vec matches a LoRA-fine-tuned 650M-parameter ESM-2 model on the two tasks for which LoRA fine-tuning was run to convergence (SARS-CoV-2 and HIV-1) and ties frozen ESM-2 on the two protein-family tasks, and it \emph{outperforms} the fine-tuned model on the hardest task (SARS-CoV-2 lineage:

0.854

vs.\

0.807

accuracy; macro-F1

0.684

vs.\

0.401

).

Sarwan Ali, Taslim Murad, Imdadullah Khan +1

Columbia University, NY, USA · Institute of Business Administration, Karachi, Pakistan · Lahore University of Management Sciences, Lahore, Pakistan +1

Protein Language Models Randomized Sketching Kernel Methods Protein Representation Learning Sequence Modeling