# A Linear-Time Kernel Goodness-of-Fit Test

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2017.

## Built on by (most cited first, 30 of 41)

- [Benchmarking Simulation-Based Inference](https://mlsanity.com/paper/2101.04653/) (2021)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [KSD Aggregated Goodness-of-fit Test](https://mlsanity.com/paper/2202.00824/) (2022)
- [Detecting Adversarial Data by Probing Multiple Perturbations Using Expected Perturbation Score](https://mlsanity.com/paper/2305.16035/) (2023)
- [Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data](https://mlsanity.com/paper/2106.07636/) (2021)
- [Sampling with Mirrored Stein Operators](https://mlsanity.com/paper/2106.12506/) (2021)
- [Controlling Moments with Kernel Stein Discrepancies](https://mlsanity.com/paper/2211.05408/) (2022)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (2021)
- [Efficient and Generalizable Tuning Strategies for Stochastic Gradient MCMC](https://mlsanity.com/paper/2105.13059/) (2021)
- [Maximum Mean Discrepancy for Generalization in the Presence of Distribution and Missingness Shift](https://mlsanity.com/paper/2111.10344/) (2021)
- [Kernel Two-Sample Tests for Manifold Data](https://mlsanity.com/paper/2105.03425/) (2021)
- [On the Robustness of Kernel Goodness-of-Fit Tests](https://mlsanity.com/paper/2408.05854/) (2024)
- [Variance-Aware Estimation of Kernel Mean Embedding](https://mlsanity.com/paper/2210.06672/) (2022)
- [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)
- [Using Perturbation to Improve Goodness-of-Fit Tests based on Kernelized Stein Discrepancy](https://mlsanity.com/paper/2304.14762/) (2023)
- [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)
- [AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators](https://mlsanity.com/paper/2203.03673/) (2022)
- [A Fourier representation of kernel Stein discrepancy with application to Goodness-of-Fit tests for measures on infinite dimensional Hilbert spaces](https://mlsanity.com/paper/2206.04552/) (2022)
- [Minimax Estimation of Kernel Stein Discrepancy: Trace versus Hilbert-Schmidt Scales](https://mlsanity.com/paper/2607.03367/) (2026)
- [A Stein Goodness of fit Test for Exponential Random Graph Models](https://mlsanity.com/paper/2103.00580/) (2021)
- [Instrument Space Selection for Kernel Maximum Moment Restriction](https://mlsanity.com/paper/2106.03340/) (2021)
- [Neural Stein critics with staged L2-regularization](https://mlsanity.com/paper/2207.03406/) (2022)
- [Private independence testing across two parties](https://mlsanity.com/paper/2207.03652/) (2022)
- [Robust Approximate Sampling via Stochastic Gradient Barker Dynamics](https://mlsanity.com/paper/2405.08999/) (2024)
- [The Polynomial Stein Discrepancy for Assessing Moment Convergence](https://mlsanity.com/paper/2412.05135/) (2024)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)
- [Score-based Generative Modeling for Conditional Independence Testing](https://mlsanity.com/paper/2505.23309/) (2025)
- [Kernel Tests of Equivalence](https://mlsanity.com/paper/2603.10886/) (2026)

## Abstract (arXiv)

We propose a novel adaptive test of goodness-of-fit, with computational cost linear in the number of samples. We learn the test features that best indicate the differences between observed samples and a reference model, by minimizing the false negative rate. These features are constructed via Stein's method, meaning that it is not necessary to compute the normalising constant of the model. We analyse the asymptotic Bahadur efficiency of the new test, and prove that under a mean-shift alternative, our test always has greater relative efficiency than a previous linear-time kernel test, regardless of the choice of parameters for that test. In experiments, the performance of our method exceeds that of the earlier linear-time test, and matches or exceeds the power of a quadratic-time kernel test. In high dimensions and where model structure may be exploited, our goodness of fit test performs far better than a quadratic-time two-sample test based on the Maximum Mean Discrepancy, with samples drawn from the model.