Random Gegenbauer Features for Scalable Kernel Methods

• URL: http://arxiv.org/abs/2202.03474v1
• Date: Mon, 7 Feb 2022 19:30:36 GMT
• Title: Random Gegenbauer Features for Scalable Kernel Methods
• Authors: Insu Han, Amir Zandieh, Haim Avron
• Abstract summary: We propose efficient random features for approximating a new and rich class of kernel functions that we refer to as Generalized Zonal Kernels (GZK) Our proposed GZK family generalizes the zonal kernels by introducing factors in their Gegenbauer series expansion. We show that our proposed features outperform recent kernel approximation methods.
• Score: 11.370390549286757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose efficient random features for approximating a new and rich class of kernel functions that we refer to as Generalized Zonal Kernels (GZK). Our proposed GZK family, generalizes the zonal kernels (i.e., dot-product kernels on the unit sphere) by introducing radial factors in their Gegenbauer series expansion, and includes a wide range of ubiquitous kernel functions such as the entirety of dot-product kernels as well as the Gaussian and the recently introduced Neural Tangent kernels. Interestingly, by exploiting the reproducing property of the Gegenbauer polynomials, we can construct efficient random features for the GZK family based on randomly oriented Gegenbauer kernels. We prove subspace embedding guarantees for our Gegenbauer features which ensures that our features can be used for approximately solving learning problems such as kernel k-means clustering, kernel ridge regression, etc. Empirical results show that our proposed features outperform recent kernel approximation methods.

Related papers

• Optimal Kernel Choice for Score Function-based Causal Discovery [92.65034439889872]
  We propose a kernel selection method within the generalized score function that automatically selects the optimal kernel that best fits the data. We conduct experiments on both synthetic data and real-world benchmarks, and the results demonstrate that our proposed method outperforms kernel selection methods.
  arXiv  Detail & Related papers  (2024-07-14T09:32:20Z)
• On the Approximation of Kernel functions [0.0]
  The paper addresses approximations of the kernel itself. For the Hilbert Gauss kernel on the unit cube, the paper establishes an upper bound of the associated eigenfunctions. This improvement confirms low rank approximation methods such as the Nystr"om method.
  arXiv  Detail & Related papers  (2024-03-11T13:50:07Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• Improved Random Features for Dot Product Kernels [12.321353062415701]
  We make several novel contributions for improving the efficiency of random feature approximations for dot product kernels. We show empirically that the use of complex features can significantly reduce the variances of these approximations. We develop a data-driven optimization approach to improve random feature approximations for general dot product kernels.
  arXiv  Detail & Related papers  (2022-01-21T14:16:56Z)
• Hybrid Random Features [60.116392415715275]
  We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) HRFs automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest.
  arXiv  Detail & Related papers  (2021-10-08T20:22:59Z)
• Hida-Mat\'ern Kernel [8.594140167290098]
  We present the class of Hida-Mat'ern kernels, which is the canonical family of covariance functions over the entire space of stationary Gauss-Markov Processes. We show how to represent such processes as state space models using only the kernel and its derivatives. We also show how exploiting special properties of the state space representation enables improved numerical stability in addition to further reductions of computational complexity.
  arXiv  Detail & Related papers  (2021-07-15T03:25:10Z)
• 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)
• 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)
• Advanced Stationary and Non-Stationary Kernel Designs for Domain-Aware Gaussian Processes [0.0]
  We propose advanced kernel designs that only allow for functions with certain desirable characteristics to be elements of the reproducing kernel Hilbert space (RKHS) We will show the impact of advanced kernel designs on Gaussian processes using several synthetic and two scientific data sets.
  arXiv  Detail & Related papers  (2021-02-05T22:07:56Z)
• 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.