Asymptotically Optimal Search for a Change Point Anomaly under a Composite Hypothesis Model
This addresses the problem of efficient anomaly detection in sequential monitoring systems, such as network security or quality control, and is incremental as it builds on existing change point detection methods with asymptotic optimality guarantees.
The paper tackles the problem of sequentially searching for a change point in an anomalous process among multiple processes under a composite hypothesis model, proposing a deterministic algorithm that is asymptotically optimal in minimizing Bayes risk as error probability approaches zero, with simulation results validating the theoretical findings.
We address the problem of searching for a change point in an anomalous process among a finite set of M processes. Specifically, we address a composite hypothesis model in which each process generates measurements following a common distribution with an unknown parameter (vector). This parameter belongs to either a normal or abnormal space depending on the current state of the process. Before the change point, all processes, including the anomalous one, are in a normal state; after the change point, the anomalous process transitions to an abnormal state. Our goal is to design a sequential search strategy that minimizes the Bayes risk by balancing sample complexity and detection accuracy. We propose a deterministic search algorithm with the following notable properties. First, we analytically demonstrate that when the distributions of both normal and abnormal processes are unknown, the algorithm is asymptotically optimal in minimizing the Bayes risk as the error probability approaches zero. In the second setting, where the parameter under the null hypothesis is known, the algorithm achieves asymptotic optimality with improved detection time based on the true normal state. Simulation results are presented to validate the theoretical findings.