# Random Feature Stein Discrepancies

arXiv: https://arxiv.org/abs/1806.07788 · HTML: https://mlsanity.com/paper/1806.07788/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2018.

## Built on by (most cited first, 23 of 23)

- [Robust Generalised Bayesian Inference for Intractable Likelihoods](https://mlsanity.com/paper/2104.07359/) (2021)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [A Finite-Particle Convergence Rate for Stein Variational Gradient Descent](https://mlsanity.com/paper/2211.09721/) (2022)
- [KSD Aggregated Goodness-of-fit Test](https://mlsanity.com/paper/2202.00824/) (2022)
- [Sampling with Mirrored Stein Operators](https://mlsanity.com/paper/2106.12506/) (2021)
- [Targeted Separation and Convergence with Kernel Discrepancies](https://mlsanity.com/paper/2209.12835/) (2022)
- [Controlling Moments with Kernel Stein Discrepancies](https://mlsanity.com/paper/2211.05408/) (2022)
- [MixFlows: principled variational inference via mixed flows](https://mlsanity.com/paper/2205.07475/) (2022)
- [KerJEPA: Kernel Discrepancies for Euclidean Self-Supervised Learning](https://mlsanity.com/paper/2512.19605/) (2025)
- [On the Robustness of Kernel Goodness-of-Fit Tests](https://mlsanity.com/paper/2408.05854/) (2024)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [Bounding Wasserstein distance with couplings](https://mlsanity.com/paper/2112.03152/) (2021)
- [Probabilistic Inference and Learning with Stein's Method](https://mlsanity.com/paper/2603.07467/) (2026)
- [Standardisation-function Kernel Stein Discrepancy: A Unifying View on Kernel Stein Discrepancy Tests for Goodness-of-fit](https://mlsanity.com/paper/2106.12105/) (2021)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [Active Slices for Sliced Stein Discrepancy](https://mlsanity.com/paper/2102.03159/) (2021)
- [Minimax Estimation of Kernel Stein Discrepancy: Trace versus Hilbert-Schmidt Scales](https://mlsanity.com/paper/2607.03367/) (2026)
- [The Polynomial Stein Discrepancy for Assessing Moment Convergence](https://mlsanity.com/paper/2412.05135/) (2024)
- [Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics](https://mlsanity.com/paper/2106.05739/) (2021)
- [Posterior sampling with CNN-based, Plug-and-Play regularization with applications to Post-Stack Seismic Inversion](https://mlsanity.com/paper/2212.14595/) (2022)
- [Correcting Mode Proportion Bias in Generalized Bayesian Inference via a Weighted Kernel Stein Discrepancy](https://mlsanity.com/paper/2503.02108/) (2025)
- [λ-PSD: Scalable Approximate SNR-Optimised Polynomial Stein Discrepancies](https://mlsanity.com/paper/2606.26621/) (2026)

## Abstract (arXiv)

Computable Stein discrepancies have been deployed for a variety of applications, ranging from sampler selection in posterior inference to approximate Bayesian inference to goodness-of-fit testing. Existing convergence-determining Stein discrepancies admit strong theoretical guarantees but suffer from a computational cost that grows quadratically in the sample size. While linear-time Stein discrepancies have been proposed for goodness-of-fit testing, they exhibit avoidable degradations in testing power -- even when power is explicitly optimized. To address these shortcomings, we introduce feature Stein discrepancies (PhiSDs), a new family of quality measures that can be cheaply approximated using importance sampling. We show how to construct PhiSDs that provably determine the convergence of a sample to its target and develop high-accuracy approximations -- random PhiSDs (RPhiSDs) -- which are computable in near-linear time. In our experiments with sampler selection for approximate posterior inference and goodness-of-fit testing, RPhiSDs perform as well or better than quadratic-time KSDs while being orders of magnitude faster to compute.