Random Fourier features replace a kernel by a finite sum of random sinusoids. Practitioners use them to make Gaussian processes cheap. A Gaussian process (GP) is a distribution over functions, set by a covariance kernel. Probabilistic numerical solvers use one as a prior over the unknown solution of a differential equation, then report uncertainty about that solution. These solvers only stay honest when the prior's smoothness matches the solution's. Bayesian Numerical Methods for Nonlinear Partial Differential Equations shows that infinitely smooth kernels make PDE solvers badly over-confident. The cure it proposes is Matérn kernels whose differentiability barely covers the order of the differential operator. This note argues that this "barely smooth enough" regime is exactly where plain random Fourier features break. They break even though they look fine when you check how well they approximate the kernel itself.
The mechanism is simple. A Matérn kernel's frequency distribution has a heavy power-law tail. When the solver conditions on derivatives of order $p$, the random-feature estimate of the needed derivative covariance multiplies each sampled frequency by $|\omega|^{2p}$. Once $p$ reaches half the smoothness parameter $\nu$, this estimate has infinite variance, even though the exact quantity is finite. A typical draw of a heavy-tailed average sits below its mean. So a typical finite-feature model underestimates how rough the solution can be, and it behaves like a smoother kernel. We propose to prove this threshold and to measure the resulting over-confidence. We also propose a minimal fix: draw frequencies from a heavier-tailed proposal and reweight them. This restores the usual $m^{-1/2}$ convergence in the number of features $m$, and the approximate kernel remains a valid covariance.
Core Claim
Take the Matérn kernel in $d$ dimensions with smoothness $\nu$. Its frequency density decays like $p(\omega) \propto |\omega|^{-(2\nu+d)}$. Two facts follow from moments of this density.
First, the exact derivative covariance $\partial^{p,p}k$ exists iff $\int |\omega|^{2p} p(\omega)\,d\omega < \infty$, which holds iff $p < \nu$.
Second, the Monte Carlo estimate of that covariance from $m$ features has finite variance iff $\int |\omega|^{4p} p(\omega)\,d\omega<\infty$, which holds iff $p<\nu/2$.
So there is a window $\nu/2 \le p < \nu$ where the solver's operator covariance is well defined but its random-feature estimate converges more slowly than $m^{-1/2}$, with heavy-tailed fluctuations. Matching the prior to the operator, as Wang et al. recommend, places most practical setups inside this window. Burgers' equation needs $p=2$ and is typically modeled with $\nu$ around 5/2. Bayesian optimization with a Matérn-5/2 kernel and Hessian information also needs $p=2$.
The fix uses importance-weighted features. Each feature is $$z_j(x)=\sqrt{\tfrac{2\,p(\omega_j)}{m\,q(\omega_j)}}\cos(\omega_j^\top x+b_j),$$ where $\omega_j$ is drawn from a proposal $q$ (a Matérn-$\nu'$ spectral density, i.e. Student-$t$) and $b_j$ is a uniform phase.
The derivative-covariance estimate then has variance proportional to $\int |\omega|^{4p} p(\omega)^2/q(\omega)\,d\omega$. Comparing power-law exponents shows this is finite iff $\nu' < 2(\nu-p)$. A heavier-tailed proposal therefore always exists inside the window.
The estimate stays unbiased, and the features keep nonnegative weights. The approximate kernel is therefore positive semi-definite and still defines a GP with explicit, cheap sample paths. Every finite expansion has infinitely differentiable paths, as the file's gap analysis notes. Our claim is that the damage comes from biased typical second moments of derivatives, not from smoothness of the paths as such. The fix targets those moments.
Relation to Prior Work
Two papers motivate the problem.
Sample path regularity of Gaussian processes from the covariance kernel proves that Matérn-$\nu$ paths are exactly $\lfloor\nu\rfloor$ times differentiable. This fixes the target that any approximation should mimic. Wang et al. show that missing this target in the smooth direction ruins calibration. Neither paper considers approximate kernels.
Two papers constrain the problem by supplying derivative rates. Optimal Rates for Random Fourier Features and On Kernel Derivative Approximation with Random Fourier Features prove $\sqrt{\log|S|/m}$ uniform rates for kernel derivatives. They do this only under Bernstein-type tail conditions on $p(\omega)$, which low-$\nu$ Matérn kernels fail. Our threshold describes what happens precisely outside their assumptions.
Three papers supply method or contrast.
- Cauchy Random Features for Operator Learning in Sobolev Space already samples heavy-tailed Cauchy frequencies to target Sobolev spaces. It does deterministic operator learning without reweighting toward a target Matérn kernel and without studying uncertainty. We use heavy tails as an importance proposal for a fixed Bayesian prior, not as a choice of kernel.
- Continuous logistic Gaussian random measure fields for spatial distributional modelling reports an unexplained error floor from its random-feature approximation.
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions uses random-feature paths to sample maximizers.
Both of the last two treat random features as a harmless convenience. Our theory predicts when they are not.
Research Program
The theoretical part has three pieces.
- Prove the variance threshold and the infinite-variance regime. In that regime we will derive the stable-law rate $m^{-(1-1/\alpha)}$ with tail index $\alpha=\nu/p$. This follows from the generalized central limit theorem for summands whose tail decays like $t^{-\alpha}$. We will also prove that the median of the estimated derivative variance falls below its true value, which is the source of over-confidence.
- Establish $L^r$ convergence at rate $m^{-1/2}$ for the importance-weighted estimator whenever $\nu'<2(\nu-p)$.
- Determine the variance-optimal $\nu'$, and say when uniform rates hold. Uniform rates are harder because the envelope $|\omega|^{2p}p/q$ can be unbounded.
The computational part has two pieces. We will build a random-feature version of the Wang et al. sequential Bayesian PDE solver, which uses local linearization of the nonlinear term. Cost becomes $O(Nm^2)$ instead of cubic in the number of grid points. We will also build a matching feature sampler for Bayesian optimization paths.
Baselines
The naive reference is the exact GP solver of Wang et al. with a Squared Exponential kernel, run on the same grid. It represents the over-smooth failure our method should avoid.
The strongest competitor on accuracy and calibration is the same exact solver with the matched Matérn tensor-product kernel. It is the gold standard our approximation tries to reproduce at lower cost. That paper reports only that posterior Z-scores came "close to unity as the grid was refined" on homogeneous Burgers. We found no numerical calibration table for these solvers on Lacuna. So we will rerun the exact solver ourselves with identical grids, hyperparameters, and linearization schedule.
The scalable competitors are plain Monte Carlo random Fourier features from the Matérn density and Nyström/inducing-point approximation with $M$ points. All scalable methods are matched on wall-clock time and memory, using the same hyperparameter-tuning budget.
The key ablation compares two variants at equal $m$. One is plain sampling. The other is frequency truncation, which caps $|\omega|$ and is equivalent to quietly using a smoother kernel. Both are compared against importance weighting while $\nu'$ is swept across the threshold $2(\nu-p)$.
Beating the scalable baselines means two things at equal compute. The approximate solver's Z-score and 95% coverage should be statistically indistinguishable from the exact matched-Matérn solver. Plain random features at the same $m$ should be measurably over-confident.
Why not just…?
Why not just use more features? In the infinite-variance window, error decays like $m^{-(1-1/\alpha)}$, not $m^{-1/2}$. At $\alpha$ near 1 (for example $p=2$ with $\nu=5/2$, giving $\alpha=1.25$), the plain estimator's error falls only like $m^{-0.2}$. Our log-log convergence plots of derivative-covariance error against $m$ will show whether this slope appears in practice. If plain features reach acceptable calibration at affordable $m$, the practical case weakens, and we will report that.
Why not just raise $\nu$ until $p<\nu/2$? This moves the prior into the over-smooth regime that Wang et al. show causes over-confidence. The Squared Exponential and high-$\nu$ exact-solver runs will measure this cost directly.
Why not just use Nyström or inducing points? They evaluate exact kernel derivatives and avoid the variance problem entirely. By Variational Gaussian Processes: A Functional Analysis View, their posterior mean equals Nyström kernel ridge regression. On small 1D problems this is a real threat. However, they cost $O(M^3)$ and do not give an explicit global path, which Bayesian optimization needs. The matched-compute comparison will show where each method wins.
Why not just use deterministic Fourier truncation with fast transforms? Fast kernel methods: Sobolev, physics-informed, and additive models scales to $10^{10}$ points in about a minute on one GPU. It is limited to $d\le 3$, and it is not Bayesian. Truncation also discards the frequency tail, which is the same smoothing our ablation tests. For 1D-plus-time PDEs it may beat us on speed. We therefore position the method for $d\ge 3$ and for uncertainty-aware use.
Why not just use random ReLU features, which have kinks? Random ReLU Features: Universality, Approximation, and Composition studies such features. Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networks places the matching wide-network sample paths in $H^{d/2+1/2-\epsilon}$. Their second derivatives vanish almost everywhere, so they cannot carry a second-order operator constraint. We include them only in the derivative-covariance accuracy study.
Proposed Experiments
Kernel-level study. First we will isolate the mechanism at the level of the kernel. We will measure the error of the derivative covariance $\partial^{p,p}k$ against $m$ for $\nu\in\{3/2,5/2,7/2\}$, $p\in\{1,2\}$, and $d\in\{1,3,6\}$. The fitted slope should cross from $-1/2$ to roughly $-(1-p/\nu)$ at $p=\nu/2$. Importance weighting should restore $-1/2$.
PDE solvers. We will run homogeneous Burgers, forced Burgers, and the porous medium equation as in Wang et al. We will report relative $L^2$ error, Z-score, 95% coverage, and wall-clock time for all baselines. We will also add a 2D-space-plus-time Burgers variant, where exact solvers become expensive.
The decisive check has two parts. Plain features at matched-$\nu$ should show Z-scores drifting above 1 as $m$ varies, which is the over-confidence signature. Importance-weighted features should track the exact solver.
Bayesian optimization. We will sample maximizers with Matérn-5/2 random-feature paths on Branin-Hoo and Hartmann. We will compare the distribution of the maximizer and the curvature (Hessian) at the maximizer under plain versus weighted features, and track immediate regret of Predictive Entropy Search. No numerical regret values for this setup were found on Lacuna, so all runs will be ours.
The hypothesis fails if plain features already match exact-solver calibration at practical $m$ in the window $\nu/2\le p<\nu$.
References
- Bayesian numerical methods for nonlinear partial differential equations
- Sample path regularity of Gaussian processes from the covariance kernel
- Optimal Rates for Random Fourier Features
- On Kernel Derivative Approximation with Random Fourier Features
- Cauchy Random Features for Operator Learning in Sobolev Space
- Continuous logistic Gaussian random measure fields for spatial distributional modelling
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
- Variational Gaussian Processes: A Functional Analysis View
- Fast kernel methods: Sobolev, physics-informed, and additive models
- Random ReLU Features: Universality, Approximation, and Composition.
- Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networks