Research map / Learning theory and algorithms / Sample complexity
Optimal Online Change Detection via Random Fourier Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Online RFF-MMD, a window-free, genuinely online sequential change detector that runs sequential random-Fourier-feature MMD tests on a dyadic grid, with logarithmic per-observation time and space, and proves minimax-optimal detection delay up to log terms.
Problem
Online non-parametric change point detection in multivariate data streams without known pre-change distribution, historical reference data, or a user-specified window parameter, with low computational cost per observation.
Approach
Approximate the squared MMD with random Fourier features so each local two-sample statistic is a Euclidean distance of mean feature vectors that can be updated online; test all dyadic split points of the stream with a threshold sequence, and maintain the dyadic partition with a logarithmic list of merged feature-sum windows.
Key results
- On synthetic d=20 Gaussian to mixed normal/Laplace/Uniform changes, Online RFF-MMD achieves smaller expected detection delay than NEWMA, Scan B-statistics and OKCUSUM at matched ARL.
- On HASC (10 datasets), Online RFF MMD gets average delay 21.86 versus OKCUSUM 17.44, ScanB 31.20, NewMA 34.25, with 2 too-early and 1 miss.
- Theory: minimax lower bound shows detection delay of order log(1/alpha)/MMD^2 is optimal up to log terms; runtime per observation is O(r log n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Online RFF-MMD instead of OKCUSUM | HASC change detection · HASC 2011, 10 derived datasets | Average delay: 17.44 -> 21.86 | Hurt |
| Use Online RFF-MMD instead of ScanB | HASC change detection · HASC 2011, 10 derived datasets | Average delay: 31.20 -> 21.86 | Helped |
| Use Online RFF-MMD instead of NewMA | HASC change detection · HASC 2011, 10 derived datasets | Average delay: 34.25 -> 21.86 | Helped |
| Use Online RFF-MMD instead of RuLSIF | HASC change detection · HASC 2011, 10 derived datasets | Too early: 8 -> 2 | Helped |
| Use Online RFF-MMD instead of RuLSIF | HASC change detection · HASC 2011, 10 derived datasets | Average delay: 4.50 -> 21.86 | Hurt |
| Use Online RFF-MMD instead of ScanB | HASC change detection · HASC 2011, 10 derived datasets | Miss: 0 -> 1 | Hurt |
| Use the distribution-free threshold sequence instead of Monte Carlo threshold estimation (ablation) | Online RFF-MMD · MNIST digit 0 to digits 1–9 | Expected detection delay | Hurt |
| Use Online RFF-MMD instead of tested competitors | Synthetic change detection · Synthetic post-change distributions: mixed normal, Laplace, and Uniform | Average detection delay | Helped |
| Use Online RFF-MMD instead of tested competitors | MNIST change detection · MNIST digit 0 to digits 1–3 | Expected detection delay | Helped |
| Use distribution-dependent thresholds instead of distribution-free thresholds (ablation) | Online RFF-MMD · MNIST digit 0 to digits 1–9 | Expected detection delay | Helped |
Surprising findings
- On HASC, OKCUSUM achieves a lower average delay (17.44) than Online RFF MMD (21.86), and RuLSIF with no pre-change data achieves 4.50 but flags 8 cases too early.
Limitations
- Kernel choice and parameters affect power and are selected with few samples; kernel optimization in the sequential setting is left open.
- Theory assumes i.i.d. data; non-i.i.d. (mixing or functional dependence) settings are future work.
- Distribution-free thresholds are conservative, increasing detection delay (e.g. missed digit-5 change at guaranteed ARL 1e5).
Experimental setup
Datasets: MNIST HASC MazurkaBL
Benchmarks: MNIST digit change detection HASC MazurkaBL synthetic streams
Metrics: expected detection delay average run length average runtime per insert average detection delay too early count miss count
Baselines: NEWMA Scan B-statistics Online kernel CUSUM RuLSIF
Builds on: maximum mean discrepancy random Fourier features NEWMA Scan B-statistics online kernel CUSUM
Closest papers by meaning
- Restarted Bayesian Online Change-point Detector achieves Optimal Detection Delay (ICML 2020 · similarity 0.89)
- Beyond Euclidean Summaries: Online Change Point Detection for Distribution-Valued Data (ICML 2026 · similarity 0.88)
- Online Change Point Detection for Multivariate Inhomogeneous Poisson Processes Time Series (ICML 2026 · similarity 0.87)
- Reducing sequential change detection to sequential estimation (ICML 2024 · similarity 0.87)
- Non-parametric Online Change Point Detection on Riemannian Manifolds (ICML 2024 · similarity 0.86)
- Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.