A0683
Title: Robust high-dimensional change point detection under heavy tails
Authors: Yudong Chen - London School of Economics and Political Science (United Kingdom) [presenting]
Mengchu Li - University of Warwick (United Kingdom)
Tengyao Wang - London School of Economics (United Kingdom)
Yi Yu - University of Warwick (United Kingdom)
Abstract: The mean change point detection problem for heavy-tailed high-dimensional data is studied. Firstly, it is shown that when each component of the error vector follows an independent sub-Weibull distribution, a CUSUM-type statistic achieves the minimax testing rate in almost all sparsity regimes. Secondly, when the error distributions have polynomially decaying tails admitting bounded $\alpha$th moment for some $\alpha \geq 4$, a median-of-means-type statistic that achieves a near-optimal testing rate in both the dense and the sparse regime is introduced. A "black-box" robust sparse mean estimator is combined with the median-of-means-type statistic to achieve optimality in the sparse regime. Although such an estimator is usually computationally inefficient for its original purpose of mean estimation, the combined approach for change point detection is polynomial time. Lastly, the even more challenging case is investigated when $2 \leq \alpha <4$ unveil a new phenomenon that the (minimax) testing rate has no sparse regime, i.e. sparse testing changes is information-theoretically as hard as testing dense changes. It is shown that the dependence of the testing rate on the data dimension exhibits a phase transition at $\alpha = 4$.
