# Optimal Online Change Detection via Random Fourier Features

arXiv: https://arxiv.org/abs/2505.17789 · HTML: https://mlsanity.com/paper/2505.17789/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 69 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 24 of 24)

- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [A Linear-Time Kernel Goodness-of-Fit Test](https://mlsanity.com/paper/1705.07673/) (2017)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Scan B-Statistic for Kernel Change-Point Detection](https://mlsanity.com/paper/1507.01279/) (2015)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [KSD Aggregated Goodness-of-fit Test](https://mlsanity.com/paper/2202.00824/) (2022)
- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [An Adaptive Test of Independence with Analytic Kernel Embeddings](https://mlsanity.com/paper/1610.04782/) (2016)
- [NEWMA: a new method for scalable model-free online change-point detection](https://mlsanity.com/paper/1805.08061/) (2018)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Sequential change-point detection based on nearest neighbors](https://mlsanity.com/paper/1604.03611/) (2016)
- [Optimal nonparametric multivariate change point detection and localization](https://mlsanity.com/paper/1910.13289/) (2019)
- [Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings](https://mlsanity.com/paper/1809.05250/) (2018)
- [Fast Online Changepoint Detection via Functional Pruning CUSUM statistics](https://mlsanity.com/paper/2110.08205/) (2021)
- [Minimax Optimal Goodness-of-Fit Testing with Kernel Stein Discrepancy](https://mlsanity.com/paper/2404.08278/) (2024)
- [Online Kernel CUSUM for Change-Point Detection](https://mlsanity.com/paper/2211.15070/) (2022)
- [A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning](https://mlsanity.com/paper/2302.02718/) (2023)
- [A review on minimax rates in change point detection and localisation](https://mlsanity.com/paper/2011.01857/) (2020)
- [Maximum Mean Discrepancy on Exponential Windows for Online Change Detection](https://mlsanity.com/paper/2205.12706/) (2022)
- [Spectral Regularized Kernel Goodness-of-Fit Tests](https://mlsanity.com/paper/2308.04561/) (2023)
- [Sequential Change-point Detection for High-dimensional and non-Euclidean Data](https://mlsanity.com/paper/1810.05973/) (2018)
- [Change point detection and inference in multivariable nonparametric models under mixing conditions](https://mlsanity.com/paper/2301.11491/) (2023)
- [A grid-based methodology for fast online changepoint detection](https://mlsanity.com/paper/2504.09573/) (2025)

## Built on by (most cited first, 2 of 2)

- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)
- [Kernel-based External Validity of Experimental Studies](https://mlsanity.com/paper/2610.13625/) (2026)

## Abstract (arXiv)

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.