Mean change detection for heavy-tailed high-dimensional data

We study the problem of mean change detection for heavy-tailed high-dimensional data. We show that when each component of the error vector follows an independent sub-Weibull($\alpha$) distribution, a CUSUM-type statistic achieves the minimax testing rate in almost all sparsity regimes. When the error distributions have even heavier tails, e.g. only admitting bounded $\alpha$-th moment for some $\alpha \geq 4$, we introduce a median-of-means-type statistic that achieves a near-optimal testing rate in both the dense and the sparse regime. A `black-box’ robust sparse mean estimator may then be combined to provide the optimal rate in the sparse regime. Although such an estimator may not be computationally efficient for its original purpose of mean estimation, our combined approach for change point detection is polynomial-time.