New method reduces variance and bias in approximating indefinite kernels.
problem Approximating non-stationary indefinite kernels with low variance and bias.
method Generalized orthogonal random features (GORF)
result GORF achieves lower variance and approximation error compared to existing methods.
Paper improves kernel approximations for better statistical learning.
problem Improving kernel approximations for better statistical learning.
method Taylor series approximations of radial kernel functions.
result Establishes upper bounds for eigenfunctions, leading to better approximations.
Gaussian process regression generally does not scale to beyond a few thousands data points without applying some sort of kernel approximation method. Most approximations focus on the high eigenvalue part of the spectrum of the kernel matrix, K, which leads to bad performance when the length scale of the kernel is sma…
Paper develops a new kernel approximation framework.
problem High time and space complexity of kernel methods for large datasets.
method Perturbation-based kernel approximation framework using classical perturbation theory.
result Framework generalizes and improves upon existing methods.
New method improves Gaussian kernel approximations for high-frequency data.
problem Limited scalability of kernel-based models to large data sets.
method Local random feature approximations using Maclaurin expansions and polynomial sketches.
result Significant improvement in kernel approximations and downstream performance for high-frequency data.
SRF improves kernel approximation and GP regression performance.
problem Efficient kernel approximation and Bayesian kernel learning in large-scale regression problems.
method Stein variational gradient descent to generate high-quality random features and approximate spectral measure posteriors.
result SRF outperforms traditional approaches in kernel approximation and GP regression.
New algorithm speeds up polynomial kernel approximations.
problem Efficiently approximating polynomial kernels of high degree.
method Oblivious sketching combined with novel sampling.
result Polynomial factor slowdown removed in running time.
Improved Nyström approximation for kernel quadrature with theoretical guarantees.
problem Efficiently approximating positive definite kernels for large datasets.
method Refined sampling and subspace selection in Nyström approximation.
result Novel theoretical guarantees for non-i.i.d. landmark points in kernel quadrature.
We give a short proof of a strong version of the short time asymptotic expansion of heat kernels associated to Laplace type operators acting on sections of vector bundles over compact Riemannian manifolds, including exponential decay of the difference of the approximate heat kernel and the true heat kernel. We use this…
We consider the problem of improving kernel approximation via randomized feature maps. These maps arise as Monte Carlo approximation to integral representations of kernel functions and scale up kernel methods for larger datasets. Based on an efficient numerical integration technique, we propose a unifying approach that…
New RFs reduce kernel approximation variance and improve Transformer performance.
problem Efficient approximation of Gaussian and softmax kernels for kernel methods and Transformers.
method Parameterized, positive, non-trigonometric RFs optimized for variance reduction.
result Significant variance reduction in practice, outperforming previous methods.
Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed tha…
Improves learning of spectral mixture kernels with approximate Bayesian inference.
problem Difficult optimization of large number of SM kernel parameters.
method Approximate Bayesian inference using variational distribution of spectral points and random Fourier features.
result Accelerates convergence and leads to better optimal parameters.
Orthogonal random features approximate a Bessel kernel, offering sharper bounds than random Fourier features.
problem Approximating Gaussian kernel efficiently for large datasets.
method Use of Haar orthogonal matrices to construct orthogonal random features and analyze their bias and variance.
result Orthogonal random features approximate a Bessel kernel, not the Gaussian kernel, with sharper bounds.
We provide bounds for kernel matrices and new approximations for high-dimensional data.
problem Approximating high-dimensional empirical kernel matrices.
method Decoupling results for U-statistics and non-commutative Khintchine inequality.
result New tighter approximations for inner-product kernel matrices.
Nyström KPCA balances computational efficiency and statistical accuracy.
problem Computational burden in large sample situations for kernel methods.
method Theoretical analysis of Nyström approximate kernel principal component analysis (KPCA).
result Nyström approximate KPCA matches statistical performance of non-approximate KPCA while being computationally beneficial.
The paper examines how kernel approximations affect Gaussian process regression in large data applications.
problem Effect of kernel approximations on Gaussian process regression in large data applications.
method Unified framework to analyze Gaussian process regression under computational and epistemic misspecification.
result Theoretical analysis of Gaussian process regression under various misspecifications.
Kernel approximation via nonlinear random feature maps is widely used in speeding up kernel machines. There are two main challenges for the conventional kernel approximation methods. First, before performing kernel approximation, a good kernel has to be chosen. Picking a good kernel is a very challenging problem in its…
Deep ReLU networks approximate as well as shallow ones in kernel regimes.
problem Understanding the limitations of kernel methods for deep ReLU networks.
method Characterizing eigenvalue decays of kernels derived from deep ReLU networks.
result Deep ReLU networks and shallow two-layer networks have equivalent approximation properties in kernel regimes.
Random Fourier features (RFF) represent one of the most popular and wide-spread techniques in machine learning to scale up kernel algorithms. Despite the numerous successful applications of RFFs, unfortunately, quite little is understood theoretically on their optimality and limitations of their performance. Only recen…
Improved kernel ridge regression for large datasets using weighted random binning.
problem Efficiently approximating kernel matrices for large-scale datasets.
method Introduced weighted random binning features for locality sensitive hashing.
result Weighted random binning features generate Gaussian processes of any desired smoothness.
We study the problem of column selection in large-scale kernel canonical correlation analysis (KCCA) using the Nyström approximation, where one approximates two positive semi-definite kernel matrices using "landmark" points from the training set. When building low-rank kernel approximations in KCCA, previous work mostl…
Kernel k-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear k-means clustering algorithm. However, kernel k-means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel …
Improves efficiency of random feature approximations for dot product kernels.
problem Efficiency of random feature approximations for dot product kernels.
method Generalization of existing random feature approximations using complex-valued random features, theoretical analysis of variances, data-driven optimization approach.
result Complex-valued random features can significantly reduce the variances of approximations.
Positive definite kernels and their associated Reproducing Kernel Hilbert Spaces provide a mathematically compelling and practically competitive framework for learning from data. In this paper we take the approximation theory point of view to explore various aspects of smooth kernels related to their inferential proper…
Unified quadrature framework for large-scale kernel machines.
problem Efficiently approximating kernel functions for large-scale machine learning.
method Deterministic and randomized interpolatory rules for numerical integration of kernel functions.
result The proposed method reduces the number of nodes needed for accurate kernel approximation.
Develops multifactor approximations for SVEs with completely monotone kernels.
problem Approximating SVEs with kernels of completely monotone type.
method Multifactor approximation, Euler discretization, L2-estimation, convergence analysis. result New multifactor Euler scheme reduces computational cost and outperforms SVEs for option pricing.
We investigate how to train kernel approximation methods that generalize well under a memory budget. Building on recent theoretical work, we define a measure of kernel approximation error which we find to be more predictive of the empirical generalization performance of kernel approximation methods than conventional me…
Efficient and accurate low-rank approximations of multiple data sources are essential in the era of big data. The scaling of kernel-based learning algorithms to large datasets is limited by the O(n^2) computation and storage complexity of the full kernel matrix, which is required by most of the recent kernel learning a…
New approximative kernels improve PDE-G-CNNs for geometric deep learning.
problem Inaccurate approximations of exact kernels in PDE-G-CNNs.
method Developed new approximative kernels that work regardless of spatial anisotropy.
result New kernels provide better error estimates and maintain reflectional symmetries.
Paper improves clustering risk bounds for kernel k-means.
problem Improving clustering risk bounds for kernel k-means.
method Analyzes kernel k-means and Nyström approximation.
result Achieves nearly optimal excess clustering risk bound.
Conditional diffusion models can approximate target distributions well with Gaussian-mixture reverse kernels.
problem Approximating target distributions in conditional diffusion models.
method Using finite Gaussian mixtures with ReLU-network logits as reverse kernels, reducing the problem to static conditional density approximation.
result The resulting neural reverse-kernel class is dense in conditional KL divergence under exact terminal matching.
Kernel methods are powerful learning methodologies that allow to perform non-linear data analysis. Despite their popularity, they suffer from poor scalability in big data scenarios. Various approximation methods, including random feature approximation, have been proposed to alleviate the problem. However, the statistic…
Nystrom approximation speeds up kernel model training.
problem Slow convergence in kernel models due to poor conditioning.
method Spectral preconditioning with Nystrom approximation for scalability.
result Nystrom approximation accelerates gradient descent nearly as well as exact preconditioner.
Accelerated RPCholesky speeds up kernel matrix approximations.
problem Efficiently approximating large kernel matrices.
method Accelerated randomly pivoted Cholesky (RPCholesky) with block matrix computations and rejection sampling.
result Approximates kernel matrices up to 40 times faster.
Paper explores Fisher-Rao gradient flows and their kernel approximations.
problem Understanding and analyzing approximations of Fisher-Rao gradient flows.
method Rigorous investigation of Fisher-Rao and Wasserstein type gradient flows, focusing on kernel approximations.
result Proves evolutionary Γ-convergence for kernel-approximated Fisher-Rao flows, providing theoretical guarantees.
New probabilistic complexity measures for linear and kernel methods.
problem Limitations of linear and kernel methods in machine learning.
method Introducing approximate notions of dimensional and margin complexity.
result Approximate complexity measures are both sufficient and necessary for learning.
A novel Laplace-approximated Bayesian Tensor Network Kernel Machine (LA-TNKM) provides principled uncertainty estimates.
problem How to provide principled uncertainty estimates for tensor network kernel machines.
method Employing a linearized Laplace approximation for Bayesian inference.
result Consistently matches or surpasses Gaussian Processes and BNNs across diverse UCI regression benchmarks.
The study assesses low-rank approximations in Gaussian Process regression.
problem Improving Gaussian Process regression efficiency with low-rank approximations.
method Analyzes two low-rank approximations: random Fourier features and Mercer expansion truncation.
result Bounds on the divergence and error between exact and approximate GP models.
This study approximates neural network features for modeling relations and attention mechanisms.
problem Approximating neural network features for modeling relations and attention mechanisms.
method Analyzes inner products of multi-layer perceptrons for universal approximation of symmetric and asymmetric relation functions.
result Universal approximation of relation functions and attention mechanisms using inner products of neural networks.
Stochastic gradient descent optimizes Nyström samples for kernel matrix approximation.
problem Optimizing Nyström samples for kernel matrix approximation.
method Stochastic gradient descent applied to multisets of landmark points (Nyström samples) using a surrogate criterion (radial SKD).
result Local minimization of the radial SKD yields improved Nyström approximation accuracy.
Novel confidence intervals improve convergence rates for sparse kernel-based models.
problem High computational cost in kernel-based learning models.
method Novel confidence intervals for Nyström method and sparse variational Gaussian process approximation.
result Improved performance bounds in regression and optimization problems.
Efficiently approximates statistical leverage scores for faster KRR.
problem Accurately estimating statistical leverage scores for fast KRR.
method Analytic formula for statistical leverage scores, leveraging kernel spectral density.
result Linear time approximation with theoretical guarantees, significantly faster than existing methods.
RPCholesky approximates kernel matrices with few evaluations.
problem Approximating kernel matrices efficiently.
method Randomly pivoted partial Cholesky factorization.
result RPCholesky provides nearly optimal low-rank approximations.
Kernel means are frequently used to represent probability distributions in machine learning problems. In particular, the well known kernel density estimator and the kernel mean embedding both have the form of a kernel mean. Unfortunately, kernel means are faced with scalability issues. A single point evaluation of the …
HRFs adaptively linearize kernels for accurate approximations.
problem Linearizing softmax and Gaussian kernels for machine learning applications.
method Generalizes Bochner's Theorem for kernels, uses random features for compositional kernels.
result Strong theoretical guarantees and unbiased approximation with smaller relative errors.
Improved kernel herding algorithm for faster quadrature rule convergence.
problem Slow convergence speed of standard kernel herding algorithm.
method Improved gradient approximation to obtain sparser solutions.
result The cosine of the angle between negative gradient and approximate gradient determines convergence speed.
Paper bounds the minimal rank for kernel ridge regression approximations.
problem Efficient memory and computation for kernel ridge regression.
method Lower bound on minimal rank for reliable prediction power.
result Nyström method's computational cost is almost linear in sample size.