# Nystr"om Kernel Stein Discrepancy

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 90 references that are in the map.
- First posted on arXiv 12 Jun 2024.

## Builds on (most cited first, 30 of 38)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Measuring Sample Quality with Kernels](https://mlsanity.com/paper/1703.01717/) (2017)
- [Measuring Sample Quality with Stein's Method](https://mlsanity.com/paper/1506.03039/) (2015)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [Fast Two-Sample Testing with Analytic Representations of Probability Measures](https://mlsanity.com/paper/1506.04725/) (2015)
- [Stein Points](https://mlsanity.com/paper/1803.10161/) (2018)
- [A Linear-Time Kernel Goodness-of-Fit Test](https://mlsanity.com/paper/1705.07673/) (2017)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Stein's Method Meets Computational Statistics: A Review of Some Recent Developments](https://mlsanity.com/paper/2105.03481/) (2021)
- [Detecting Out-of-Distribution Inputs to Deep Generative Models Using Typicality](https://mlsanity.com/paper/1906.02994/) (2019)
- [Stochastic Stein Discrepancies](https://mlsanity.com/paper/2007.02857/) (2020)
- [Stein Point Markov Chain Monte Carlo](https://mlsanity.com/paper/1905.03673/) (2019)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget](https://mlsanity.com/paper/1304.5299/) (2013)
- [Random Feature Stein Discrepancies](https://mlsanity.com/paper/1806.07788/) (2018)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [KSD Aggregated Goodness-of-fit Test](https://mlsanity.com/paper/2202.00824/) (2022)
- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [Testing Goodness of Fit of Conditional Density Models with Kernels](https://mlsanity.com/paper/2002.10271/) (2020)
- [An Adaptive Test of Independence with Analytic Kernel Embeddings](https://mlsanity.com/paper/1610.04782/) (2016)
- [Kernelized Stein Discrepancy Tests of Goodness-of-fit for Time-to-Event Data](https://mlsanity.com/paper/2008.08397/) (2020)
- [Efficient and Generalizable Tuning Strategies for Stochastic Gradient MCMC](https://mlsanity.com/paper/2105.13059/) (2021)
- [Bayesian posterior approximation via greedy particle optimization](https://mlsanity.com/paper/1805.07912/) (2018)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)

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

- [The Minimax Lower Bound of Kernel Stein Discrepancy Estimation](https://mlsanity.com/paper/2510.15058/) (2025)
- [DriftXpress: Faster Drifting Models via Projected RKHS Fields](https://mlsanity.com/paper/2605.12183/) (2026)
- [Minimax Estimation of Kernel Stein Discrepancy: Trace versus Hilbert-Schmidt Scales](https://mlsanity.com/paper/2607.03367/) (2026)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)

## Abstract (arXiv)

Kernel methods underpin many of the most successful approaches in data science and statistics, and they allow representing probability measures as elements of a reproducing kernel Hilbert space without loss of information. Recently, the kernel Stein discrepancy (KSD), which combines Stein's method with the flexibility of kernel techniques, gained considerable attention. Through the Stein operator, KSD allows the construction of powerful goodness-of-fit tests where it is sufficient to know the target distribution up to a multiplicative constant. However, the typical U- and V-statistic-based KSD estimators suffer from a quadratic runtime complexity, which hinders their application in large-scale settings. In this work, we propose a Nystr"om-based KSD acceleration -- with runtime mathcal Oleft(mn+m3right) for n samples and mll n Nystr"om points -- , show its √n-consistency with a classical sub-Gaussian assumption, and demonstrate its applicability for goodness-of-fit testing on a suite of benchmarks. We also show the √ n-consistency of the quadratic-time KSD estimator.