UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A linear-time kernel goodness-of-fit test

Jitkrittum, W; Xu, W; Szabó, Z; Fukumizu, K; Gretton, A; (2017) A linear-time kernel goodness-of-fit test. In: Guyon, I and Luxburg, U.V. and Bengio, S and Wallach and, H and Furges, R and Vishwanathan, S and Garnett., R, (eds.) Proceedings of Advances in Neural Information Processing Systems 30 (NIPS 2017). NIPS Foundation: CA, USA. (In press). Green open access

[thumbnail of Gretton_1705.07673.pdf]
Preview
Text
Gretton_1705.07673.pdf - Accepted Version

Download (1MB) | Preview

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.

Type: Proceedings paper
Title: A linear-time kernel goodness-of-fit test
Event: Advances in Neural Information Processing Systems 30 (NIPS 2017)
Open access status: An open access version is available from UCL Discovery
Publisher version: https://papers.nips.cc/paper/6630-a-linear-time-ke...
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Gatsby Computational Neurosci Unit
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1558067
Downloads since deposit
24Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item