Score-Matched Witnesses for Random-Feature Stein Tests

Suppose you have a model whose density is known only up to a normalizing constant, such as an energy-based model or a Bayesian posterior, and a pile of samples. You want to test whether the samples actually come from the model. The standard tool is the kernelized Stein discrepancy. It uses only the model's score, meaning the gradient of its log-density, and it compares all pairs of samples, so its cost grows quadratically in the sample size. Cheap linear-time versions built from random Fourier features replace the kernel with a few hundred random cosine functions. These versions are known to lose almost all their power as the dimension grows. We propose a different way to use the same random features. Instead of weighting every feature equally, we fit the "witness" by score matching inside the feature space. The witness is the function that exposes where the samples and the model disagree, and score matching here means a ridge-regression-like fit of the gap between the data's score and the model's score. The resulting test statistic is a regularized quadratic form in the random features. It interpolates between the kernel Stein discrepancy and the Fisher divergence, which is the quantity score matching minimizes.

The two-sentence version is this. Random-feature Stein tests fail in high dimension because they sum many uninformative features with equal weight. If you whiten the features by their own second-moment matrix, the test instead measures how well a random-feature model can fit the score gap, and that quantity does not shrink exponentially with dimension the way Gaussian-kernel discrepancies do. A useful side effect is that score matching, which by itself only gives a training loss up to an unknown constant, now comes with a calibrated goodness-of-fit test built from the same closed-form computations.

Core Claim

Let $z(x)\in\mathbb{R}^m$ be a random Fourier feature map, and let $s_p(x)=\nabla_x\log p(x)$ be the model score. Consider witnesses $f_W(x)=Wz(x)$ with $W\in\mathbb{R}^{d\times m}$. The Langevin Stein operator applied to $f_W$ is linear in $W$: $\mathbb{E}_q[\mathcal{A}_pf_W]=\langle W,\mu\rangle$. Here $\mu=\mathbb{E}_q[s_p(x)z(x)^\top+\nabla z(x)^\top]$ is the mean "Stein feature" matrix, $\nabla z(x)$ is the $m\times d$ Jacobian of the features, and $q$ is the sample distribution.

Standard random-feature KSD takes the supremum of $\langle W,\mu\rangle$ over a Euclidean ball in $W$, which gives $\|\mu\|_F^2$. We instead constrain the witness in $L^2(q)$ with a ridge term. The constraint is $\mathrm{tr}(WGW^\top)+\lambda\|W\|_F^2\le 1$, where $G=\mathbb{E}_q[z(x)z(x)^\top]$ is the $m\times m$ feature Gram matrix. This yields

$$T_\lambda=\mathrm{tr}\big(\mu\,(G+\lambda I)^{-1}\mu^\top\big).$$

By Stein's identity under $q$, $\langle W,\mu\rangle=\mathbb{E}_q[(s_p-s_q)^\top f_W]$. So as $\lambda\to0$, $T_\lambda$ is the squared $L^2(q)$ norm of the projection of the score gap $s_p-s_q$ onto the span of the random features. That is a projected Fisher divergence $\mathbb{E}_q\|s_q-s_p\|^2$. The maximizing $W$ is exactly the closed-form random-feature score-matching estimate of that gap. As $\lambda\to\infty$, $\lambda T_\lambda$ recovers the ordinary random-feature KSD. We estimate $T_\lambda$ with the off-diagonal U-statistic $\frac{1}{n(n-1)}\sum_{i\ne j}\mathrm{tr}(\xi_i(\hat G+\lambda I)^{-1}\xi_j^\top)$, where $\xi_i$ is the Stein feature matrix at sample $x_i$, and we calibrate it with a wild bootstrap.

Two structural facts make this practical. First, $G$ is shared across all $d$ output coordinates, because the $L^2(q)$ norm of $Wz$ decouples by rows. The cost is therefore $O(nmd+m^3)$, with no $md\times md$ matrix anywhere. Second, $G$ does not involve the model at all, so it can be computed once per sample set and reused when testing many candidate models.

The claim to be tested is this. With the number of features $m(n)\to\infty$ and $\lambda(n)\to0$ at appropriate rates, the test is consistent against smooth alternatives with finite Fisher divergence. Empirically, it retains power at $d\ge 50$ on the standard Laplace, Student-t and restricted Boltzmann machine (RBM) alternatives, where unweighted random-feature KSD collapses.

Relation to Prior Work

Four papers motivate the gap. A Kernelized Stein Discrepancy for Goodness-of-fit Tests and A Kernel Test of Goodness of Fit define the quadratic-time test we aim to approximate. The Minimax Lower Bound of Kernel Stein Discrepancy Estimation shows that for Gaussian kernels the estimation constant decays like $(4\gamma+1)^{-d/4}$. That decay is the motivation for measuring a Fisher-type quantity instead, since Fisher divergence has no such built-in decay. Nyström Kernel Stein Discrepancy reports that linear random-feature and finite-set tests lose power as dimension grows, which is the failure we target.

One result constrains the design. Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features proves that fixed-$m$ random-feature discrepancy tests are not pointwise consistent. We therefore do not claim a fixed-$m$ linear-time consistent test. We claim consistency only under a growing $m(n)$, and we characterize the compute-power trade-off along that schedule.

Three papers supply the method. Denoising Score Matching with Random Fourier Features derives closed-form score matching over random Fourier features for density estimation, but never builds a test. We reuse its closed form as the witness fit. We also reuse its observation that noise injection down-weights high frequencies as an optional replacement for plain ridge regularization. Minimum Stein Discrepancy Estimators shows that score matching is a Stein discrepancy with an $L^2$-type witness class. Our statistic is the random-feature, testing-oriented instance of that correspondence. Their diffusion matrix for heavy tails is an orthogonal extension we would add only if Student-t experiments require it.

The closest competitor is Random Feature Stein Discrepancies. It uses importance-sampled random features with an $L^1$ penalty on coefficients and works well with $M\approx10$ features. It is still an unweighted norm on feature means, and it needs a hand-tuned overdispersed proposal. Our statistic differs in the geometry of the witness ball: an $L^2(q)$ ball estimated from data, rather than a fixed norm on coefficients. $\lambda$-PSD shows for polynomial bases that richer features can drive the signal-to-noise ratio to zero unless they are reweighted. Our whitening is a data-driven reweighting for Fourier bases, and part of the study is to check whether it avoids that failure. Stein Random Feature Regression moves frequencies with Stein updates for regression only. We treat frequency adaptation as a later ablation, not the core idea.

Research Program

The first component is theory. We will prove that for a fixed $\lambda>0$, $T_\lambda$ converges to a kernel Stein discrepancy with the data-adapted kernel $k_\lambda(x,y)=z(x)^\top(G+\lambda I)^{-1}z(y)$. We will then give rates in $m$ and $\lambda$ under which $T_\lambda$ converges to the projected Fisher divergence, and show this vanishes only if $q=p$ when the feature span is dense in $L^2(q)$. The unbounded Stein-feature issue will be handled with the sub-Gaussian arguments of Nyström Kernel Stein Discrepancy. We will also characterize the null distribution when $\hat G$ is estimated on the same samples, and show that the wild bootstrap is valid conditional on $\hat G$. If it is not, we fall back to estimating $\hat G$ on a small held-out subset.

The second component is a population-level calculation for the Laplace and Student-t alternatives. We will compute how $T_\lambda$, unweighted random-feature KSD and Gaussian KSD scale with $d$ at median-heuristic bandwidth. The purpose is to predict, before running experiments, where whitening should and should not help.

The third component is a secondary use of the same statistic. Because $T_\lambda(\theta)$ is closed form in the model parameters $\theta$, minimizing it trains an unnormalized model with per-step cost linear in $n$. This is the primal-space minimum-Stein-discrepancy estimator missing from Minimum Stein Discrepancy Estimators. We will test it on the 2D geometries and UCI densities used by the denoising-score-matching random-feature paper.

Baselines

The naive reference is unweighted random-feature KSD, that is, $\|\hat\mu\|_F^2$ with Gaussian random Fourier features. It uses the same $m$, the same frequencies, the same median-heuristic bandwidth and the same wild bootstrap. Because it shares every component with our method except $(\hat G+\lambda I)^{-1}$, it is also the main ablation isolating whitening. Beating it means higher rejection rate at the same $m$ and runtime, at nominal level 0.05, on the alternatives with $d\ge20$.

The strongest existing linear-time method is the $L^1$ IMQ variant from Random Feature Stein Discrepancies, run with its recommended proposal and $M$ matched to our $m$. The file reports only that it tracked the true KSD with $M=10$ features and matched or exceeded quadratic KSD power on RBM tests. No reported numerical rejection rate was found on Lacuna for it, so we rerun it.

The strongest sub-quadratic method is Nyström Kernel Stein Discrepancy with an IMQ kernel and $m\approx\sqrt n$ inducing points at $n=5000$. For this method too, no reported numerical rejection rate was found on Lacuna; the file states only that it "nearly matched" quadratic KSD. The comparison will be made at equal wall-clock time, and separately at equal $m$. For high-dimensional power specifically, the reference is Active Slices from Active Slices for Sliced Stein Discrepancy. No numerical power figure was found on Lacuna for it; only its 14x to 80x speedup over maxSKSD is reported. The quadratic IMQ KSD is the upper reference.

Finally, a Hotelling-style variant that whitens by the covariance of the Stein features, instead of by $G$, is a second ablation. It tests whether the score-matching geometry specifically matters. All methods will share the same samples and random seeds, and bandwidth and $\lambda$ will be tuned on separate null-only simulations with an equal budget for every method.

Why not just…?

Why not just use Nyström KSD? It is provably consistent and already reported to hold power where random features fail, so it is a real threat. Our cost $O(nmd+m^3)$ has the same cubic term, so we do not claim a large speed advantage. The case for our method rests on power at equal compute, and on reusing $\hat G$ across many candidate models, for instance in sampler hyperparameter sweeps, which Nyström cannot do because its projection depends on the model's Stein kernel. If Nyström matches our power at equal time on the $d\in[50,100]$ alternatives, the testing contribution reduces to the Fisher-divergence interpretation and the training use, and we will report it that way.

Why not just use $L^1$ IMQ random-feature Stein discrepancies with more features? They are already sample-efficient. However, their witness ball is a fixed norm on coefficients that ignores how features are distributed under the data, and Nyström Kernel Stein Discrepancy shows random-feature approaches losing power with dimension. The equal-$m$ power-versus-$d$ curves will show directly whether data whitening adds anything beyond the $L^1$ geometry. We will also try an $L^1$-whitened hybrid in case the two are complementary.

Why not whiten by the full Stein-feature covariance, which is SNR-optimal for a fixed feature set? That matrix is $md\times md$. At $d=100$ and $m=500$ this is a 50,000-dimensional matrix that cannot be inverted and cannot be estimated from $n=5000$ samples. Our $G$-whitening exploits the row-decoupling of the $L^2(q)$ norm and stays $m\times m$. The Hotelling ablation at small $d$ will show how much power this restriction costs.

Why not use sliced Stein tests for the high-dimensional case? On the single-coordinate "diffusion" alternative, a linear slice is exactly the right tool, and we expect Active Slices to win there. We will report that loss. Our target is alternatives such as Laplace and Student-t tails and RBM perturbations, where the discrepancy is spread over many directions. On those, the eigendecomposition used by Active Slices relies on noisy estimates of the score difference.

Proposed Experiments

We will use the synthetic suite of Nyström Kernel Stein Discrepancy and Sliced Kernelized Stein Discrepancy: a standard Gaussian null against Laplace, Student-t and single-coordinate alternatives, with $d\in\{2,5,10,20,50,100\}$ and $n=5000$. The Gaussian-Bernoulli RBM perturbation benchmark from A Linear-Time Kernel Goodness-of-Fit Test is added, reporting rejection rate at $\alpha=0.05$, type-I error under the null, and wall-clock time. We will sweep $m\in\{10,50,200,1000\}$ and $\lambda$ over five orders of magnitude to trace the interpolation from KSD to Fisher divergence. The practical check is the SGLD step-size selection task from Random Feature Stein Discrepancies, which asks whether the statistic picks the same step size as quadratic KSD. As a score-matching tie-in, we will fit random-feature score-matching density models to RedWine, WhiteWine and MiniBoone, and test them with our statistic against held-out data.

Three outcomes decide the proposal. The first is whether whitened random-feature power at $d=100$ stays within reach of Nyström and quadratic KSD while the unweighted variant collapses. The second is whether type-I error stays at nominal level when $\hat G$ is estimated in-sample. The third is whether power at fixed $n$ grows with $m$, as the consistency theory predicts, rather than saturating. If whitening fails the first check, the idea is wrong and we will say so. If it passes but loses to Nyström at equal time, the result stands as an explanation of why random-feature Stein tests collapse, not as a better test.