Nyström Kernel Stein Discrepancy
This work addresses scalability issues for statisticians and data scientists using KSD for goodness-of-fit tests, though it is incremental as it builds on existing KSD methods with a computational improvement.
The paper tackles the quadratic runtime complexity of kernel Stein discrepancy (KSD) estimators, which limits large-scale applications, by proposing a Nyström-based acceleration that reduces runtime to O(mn + m^3) and demonstrates √n-consistency and applicability in goodness-of-fit testing on benchmarks.
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öm-based KSD acceleration -- with runtime $\mathcal O\left(mn+m^3\right)$ for $n$ samples and $m\ll n$ Nyström points -- , show its $\sqrt{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 $\sqrt n$-consistency of the quadratic-time KSD estimator.