Optimal Online Change Detection via Random Fourier Features

Shakeel Gavioli-Akilagun (City University of Hong Kong) · Florian Kalinke (Karlsruhe Institute of Technology (KIT))

competitive performancedetection delayinformation-theoretic boundskernel-based two-sample testinglogarithmic space complexitylogarithmic time complexityminimax sensemultivariate data streamsnumerical studiesonline non-parametric change point detectionrandom fourier featuressequential testing procedurestate of the art synthetic data theoretical guarantees

This article studies the problem of online non-parametric change point detection in multivariate data streams. We approach the problem through the lens of kernel-based two-sample testing and introduce a sequential testing procedure based on random Fourier features, running with logarithmic time complexity per observation and with overall logarithmic space complexity. The algorithm has two advantages compared to the state of the art. First, our approach is genuinely online, and no access to training data known to be from the pre-change distribution is necessary. Second, the algorithm does not require the user to specify a window parameter over which local tests are to be calculated. We prove strong theoretical guarantees on the algorithm's performance, including information-theoretic bounds demonstrating that the detection delay is optimal in the minimax sense. Numerical studies on real and synthetic data show that our algorithm is competitive with respect to the state of the art.