Abstract
Online change point detection (CPD) is the task of identifying sudden changes in the underlying distribution of a data stream in real-time. Traditional methods often rely on restrictive parametric assumptions or lack non-asymptotic theoretical guarantees. We propose a flexible, contrastive framework that trains a discriminator to distinguish between pre-change and post-change data. This approach handles both simple parametric shifts and complex nonparametric changes. We provide the first non-asymptotic high-probability bounds for detection delay using neural networks and introduce FALCON, a computationally efficient variant optimized for real-time use.
Introduction
Identifying when a data stream's distribution changes is a fundamental problem in fields ranging from finance to activity recognition. The "online" setting is particularly demanding, as algorithms must process data sequentially and decide "on the fly" whether a change has occurred. The primary challenge lies in balancing two competing objectives: minimizing false alarms (Type I error) and minimizing detection delay.
Existing methods often fall into two camps: parametric approaches (like CUSUM) which are efficient but fragile if assumptions are violated, and nonparametric methods which are robust but often lack rigorous theoretical guarantees or suffer from high computational costs. This work seeks a "universal" approach that is both theoretically grounded and computationally efficient.
Methods
The core of our approach is a contrastive framework. Rather than performing explicit density estimation—which is notoriously difficult in high dimensions—we train an auxiliary classifier (a discriminator) to distinguish between segments of the time series.
The Contrastive Objective
We maximize a cross-entropy-based functional that measures the discrepancy between two data segments. If a change occurs at time $\tau$, a well-trained discriminator will easily separate data points before $\tau$ from those after $\tau$. This discriminator implicitly learns the log-density ratio, which is the sufficient statistic for optimal change detection. This objective is fundamentally linked to the Jensen-Shannon (JS) divergence between the pre- and post-change distributions.
Algorithms and Efficiency
The base procedure (Algorithm II.1) searches for the optimal change point candidate by maximizing the contrastive loss over a function class, such as polynomials or neural networks. While theoretically sound, this brute-force approach has $O(t^2)$ complexity. To address this, we developed FALCON (Fast ALgorithm based on CONtrastive approach). FALCON utilizes Online Convex Optimization—specifically the "Follow the Approximate Leader" (FTAL) strategy—to update discriminator parameters recursively, enabling real-time performance.
Theoretical Foundations
A key contribution of this work is the derivation of non-asymptotic bounds on the Average Running Length (ARL) and the Expected Detection Delay (EDD). By applying VC-dimension and bracketing number theory, we provide safety guarantees for using complex function classes like ReLU neural networks in sequential testing.
Experimental Evaluation
We evaluated the contrastive approach against several baselines across synthetic and real-world datasets.
Synthetic Benchmarks
The method was tested on mean shifts, variance changes, and complex distributional shifts (e.g., shifting from a Uniform to a Gaussian distribution while keeping the first two moments identical). While specialized detectors like CUSUM failed on variance or pure distributional changes, the contrastive approach remained robust.
Real-World Performance
- Financial Data (Sberbank): The polynomial-based contrastive method achieved a detection delay of 9.0, significantly outperforming the M-statistic (41.2) and KLIEP (49.8).
- Speech Recognition (CENSREC): Neural network discriminators proved highly robust to background noise, maintaining low detection delays even at low Signal-to-Noise Ratios (SNR).
- Activity Recognition (WISDM) and Room Occupancy (UCI): The framework successfully handled multi-variable data streams, demonstrating its versatility across domains.
Conclusion
The contrastive framework bridges the gap between flexible deep learning models and rigorous statistical testing. By focusing on density ratios rather than density estimation, it provides a powerful tool for online CPD. Future work will address temporal dependencies (autocorrelation) in the theoretical analysis and explore scenarios with non-stationary post-change distributions.
Summary updated