Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures

Abstract

In this paper, we attempt to solve a long-lasting open question for non-positive definite (non-PD) kernels in machine learning community: can a given non-PD kernel be decomposed into the difference of two PD kernels (termed as positive decomposition)? We cast this question as a distribution view by introducing the \emph{signed measure}, which transforms positive decomposition to measure decomposition: a series of non-PD kernels can be associated with the linear combination of specific finite Borel measures. In this manner, our distribution-based framework provides a sufficient and necessary condition to answer this open question. Specifically, this solution is also computationally implementable in practice to scale non-PD kernels in large sample cases, which allows us to devise the first random features algorithm to obtain an unbiased estimator. Experimental results on several benchmark datasets verify the effectiveness of our algorithm over the existing methods.

arXiv commentaccepted by AISTATS-2021

References in corpus (17)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• On Lazy Training in Differentiable Programming
• Randomized Nonlinear Component Analysis
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Convergence of Adversarial Training in Overparametrized Neural Networks
• The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
• On the Error of Random Fourier Features
• Quadrature-based features for kernel approximation
• But How Does It Work in Theory? Linear SVM with Random Features
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
• Learning Low-Dimensional Metrics
• Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Representation by Integrating Reproducing Kernels
• Probabilistic classifiers with low rank indefinite kernels