Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences

1 Introduction

• Gaussian processes and RKHS methods are closely connected through positive definite kernels, yet differ in probabilistic versus decision-theoretic treatment and in their hypothesis spaces.The paper highlights equivalences between GP posterior means and kernel ridge regression estimators, while noting that GP sample paths almost surely lie outside the corresponding RKHS.Source: §1 · pp. 2–3

1.1 Contents of the Paper

• The paper develops connections spanning GP regression, posterior variance, hypothesis spaces, convergence rates, integral transforms, and a GP formulation of HSIC.It interprets posterior variance as an RKHS worst-case error, relates noise variance to regularization, connects MMD with GP average-case integration error, and formulates HSIC using GPs, recovering Brownian distance covariance.Source: §1.1 · pp. 4–5

1.2 Notation and Definitions

• The notation section defines the matrix, probability, multi-index, derivative, function-space, and Fourier-transform conventions used throughout the paper.These definitions establish notation for transposes, natural-number multi-indices, Euclidean spaces and norms, expectations, kernel matrices, function vectors, Lp spaces, and Fourier transforms.Source: §1.2 · p. 6

2.1 Positive Definite Kernels

• Positive definite kernels are symmetric functions whose finite Gram matrices are positive semidefinite, and each kernel serves as the covariance kernel of a GP and the reproducing kernel of a unique RKHS.The framework includes Gaussian, Matérn, polynomial, and kernels on non-Euclidean domains; kernel parameters govern induced smoothness.Source: §2.1 · p. 7, §2.2 · p. 8, §2.3 · p. 11

2.2 Gaussian Processes

• A Gaussian process is determined by a mean function and positive definite covariance kernel through multivariate-normal finite-dimensional restrictions, with every such pair defining a corresponding GP.Kernel choice also induces function properties: square-exponential covariance yields infinitely continuously differentiable sample paths, while finite-dimensional restrictions are directly computational.Source: §2.2 · pp. 8–9

2.3 Reproducing Kernel Hilbert Spaces

• An RKHS represents inputs through possibly infinite-dimensional canonical feature maps, and its norm captures both function magnitude and smoothness, motivating regularization against overfitting.For the square-exponential kernel, Fourier transforms of RKHS functions decay exponentially, with faster decay as bandwidth γ increases.Source: §2.3 · pp. 10–11, §2.4 · p. 13
• For Matérn kernels with s = α + d/2 an integer, the associated RKHS is norm-equivalent to a Sobolev space, with the RKHS norm encoding weak derivatives through order s.Classical differentiability is guaranteed only up to order α, despite weak differentiability through order s.Source: §2.3 · p. 12

2.4 A Spectral Characterization for RKHSs Associated with Shift-Invariant Kernels

• For shift-invariant kernels on R^d, the RKHS is characterized through the Fourier transform of the kernel, whose decay controls the smoothness of its functions.Rapid decay of F[Φ] forces rapid decay of F[f], so smooth kernels induce smooth RKHS members.Source: §2.4 · pp. 12–13
• Kernel ridge regression has a posterior mean exactly equal to that of Gaussian process regression, but usually does not provide an error estimate.The omission can be deliberate when one does not wish to impose assumptions such as additive Gaussian noise.Source: §2.4 · p. 14
• For any f ∈ H_kα,h, the magnitude of its Fourier transform decays polynomially as |ω| grows, and the decay becomes faster as α increases.Source: §2.4 · p. 14
• The Matérn-kernel RKHS H_kα,h is norm-equivalent to the Sobolev space of order α + d/2 [2005, Corollary 10.48].Source: §2.4 · p. 14

3 Connections between Gaussian Process and Kernel Ridge Regression

• Regression models outputs as y_i = f(x_i) + ξ_i, with interpolation arising when ξ_i = 0 and exact training values are available.The regression function is the conditional expectation of the output given the input.Source: §3 · pp. 14–15

3.1 Gaussian Process Regression and Interpolation

• A Gaussian process prior with kernel k and likelihood for observation noise yields a posterior GP whose mean and covariance are given by closed-form linear-algebra expressions.The posterior mean predicts f(x), while the posterior covariance quantifies uncertainty; hyperparameters include the prior mean, kernel, and noise variance.Source: §3.1 · pp. 15–17
• In the noise-free case, GP interpolation uses Gaussian conditioning with σ^2 = 0 rather than Bayes’ rule, but requires an invertible kernel matrix.The likelihood is degenerate without noise, and jitter can regularize singular or nearly singular kernel matrices.Source: §3.1 · pp. 16–18

3.2 Kernel Ridge Regression and Kernel Interpolation

• Kernel ridge regression minimizes empirical loss plus λ∥f∥_Hk^2 in an RKHS, where larger λ produces a smoother estimator and regularization prevents overfitting in noisy ill-posed problems.For square loss, the unique estimator has a finite kernel expansion obtained through the representer theorem and linear algebra.Source: §3.2 · pp. 18–19
• KRR coefficients need not be unique when kXX is singular, but all valid coefficient vectors define the same unique estimator function.When kXX is invertible, the coefficients are given by α = (kXX + nλI_n)^−1Y.Source: §3.2 · pp. 19–20
• Kernel interpolation sets λ = 0 and, when kXX is invertible, is the unique RKHS function interpolating the data with minimum norm, equivalently the smoothest interpolant.The RKHS norm quantifies smoothness, so the constrained solution selects the smoothest function passing through all training values.Source: §3.2 · pp. 20–21
• Kernel-matrix regularization may remain necessary without output noise for numerical stability, although the constant can then be chosen very small.This applies when the kernel matrix is nearly singular because the regularization is unrelated to output-noise variance.Source: §3.2 · p. 21

3.3 Equivalences in Regression and Interpolation

• GP regression and kernel ridge regression have identical estimators when λ = σ2/n; the GP posterior mean lies in Hk, whereas posterior samples almost surely do not.The equivalence assumes f ∼GP(0, k), additive Gaussian noise, and kernel-ridge regularization λ > 0.Source: §3.3 · pp. 21–22
• Additive noise acts as regularization: larger σ2 corresponds to larger λ, smoother latent functions, and rougher observed processes than the latent function.The observation process is modeled as y = f plus independent noise, so the noise assumption encodes that f is smoother than y.Source: §3.3 · p. 22
• With an invertible kernel matrix and noise-free observations, GP interpolation and kernel interpolation produce the same posterior mean and RKHS solution.The equivalence identifies the posterior mean from the GP prior f ∼GP(0, k) with the kernel-interpolation solution in Hk.Source: §3.3 · p. 22

3.4 Error Estimates: Posterior Variance and Worst-Case Error

• The posterior variance admits a kernel/frequentist worst-case-error interpretation, with an additional σ2 term under noise; without that term, average-case and worst-case errors are identical.As σ2 increases, the noise contribution increases, making worst-case error more pessimistic than average-case error.Source: §3.4 · pp. 23, 26

3.5 A Weight Vector Viewpoint of Regularization and the Additive Noise Assumption

• The weight-vector formulation decomposes prediction error into noise-free RKHS worst-case error plus σ2∥w∥2, equal to the variance from noisy observations.Thus the weights minimize the sum of approximation worst-case error and estimator variance, without requiring the fixed latent function to be Gaussian.Source: §3.5 · pp. 27–28

4 Hypothesis Spaces: Do Gaussian Process Draws Lie in an RKHS?

• GP sample paths lie outside the covariance-kernel RKHS almost surely, yet lie in certain powers of that RKHS, preserving a deep GP–RKHS connection.The section also relates these sample-path properties to convergence equivalences between Gaussian processes and kernel ridge regression.Source: §4 · pp. 28–29

4.1 Characterizations via Orthonormal Expansions

• Under compactness and continuity assumptions, Mercer and Karhunen–Loève expansions characterize RKHSs and Gaussian processes using the same kernel-integral-operator eigensystem.The eigenvalues and eigenfunctions provide orthonormal bases and series representations for both frameworks.Source: §4.1 · p. 29, §4.1.3 · p. 31

4.1.1 Mercer’s Theorem

• Mercer’s theorem gives an absolutely and uniformly convergent eigenfunction expansion of a continuous kernel, provided the finite measure’s support is all of X.The expansion depends on the measure and can fail outside its support.Source: §4.1.1 · p. 30

4.1.2 Mercer Representation of RKHSs

• The Mercer representation expresses the RKHS through eigenfunctions weighted by inverse eigenvalues, with the resulting RKHS independent of the full-support measure choice.The basis representation changes with ν, but Hk remains the same under the theorem’s assumptions.Source: §4.1.2 · p. 30

4.1.3 Karhunen-Lo`eve Expansion of Gaussian Processes

• The Karhunen–Loève expansion represents f ∼GP(0, k) using the Mercer eigenfunctions and independent standard-normal coefficients, with uniform mean-square convergence.Finite truncations yield approximate finite-dimensional Gaussian processes.Source: §4.1.3 · p. 31

4.2 Sample Path Properties and the Zero-One Law

• Driscoll’s generalized zero-one law states that GP membership in an RKHS is almost sure when the inclusion is Hilbert-Schmidt and otherwise has probability zero.Consequently, for infinite-dimensional Hk, a GP with covariance k belongs to Hk with probability 0, whereas finite-dimensional Hk admits an almost-sure version.Source: §4.2 · pp. 33–34
• Brownian motion is continuous but lies outside its Cameron–Martin RKHS almost surely, equivalently lacking a square-integrable weak derivative.The RKHS is the first-order Sobolev space on [0, 1].Source: §4.2 · p. 35

4.3 Powers of RKHSs as GP Sample Spaces

• Power RKHSs interpolate between L2(ν) and H_k: decreasing θ enlarges the space and permits less-smooth functions, whereas increasing θ yields smoother functions.The power construction also supplies the corresponding reproducing kernel.Source: §4.3 · p. 36
• A GP sample-space characterization uses powers of RKHSs Hθ_k: under the stated eigensystem condition, equivalent statements include existence of a version belonging to Hθ_k with probability 1.The power RKHS H_r can be constructed from the covariance kernel’s eigensystem through a corresponding power of H_k.Source: §4.3 · pp. 35–36

4.4 Examples of Sample Path Properties

• For square-exponential kernels, exponentially decaying eigenvalues make GP sample paths lie almost surely in spaces infinitesimally larger than H_kγ, approaching H_kγ as θ approaches 1.Thus the RKHS-exclusion issue is practically mild for these infinitely smooth kernels, unlike the Matérn case.Source: §4.4 · p. 37
• For Matérn kernels, a GP sample path belongs almost surely to H_kα′,h′ when α > α′ + d/2, so its smoothness is roughly d/2 lower than that of H_kα,h.The condition is sharp at equality, where almost-sure membership fails; α′ + d/2 need not be an integer.Source: §4.4 · pp. 37–38

5.1 Convergence Rates for Gaussian Process and Kernel Ridge Regression

• GP posterior contraction and kernel-ridge convergence are essentially equivalent in Sobolev regression, with fixed GP noise variance corresponding to λ_n = c n^-1 and matching optimal kernel smoothness.The equivalence recovers the GP rate from kernel-ridge results and identifies regularization as the kernel-method counterpart of additive output noise.Source: §5.1 · pp. 38, 39, 41
• The optimal matched-smoothness rate is n^-2β/(2β+d), attained when GP sample-path smoothness α equals regression-function smoothness β; this is minimax optimal for Sobolev regression.For kernel ridge, the regression function need not lie in the RKHS, and smaller β requires a faster-decreasing regularization schedule.Source: §5.1 · pp. 39–40

5.2 Upper-bounds and Contraction Rates for Posterior Variance

• Posterior variance contracts according to local fill distance, dimension, and kernel smoothness, reaching zero as design points become denser near the prediction location.For infinitely smooth kernels, the exponent can be arbitrarily large, although the associated constants depend on that exponent.Source: §5.2 · pp. 41–42
• With equally spaced points in a radius-ρ ball, hρ,X(x) = O(n^-1/d) and posterior variance contracts as O(n^-(2s/d−1)), exposing the curse of dimensionality.Achieving a fixed contraction level therefore requires exponentially more points as dimension d increases.Source: §5.2 · p. 42

6.1 Maximum Mean Discrepancy: Worst Case and Average Case Errors

• For characteristic kernels, MMD is a proper metric and equals the GP variance of the difference between integrals, linking RKHS worst-case and GP average-case errors.A characteristic kernel also makes P = Q equivalent to Pf = Qf almost surely for f drawn from GP(0, k).Source: §6.1 · pp. 44–45

6.2 Sampling and Numerical Integration

• Kernel quadrature minimizes MMD over weighted design points, yielding closed-form weights when the kernel matrix is invertible, but requires compatibility enabling evaluation of the kernel mean.Bayesian quadrature instead places a GP prior on the integrand and conditions the integral on observed function values; its posterior variance depends only on the kernel, design points, and measure.Source: §6.2 · pp. 46–47
• Kernel and Bayesian quadrature share the same weights and error: Bayesian quadrature’s posterior mean matches kernel quadrature, while its posterior variance equals squared MMD.The equivalence transfers RKHS worst-case-error results to Bayesian posterior contraction rates; regularization also provides robustness to misspecification through an additive-noise interpretation.Source: §6.2 · pp. 47–48

6.3 Kernel Mean Shrinkage Estimator and Its Bayesian Interpretation

• The spectral kernel mean estimator shrinks the empirical kernel mean toward zero, trading variance for bias through regularization and offering a Bayesian interpretation, although theoretical superiority over the empirical estimator is unestablished.The ordinary empirical estimator has O(n^-1/2) error, a minimax-optimal rate, whereas shrinkage can improve fixed-sample mean-squared error under stated conditions; the SKME has only empirical evidence of improvement.Source: §6.3 · pp. 49–50
• When θ = 1 and λ = σ2/n, the posterior mean equals the kernel mean shrinkage estimator, giving estimator (80) a probabilistic interpretation [80].The model uses a GP prior and additive Gaussian noise, while the probabilistic formulation supports empirical-Bayes hyperparameter selection and posterior-covariance uncertainty quantification.Source: §6.3 · p. 51
• For θ > 1, the powered kernel kθ can ensure that the kernel mean is a GP sample path, whereas the Gaussian-noise likelihood is computationally useful but may misrepresent bounded, dependent, and heteroscedastic errors.For square-exponential kernels, θ = 1 + ε with arbitrarily small ε > 0 suffices; the smoother-kernel posterior mean then no longer coincides with the shrinkage estimator, leaving its advantage over the empirical estimator unresolved.Source: §6.3 · p. 51
• The weighted-sum representation of kernel mean shrinkage equals the empirical mean of a GP posterior mean, linking the estimator to Bayesian quadrature with the empirical measure Pn.This identifies the fitted-function average as the relevant quadrature construction.Source: §6.3 · pp. 51–52

6.4 Gaussian Process Interpretation of Hilbert Schmidt Independence Criterion

• HSIC is the squared MMD between the joint distribution and the product of marginals, and with characteristic k ⊗ ℓ it vanishes exactly under independence.The paper presents a probabilistic interpretation of this general HSIC construction in terms of independent GPs f ∼ GP(0, k) and g ∼ GP(0, ℓ).Source: §6.4 · pp. 52–53
• HSIC equals the expectation over GP draws of the squared covariance between nonlinear transformations f(X) and g(Y), recovering Brownian distance covariance for the corresponding kernels [Székely and Rizzo, 2009; Sejdinovic et al., 2013].Thus HSIC can be understood as averaging dependence across GP-generated transformations, while the Brownian-motion specialization yields distance covariance on Euclidean spaces.Source: §6.4 · pp. 53–54

• Kernel methods emphasize regularization and optimization, whereas Gaussian processes are generative models defined through marginal and conditional distributions.The paper positions both frameworks as central to theoretical analysis in machine learning, statistics, and numerical analysis.Source: §7 · p. 54
• Clarifying the intersection of the two frameworks can facilitate transferring knowledge and methods between them.The review is intended to support further advances that would otherwise be more difficult to achieve.Source: §7 · p. 54
• The discussion highlights that frequentist and Bayesian statistics may be less different than they initially appear.This observation is framed amid expectations of a possible third theoretical foundation for deep models.Source: §7 · p. 54

A.1 Proof of Lemma 3.9

• The proof begins by rewriting the right side of (38) using the reproducing property.Source: §A.1 · p. 55
• It then applies the Cauchy-Schwarz inequality to obtain an upper bound on the rewritten expression.Source: §A.1 · p. 55
• The argument introduces g through a kernel expansion involving coefficients c_i and functions k(·, x).Source: §A.1 · p. 55
• Using this construction, the proof establishes that ∥g∥Hk = 1.Source: §A.1 · p. 55
• The normalization of g yields a lower bound for the right side of (95).Source: §A.1 · p. 55
• Combining the lower and upper bounds with (95) proves the assertion.Source: §A.1 · p. 55

Interpolation-space lemma

• Interpolation spaces are defined through the K-functional, and continuous embeddings G ,→ F ,→ E imply [E, G]θ,2 ,→ [E, F]θ,2.The proof derives the K-functional inequality K(x,t,E,F) ≤ K(x,ct,E,G), which gives the interpolation embedding.Source: §A.2 · pp. 55–56

Sobolev–Besov embedding

• The RKHS embeds into W^m_2(X), while interpolation identifies [L2(ν), W^m_2(X)]θ,2 with the Besov space B^θm_22(X).Because X is a bounded Lipschitz domain and θm > d/2, this Besov space embeds into L∞(ν), establishing the required embedding.Source: §A.2 · p. 56

Entropy and eigenvalue bounds

• The proof uses dyadic entropy numbers of id : Hkγ _ L2(ν) and bounds on the embedding to control the ordered eigenvalues λi.Compactness of the embedding follows from integrability of X kγ(x, x)dν(x), allowing the cited entropy-number and eigenvalue estimates to be applied.Source: §A.2 · pp. 56–57

Completion of the corollary proof

• Choosing p ∈ (0, 1) with 1−θ > p makes the resulting bound finite and implies the required eigenvalue summability condition.This establishes the assertion through Theorem 4.12 and completes the proof of Corollary 4.13.Source: §A.2 · pp. 56–57

• The proof reduces Proposition 6.4 to showing that the right-hand side of identity (92) equals HSIC (87).Source: §A.3 · p. 57
• Using k(x, x′) = E_f[f(x)f(x′)], the proof rewrites the relevant expression in terms of kernel expectations.Source: §A.3 · p. 57
• After defining centered features k(·, X) := k(·, X) − µ_PX and l(·, Y ) := l(·, Y ) − µ_PY, the expression expands into four tensor-product terms.Source: §A.3 · p. 58