Optimal Change-Point Detection with Training Sequences in the Large and
  Moderate Deviations 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.
