A general technique for approximating high-dimensional empirical kernel matrices

• URL: http://arxiv.org/abs/2511.03892v1
• Date: Wed, 05 Nov 2025 22:36:52 GMT
• Title: A general technique for approximating high-dimensional empirical kernel matrices
• Authors: Chiraag Kaushik, Justin Romberg, Vidya Muthukumar,
• Abstract summary: We present user-friendly bounds for the expected operator norm of a random kernel matrix on the kernel function $k(cdot,cdot)$.<n>We then apply our method to provide new, tighter approximations for inner-product kernel matrix on general high-dimensional data.
• Score: 16.583173656638806
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present simple, user-friendly bounds for the expected operator norm of a random kernel matrix under general conditions on the kernel function $k(\cdot,\cdot)$. Our approach uses decoupling results for U-statistics and the non-commutative Khintchine inequality to obtain upper and lower bounds depending only on scalar statistics of the kernel function and a ``correlation kernel'' matrix corresponding to $k(\cdot,\cdot)$. We then apply our method to provide new, tighter approximations for inner-product kernel matrices on general high-dimensional data, where the sample size and data dimension are polynomially related. Our method obtains simplified proofs of existing results that rely on the moment method and combinatorial arguments while also providing novel approximation results for the case of anisotropic Gaussian data. Finally, using similar techniques to our approximation result, we show a tighter lower bound on the bias of kernel regression with anisotropic Gaussian data.

Related papers

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Gaussian Process Regression under Computational and Epistemic Misspecification [4.5656369638728656]
  In large data applications, computational costs can be reduced using low-rank or sparse approximations of the kernel. This paper investigates the effect of such kernel approximations on the element error.
  arXiv  Detail & Related papers  (2023-12-14T18:53:32Z)
• Local Random Feature Approximations of the Gaussian Kernel [14.230653042112834]
  We focus on the popular Gaussian kernel and on techniques to linearize kernel-based models by means of random feature approximations. We show that such approaches yield poor results when modelling high-frequency data, and we propose a novel localization scheme that improves kernel approximations and downstream performance significantly.
  arXiv  Detail & Related papers  (2022-04-12T09:52:36Z)
• How Good are Low-Rank Approximations in Gaussian Process Regression? [28.392890577684657]
  We provide guarantees for approximate Gaussian Process (GP) regression resulting from two common low-rank kernel approximations. We provide experiments on both simulated data and standard benchmarks to evaluate the effectiveness of our theoretical bounds.
  arXiv  Detail & Related papers  (2021-12-13T04:04:08Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
  arXiv  Detail & Related papers  (2020-07-13T17:39:35Z)
• Sparse Gaussian Processes via Parametric Families of Compactly-supported Kernels [0.6091702876917279]
  We propose a method for deriving parametric families of kernel functions with compact support. The parameters of this family of kernels can be learned from data using maximum likelihood estimation. We show that these approximations incur minimal error over the exact models when modeling data drawn directly from a target GP.
  arXiv  Detail & Related papers  (2020-06-05T20:44:09Z)
• How Good are Low-Rank Approximations in Gaussian Process Regression? [24.09582049403961]
  We provide guarantees for approximate Gaussian Process (GP) regression resulting from two common low-rank kernel approximations. We provide experiments on both simulated data and standard benchmarks to evaluate the effectiveness of our theoretical bounds.
  arXiv  Detail & Related papers  (2020-04-03T14:15:10Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)

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.