Sampling-based Nystr\"om Approximation and Kernel Quadrature

• URL: http://arxiv.org/abs/2301.09517v3
• Date: Tue, 23 May 2023 01:18:39 GMT
• Title: Sampling-based Nystr\"om Approximation and Kernel Quadrature
• Authors: Satoshi Hayakawa, Harald Oberhauser, Terry Lyons
• Abstract summary: We analyze the Nystr"om approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nystr"om approximation with i.i.d. sampling and singular-value decomposition. We then introduce a refined selection of subspaces in Nystr"om approximation with theoretical guarantees that is applicable to non-i.i.d. landmark points.
• Score: 8.658596218544774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the Nystr\"om approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nystr\"om approximation with i.i.d. sampling and singular-value decomposition in the continuous regime; the proof techniques are borrowed from statistical learning theory. We further introduce a refined selection of subspaces in Nystr\"om approximation with theoretical guarantees that is applicable to non-i.i.d. landmark points. Finally, we discuss their application to convex kernel quadrature and give novel theoretical guarantees as well as numerical observations.

Related papers

• 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)
• Provable convergence guarantees for black-box variational inference [19.421222110188605]
  Black-box variational inference is widely used in situations where there is no proof that its optimization succeeds. We provide rigorous guarantees that methods similar to those used in practice converge on realistic inference problems.
  arXiv  Detail & Related papers  (2023-06-04T11:31:41Z)
• Local optimisation of Nystr\"om samples through stochastic gradient descent [32.53634754382956]
  We consider an unweighted variation of the squared-kernel discrepancy criterion as a surrogate for the classical criteria used to assess the Nystr"om approximation accuracy. We perform numerical experiments which demonstrate that the local minimisation of the radial SKD yields Nystr"om samples with improved Nystr"om approximation accuracy.
  arXiv  Detail & Related papers  (2022-03-24T18:17:27Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Positively Weighted Kernel Quadrature via Subsampling [8.250374560598495]
  We study kernel quadrature rules with positive weights for probability measures on general domains. This results in effective algorithms to construct kernel quadrature rules with positive weights and small worst-case error.
  arXiv  Detail & Related papers  (2021-07-20T16:18:56Z)
• 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)
• Fast Statistical Leverage Score Approximation in Kernel Ridge Regression [12.258887270632869]
  Nystr"om approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems. We propose a linear time (modulo poly-log terms) algorithm to accurately approximate the statistical leverage scores in the stationary- Kernel-based KRR.
  arXiv  Detail & Related papers  (2021-03-09T05:57:08Z)
• Nonparametric Score Estimators [49.42469547970041]
  Estimating the score from a set of samples generated by an unknown distribution is a fundamental task in inference and learning of probabilistic models. We provide a unifying view of these estimators under the framework of regularized nonparametric regression. We propose score estimators based on iterative regularization that enjoy computational benefits from curl-free kernels and fast convergence.
  arXiv  Detail & Related papers  (2020-05-20T15:01:03Z)
• Diversity sampling is an implicit regularization for kernel methods [13.136143245702915]
  We show that Nystr"om kernel regression with diverse landmarks increases the accuracy of the regression in sparser regions of the dataset. A greedy is also proposed to select diverse samples of significant size within large datasets when exact DPP sampling is not practically feasible.
  arXiv  Detail & Related papers  (2020-02-20T08:24:42Z)

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.