Random Fourier Features for Asymmetric Kernels

• URL: http://arxiv.org/abs/2209.08461v1
• Date: Sun, 18 Sep 2022 03:39:18 GMT
• Title: Random Fourier Features for Asymmetric Kernels
• Authors: Mingzhen He and Fan He and Fanghui Liu and Xiaolin Huang
• Abstract summary: We introduce a complex measure with the real and imaginary parts corresponding to four finite positive measures, which expands the application scope of the Bochner theorem. This framework allows for handling classical symmetric, PD kernels via one positive measure; symmetric, non-positive definite kernels via signed measures; and asymmetric kernels via complex measures. Our AsK-RFFs method is empirically validated on several typical large-scale datasets and achieves promising kernel approximation performance.
• Score: 24.20121243104385
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The random Fourier features (RFFs) method is a powerful and popular technique in kernel approximation for scalability of kernel methods. The theoretical foundation of RFFs is based on the Bochner theorem that relates symmetric, positive definite (PD) functions to probability measures. This condition naturally excludes asymmetric functions with a wide range applications in practice, e.g., directed graphs, conditional probability, and asymmetric kernels. Nevertheless, understanding asymmetric functions (kernels) and its scalability via RFFs is unclear both theoretically and empirically. In this paper, we introduce a complex measure with the real and imaginary parts corresponding to four finite positive measures, which expands the application scope of the Bochner theorem. By doing so, this framework allows for handling classical symmetric, PD kernels via one positive measure; symmetric, non-positive definite kernels via signed measures; and asymmetric kernels via complex measures, thereby unifying them into a general framework by RFFs, named AsK-RFFs. Such approximation scheme via complex measures enjoys theoretical guarantees in the perspective of the uniform convergence. In algorithmic implementation, to speed up the kernel approximation process, which is expensive due to the calculation of total mass, we employ a subset-based fast estimation method that optimizes total masses on a sub-training set, which enjoys computational efficiency in high dimensions. Our AsK-RFFs method is empirically validated on several typical large-scale datasets and achieves promising kernel approximation performance, which demonstrate the effectiveness of AsK-RFFs.

Related papers

• Nonparametric estimation of Hawkes processes with RKHSs [1.775610745277615]
  This paper addresses nonparametric estimation of nonlinear Hawkes processes, where the interaction functions are assumed to lie in a reproducing kernel space (RKHS) Motivated by applications in neuroscience, the model allows complex interaction functions, in order to express exciting and inhibiting effects, but also a combination of both. It shows that our method achieves a better performance compared to related nonparametric estimation techniques and suits neuronal applications.
  arXiv  Detail & Related papers  (2024-11-01T14:26:50Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Posterior Contraction Rates for Mat\'ern Gaussian Processes on Riemannian Manifolds [51.68005047958965]
  We show that intrinsic Gaussian processes can achieve better performance in practice. Our work shows that finer-grained analyses are needed to distinguish between different levels of data-efficiency.
  arXiv  Detail & Related papers  (2023-09-19T20:30:58Z)
• Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence [65.63201894457404]
  We propose a novel non-parametric learning paradigm for the identification of drift and diffusion coefficients of non-linear differential equations. The key idea essentially consists of fitting a RKHS-based approximation of the corresponding Fokker-Planck equation to such observations.
  arXiv  Detail & Related papers  (2023-05-24T20:43:47Z)
• Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data [22.59079286063505]
  We study the statistical inference of nonlinear approximation algorithms utilizing a single trajectory of Markovian data. Our methodology has practical applications in various scenarios, such as Gradient Descent (SGD) on autoregressive data and asynchronous Q-Learning.
  arXiv  Detail & Related papers  (2023-02-15T14:31:11Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Revisiting Memory Efficient Kernel Approximation: An Indefinite Learning Perspective [0.8594140167290097]
  Matrix approximations are a key element in large-scale machine learning approaches. We extend MEKA to be applicable not only for shift-invariant kernels but also for non-stationary kernels. We present a Lanczos-based estimation of a spectrum shift to develop a stable positive semi-definite MEKA approximation.
  arXiv  Detail & Related papers  (2021-12-18T10:01:34Z)
• 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)
• Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs [3.3504365823045044]
  We study the problem of maximum a posteriori (MAP) inference for determinantal point processes defined by a nonsymmetric kernel matrix. We obtain the first multiplicative approximation guarantee for this problem using local search. Our approximation factor of $kO(k)$ is nearly tight, and we show theoretically and experimentally that it compares favorably to the state-of-the-art methods for this problem.
  arXiv  Detail & Related papers  (2021-02-10T09:34:44Z)
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines [35.32894170512829]
  We develop a quadrature framework for large-scale kernel machines via a numerical integration representation. We leverage fully symmetric interpolatory rules to efficiently compute quadrature nodes and associated weights for kernel approximation.
  arXiv  Detail & Related papers  (2020-11-03T12:48:07Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.