Cao Yang, Xie Liyan, Xie Yao, Xu Huan
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA.
Entropy (Basel). 2018 Feb 7;20(2):108. doi: 10.3390/e20020108.
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 tackling 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.
当分布参数未知时，序贯变点检测是统计学和机器学习中的一个基本问题。当变化后的参数未知时，我们考虑一组基于序贯似然比的检测程序，其中使用在线凸优化算法（如在线镜像下降）构建非预期估计器，这为处理无法找到递归最大似然估计器的复杂情况提供了一种更通用的方法。当基础分布属于指数族且估计器满足对数遗憾性质时，我们表明这种方法几乎是二阶渐近最优的。这意味着当阈值趋于无穷大时，算法的误报率上限（以平均运行长度衡量）在渐近意义上达到下限，相差一个对数-对数因子。我们的证明是通过在序贯变点和在线凸优化之间建立联系，并利用在线镜像下降算法的对数遗憾界性质来实现的。数值和实际数据示例验证了我们的理论。
