PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Bounds for Kernel Quadrature

A. Cloninger, Q. T. Le Gia, H. N. Mhaskar

arXiv:2609.00553v1math.NA

TL;DR

Kernel methods face prohibitive Gram-matrix storage and computation, while random feature sampling can be inadequate for spectral approximation. The paper develops deliberately constructed quadrature features with spectral error bounds and tests them across Gaussian and neural tangent kernels. The reported results show substantially better eigenvalue approximation than random features, including faster convergence and near-zero spectral error with few points in representative experiments.

  • Problem

    Kernel methods require O(M^2) memory and up to O(M^3) computation, while random-feature Monte Carlo error decays at N^-1/2 and may require more features than data points for spectral guarantees.

  • Method

    The paper replaces random sampling of the integral representation with finitely supported quadrature measures that integrate a chosen function subspace exactly, and derives spectral error bounds.

  • Results

    Well-designed quadrature formulas substantially improve kernel eigenvalue estimation over random features across Gaussian and spherical neural tangent kernel examples.

  • Takeaways & Limitations

    Quadrature features can deliver stronger spectral fidelity with fewer stored points, including near-zero spectral error with only a handful of points per dimension in reported experiments.

  • Takeaways & Limitations

    The analysis assumes that the feature map G is known and defines the kernel from that feature map.

Abstract

from arXiv · show

A bottleneck in the theory of kernel methods in machine learning is the storage requirement. To ameliorate this, a standard trick is to replace the kernel with an explicit feature map. Perhaps, the most well known example is the Gaussian kernel which can be expressed in terms of the Fourier features. Analytically, the kernel $K$ can be expressed in terms of an integral expression that involves a possibly asymmetric kernel $G$ representing the feature map. Numerically, one needs to approximate this integral by a suitable numerical integration scheme, typically Monte Carlo. In this paper, we demonstrate that the eigenvalues of $K$ are approximated much better by the eigenvalues of the kernel obtained by discretizing the integral using suitable quadrature formulas instead. We illustrate this fact in the case of the Gaussian kernel and neural tangent kernels on the unit sphere of a four-dimensional Euclidean space corresponding to the sigmoid and ReLU activation functions.

1. Introduction

Kernel methods offer strong nonlinear learning but scale poorly because Gram-matrix storage and computation grow quadratically and cubically with dataset size. This paper argues that deliberately constructed quadrature features can provide more faithful spectral approximations than random features while reducing storage.

  • Motivation: Kernel methods require O(M^2) memory and up to O(M^3) time for naive Gram-matrix operations on M data points.This creates a prohibitive bottleneck for modern datasets.
  • Motivation: Explicit feature maps replace kernel evaluation with inner products in N-dimensional features, enabling linear rather than quadratic dependence on M.The approximation quality depends on the numerical integration rule used to construct the features.
  • Limitations of random features: Random Fourier Features achieve O(N^-1/2) pointwise Monte Carlo error, but pointwise accuracy does not ensure spectral approximation of the kernel matrix.Spectral guarantees can require N to exceed M, eliminating the storage advantage.
  • Quadrature approach: The paper replaces random sampling with finitely supported quadrature measures that integrate selected function subspaces exactly and studies the resulting spectral error.The central question is how spectral error depends on the quadrature rule.
  • Quadrature approach: Quadrature error can be governed by feature approximation quality, becoming exponentially fast for analytic features instead of remaining subject to the Monte Carlo N^-1/2 ceiling.Structured domains can also achieve target accuracy with fewer, better-placed points.
  • Theory and scope: A general bound reduces spectral kernel approximation to approximation of features by the exactly integrated subspace and yields operator inequalities below a specified error threshold.The framework applies to Fourier features, arc-cosine kernels, and neural-network-inspired settings.
  • Theory and scope: Quadrature retains a spectral advantage for non-smooth features: Leaky ReLU errors decay exponentially, while standard ReLU converges more slowly but faster than random features.Random-feature error can remain large or even increase as features are added.
  • Practical implementation: Product quadrature grids reduce Fourier-feature storage from O(Mn^q) to O(Mqn), making compact feature sets practical in higher dimensions.Per-coordinate factorization recovers inner products without storing the full feature tensor.

2. Main results

The paper formulates spectral kernel approximation through finitely supported quadrature measures that exactly integrate a chosen function subspace. It bounds eigenvalue and operator errors using the approximation quality of the feature functions.

  • Setup: A kernel K is represented by integrating products of feature functions G(w, x)G(w, y) against a measure µ∗.
  • Setup: The approximation replaces µ∗ with a finitely supported measure ν and defines the approximating kernel through the resulting finite sum.
  • Quadrature construction: Quadrature requires exact integration over a subspace V, while products of functions in V generally lie outside V.
  • Main theorem: Theorem 2.1 bounds the spectral error for Gram matrices generated from a quadrature measure supported on N points.
  • Main theorem: ε = 4(1 + |ν|)M|||G|||ϵ(V ) bounds every eigenvalue discrepancy: max 1≤j≤M |σj −τj| ≤ε.
  • Main theorem: The same ε bounds the spectral norm of K − bK and yields the operator inequality (1 −∆)(K + λI) ≪ bK + λI ≪ (1 + ∆)(K + λI).

3. Fourier features

The paper formulates Fourier-feature construction as quadrature of Gaussian-weighted integrals and uses tensor Gauss–Hermite rules to approximate kernel spectra. These rules can achieve much faster spectral-error decay than random Fourier features while exploiting grid structure for storage savings.

  • 3. Fourier features: The quadrature framework uses Hermite functions and Gauss–Hermite nodes and weights to discretize the Gaussian-weighted feature integral.The Hermite basis is orthonormal, and the degree-n rule integrates the corresponding approximation space.
  • 3. Fourier features: Tensor-product quadrature features can be stored in O(Mqn) space instead of the naive O(Mn^q), because the quadrature points lie on a Cartesian grid.The grid allows feature weights to be represented as a tensor indexed by data point, coordinate, and one-dimensional quadrature node.
  • 3. Fourier features: The experiments compare eigenvalue discrepancies and spectral scores for quadrature and random features across feature counts and data-set sizes.The spectral score measures how far associated matrix differences are from being positive semi-definite.
  • 3. Fourier features: Quadrature spectral error decays exponentially for almost any (λ, ∆) and is often exactly 0 by n = 10, whereas random Fourier error remains quite large by n = 15.The comparison uses M = 1000 Gaussian-sampled points in q = 5 with bandwidth σ = 1 and complex-exponential features.

4. The arc-cosine kernel on the unit sphere

The paper constructs quadrature measures for arc-cosine kernels restricted to the unit sphere, reducing spherical integration to structured angular and polynomial quadrature. The S3 construction combines equally spaced angular nodes with Gauss–Legendre and Chebyshev components.

  • 4. The arc-cosine kernel on the unit sphere: Arc-cosine kernels are defined from truncated powers of inner-product-related quantities, including the special order-zero case.The section introduces the kernel family before restricting inputs to the sphere.
  • 4. The arc-cosine kernel on the unit sphere: On the sphere, points are parameterized by angles, allowing the surface integral to be expressed through angular variables and spherical measures.For S3, the substitution z = cos(θ2) converts one angular factor into a polynomial-weighted integral.
  • 4. The arc-cosine kernel on the unit sphere: The proposed spherical quadrature measure is finitely supported and integrates spherical polynomials of degree less than 2n exactly.Its support size is N = #supp(ν).
  • 4. The arc-cosine kernel on the unit sphere: The construction follows a two-formula approach after an initial FFT along θ1, rather than using ultraspherical formulas for every dimension.This is presented as a modification of an earlier spherical quadrature construction.
  • 4. The arc-cosine kernel on the unit sphere: For S3, the quadrature uses equally spaced θ1 nodes, Gauss–Legendre zeros and weights in θ2, and Chebyshev points in θ3.The resulting rule is defined as a quadrature for continuous functions on S3 and represented by a finite measure.

5. Numerical experiments on S3

Numerical experiments on S3 compare quadrature and randomly selected feature measures for arc-cosine and related kernels. The reported spectral-score comparison favors quadrature for the smoother kernel K1.

  • 5. Numerical experiments on S3: The experiments generate scattered points on S3, construct K0 and its quadrature and random-feature approximations, and compute eigenvalue discrepancies.Random points use an equal-weight finite measure with the same support size as the quadrature measure.
  • 5. Numerical experiments on S3: The S3 experiments evaluate both K0 and K1 with equal quadrature and random support sizes, including N = 134400 in Table 3.Random experiments are repeated 100 times and averaged values are reported.
  • 5. Numerical experiments on S3: Additional experiments fix M = 500 while varying the number of quadrature points, and also vary M and quadrature size in larger experiments.Tables 4 and 5 report comparisons for K0 and K1.
  • 5. Numerical experiments on S3: For the smoother kernel K1, the quadrature spectral score is better than the score from random points.Figures 2 and 3 compare scores as the number of quadrature points changes for K0 and K1.
  • 5. Numerical experiments on S3: The very smooth kernel Kg is evaluated using spectral scores SM for quadrature points and SR for random points against a degree-n = 60 reference kernel.The experiments use M = 1000 data points.

6. Conclusion

The conclusion revisits the storage and computation costs of kernel Gram matrices and reports that designed quadrature formulas improve eigenvalue estimation relative to random features. The examples cover Gaussian kernels and spherical neural tangent kernels.

  • 6. Conclusion: Kernel methods require M^2 storage and up to O(M^3) time for operations on the Gram matrix [K(x_i, x_j)]^M_i,j=1.Explicit feature maps are used to avoid this high complexity.
  • 6. Conclusion: Systematic use of well-designed quadrature formulas yields a substantial improvement in estimating kernel eigenvalues compared with random features.The conclusion frames this as the paper’s central demonstrated result.
  • 6. Conclusion: The theory is illustrated for the Gaussian kernel with Gauss–Hermite quadrature and for spherical neural tangent kernels with a tensor-product quadrature formula.The spherical examples concern kernels associated with the unit-sphere setting.
Loading 2609.00553v1…