Optimal Multi-Stream Quickest Detection with False Discovery Rate Control

This paper addresses the problem of online change-point detection in multi-stream data. Rapid detection of changes in the underlying probability model of a data stream is relevant in a variety of applications ranging from the Internet of Things and wireless communications to environmental monitoring. In this paper, we consider multi-stream change-point detection under False Discovery Rate (FDR) constraints. FDR is a widely used performance criterion for controlling the rate of false positives in multiple hypothesis testing. We derive the structure of an optimal method for change-point detection which minimizes the total average detection delay subject to an FDR constraint. We prove that the optimal procedure is a combination of Shiryaev tests applied to each data stream separately with a different detection threshold at each stream. Finding the optimal set of thresholds using e.g. brute force simulations is highly tedious, hence we propose an approximate approach for choosing the thresholds. We demonstrate in simulations that the approximate method provides better detection performance than a naive choice of thresholds in which the same false alarm constraint is imposed on each data stream.