Adversarially Robust Change Point Detection
Adversarially Robust Change Point Detection
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Mengchu Li;Yi Yu
中科院分区：
文献类型：
--
作者：
Mengchu Li;Yi Yu
变化点检测在许多应用领域越来越受欢迎。一方面，大多数理论上合理的方法都是在没有模型违反的理想环境中进行研究的，或者仅仅对相同的长时间重尾噪声分布和/或孤立的异常值具有鲁棒性；另一方面，我们意识到来自对手的攻击呈指数级增长，他们可能会对数据进行系统污染，以故意创建虚假的变化点或伪装真实的变化点。鉴于迫切需要一种对对手具有鲁棒性的变化点检测方法，我们从最简单的单变量平均变化点检测问题开始。对抗性攻击是通过Huber $\varepsilon$- pollution框架制定的，该框架特别允许污染分布在每个时间点不同。本文讨论了变点检测中的相变现象。该检测边界是污染比例$\varepsilon$的函数，在文献中首次出现。此外，我们导出了最小率最优定位错误率，以污染比例量化精度成本。我们提出了一种计算上可行的方法，在一定条件下匹配极大极小下界，节省了对数因子。进行了大量的数值实验，并与现有文献中的鲁棒变化点检测方法进行了比较。
Change point detection is becoming increasingly popular in many application areas. On one hand, most of the theoretically-justified methods are investigated in an ideal setting without model violations, or merely robust against identical heavy-tailed noise distribution across time and/or against isolate outliers; on the other hand, we are aware that there have been exponentially growing attacks from adversaries, who may pose systematic contamination on data to purposely create spurious change points or disguise true change points. In light of the timely need for a change point detection method that is robust against adversaries, we start with, arguably, the simplest univariate mean change point detection problem. The adversarial attacks are formulated through the Huber $\varepsilon$-contamination framework, which in particular allows the contamination distributions to be different at each time point. In this paper, we demonstrate a phase transition phenomenon in change point detection. This detection boundary is a function of the contamination proportion $\varepsilon$ and is the first time shown in the literature. In addition, we derive the minimax-rate optimal localisation error rate, quantifying the cost of accuracy in terms of the contamination proportion. We propose a computationally feasible method, matching the minimax lower bound under certain conditions, saving for logarithmic factors. Extensive numerical experiments are conducted with comparisons to robust change point detection methods in the existing literature.