Our paper, "A Linear-Time Kernel Goodness-of-Fit Test," received the Best Paper Award at NeurIPS 2017 (Advances in Neural Information Processing Systems 30). The work is co-authored by Sentinel Assurance co-founder Wenkai Xu, together with Wittawat Jitkrittum and Arthur Gretton (Gatsby Computational Neuroscience Unit, University College London), and Zoltan Szabo and Kenji Fukumizu (Institute of Statistical Mathematics).
What the paper does
- Introduces an adaptive goodness-of-fit test whose computational cost scales linearly with the number of samples, instead of the quadratic cost typical of earlier kernel-based tests.
- Learns the specific test features that best indicate where a model diverges from the data, rather than returning a single undifferentiated statistic.
- Built with Stein's method, so it never needs to compute the model's normalizing constant, which is often intractable in practice.
- Proven to have greater relative (Bahadur) efficiency than prior linear-time kernel tests under mean-shift alternatives, and matches or exceeds the power of quadratic-time tests in high-dimensional settings.
Our take
A test that can't scale to the amount of data a real system produces doesn't get run in practice, however sound the theory is. Getting goodness-of-fit testing down to linear time while keeping it interpretable is exactly the kind of unglamorous, foundational work that makes rigorous verification something you can run continuously, not just as an occasional audit.