Title: Nearly second-order asymptotic optimality of sequential change-point detection with one-sample updates,
Abstract: Sequential change-point detection when the distribution parameters are
unknown is a fundamental problem in statistics and machine learning. When the
post-change parameters are unknown, we consider a set of detection procedures
based on sequential likelihood ratios with non-anticipating estimators
constructed using online convex optimization algorithms such as online mirror
descent, which provides a more versatile approach to tackle complex situations
where recursive maximum likelihood estimators cannot be found. When the
underlying distributions belong to a exponential family and the estimators
satisfy the logarithm regret property, we show that this approach is nearly
second-order asymptotically optimal. This means that the upper bound for the
false alarm rate of the algorithm (measured by the average-run-length) meets
the lower bound asymptotically up to a log-log factor when the threshold tends
to infinity. Our proof is achieved by making a connection between sequential
change-point and online convex optimization and leveraging the logarithmic
regret bound property of online mirror descent algorithm. Numerical and real
data examples validate our theory.