Nyström Kernel Stein Discrepancy

Florian Kalinke, Zoltán Szabó, Bharath Sriperumbudur
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:388-396, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-kalinke25a, title = {Nystr{ö}m Kernel Stein Discrepancy}, author = {Kalinke, Florian and Szab{\'o}, Zolt{\'a}n and Sriperumbudur, Bharath}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {388--396}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/kalinke25a/kalinke25a.pdf}, url = {https://proceedings.mlr.press/v258/kalinke25a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Nyström Kernel Stein Discrepancy %A Florian Kalinke %A Zoltán Szabó %A Bharath Sriperumbudur %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-kalinke25a %I PMLR %P 388--396 %U https://proceedings.mlr.press/v258/kalinke25a.html %V 258 %X 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.
APA
Kalinke, F., Szabó, Z. & Sriperumbudur, B.. (2025). Nyström Kernel Stein Discrepancy. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:388-396 Available from https://proceedings.mlr.press/v258/kalinke25a.html.

Related Material