Optimal Online Change Detection via Random Fourier Features

Florian Kalinke, Shakeel Gavioli-Akilagun

Abstract

Detecting distributional changes in high-dimensional data streams is a fundamental challenge in anomaly detection and monitoring. Traditional methods often rely on historical "normal" data or manually tuned window sizes, which limit their applicability in dynamic environments. This paper introduces Online RFF-MMD, a kernel-based approach that is genuinely online and window-free. By utilizing Random Fourier Features (RFF) and a dyadic grid testing framework, the algorithm achieves minimax optimal detection delay with $O(r \log n)$ time and space complexity. Empirical evaluations on synthetic and real-world datasets, including MNIST and human activity sensing, demonstrate its superior performance and scalability.

Introduction

Online Change Point Detection (CPD) aims to identify the exact moment the statistical distribution of a data stream shifts. This task is vital for applications ranging from cardiac monitoring to network security. However, existing non-parametric methods face significant hurdles. Many are not "genuinely online," requiring a clean historical dataset to define the pre-change distribution. Others suffer from the "window parameter dilemma," where the choice of look-back window size creates a trade-off between sensitivity and detection speed.

Comparison of Online RFF-MMD with state-of-the-art methods across key operational metrics.

Furthermore, while kernel-based methods are effective for high-dimensional data, their quadratic computational costs ($O(n^2)$) often preclude real-time application on high-volume streams.

Methodology

The proposed Online RFF-MMD algorithm addresses these challenges by integrating three core components:

  1. Maximum Mean Discrepancy (MMD): A robust kernel-based metric used to quantify the distance between distributions.
  2. Random Fourier Features (RFF): To bypass the $O(n^2)$ cost, RFFs map data into a finite-dimensional feature space, enabling constant-time ($O(1)$) updates per observation.
  3. Dyadic Grid Testing: Instead of exhaustive testing, the algorithm evaluates potential change points on a dyadic grid (at distances of $2^j$ from the current time). This reduces the number of active tests to $O(\log n)$.
The dyadic grid merging process, illustrating how blocks of data are combined to maintain logarithmic complexity.

By combining these techniques, the algorithm ensures a total complexity of $O(r \log n)$, where $r$ is the number of random features.

Experimental Evaluation

The algorithm was tested against several benchmarks to verify its performance in diverse scenarios:

  • Synthetic Data: Multivariate Gaussian, Laplace, and Uniform distributions were used to assess the trade-off between false alarms and detection delay.
  • High-Dimensional Streams: MNIST (784-dim) data where changes involve transitions between digit classes.
  • Real-World Sensors: HASC (Human Activity Sensing Consortium) 3D accelerometer data for detecting activity transitions (e.g., walking to standing).
  • Audio Analysis: MazurkaBL music dataset for detecting changes in musical expression.

Key Results and Insights

The paper establishes that Online RFF-MMD is minimax optimal, meaning no algorithm can achieve a faster detection delay for a fixed false alarm rate. Key findings include:

  • No Burn-in: The algorithm learns "normal" behavior on the fly by comparing recent data against the entire preceding stream.
  • Scalability: Logarithmic scaling was empirically confirmed, allowing the processing of hundreds of thousands of observations with minimal overhead.
  • Robustness: The method maintained high performance in high-dimensional settings (e.g., MNIST) where other methods often degrade.

Conclusion and Future Work

Online RFF-MMD provides a scalable, theoretically grounded solution for online CPD. Future research directions include automated kernel bandwidth optimization, extending the framework to handle autocorrelated (non-i.i.d.) data, and refining "restart" mechanisms for continuous monitoring of multiple change points.

Summary updated

BibTeX
@inproceedings{kalinke2025optimal,
  author = {Florian Kalinke and Shakeel Gavioli-Akilagun},
  title = {{Optimal Online Change Detection via Random Fourier Features}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=GhVQnjVjlI},
}
Figure