Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes
This addresses the challenge of detecting change-points with limited distributional knowledge, offering theoretical guarantees for applications like anomaly detection, though it is incremental in extending information-theoretic frameworks.
The paper tackles the problem of offline change-point detection when pre- and post-change distributions are unknown and must be learned from training sequences, requiring error probabilities to decay exponentially or sub-exponentially. It designs an optimal estimator and fully characterizes the optimal confidence width as a function of undetected error in both regimes.
This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. In contrast to most related works, we assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available. We further require the probability of the \emph{estimation error} to decay either exponentially or sub-exponentially fast (corresponding respectively to the large and moderate deviations regimes in information theory parlance). Based on the training sequences as well as the test sequence consisting of a single change-point, we design a change-point estimator and further show that this estimator is optimal by establishing matching (strong) converses. This leads to a full characterization of the optimal confidence width (i.e., half the width of the confidence interval within which the true change-point is located at with high probability) as a function of the undetected error, under both the large and moderate deviations regimes.