Kernel Methods

Ask about this topic

Overview

Kernel methods represent data through similarity functions, allowing linear algorithms in feature spaces to model nonlinear patterns without explicitly constructing those spaces. Common approaches include support vector machines and kernel ridge regression for prediction, Gaussian processes for uncertainty, and kernel mean embeddings and maximum mean discrepancy for comparing distributions and testing dependence. Researchers also use kernels to learn dynamical systems and operators, and scale computations with random features, Nyström approximations, and structured kernels. A central tension is balancing expressive, well-chosen kernels and reliable guarantees against the computation and sensitivity to kernel or bandwidth selection that can limit practical use.

Latest papers

CardsList

234 papers40 papers in the last four weeks, up 111% on the four weeks before. 0.2% of all new papers.

Dec 10, 2025

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

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 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.\ Results: We introduce Murmur2Vec, an alignment-free, training-free embedding that aggregates kk-mer counts into a small hash table via the deterministic MurmurHash function, and we cast it as a randomized sketch of the classical kk-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 kk-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 outperforms the fine-tuned model on the hardest task (SARS-CoV-2 lineage: 0.8540.854 vs.\ 0.8070.807 accuracy; macro-F1 0.6840.684 vs.\ 0.4010.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 ModelsRandomized SketchingKernel MethodsProtein Representation LearningSequence ModelingBioinformatics
AskPDF
Nov 26, 2025

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 TestingMaximum Mean DiscrepancyHybrid Quantum-Classical MLQuantum Kernel MethodsKernel Methods
AskPDF
Nov 5, 2025

Sparse, self-organizing ensembles of local kernels detect rare statistical anomalies

Modern artificial intelligence has revolutionized how we extract representations from scientific data, yet the statistical properties of these representations remain poorly controlled, causing misspecified anomaly detection methods to falter. The hardest anomalies to detect are the rare, weakly separable ones hiding within the nominal distribution-a regime that grows in importance as models mature and easily separable signals are exhausted. We identify structural desiderata for detection in this regime under minimal prior information: sparsity, to enforce parsimony; locality, to preserve geometric sensitivity; and competition, to promote efficient allocation of model capacity. These principles define a class of self-organizing local kernels that adaptively partition the representation space around regions of statistical imbalance. As an instantiation, we introduce SparKer, a sparse ensemble of Gaussian kernels trained in a semi-supervised Neyman-Pearson framework to locally model the likelihood ratio between a sample that may contain anomalies and an anomaly-free reference. We provide theoretical insights into the mechanisms driving detection and self-organization, and demonstrate the approach on realistic high-dimensional problems in scientific discovery, open-world novelty detection, intrusion detection, and generative-model validation. Ensembles of only a handful of kernels identify statistically significant anomalies in representation spaces of thousands of dimensions while remaining sensitive across regimes, underscoring the interpretability, efficiency, and scalability of the approach.

Gaia Grosso, Sai Sumedh R. Hindupur, Thomas Fel +3

NSF AI Institute for Artificial Intelligence and Fundamental Interactions, Cambridge, 02139, MA · Laboratory for Nuclear Science, Massachusetts Institute of Technology, Cambridge, 02139, MA · School of Engineering and Applied Sciences, Harvard University, Allston, 02134, MA +1

Kernel MethodsSemi-Supervised Anomaly DetectionStatistical Learning TheoryAnomaly Detection
AskPDF
Oct 27, 2025

Manifold Approximation leads to Robust Kernel Alignment

Centered kernel alignment (CKA) is a popular metric for comparing representations, determining equivalence of networks, and conducting neuroscience research. However, CKA does not account for the underlying manifold and relies on numerous heuristics that cause it to behave differently at different scales of data. In this work, we propose Manifold-approximated Kernel Alignment (MKA), which incorporates manifold geometry (i.e., local neighborhood) into the alignment task. We derive a theoretical framework for MKA. Our construction removes representation-dependent degree weighting, yields a closed-form alignment score, and gives each row a probabilistic interpretation as a local Markov transition distribution. We further establish kernel- and score-level stability with respect to the neighborhood size. We perform empirical evaluations on synthetic datasets and real-world examples to characterize and compare MKA to its contemporaries. In controlled synthetic experiments, MKA is consistently less sensitive to hyperparameters and captures the selected topology-preserving relationships. On the large-scale benchmark, MKA achieves its strongest aggregate performance in vision, is competitive on graphs, and is weaker than CKA in several NLP evaluations. Our findings suggest that manifold-aware kernel alignment provides a robust foundation for measuring representations and is potentially useful when local neighborhood geometry is important, with possible applications in representation learning.

Mohammad Tariqul Islam, Du Liu, Deblina Sarkar

MIT

Kernel MethodsRepresentational Similarity AnalysisNeural Representation Geometry
AskPDF
Oct 17, 2025

Theoretical Refinement of CLIP by Utilizing Linear Structure of Optimal Similarity

In this study, we propose an enhancement to the similarity computation mechanism in multimodal contrastive pretraining frameworks such as CLIP. Prior theoretical research has demonstrated that the optimal similarity metrics between paired modalities should correspond to the pointwise mutual information (PMI) between the two modalities. However, the current implementations of CLIP and its variants fail to fully utilize the underlying linear structure of PMI. We therefore propose KME-CLIP, which leverages this structure through the inner product in a reproducing kernel Hilbert space (RKHS). We theoretically prove that, under our assumptions, the KME-CLIP similarity can bring the contrastive loss arbitrarily close to its optimal value, which is attained by PMI, as the size of the point set grows, and we empirically evaluate KME-CLIP against CLIP and its kernel-based variants across several retrieval and classification tasks.

Naoki Yoshida, Satoshi Hayakawa, Yuhta Takida +3

The University of Tokyo · Sony Group Corporation · Sony AI

Cross-Modal LearningKernel Mean EmbeddingsMultimodal PretrainingCross-Modal RetrievalMultimodal ClassificationKernel Methods+2
AskPDF
Oct 16, 2025

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∗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 RegressionKernel MethodsStatistical Learning TheoryLearning Curves
AskPDF
Sep 21, 2025

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 SystemsNonlinear System IdentificationSystem IdentificationKernel MethodsHamiltonian Dynamics
AskPDF
Sep 17, 2025

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 ℓ1\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 RegressionKernel RegressionKernel MethodsFeature Selection
AskPDF
Sep 14, 2025

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′)TK(x,x')=k(x,x')T, where kk is a scalar-valued kernel and TT 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=kIK=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 ApproximationReproducing Kernel Hilbert SpacesKernel MethodsOperator LearningStatistical Learning Theory
AskPDF
Jul 31, 2025

Signature-Kernel One-Class Learning with Manifold Regularisation for Multivariate Time Series Anomaly Detection

One-class learning is an effective methodology for time series anomaly detection, yet kernel one-class approaches often compare sequences in a pointwise fashion and ignore the geometry of normal data. In this work, we present a manifold-regularised, large-margin ℓp\ell_p-support vector data description (ℓp\ell_p-SVDD) method that analyses sequences as paths via the signature kernel. By incorporating a a graph-Laplacian penalty into the ℓp\ell_p-SVDD objective function and utilising the representer theorem for manifold regularisation, we illustrate that the dual task retains the functional form of the original one with a modified kernel matrix. As such, existing Frank--Wolfe solvers can be applied unchanged. We show that this new modified kernel is a valid kernel matrix and under a generic norm bound on the discriminant, the proposed model yields a smaller Rademacher-complexity bound than the baseline. Furthermore, the signature kernel which is computed through a Goursat partial differential equation and can handle irregularly sampled data and is invariant to reparametrisation has not previously been used for one-class time series anomaly detection to the best of our knowledge. Our experiments on five widely used benchmarks, evaluated without point adjustment, demonstrate that the proposed approach compares very favourably with the state of the art approaches.

Shervin Rahimzadeh Arashloo

Department of Computer Engineering, Faculty of Engineering, Bilkent University, Ankara, Turkey.

Time-Series Anomaly DetectionOne-Class ClassificationKernel Methods
AskPDF
Jun 25, 2025

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 ℓ0\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 RetrievalKernel MethodsApproximate Nearest Neighbor Search
AskPDF
Jun 20, 2025

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 ProcessesReproducing Kernel Hilbert SpacesKernel MethodsGaussian Process Regression
AskPDF
May 21, 2025

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 AnalysisKernel MethodsOOD Detection
AskPDF
May 10, 2025

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.

Multidimensional ScalingKernel MethodsDimensionality Reduction
AskPDF
Mar 21, 2025

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 OverfittingQuantum Machine LearningQuantum Kernel MethodsKernel Methods
AskPDF
Feb 24, 2025

A Mechanistic Interpretation of Prescribed-Parameter Convolutional Kernels

Prescribed-parameter convolutional transforms achieve strong time series classification performance using fixed kernels, simple pooling operations, and a linear classifier. Their success raises a mechanistic question: which properties of the representation make this construction effective? We study the proportion of positive values (PPV), a pooling operator shared by ROCKET, MiniROCKET, and MultiROCKET. We establish exact invariance to circular translations under periodic boundaries and quantify departures from invariance under finite boundaries. A complementary analysis bounds the sensitivity of a smooth PPV surrogate. We then define the population pairwise geometry induced by a distribution of convolutional parameters and show how a finite random kernel bank concentrates around that geometry. This separates the role of the parameter distribution from the number of sampled kernels. Experiments on the UCR classification collection examine effective dimensionality, distance correlation with the input, and classification accuracy using PPV-only, unit-energy ROCKET kernels. Increasing kernel count produces diminishing representational gains. Increasing kernel length generally raises effective dimensionality and distance correlation, while the best test performance occurs at intermediate lengths and training accuracy remains close to perfect. Together, these results support an interpretation in which nonlinear pooling creates a richer but structured representation that can favour linear separation, while further representational richness need not improve generalisation.

Jorge Marco Blanco, Rubén Cuevas Rumín

Universidad Carlos III de Madrid, Spain · UC3M-Santander Big Data Institute, Spain

Time Series ClassificationKernel Methods
AskPDF
Feb 16, 2025

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 MachinesKernel MethodsPhysics-Informed MLSpectral Methods
AskPDF
Jan 18, 2025

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 RegularizationConcept DriftTransfer LearningKernel MethodsSpectral MethodsStatistical Learning Theory
AskPDF
Oct 29, 2024

Conditional Moment Kernels: Joint Modeling of Expected Returns and Covariances in Unbalanced Panels

We propose the conditional moment kernel (CMK), a joint model of the conditional mean and covariance matrix of asset returns given their characteristics. A single kernel function of the characteristics gives the means and second moments of all returns. The implied covariance matrices are positive semidefinite for any number and composition of assets, so the model applies directly to unbalanced panels. Its estimation is a convex program whose size does not depend on the number of assets. A floor at the scale of the idiosyncratic noise keeps the estimated systematic covariance away from zero where the data cannot resolve it, and a trace penalty selects the number of factors. A closed form, the CMK estimator, approximates the solution. For fixed features and hyper-parameters, we prove identification, consistency and finite-sample bounds. In out-of-sample tests on US stocks from 1972 to 2021, the CMK estimator fits the conditional moments significantly better than instrumented principal component analysis (IPCA) with the same characteristics. Almost all of the gain is in the covariance matrix, and nonlinear functions of the characteristics add to it. The implied unconditionally mean--variance efficient portfolios earn annualized Sharpe ratios of 4.0 to 5.1 before costs, close to those of IPCA and declining over time.

Damir Filipovic, Paul Schneider

École Polytechnique Fédérale de Lausanne and Swiss Finance Institute · Università della Svizzera italiana and Swiss Finance Institute

Quantitative FinanceCovariance EstimationKernel Methods
AskPDF
Oct 14, 2024

Which Spaces can be Embedded in LpL_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 converse: a bound on the metric entropy growth of a function space allows its embedding to a Lp−L_p-type Reproducing Kernel Banach Space (RKBS). This shows that the Lp−{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 SpacesKernel MethodsStatistical Learning Theory
AskPDF
Sep 13, 2024

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 (KSD\mathsf{KSD}) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of NN particle locations and the NN-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 KSD\mathsf{KSD} rates of order 1/N1/\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 dd. 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 MethodsVariational InferenceStein Variational Gradient DescentWasserstein Distance
AskPDF
May 12, 2024

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 LearningSystem IdentificationKernel Methods
AskPDF
Oct 18, 2023

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 MethodsImage Generation EvaluationGenerative AI Evaluation
AskPDF
Dec 23, 2018

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 EstimationUncertainty QuantificationKernel Methods
AskPDF