Sequential Multivariate Change Detection with Calibrated and Memoryless False Detection Rates
This work addresses the challenge of false positive calibration in change detection for applications like monitoring systems, offering an incremental improvement over existing threshold-setting methods.
The paper tackles the problem of setting detection thresholds in sequential change detection to achieve accurate false positive rates, presenting a simulation-based method that ensures constant false positive rates across time steps and reduces computational costs for the MMD estimator from O(N^2B) to O(N^2+NB) during configuration and from O(N^2) to O(N) during operation.
Responding appropriately to the detections of a sequential change detector requires knowledge of the rate at which false positives occur in the absence of change. Setting detection thresholds to achieve a desired false positive rate is challenging. Existing works resort to setting time-invariant thresholds that focus on the expected runtime of the detector in the absence of change, either bounding it loosely from below or targeting it directly but with asymptotic arguments that we show cause significant miscalibration in practice. We present a simulation-based approach to setting time-varying thresholds that allows a desired expected runtime to be accurately targeted whilst additionally keeping the false positive rate constant across time steps. Whilst the approach to threshold setting is metric agnostic, we show how the cost of using the popular quadratic time MMD estimator can be reduced from $O(N^2B)$ to $O(N^2+NB)$ during configuration and from $O(N^2)$ to $O(N)$ during operation, where $N$ and $B$ are the numbers of reference and bootstrap samples respectively.