A Linear-Time Kernel Goodness-of-Fit Test

Abstract

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.

Accepted to NIPS 2017

References in corpus (2)

• Measuring Sample Quality with Kernels
• An Adaptive Test of Independence with Analytic Kernel Embeddings

Cited by in corpus (19)

• Learning the Stein Discrepancy for Training and Evaluating Energy-Based Models without Sampling
• A Kernel Two-Sample Test for Functional Data
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence
• Metrizing Weak Convergence with Maximum Mean Discrepancies
• Sliced Kernelized Stein Discrepancy
• MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means
• Learning deep kernels for exponential family densities
• hyppo: A Multivariate Hypothesis Testing Python Package
• Learning Kernel Tests Without Data Splitting
• Classification Logit Two-sample Testing by Neural Networks
• Maximum Mean Discrepancy for Generalization in the Presence of Distribution and Missingness Shift
• Kernelized Complete Conditional Stein Discrepancy
• Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit
• Testing Goodness of Fit of Conditional Density Models with Kernels
• Sampling with Mirrored Stein Operators
• Asymptotically Optimal One- and Two-Sample Testing with Kernels
• Active Slices for Sliced Stein Discrepancy
• Bayesian posterior approximation via greedy particle optimization
• Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data