Kernel quadrature with randomly pivoted Cholesky
- URL: http://arxiv.org/abs/2306.03955v3
- Date: Thu, 7 Dec 2023 16:52:34 GMT
- Title: Kernel quadrature with randomly pivoted Cholesky
- Authors: Ethan N. Epperly and Elvira Moreno
- Abstract summary: This paper presents new quadrature rules for functions in a reproducing kernel Hilbert space using nodes drawn by a sampling algorithm known as randomly pivoted Cholesky.
Results show that randomly pivoted Cholesky is fast and achieves comparable quadrature error rates to more computationally expensive quadrature schemes.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents new quadrature rules for functions in a reproducing
kernel Hilbert space using nodes drawn by a sampling algorithm known as
randomly pivoted Cholesky. The resulting computational procedure compares
favorably to previous kernel quadrature methods, which either achieve low
accuracy or require solving a computationally challenging sampling problem.
Theoretical and numerical results show that randomly pivoted Cholesky is fast
and achieves comparable quadrature error rates to more computationally
expensive quadrature schemes based on continuous volume sampling, thinning, and
recombination. Randomly pivoted Cholesky is easily adapted to complicated
geometries with arbitrary kernels, unlocking new potential for kernel
quadrature.
Related papers
- Hybrid model of the kernel method for quantum computers [0.0]
We propose a hybrid learning method based on classic kernel methods and a quantum algorithm for the calculation of internal products between vectors of continuous values.
As a test case, we applied this new algorithm to learn to classify whether new points generated randomly, in a finite square located under a plane, were found inside or outside a circle located inside this square.
It was found that the algorithm was able to correctly detect new points in 99% of the samples tested, with a small difference due to considering the radius slightly larger than the ideal.
arXiv Detail & Related papers (2024-10-29T16:49:03Z) - Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
We propose a scalable algorithm for sampling random realizations of the prior and posterior of GP models.
The proposed algorithm leverages inducing points approximation with sparse grids, as well as additive Schwarz preconditioners.
arXiv Detail & Related papers (2024-08-01T00:19:36Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms.
The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
arXiv Detail & Related papers (2022-02-26T19:10:48Z) - 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) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z) - 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) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning.
Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms.
We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
arXiv Detail & Related papers (2020-07-01T18:43:32Z) - 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) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems.
We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms.
Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
arXiv Detail & Related papers (2020-02-21T17:45:32Z)
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.