Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit
We characterize the asymptotic performance of nonparametric goodness of fit testing. The exponential decay rate of the type-II error probability is used as the asymptotic performance metric, and a test is optimal if it achieves the maximum rate subject to a constant level constraint on the type-I error probability. We show that two classes of Maximum Mean Discrepancy (MMD) based tests attain this optimality on $\mathbb R^d$, while the quadratic-time Kernel Stein Discrepancy (KSD) based tests achieve the maximum exponential decay rate under a relaxed level constraint. Under the same performance metric, we proceed to show that the quadratic-time MMD based two-sample tests are also optimal for general two-sample problems, provided that kernels are bounded continuous and characteristic. Key to our approach are Sanov's theorem from large deviation theory and the weak metrizable properties of the MMD and KSD.
Code (0)
등록된 구현이 없습니다.
Tasks
Two-sample testingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Asymptotically Optimal One- and Two-Sample Testing with Kernels
We characterize the asymptotic performance of nonparametric one- and two-sample testing. The exponential decay rate or error exponent of the type-II error probability is used as the asymptotic performance metric, and an …
Change DetectionTwo-sample testingVocal Bursts Valence PredictionAsymptotically Optimal Sequential Testing with Markovian Data
We study one-sided and $α$-correct sequential hypothesis testing for data generated by an ergodic, finite-state Markov chain. The null hypothesis is that the unknown transition matrix belongs to a prescribed set $P$ of s…
Sequential Controlled Sensing for Composite Multihypothesis Testing
The problem of multi-hypothesis testing with controlled sensing of observations is considered. The distribution of observations collected under each control is assumed to follow a single-parameter exponential family dist…
Two-sample testingA Convex Parametrization of a New Class of Universal Kernel Functions
The accuracy and complexity of kernel learning algorithms is determined by the set of kernels over which it is able to optimize. An ideal set of kernels should: admit a linear parameterization (tractability); be dense in…
AllLinear Hypothesis Testing in Dense High-Dimensional Linear Models
We propose a methodology for testing linear hypothesis in high-dimensional linear models. The proposed test does not impose any restriction on the size of the model, i.e. model sparsity or the loading vector representing…
regressionTwo-sample testingvalidVocal Bursts Intensity Prediction