# Minimax rates in sparse, high-dimensional changepoint detection

arXiv: https://arxiv.org/abs/1907.10012 · HTML: https://mlsanity.com/paper/1907.10012/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2019.

## Built on by (most cited first, 9 of 9)

- [Segmenting Human-LLM Co-authored Text via Change Point Detection](https://mlsanity.com/paper/2605.03723/) (2026)
- [Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates](https://mlsanity.com/paper/2211.08580/) (2022)
- [High dimensional change-point detection: a complete graph approach](https://mlsanity.com/paper/2203.08709/) (2022)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Inference for Change Points in High Dimensional Mean Shift Models](https://mlsanity.com/paper/2107.09150/) (2021)
- [Minimax Signal Detection in Sparse Additive Models](https://mlsanity.com/paper/2304.09398/) (2023)
- [Inferring Change Points in High-Dimensional Regression via Approximate Message Passing](https://mlsanity.com/paper/2404.07864/) (2024)
- [High-Dimensional Change Point Detection via Graph Spanning Ratio](https://mlsanity.com/paper/2512.07541/) (2025)

## Abstract (arXiv)

We study the detection of a sparse change in a high-dimensional mean vector as a minimax testing problem. Our first main contribution is to derive the exact minimax testing rate across all parameter regimes for n independent, p-variate Gaussian observations. This rate exhibits a phase transition when the sparsity level is of order √p log log (8n) and has a very delicate dependence on the sample size: in a certain sparsity regime it involves a triple iterated logarithmic factor in~n. Further, in a dense asymptotic regime, we identify the sharp leading constant, while in the corresponding sparse asymptotic regime, this constant is determined to within a factor of √2. Extensions that cover spatial and temporal dependence, primarily in the dense case, are also provided.