Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
- URL: http://arxiv.org/abs/2006.00247v3
- Date: Tue, 9 Feb 2021 14:20:54 GMT
- Title: Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
- Authors: Fanghui Liu, Xiaolin Huang, Yingyi Chen, and Johan A.K. Suykens
- Abstract summary: We cast this question as a distribution view by introducing the emphsigned measure
A series of non-PD kernels can be associated with the linear combination of specific finite Borel measures.
Specifically, this solution is also computationally implementable in practice to scale non-PD kernels in large sample cases.
- Score: 31.986482149142503
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- On the Sublinear Regret of GP-UCB [58.25014663727544]
We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates.
Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
arXiv Detail & Related papers (2023-07-14T13:56:11Z) - Plug-and-Play split Gibbs sampler: embedding deep generative priors in
Bayesian inference [12.91637880428221]
This paper introduces a plug-and-play sampling algorithm that leverages variable splitting to efficiently sample from a posterior distribution.
It divides the challenging task of posterior sampling into two simpler sampling problems.
Its performance is compared to recent state-of-the-art optimization and sampling methods.
arXiv Detail & Related papers (2023-04-21T17:17:51Z) - Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
We propose a Monte Carlo PDE solver for training unsupervised neural solvers.
We use the PDEs' probabilistic representation, which regards macroscopic phenomena as ensembles of random particles.
Our experiments on convection-diffusion, Allen-Cahn, and Navier-Stokes equations demonstrate significant improvements in accuracy and efficiency.
arXiv Detail & Related papers (2023-02-10T08:05:19Z) - Coefficient-based Regularized Distribution Regression [4.21768682940933]
We consider the coefficient-based regularized distribution regression which aims to regress from probability measures to real-valued responses over a kernel reproducing Hilbert space (RKHS)
Asymptotic behaviors of the algorithm in different regularity ranges of the regression function are comprehensively studied.
We get the optimal rates under some mild conditions, which matches the one-stage sampled minimax optimal rate.
arXiv Detail & Related papers (2022-08-26T03:46:14Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
We show that a phenomenon can be precisely characterized in the context of kernel methods.
We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
arXiv Detail & Related papers (2022-02-28T13:01:04Z) - 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) - Sparse Spectrum Warped Input Measures for Nonstationary Kernel Learning [29.221457769884648]
We propose a general form of explicit, input-dependent, measure-valued warpings for learning nonstationary kernels.
The proposed learning algorithm warps inputs as conditional Gaussian measures that control the smoothness of a standard stationary kernel.
We demonstrate a remarkable efficiency in the number of parameters of the warping functions in learning problems with both small and large data regimes.
arXiv Detail & Related papers (2020-10-09T01:10:08Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data.
We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem.
In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
arXiv Detail & Related papers (2020-06-11T19:40:38Z) - Distributed, partially collapsed MCMC for Bayesian Nonparametrics [68.5279360794418]
We exploit the fact that completely random measures, which commonly used models like the Dirichlet process and the beta-Bernoulli process can be expressed as, are decomposable into independent sub-measures.
We use this decomposition to partition the latent measure into a finite measure containing only instantiated components, and an infinite measure containing all other components.
The resulting hybrid algorithm can be applied to allow scalable inference without sacrificing convergence guarantees.
arXiv Detail & Related papers (2020-01-15T23:10:13Z) - Randomly Projected Additive Gaussian Processes for Regression [37.367935314532154]
We use additive sums of kernels for GP regression, where each kernel operates on a different random projection of its inputs.
We prove this convergence and its rate, and propose a deterministic approach that converges more quickly than purely random projections.
arXiv Detail & Related papers (2019-12-30T07:26:18Z)
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.