# Optimal Change-Point Detection and Localization

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

## Key facts

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

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

- [Automatic Change-Point Detection in Time Series via Deep Learning](https://mlsanity.com/paper/2211.03860/) (2022)
- [Optimal network online change point localisation](https://mlsanity.com/paper/2101.05477/) (2021)
- [Theoretical guarantees for change localization using conformal p-values](https://mlsanity.com/paper/2510.08749/) (2025)
- [Segmenting Human-LLM Co-authored Text via Change Point Detection](https://mlsanity.com/paper/2605.03723/) (2026)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)
- [Tessellated Linear Model for Age Prediction from Voice](https://mlsanity.com/paper/2501.09229/) (2025)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)
- [Distribution-free root cause analysis](https://mlsanity.com/paper/2605.21627/) (2026)
- [Denoising and change point localisation in piecewise-constant high-dimensional regression coefficients](https://mlsanity.com/paper/2110.14298/) (2021)
- [Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series](https://mlsanity.com/paper/2306.09555/) (2023)
- [Continuous Optimization for Offline Change Point Detection and Estimation](https://mlsanity.com/paper/2407.03383/) (2024)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)

## Abstract (arXiv)

Given a times series bf Y in ℝn, with a piece-wise contant mean and independent components, the twin problems of change-point detection and change-point localization respectively amount to detecting the existence of times where the mean varies and estimating the positions of those change-points. In this work, we tightly characterize optimal rates for both problems and uncover the phase transition phenomenon from a global testing problem to a local estimation problem. Introducing a suitable definition of the energy of a change-point, we first establish in the single change-point setting that the optimal detection threshold is √2loglog(n). When the energy is just above the detection threshold, then the problem of localizing the change-point becomes purely parametric: it only depends on the difference in means and not on the position of the change-point anymore. Interestingly, for most change-point positions, it is possible to detect and localize them at a much smaller energy level. In the multiple change-point setting, we establish the energy detection threshold and show similarly that the optimal localization error of a specific change-point becomes purely parametric. Along the way, tight optimal rates for Hausdorff and l1 estimation losses of the vector of all change-points positions are also established. Two procedures achieving these optimal rates are introduced. The first one is a least-squares estimator with a new multiscale penalty that favours well spread change-points. The second one is a two-step multiscale post-processing procedure whose computational complexity can be as low as O(nlog(n)). Notably, these two procedures accommodate with the presence of possibly many low-energy and therefore undetectable change-points and are still able to detect and localize high-energy change-points even with the presence of those nuisance parameters.