PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

Francis Bach

arXiv:1502.06800v2cs.LGmath.NAstat.ML

TL;DR

The paper asks how kernel quadrature and random feature expansions relate and how many samples are needed for accurate approximation. It establishes an always-available kernel decomposition, derives eigenvalue-based upper and lower bounds, and applies them to quadrature, function approximation, and learning with random features. The results recover Sobolev-space bounds, extend to L2- and L∞-approximation, and improve the number of random features needed to preserve generalization guarantees for Lipschitz-continuous losses.

  • Problem

    High-dimensional integration and random-feature representations require accurate approximation using as few function evaluations or features as possible.

  • Method

    The paper identifies kernel quadrature as a random feature expansion under an always-existing positive-definite-kernel decomposition and analyzes sample complexity through integral-operator eigenvalues.

  • Results

    The resulting upper and lower approximation bounds match up to logarithmic terms, with the upper bound achieved by i.i.d. samples from a specific non-uniform distribution and the lower bound valid for any point set.

  • Takeaways & Limitations

    The framework recovers Sobolev quadrature bounds, matches known special-case results for L2- and L∞-function approximation, and improves the random-feature count needed to preserve learning generalization guarantees.

  • Takeaways & Limitations

    The distribution used for the upper bound is typically hard to compute and sample from, although an approximation algorithm is given.

Abstract

from arXiv · show

We show that kernel-based quadrature rules for computing integrals can be seen as a special case of random feature expansions for positive definite kernels, for a particular decomposition that always exists for such kernels. We provide a theoretical analysis of the number of required samples for a given approximation error, leading to both upper and lower bounds that are based solely on the eigenvalues of the associated integral operator and match up to logarithmic terms. In particular, we show that the upper bound may be obtained from independent and identically distributed samples from a specific non-uniform distribution, while the lower bound if valid for any set of points. Applying our results to kernel-based quadrature, while our results are fairly general, we recover known upper and lower bounds for the special cases of Sobolev spaces. Moreover, our results extend to the more general problem of full function approximations (beyond simply computing an integral), with results in L2- and L$\infty$-norm that match known results for special cases. Applying our results to random features, we show an improvement of the number of random features needed to preserve the generalization guarantees for learning with Lipschitz-continuous losses.

1. Introduction

The paper connects kernel quadrature with random feature expansions and analyzes approximation complexity through integral-operator eigenvalues. It applies this framework to quadrature, function approximation, and random features.

  • Motivation: High-dimensional quadrature approximates integrals from as few well-chosen function evaluations as possible, including potentially noisy values.The paper focuses on quadrature rules for important computational problems such as Bayesian inference and complex-system analysis.
  • Contributions: Kernel quadrature is a special random feature expansion arising from a decomposition that exists for every positive definite kernel.The connection interprets optimized quadrature weights as decomposing a function into specially chosen random features.
  • Contributions: Upper and lower sample-complexity bounds depend only on integral-operator eigenvalues and match up to logarithmic terms.The upper bound uses i.i.d. samples from a specific non-uniform distribution, whereas the lower bound applies to any point set.
  • Applications: The framework recovers known upper and lower bounds for kernel quadrature in Sobolev spaces.This applies the general eigenvalue-based analysis to a recognized special case.
  • Applications: The results extend to full function approximation in L2- and L∞-norms, matching known results for special cases.The extension goes beyond computing a single integral.
  • Applications: The analysis improves the number of random features needed to preserve generalization guarantees for learning with Lipschitz-continuous losses.This is the paper’s random-feature application.

2. Random Feature Expansions of Positive Definite Kernels

This section develops the RKHS, integral-operator, spectral, and random-feature structures used to represent positive definite kernels. It connects feature decompositions to square roots of the integral operator and frames approximation through L2 error and feature sampling.

  • Reproducing kernel Hilbert spaces and integral operators: A continuous positive definite kernel defines a separable reproducing kernel Hilbert space F, with function evaluations represented as inner products with kernel evaluations.The RKHS is assumed contained in and dense in L2(dρ), under integrability of x 7→k(x,x).
  • Reproducing kernel Hilbert spaces and integral operators: The integral operator Σ on L2(dρ) is self-adjoint, positive semidefinite, and trace-class, while Σ1/2 provides an isometric representation of F.For f = Σ1/2g, the RKHS norm satisfies ∥f∥F = ∥g∥L2(dρ).
  • Spectral properties: The Mercer decomposition supplies an orthonormal basis and non-increasing positive eigenvalues that characterize RKHS functions through coefficient decay.The eigenvalue sequence depends on both the kernel k and the distribution dρ.
  • Kernels as expectations: A random-feature representation writes k(x,y) as the expectation of ϕ(v,x)ϕ(v,y), with v sampled according to dτ.The scalar feature ϕ(v,x) induces the corresponding one-dimensional feature dot product.
  • Kernels as expectations: The feature operator T satisfies Σ = TT*, so random-feature decompositions correspond to square roots of the integral operator; the positive self-adjoint square root yields the quadrature equivalence.The paper seeks improved approximation by selecting a better sampling distribution and optimized weights, evaluated in L2(dρ).

3. Quadrature in RKHSs

The section formulates RKHS quadrature as approximating integrals from evaluations at selected points, then connects its error to random-feature approximation through a kernel-specific decomposition. It also situates quadrature relative to column sampling and extends the formulation toward full function approximation.

  • 3. Quadrature in RKHSs: Quadrature approximates integrals of functions in an RKHS using evaluations at selected points and coefficients that may depend on the integrand but not the function being integrated.The goal is to minimize the approximation error while using as few function evaluations as possible.
  • 3. Quadrature in RKHSs: Standard Monte Carlo samples points i.i.d. from dρ, uses α_i = g(x_i)/n, and yields error decreasing as 1/√n.For g = 1, the resulting error corresponds to a metric between dρ and its empirical distribution.
  • 3. Quadrature in RKHSs: The paper instead considers sampling points from a distribution with density q relative to dρ, while noise robustness is characterized through importance-weighted coefficients β_i = α_i q(x_i)^1/2.Under the stated noise condition, tolerance to noise is characterized by the ℓ2-norm of β.
  • 3.2 Reformulation as random features: Using the isometry Σ^1/2, the kernel is represented as an inner product of functions ψ, making quadrature error an instance of random-feature approximation with V = X and ϕ = ψ.This decomposition is always possible, although it generally lacks a closed-form expression.
  • 3.3 Relationship with column sampling: Quadrature and column sampling differ in their error measures and objectives: column sampling targets kernel-matrix approximation or prediction, whereas this paper studies approximation properties.The two frameworks are not equivalent because the column-sampling formulation uses a Dirac function that is not in L2(dρ).
  • 3. Quadrature in RKHSs: The framework extends beyond integration to full function approximation, including L2- and L∞-norm errors and cases where the target belongs to a strict subspace of the RKHS.The paper relates quadrature uniformly over L2(dρ) functions to full approximation from n point evaluations.

4. Theoretical Analysis

The analysis gives eigenvalue-based sample-complexity bounds for random feature and quadrature approximations, with optimized sampling achieving near-matching guarantees and extensions to Sobolev spaces and full function approximation.

  • General bounds: The theory provides generic upper bounds and matching lower bounds up to logarithmic terms for approximating the unit ball of the feature space.Upper bounds use specific sampling distributions, while lower bounds apply to any set of points.
  • General bounds: For a target squared error 4λ, sampling from density q requires, up to logarithmic terms, at most a constant times dmax(q, λ) samples.The bound is stated for fixed q and λ and depends on the chosen sampling density.
  • Optimized distribution: The optimized distribution yields guarantees governed by the degrees of freedom d(λ)=tr Σ(Σ+λI)^−1, which depends only on the integral operator.This sample guarantee is shared across all square-root feature expansions, although computational practicality can differ.
  • Eigenvalue decay: For polynomial eigenvalue decay µm=O(m−2s), n samples give non-squared errors proportional to (log n)^s n−s; geometric decay gives geometric errors.The achieved error is determined by eigenvalues evaluated around m=O(n/log(n)).
  • Sobolev spaces: For Sobolev spaces, eigenvalue decay m−2s/d yields approximation error n−s/d, recovering known bounds up to logarithmic terms.The result applies independently of whether the expansion is spatial for quadrature or spectral for random Fourier features.
  • Optimized distribution: The optimized distribution is uniform for Sobolev kernels on [0,1]^d with uniform dρ, but is typically hard to compute and sample from in general.An approximation algorithm is proposed for the general case.
  • Quadrature and function approximation: The framework also bounds quadrature error and the expected squared error for approximating the unit ball by an approximated kernel.The regularized quadrature guarantee is valid for λ>0, and the expected squared error is less than 8λ.
  • Random feature expansions: For random features, slowly decaying eigenvalues recover n≥10m log 2m, while polynomial decay gives n≥m^1/(2s) log m and geometric decay gives n≥(log m)^2.The latter rates improve substantially over the worst-case bound.

5. Quadrature-related Extensions

The paper extends its analysis from quadrature to function approximation, stronger norms, noise, and smoother functions. Error rates are governed by the integral-operator spectrum, with robustness and noise conditions made explicit.

  • Function approximation: The L2 approximation uses n function evaluations and, with optimal sampling, achieves squared error μ_n up to logarithmic terms.Here μ_n is the n-th largest eigenvalue of the integral operator Σ.
  • Robustness to noise: Noise with variance below q(x_i)τ^2 causes no performance loss when its amount is less than nμ_n.This permissible noise bound decreases with n.
  • Function approximation: For Sobolev-type eigenvalues, the optimal number of quadrature points is proportional to max({m, μ_m^(2s) ≥ ε}).The result follows from eigenvalues proportional to (μ_m)^(2s).
  • Adaptivity to smoother functions: Using an RKHS that is somewhat larger than the target space can still achieve the optimal rate under regularized quadrature-coefficient estimation.The stated robustness does not extend theoretically to arbitrarily large RKHSs or non-regularized coefficients.
  • Approximation with stronger norms: When r = 1/2, the approximation result controls the RKHS norm but provides no decay to zero.The RKHS norm can control L∞ error, although practical control may use smaller r.
  • Approximation with stronger norms: For uniformly bounded eigenfunctions, L∞ approximation can be bounded, while the resulting rate degrades relative to squared L2 error by additional factors.The supplied passage links this degradation to the non-improvable result of Novak (1988).

6. Simulations

Simulations examine Sobolev quadrature under matched and mismatched smoothness, alternative quadrature rules, and optimized sampling distributions. The results illustrate the predicted convergence, adaptivity, and distributional behavior.

  • Sobolev quadrature: For matched smoothness s = t, convergence exponents are close to 2s.The experiments average errors over 1000 draws without regularization when computing quadrature weights.
  • Sobolev quadrature: When test functions are less smooth than the learning space, t > s, quadrature performance need not decay with sample size.This is the adverse direction of smoothness mismatch identified in the simulations.
  • Sobolev quadrature: When test functions are smoother, s > t, convergence occurs but can be slower than the optimal rate.The experiments also report equality with the optimal rate when t ≥ s/2.
  • Comparisons of quadrature rules: For s = 1, Simpson, Gauss–Legendre, Sobol, and kernel-based rules all show squared-error decay near n^-2, with a worse constant for the kernel rule.For s = 2, Sobol is not adaptive, while the other rules reach rates around n^-4.
  • Non-uniform sampling: The optimized density approaches the uniform density for large λ and a Beta distribution with parameters a = b = .25 as λ tends to zero.The small-λ density is proportional to x^1/4(1 − x)^1/4 relative to the input distribution.
  • Fourier feature sampling: For Fourier features, the optimal density recovers the input density for large λ but tends toward a uniform density as λ approaches zero.The density is shown relative to both the input distribution and the counting measure.

7. Conclusion

The conclusion identifies kernel quadrature as a special random-feature expansion and summarizes the resulting approximation guarantees. It also notes broad applicability and several directions for extending the framework.

  • Conclusion: Kernel-based quadrature rules are a special case of random feature expansions for positive definite kernels.The correspondence uses a particular decomposition that always exists, though it need not be available in closed form.
  • Conclusion: Upper and lower approximation bounds based only on integral-operator eigenvalues match up to logarithmic terms.The upper bound uses iid samples from a specific non-uniform distribution, while the lower bound applies to any point set.
  • Future directions: The work suggests extensions to bandit optimization, quasi-random sampling, kernel herding, non-parametric regression, online learning, and stochastic approximation.These are proposed directions rather than results established in the paper.

Appendix A. Kernels on product spaces

The appendix analyzes product spaces by combining component kernels and measures. For additive product-space RKHSs, the integral-operator spectrum is obtained by concatenating component spectra, yielding dimension-dependent decay.

  • Setup: The appendix considers product spaces X = X_1 × ··· × X_d with component kernels, RKHSs, measures, eigenvalues, and eigenfunctions.It analyzes both polynomial and exponential eigenvalue decays.
  • Spectrum: For polynomial component decay μ_m ∝ m^-2s, the product spectrum decays proportionally to (m/d)^-2s.The corresponding eigenvalue-counting function scales as dλ^-1/(2s).
  • Product-space structure: The product-space RKHS contains separable additive functions g(x) = Σ_j f_j(x_j), and its integral operator is block-diagonal.The j-th block equals the integral operator for component kernel k_j and measure dρ_j.
  • Spectrum: The eigenvalues of the product-space operator are the concatenation of the component eigenvalue sequences.Consequently, the counting function for eigenvalues above λ is the sum of the component counting functions.
  • Spectrum: For exponential component decay exp(−ρm), the product spectrum decays as exp(−ρm/d).The dimension d changes the effective decay rate through the index rescaling.

A.2 Product of kernels: k(x, y) = Qd

For product kernels, the RKHS and integral operator decompose as tensor products, making the eigenvalues products of the component eigenvalues and determining their decay.

  • The RKHS for K is the tensor product of the component spaces F1, ..., Fd.
  • The integral operator for k is the tensor product of the d component integral operators.
  • The product operator has eigenvalues µ1_m1 × ··· × µd_md for nonnegative multi-indices.
  • For exponential component decay, counting multi-indices in a d-dimensional simplex yields eigenvalue decay bounded by exp(−ρd m^(1/d)).

B.1 Proof of Prop. 1

The proof controls the regularized empirical covariance operator using operator inequalities and matrix Bernstein concentration, yielding bounds on approximation-related quadratic forms and expected error.

  • The analysis studies ⟨f, (Σ_hat + λI)^−1f⟩ for functions satisfying ⟨f, Σ^−1f⟩ ≤ 1.
  • If the normalized covariance deviation is bounded below by −tI, the empirical quadratic form is at most (1−t)^−1 times the population form.
  • The required covariance control is obtained by treating independent identically distributed self-adjoint operators with an operator-norm concentration bound.
  • With high probability, (Σ_hat + λI)^−1 ≼ 4(Σ + λI)^−1, while the proof notes that this ordering cannot generally be squared.
  • In expectation, the squared error is less than 8λ when n satisfies a logarithmic sample-size condition involving d_max(λ), tr Σ, and δ.

B.2 Proof of Prop. 2

The proof of Proposition 2 reformulates the preceding bound and derives a second statement under an additional relation between the effective dimension and the sample size.

  • Proposition 2(a) is a reformulation of Proposition 1's bound.
  • Proposition 2(b) follows from statement (a) when the relevant effective-dimension quantity is no greater than n.

B.3 Proof of Prop. 3

The lower-bound proof constructs many separated functions from leading eigenvectors, applies a packing argument, and selects the dimension to obtain the desired approximation lower bound.

  • Varshamov–Gilbert's lemma supplies at least e^(s/8) separated binary vectors in {0,1}^s.
  • Each binary vector defines a function using the s largest eigenvectors and eigenvalues of Σ, with norm controlled through the smallest selected eigenvalue µ_s.
  • Applying the approximation existence result to the separated functions yields coefficient vectors β_j with bounded squared ℓ2-norm.
  • The proof chooses s subject to a sample-size condition and then derives the stated approximation bound for all constructed functions.
  • A packing-number argument relates the separated function family to the approximation lower bound, with µ_s constrained relative to λ.
Loading 1502.06800v2…