# Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2018.

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

- [Segmenting Human-LLM Co-authored Text via Change Point Detection](https://mlsanity.com/paper/2605.03723/) (2026)
- [On Rank Energy Statistics via Optimal Transport: Continuity, Convergence, and Change Point Detection](https://mlsanity.com/paper/2302.07964/) (2023)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA](https://mlsanity.com/paper/2202.04719/) (2022)
- [Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients](https://mlsanity.com/paper/2110.14298/) (2021)
- [Noise-contrastive Online Change Point Detection](https://mlsanity.com/paper/2206.10143/) (2022)
- [Inferring Change Points in High-Dimensional Regression via Approximate Message Passing](https://mlsanity.com/paper/2404.07864/) (2024)
- [Continuous Optimization for Offline Change Point Detection and Estimation](https://mlsanity.com/paper/2407.03383/) (2024)
- [Score-based change point detection via tracking the best of infinitely many experts](https://mlsanity.com/paper/2408.14073/) (2024)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)
- [High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection](https://mlsanity.com/paper/2608.15466/) (2026)
- [TraceGuard: Adaptive Multimodal Poison Filtering through Cross-Feature Rank Agreement](https://mlsanity.com/paper/2609.29099/) (2026)
- [Beyond Sub-Gaussian Detector Scores: Robust Weighted Profile-Loss Change Point Detection for Human-LLM Text Segmentation](https://mlsanity.com/paper/2609.36888/) (2026)

## Abstract (arXiv)

The problem of univariate mean change point detection and localization based on a sequence of n independent observations with piecewise constant means has been intensively studied for more than half century, and serves as a blueprint for change point problems in more complex settings. We provide a complete characterization of this classical problem in a general framework in which the upper bound σ2 on the noise variance, the minimal spacing Delta between two consecutive change points and the minimal magnitude kappa of the changes, are allowed to vary with n. We first show that consistent localization of the change points, when the signal-to-noise ratio frackappa √Deltaσ < √log(n), is impossible. In contrast, when frackappa √Deltaσ diverges with n at the rate of at least √log(n), we demonstrate that two computationally-efficient change point estimators, one based on the solution to an ℓ0-penalized least squares problem and the other on the popular wild binary segmentation algorithm, are both consistent and achieve a localization rate of the order fracσ2kappa2 log(n). We further show that such rate is minimax optimal, up to a log(n) term.