Feature maps for the Laplacian kernel and its generalizations

Recent applications of kernel methods in machine learning have seen a renewed interest in the Laplacian kernel, due to its stability to the bandwidth hyperparameter in comparison to the Gaussian kernel, as well as its expressivity being equivalent to that of the neural tangent kernel of deep fully connected networks. However, unlike the Gaussian kernel, the Laplacian kernel is not separable. This poses challenges for techniques to approximate it, especially via the random Fourier features (RFF) methodology and its variants. In this work, we provide random features for the Laplacian kernel and its two generalizations: Mat\'{e}rn kernel and the Exponential power kernel. We provide efficiently implementable schemes to sample weight matrices so that random features approximate these kernels. These weight matrices have a weakly coupled heavy-tailed randomness. Via numerical experiments on real datasets we demonstrate the efficacy of these random feature maps.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-02-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2502.15575arXiv 2502.15575
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Average gradient outer product as a mechanism for deep neural collapse

  2024cited by this paper
• More is Better: when Infinite Overparameterization is Optimal and Overfitting is Obligatory

  2024cited by this paper
• Emergence in non-neural models: grokking modular arithmetic via average gradient outer product

  2024cited by this paper
• The fast committor machine: Interpretable prediction with kernels

  2024cited by this paper
• Mechanism for feature learning in neural networks and backpropagation-free machine learning models

  2024cited by this paper
• Toward Large Kernel Models

  2023cited by this paper
• Orthogonal Random Features: Explicit Forms and Sharp Inequalities

  2023cited by this paper
• Synthetic Lethality Screening with Recursive Feature Machines

  2023cited by this paper
• Benign, Tempered, or Catastrophic: Toward a Refined Taxonomy of Overfitting

  2022cited by this paper
• On the Inconsistency of Kernel Ridgeless Regression in Fixed Dimensions

  2022cited by this paper
• Improved Random Features for Dot Product Kernels

  2022cited by this paper
• A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors

  2022cited by this paper
• Deep learning: a statistical viewpoint

  2021cited by this paper
• Correspondence of NNGP Kernel and the Matern Kernel

  2021cited by this paper
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond

  2020cited by this paper
• On the Similarity between the Laplace and Neural Tangent Kernels

  2020cited by this paper
• Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS

  2020cited by this paper
• A simple proof of the characteristic function of Student’s t-distribution

  2019cited by this paper
• Linearized two-layers neural networks in high dimension

  2019cited by this paper
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve

  2019cited by this paper
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks

  2018cited by this paper
• Quadrature-based features for kernel approximation

  2018cited by this paper
• To understand deep learning we need to understand kernel learning

  2018cited by this paper
• Kernel Machines Beat Deep Neural Networks on Mask-based Single-channel Speech Enhancement

  2018cited by this paper
• Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

  2018cited by this paper
• The Geometry of Random Features

  2018cited by this paper
• Gaussian Process Behaviour in Wide Deep Neural Networks

  2018cited by this paper
• Kernel Machines That Adapt To Gpus For Effective Large Batch Training

  2018cited by this paper
• Gaussian Quadrature for Kernel Features

  2017cited by this paper
• The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

  2017cited by this paper
• Deep Neural Networks as Gaussian Processes

  2017cited by this paper
• Linearized GMM Kernels and Normalized Random Fourier Features

  2016cited by this paper
• Structured adaptive and random spinners for fast machine learning computations

  2016cited by this paper
• Orthogonal Random Features

  2016influential reference
• Recycling Randomness with Structure for Sublinear time Kernel Expansions

  2016cited by this paper
• Random Feature Mapping with Signed Circulant Matrix Projection

  2015cited by this paper
• On the Error of Random Fourier Features

  2015cited by this paper
• On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

  2015cited by this paper
• Fastfood: Approximate Kernel Expansions in Loglinear Time

  2014cited by this paper
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results

  2013cited by this paper
• Random Feature Maps for Dot Product Kernels

  2012cited by this paper
• Scikit-learn: Machine Learning in Python

  2011cited by this paper
• Support vector machines

  2008cited by this paper
• IEEE Standard for Floating-Point Arithmetic

  2008cited by this paper
• Random Features for Large-Scale Kernel Machines

  2007influential reference
• Multivariate stable densities and distribution functions: general and elliptical case

  2005cited by this paper
• Multivariate T-Distributions and Their Applications

  2004cited by this paper
• Stable Distributions. Models for Heavy Tailed Data

  2001influential reference
• A Generalized Representer Theorem

  2001cited by this paper
• Correction to: "On the Chambers–Mallows–Stuck Method for Simulating Skewed Stable Random Variables"

  1996cited by this paper
• Stable Non-Gaussian Random Processes : Stochastic Models with Infinite Variance

  1995cited by this paper
• On the characteristic function of multivariate Student t‐distribution

  1986cited by this paper
• A Method for Simulating Stable Random Variables

  1976cited by this paper
• Introduction to Fourier analysis on Euclidean spaces (PMS-32)

  1972cited by this paper
• Handbook of Mathematical Functions with Formulas, Graphs,

  1971cited by this paper
• Fourier Analysis on Groups.

  1965influential reference

• No citing papers are available for this paper.