Feature maps for the Laplacian kernel and its generalizations

• URL: http://arxiv.org/abs/2502.15575v1
• Date: Fri, 21 Feb 2025 16:36:20 GMT
• Title: Feature maps for the Laplacian kernel and its generalizations
• Authors: Sudhendu Ahir, Parthe Pandit,
• Abstract summary: Unlike the Gaussian kernel, the Laplacian kernel is not separable.<n>We provide random features for the Laplacian kernel and its two generalizations.<n>We demonstrate the efficacy of these random feature maps on real datasets.
• Score: 3.671202973761375
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• A mixture representation of the spectral distribution of isotropic kernels with application to random Fourier features [0.0]
  We show that the spectral distribution of every positive definite isotropic kernel can be decomposed as a scale mixture of $alpha$-stable random vectors.<n>This constructive decomposition provides a simple and ready-to-use spectral sampling formula for every multivariate positive definite shift-invariant kernel.<n>This result has broad applications for support vector machines, kernel ridge regression, Gaussian processes, and other kernel-based machine learning techniques.
  arXiv  Detail & Related papers  (2024-11-05T03:28:01Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Variable Hyperparameterized Gaussian Kernel using Displaced Squeezed Vacuum State [2.1408617023874443]
  A multimode coherent state can generate the Gaussian kernel with a constant value of hyper parameter. This constant hyper parameter has limited the application of the Gaussian kernel when it is applied to complex learning problems. We realize the variable hyper parameterized kernel with a multimode-displaced squeezed vacuum state.
  arXiv  Detail & Related papers  (2024-03-18T08:25:56Z)
• Orthogonal Random Features: Explicit Forms and Sharp Inequalities [5.8317379706611385]
  We analyze the bias and the variance of the kernel approximation based on orthogonal random features. We provide explicit expressions for these quantities using normalized Bessel functions.
  arXiv  Detail & Related papers  (2023-10-11T10:40:43Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• Tanimoto Random Features for Scalable Molecular Machine Learning [2.5112706394511766]
  We propose two kinds of novel random features to allow the Tanimoto kernel to scale to large datasets. We show that these random features are effective at approximating the Tanimoto coefficient of real-world datasets.
  arXiv  Detail & Related papers  (2023-06-26T16:11:11Z)
• Kernel Continual Learning [117.79080100313722]
  kernel continual learning is a simple but effective variant of continual learning to tackle catastrophic forgetting. episodic memory unit stores a subset of samples for each task to learn task-specific classifiers based on kernel ridge regression. variational random features to learn a data-driven kernel for each task.
  arXiv  Detail & Related papers  (2021-07-12T22:09:30Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Taming Nonconvexity in Kernel Feature Selection---Favorable Properties of the Laplace Kernel [77.73399781313893]
  A challenge is to establish the objective function of kernel-based feature selection. The gradient-based algorithms available for non-global optimization are only able to guarantee convergence to local minima.
  arXiv  Detail & Related papers  (2021-06-17T11:05:48Z)
• Kernel Identification Through Transformers [54.3795894579111]
  Kernel selection plays a central role in determining the performance of Gaussian Process (GP) models. This work addresses the challenge of constructing custom kernel functions for high-dimensional GP regression models. We introduce a novel approach named KITT: Kernel Identification Through Transformers.
  arXiv  Detail & Related papers  (2021-06-15T14:32:38Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network. We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
  arXiv  Detail & Related papers  (2021-04-03T09:08:12Z)
• Flow-based Kernel Prior with Application to Blind Super-Resolution [143.21527713002354]
  Kernel estimation is generally one of the key problems for blind image super-resolution (SR) This paper proposes a normalizing flow-based kernel prior (FKP) for kernel modeling. Experiments on synthetic and real-world images demonstrate that the proposed FKP can significantly improve the kernel estimation accuracy.
  arXiv  Detail & Related papers  (2021-03-29T22:37:06Z)
• On the Similarity between the Laplace and Neural Tangent Kernels [26.371904197642145]
  We show that NTK for fully connected networks is closely related to the standard Laplace kernel. Our results suggest that much insight about neural networks can be obtained from analysis of the well-known Laplace kernel.
  arXiv  Detail & Related papers  (2020-07-03T09:48:23Z)
• Scaling up Kernel Ridge Regression via Locality Sensitive Hashing [6.704115928005158]
  We introduce a weighted version of random binning features and show that the corresponding kernel function generates smooth Gaussian processes. We show that our weighted random binning features provide a spectral approximation to the corresponding kernel matrix, leading to efficient algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2020-03-21T21:41:16Z)

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.