Computationally efficient goodness-of-fit tests through kernelized Stein discrepancy

Zhihan Huang; Ziang Niu

stat.MLDec 23, 2025

Computationally efficient goodness-of-fit tests through kernelized Stein discrepancy

Authors: Zhihan Huang, Ziang Niu

Organizations: Department of Statistics and Data Science University of Pennsylvania

Abstract

Models with intractable normalizing constants are widely used in statistics and machine learning. Assessing the adequacy of such models poses significant challenges: obtaining samples from the fitted model often requires sophisticated sampling algorithms. Moreover, model fitting sometimes requires iterative numerical optimization, making bootstrap procedures that require repeated refitting computationally expensive. In this paper, we leverage the kernel-based testing framework to develop a general semiparametric goodness-of-fit test based on the kernelized Stein discrepancy. We establish the consistency and the asymptotic null distribution of the test statistic under general nuisance estimation. To produce a level- $α$ test, we propose a novel influence-adjusted wild bootstrap that requires neither refitting the model nor sampling from it. We prove the consistency of the proposed bootstrap test procedure under the null and the alternative, and characterize its limiting power under contiguous local alternatives. Across simulations ranging from classical normality testing to models with intractable likelihoods, the proposed test delivers competitive or superior power at a computational cost orders of magnitude lower than that of existing approaches. We illustrate the method by assessing the adequacy of a protein signaling network model for reverse-phase protein array data from lung adenocarcinoma tumors. As a complementary insight, we show that the SKSD test can be regarded as a nonparametric score test under exponentially tilted models, connecting score-based and distance-based goodness-of-fit testing.

Figures & tables

Figure 1 : Gaussianity tests with maximum-likelihood nuisance estimation.

Figure 2 : Kernel exponential-family tests with minimum-KSD nuisance estimation. The horizontal axis is the dimension-normalized signal

s=\theta_{2}\sqrt{d}

. The rightmost boxplots summarize the

d=1

cell-level mean runtimes across the displayed signals, scaled to 100 replications and shown on a logarithmic scale.

Figure 3 : Conditional Gaussian structural tests with score-matching nuisance estimation.

Figure 4 : Gaussian–Bernoulli RBM tests with nonlinear score-matching nuisance estimation.

Figure 5 : TCGA-LUAD model-adequacy p-values under the 18-edge support (left) and complete 45-edge support (right). Points show raw and Holm-adjusted p-values from the influence-adjusted procedure and Brück et al. The dashed horizontal line marks

0.05

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6 : One-dimensional kernel exponential-family comparison with score-matching nuisance estimation. The panels vary the fitted basis span, while

\phi_{3}

is omitted from each null family. The horizontal axis is

t=\eta\,\operatorname{SD}_{P_{0}}\{\phi_{3}(X)\}

. Curves show rejection rates at the nominal

0.05

p-value cutoff without size correction. The dashed line marks

0.05

Figure 7 : Structural alternatives to the conditional Gaussian null ring. Orange solid edges show weakened ring interactions. Gray solid edges are ring interactions that remain unchanged in the triadic-closure path. Colored dashed edges show newly added interactions. Their weights are $\delta$ in the first two paths and $2\delta$ in the third.

Figure 8 : Goodness-of-fit tests for the Watson family against Bingham dispersion alternatives on

\mathbb{S}^{2}

. Each panel uses

n=100

B=499

, and

1{,}000

Monte Carlo replications per signal. The dashed line marks the nominal level

0.05

. The rightmost panel shows cell mean runtimes across the six signals for

\kappa_{0}=4

, scaled to

100

replications and displayed on a logarithmic axis.

Discrepancy/ Distance	Computational complexity
Discrepancy/ Distance	$d=1$	$d=2$	$d>2$
K–S distance	$n\log n$	$n^{2}$	NP-hard
W-1 distance	$n\log n$	$n^{3}$	$n^{3}$
MMD	$(n+m)^{2}$	$(n+m)^{2}$	$(n+m)^{2}$
KSD	$n^{2}$	$n^{2}$	$n^{2}$

Appendix

Table 1 : Representative costs for the IPM-based statistics discussed above. Here

n

is the data sample size and

m

is the Monte Carlo reference-sample size used for MMD. The W-1 entries assume equally sized empirical measures.

Explore similar work

May 24, 2026stat.ML

Nyström Kernel Stein Discrepancy Tests

Kernel Stein discrepancy (KSD) is among the most popular goodness-of-fit (GoF) measures on general domains with a large number of successful deployments. One of the main applications of KSD is in constructing powerful GoF tests. However, tests relying on the classical U-/V-statistic-based KSD estimators have two major drawbacks. (i) Their runtime scales quadratically in the number of samples. (ii) Their asymptotic null distribution is computationally intractable in most cases, typically handled by bootstrapping. While it is known that the Nyström method permits accelerating KSD estimation with no loss of statistical accuracy under mild conditions, to the best of our knowledge, the fundamental question of its impact on bootstrap-based GoF testing is open; resolving this question is the focus of the current paper. In particular, we prove that the key properties of the quadratic-time bootstrapped KSD-based GoF test (asymptotic level and local consistency) are preserved by its Nyström acceleration. We numerically demonstrate the efficiency of the accelerated KSD estimator and bootstrap in the context of GoF testing of spherical and functional data. Our numerical results show that the Nyström-accelerated method performs statistically on-par with the quadratic-time approach, while requiring substantially smaller runtime.

Florian Kalinke, Zoltán Szabó, Bharath K. Sriperumbudur

Chair of Information Systems Karlsruhe Institute of Technology Am Fasanengarten 5, 76131 Karlsruhe, Germany · Department of Statistics London School of Economics Houghton Street, London, WC2A 2AE, UK · Department of Statistics The Pennsylvania State UniversityMay University Park, PA 16802, USA

Kernel Method Discrepancy

Ask PDF

Aug 5, 2026stat.ME

Nonparametric Goodness-of-fit Testing under Covariate Shift

This paper develops procedures for nonparametric goodness-of-fit testing under covariate shift, where labelled data are drawn from a source population but goodness-of-fit is evaluated for a target population. The distribution mismatch is quantified by either a bounded moment condition or a sub-exponential tail condition on the target-to-source density ratio. Our method combines truncated importance-weighting kernel ridge regression with a multiplier bootstrap to construct confidence sets for the regression function. The truncation stabilizes the importance- weighting kernel ridge regression as well as the bootstrap calibration, making our approach applicable even when the density ratio has heavy tails. We prove nonasymptotic validity and sharpness of the resulting confidence sets under suitable operator compatibility conditions, and establish explicit error rates for coverage probability under specific conditions on the target- to-source density ratio and on the spectral decay of the kernel integral operator. Numerical experiments corroborate our theoretical findings.

Zhen Hou, Dong Xia

Department of Mathematics Hong Kong University of Science and Technology

Covariate Shift Exponential Family Model-Based Bootstrap Kernel Ridge Regression

Ask PDF

May 7, 2026stat.ML

Kernel Selection is Model Selection: A Unified Complexity-Penalized Approach for MMD Two-Sample Tests

The Maximum Mean Discrepancy (MMD) is a cornerstone statistic for nonparametric two-sample testing, but its test power is dictated entirely by the chosen kernel. Because any fixed kernel inherently fails to distinguish certain distributions, the kernel must be dynamically optimized. However, data-driven optimization violates the foundational i.i.d. assumption, forcing a strict trade-off in existing frameworks. Ratio criteria ignore this dependence, inducing overfitting and variance collapse on rich kernel classes. Conversely, aggregation methods bypass the dependence using finite grids, but this strategy cannot scale to continuous search spaces like deep kernels. To break this dichotomy, we establish data-driven kernel selection as a model selection problem. We propose Complexity-Penalized MMD (CP-MMD), a criterion derived by applying the two-sample uniform concentration inequality of preceding works to the post-optimization MMD problem. The resulting penalty bounds the empirical MMD by the complexity of the kernel search space, mathematically absorbing the cost of optimization, so that CP-MMD enables direct, grid-free maximization over continuous parametric classes, including scalar bandwidths, polynomial feature bandwidths, and deep network parameters. By formally accounting for optimization complexity, we prove that CP-MMD maximizes true test power while ensuring unconditional Type-I validity. Consequently, CP-MMD enables grid-free kernel selection across linear, polynomial-feature, and deep regimes, matching or exceeding state-of-the-art test power.

Yijin Ni, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA

Maximum Mean Discrepancy Kernel Method Model Selection Two-Sample Testing Quadratic Slack Penalty Data-Driven

Ask PDF