Fast approximations of Gaussian processes (GPs, probability distributions over functions defined by a covariance kernel) usually replace the kernel with a finite sum of smooth basis functions, such as random cosines or Legendre polynomials. This has a side effect that is rarely examined. The functions drawn from the approximate process are infinitely differentiable, even when the original kernel was chosen precisely because its functions are rough. A Matérn kernel with smoothness $\nu$ produces functions that are differentiable exactly $\lfloor \nu \rfloor$ times, and its low-rank surrogate produces functions that are differentiable infinitely many times. For ordinary noisy regression this may be harmless, because observation noise hides the high frequencies where the two processes differ. When the GP is conditioned on derivatives, as in probabilistic PDE solvers, the differential operator amplifies exactly those discarded high frequencies. In that setting, prior work shows that an overly smooth prior makes the uncertainty estimates badly overconfident.
We propose to approximate the kernel as a low-rank part for the low frequencies plus a sparse, short-range "tail" kernel that keeps the high-frequency part of the Matérn spectrum. The combined surrogate has sample paths with the same differentiability as the original process, which follows from known rules for sums and products of kernels. It stays cheap because the tail kernel acts only over short distances and can be tapered to a sparse matrix. We also argue that the frequency cutoff should be chosen by a spectral accuracy criterion on the derivative covariance matrix rather than on the kernel matrix. The claim to be tested is specific. On derivative-constrained tasks, this low-rank-plus-tail surrogate should restore calibrated uncertainty where Random Fourier Features and Gauss–Legendre features fail at equal cost. On plain regression it should give no benefit, and we treat that as a falsifiable prediction rather than a weakness.
Core Claim
Existing spectral approximation guarantees control the regularized kernel matrix in the Loewner (positive semi-definite) order: $$(1-\epsilon)(K+\lambda I) \preceq \tilde K + \lambda I \preceq (1+\epsilon)(K+\lambda I).$$ Here $K$ is the exact kernel matrix, $\tilde K$ its approximation, $\lambda>0$ the regularizer and $\epsilon\in(0,1)$ the tolerance, as developed for Random Fourier Features in Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees.
This bound says nothing about eigen-directions whose energy lies below $\lambda$, and those directions carry a stationary kernel's high-frequency tail. Applying a differential operator $\mathcal D$ of order $p$ multiplies spectral density at frequency $\omega$ by roughly $|\omega|^{2p}$. The directions that were invisible under $\lambda$ can therefore dominate the derivative covariance matrix $K_{\mathcal D\mathcal D}$ (entries $\mathcal D_x \mathcal D_y k$). A sandwich on $K+\lambda I$ therefore does not imply one on $K_{\mathcal D\mathcal D}+\lambda I$.
The approximation we propose is $$\tilde k(x,y) = \phi_\Omega(x)^\top \phi_\Omega(y) + \tau_h(x-y)\, r_\Omega(x-y).$$ The terms are defined as follows. $\phi_\Omega$ is a quadrature or random-feature map for the part of the Matérn spectral density with $|\omega|\le\Omega$. $r_\Omega$ is the exact high-pass remainder kernel, the inverse Fourier transform of the spectral density restricted to $|\omega|>\Omega$. $\tau_h$ is a smooth, compactly supported taper of radius $h$ that makes the tail matrix sparse.
The remainder $r_\Omega$ keeps the Matérn spectral decay $|\omega|^{-(2\nu+d)}$, and with it the non-smoothness of the kernel at zero lag. Multiplying it by a smooth taper and adding an infinitely smooth low-rank term leaves the local regularity unchanged, by the kernel-algebra results of Sample Path Regularity of Gaussian Processes from the Covariance Kernel. Sample paths of $\tilde k$ are then $C^{\lfloor\nu\rfloor}$ and no smoother, matching the parent process.
Relation to Prior Work
Three papers motivate the proposal by establishing that the sample-path-versus-model mismatch matters.
- Da Costa et al. Sample Path Regularity of Gaussian Processes from the Covariance Kernel give necessary and sufficient kernel conditions for Hölder and Sobolev regularity of sample paths. Their kernel-algebra results are the tool we use to certify our surrogate.
- Wang et al. Bayesian Numerical Methods for Nonlinear Partial Differential Equations show that squared-exponential and rational-quadratic priors make PDE solvers overconfident, while Matérn priors matched to the solution's differentiability give calibrated error-to-uncertainty ratios.
- Implication. Wang et al. never ask what happens when the calibrated Matérn prior is replaced by a fast low-rank surrogate. That surrogate is itself an infinitely smooth prior, so their own result predicts it should reintroduce overconfidence. Testing this prediction is the first step of our program.
Two papers show that the RKHS (the Hilbert space of functions the kernel method can represent) and the space of sample paths genuinely differ.
- Variational Gaussian Processes: A Functional Analysis View proves that sample paths fall outside the RKHS almost surely.
- Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networks quantifies a half-order Sobolev gap between the two spaces for wide networks.
- Implication. Guarantees stated for RKHS-ball targets, including the uniform rates for sparse methods in Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning, do not address calibration on paths drawn from the prior. That is the regime probabilistic numerics works in.
Four lines of work supply methods and constraints.
- Gauss–Legendre features. Gauss-Legendre Features for Gaussian Process Regression supplies fixed-node quadrature on a truncated spectral integral. This is our low-rank component. Unlike that paper, we do not discard the truncated tail.
- Kernel derivatives. On Kernel Derivative Approximation with Random Fourier Features bounds only entry-wise derivative error, and only under tail conditions that rough Matérn kernels strain. We target a spectral bound on $K_{\mathcal D\mathcal D}$.
- Fractional Matérn fields. Sparse approximations of fractional Matérn fields is the closest methodological relative, since it also manipulates the Matérn spectrum to obtain sparsity. It is also a constraint: it shows that plain band-limiting causes ringing in the covariance and that Taylor-expanding the spectrum diverges beyond order four. Our design sidesteps both problems by keeping the tail exactly and localizing it in space, rather than truncating or expanding it in frequency.
- Preconditioning. Preconditioning for Scalable Gaussian Process Hyperparameter Optimization supplies the conjugate-gradient and Lanczos machinery for low-rank-plus-sparse systems. The low-rank part is a natural preconditioner.
Research Program
Theory. The first theoretical piece is a regularity statement. For any $\Omega$ and any smooth taper, the surrogate's sample paths lie in the same local Hölder class as the Matérn parent. Tapering changes the long-range behavior of the tail but not its behavior at zero lag. This should follow directly from the Da Costa et al. product and sum rules.
The second piece is a derivative-weighted cutoff rule. We seek a condition on $\Omega$ and $h$ under which $$(1-\epsilon)(K_{\mathcal D\mathcal D}+\lambda I) \preceq \tilde K_{\mathcal D\mathcal D}+\lambda I \preceq (1+\epsilon)(K_{\mathcal D\mathcal D}+\lambda I).$$ Here $\tilde K_{\mathcal D\mathcal D}$ is the derivative matrix built from $\tilde k$. The required cutoff $\Omega$ should grow with the effective degrees of freedom of $K_{\mathcal D\mathcal D}$, not of $K$. This is where derivative order enters the feature count.
The error we must control is the taper's distortion of the tail. Because $r_\Omega$ has most of its mass at lags on the order of $1/\Omega$, a radius $h$ of a few multiples of $1/\Omega$ should suffice. We will establish this empirically first and then bound it.
Construction. We will implement the surrogate with Gauss–Legendre nodes on the band $|\omega|\le\Omega$. The remainder $r_\Omega$ is computed once per hyperparameter setting in one dimension, and as a radial function in $d$ dimensions. The tail matrix is sparse. Solves use conjugate gradients preconditioned by the low-rank term, and log-determinants use the stochastic Lanczos estimators of Wenger et al.
Finally, we will integrate the surrogate into the linearized PDE solver of Wang et al. inside ProbNum: Probabilistic Numerics in Python.
Baselines
Exact Matérn GP. The naive reference point is the exact Matérn GP with the same $\nu$ and hyperparameters. On the PDE suite this is the method of Wang et al. They report Z-scores (the ratio of actual error to predicted uncertainty) that "remained stable and close to unity as the grid was refined" for Burgers' equation, according to Bayesian Numerical Methods for Nonlinear Partial Differential Equations. The file gives only this qualitative statement and no numerical Z-score table. We will re-run the exact solver at the grid sizes where it is still feasible and use those numbers as the calibration target.
Gauss–Legendre features and Random Fourier Features. These are the strongest fast competitors: Gauss–Legendre features Gauss-Legendre Features for Gaussian Process Regression, classical Random Fourier Features, and the leverage-capped variant of Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees.
- Gauss–Legendre features are the most sample-efficient spectral method in the file, with polylogarithmic feature counts and cheap hyperparameter learning.
- No reported Z-score results on the PDE suite were found on Lacuna for Gauss–Legendre features or Random Fourier Features.
- Fairness: every method gets the same memory and wall-clock budget. We match the number of nonzeros plus low-rank storage of our surrogate to the feature count $s$ of the baselines. All methods get the same hyperparameter tuning budget.
- Beating them means a median Z-score within a factor of 1.5 of one where they are off by more than a factor of 3, at equal cost, with no loss in solution error.
Nyström with ridge-leverage-score sampling. This follows Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning. It is the strongest inducing-point competitor with uniform convergence guarantees, and it is run at matched rank.
Ablations. Three ablations isolate the key ingredient.
- Diagonal-correction ablation. Low-rank features plus a diagonal term that matches the discarded marginal variance, in the style of fully independent training conditional corrections. This restores variance but not roughness.
- Smooth-tail ablation. The tail is replaced by a squared-exponential kernel of matched variance and range. This restores local correlation but gives infinitely smooth paths.
- Frequency-rule ablation. The cutoff $\Omega$ is chosen by the kernel-matrix criterion instead of the derivative criterion.
If the smooth-tail ablation matches our method, then roughness preservation is not the mechanism and the claim fails.
Why not just…?
Why not just tune the Matérn smoothness $\nu$ by marginal likelihood and keep using fast features? Tuning $\nu$ does not help, because any finite-feature surrogate yields infinitely smooth paths whatever $\nu$ is. The mismatch lives in the approximation, not in the hyperparameter. Wang et al. also show that marginal-likelihood tuning does not rescue a prior that is too smooth. We will include a tuned-$\nu$ Gauss–Legendre baseline to confirm this.
Why not just add more features? For Gaussian kernels, Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees proves that classical Random Fourier Features need $\Omega(n/\lambda)$ features in the worst case. For derivative matrices of rough kernels the requirement should be worse, because the tail is amplified. This is a genuine threat for Gauss–Legendre features in one dimension, where features are cheap. We will plot Z-score against the feature count $s$ and report the $s$ at which each baseline becomes calibrated, if it ever does. If Gauss–Legendre features reach calibration at a cost comparable to ours, the method has no practical case in one dimension, and we will say so.
Why not just add a diagonal or nugget correction for the missing variance? A diagonal term adds independent noise at each point. That fixes marginal variances but carries no information about the derivative covariance: the diagonal correction has no well-defined derivatives. We therefore expect it to fail precisely on $K_{\mathcal D\mathcal D}$. The diagonal-correction ablation tests this directly.
Why not just use the sparse Markov field (SPDE) representation of Matérn? It is exact and sparse only for integer smoothness. Fractional smoothness requires approximations that ring or diverge, per Sparse approximations of fractional Matérn fields. It also requires a mesh, which is awkward for scattered data such as 3DRoad. For integer $\nu$ on regular grids, it is a strong competitor, and we will include it there.
Proposed Experiments
Calibration on the PDE suite. The decisive experiment uses the three nonlinear initial value problems of Wang et al.: homogeneous Burgers', porous medium, and forced Burgers'. We run the exact Matérn solver, Gauss–Legendre features, Random Fourier Features, Nyström, and our surrogate, all through ProbNum, under matched cost and over a grid-refinement sweep.
- Primary metrics: the Z-score and its drift under refinement.
- Secondary metrics: solution error, and the empirical Hölder exponent of posterior samples, estimated from quadratic variation across scales.
- Prediction: fast baselines drift to Z-scores well above one as the grid refines, and our surrogate tracks the exact solver.
- Porous medium case: the solution violates the regularity assumptions here, and we report results with and without the mass-conservation constraint used by Wang et al.
Derivative-observation regression. We use the synthetic one-dimensional function $\sin(2x)+\sin(6e^x)$ with 800 points and the two-dimensional oscillatory function with 4096 points, both from the Gauss–Legendre features paper. We condition on noisy values and gradients and score negative log-likelihood and coverage on held-out derivatives. The East Africa temperature field, with 77,404 training locations, tests two-dimensional gradient prediction at realistic scale.
Negative control. We fit plain noisy regression on 3DRoad and on the UCI suite from Wenger et al. We predict no accuracy or calibration gain over Gauss–Legendre features, since noise masks the tail. We will report wall-clock cost against Wenger et al.'s reported 11.3x preconditioned speedup on 3DRoad, from Preconditioning for Scalable Gaussian Process Hyperparameter Optimization, to show that the sparse tail does not erase the savings.
Falsification conditions. A gain on this negative control would indicate a different mechanism than the one proposed. Failure of the PDE experiment would falsify the central claim. So would the smooth-tail ablation matching our method.
References
- Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
- Sample path regularity of Gaussian processes from the covariance kernel
- Bayesian numerical methods for nonlinear partial differential equations
- Variational Gaussian Processes: A Functional Analysis View
- Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networks
- Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning
- Gauss-Legendre Features for Gaussian Process Regression
- On Kernel Derivative Approximation with Random Fourier Features
- Sparse Approximations of Fractional Matérn Fields
- Preconditioning for Scalable Gaussian Process Hyperparameter Optimization
- ProbNum: Probabilistic Numerics in Python