Optimal change-point detection and localization

DOI10.1214/23-AOS2297MaRDI QIDQ6183751zbMATH OpenOpenAlexFDO

Authors Nicolas Verzelen, Magalie Fromont, M. Lerasle, P. Reynaud-Bouret

Publication date 4 January 2024

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.11470, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-4/Optimal-change-point-detection-and-localization/10.1214/23-AOS2297.full

zbMATH Keywords

change-point analysesCUSUMdetectionlocalizationminimax

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20)

Abstract: Given a times series $$ in $mathbb{R}^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 $sqrt2loglog(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 $l_1$ 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.

Recommendations

• Univariate mean change point detection: penalization, CUSUM and optimality
• Optimal nonparametric change point analysis
• Optimal covariance change point localization in high dimensions
• Optimal change point detection and localization in sparse dynamic networks
• Optimal detection of changepoints with a linear computational cost

Cites work

• A Bayes Approach to a Quality Control Model
• A Cluster Analysis Method for Grouping Means in the Analysis of Variance
• A kernel multiple change-point algorithm via model selection
• A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
• A MOSUM procedure for the estimation of multiple random change points
• A test for a change in a parameter occurring at an unknown point
• Adaptive risk bounds in univariate total variation denoising and trend filtering
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Asymptotically minimax hypothesis testing for nonparametric alternatives. I
• Consistencies and rates of convergence of jump-penalized least squares estimators
• Consistent change-point detection with kernels
• CONTINUOUS INSPECTION SCHEMES
• Detecting multiple change-points in the mean of Gaussian process by model selection
• Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
• Detection of abrupt changes: theory and application
• Detection of an anomalous cluster in a network
• Detection with the scan and the average likelihood ratio
• Estimating and Testing Linear Models with Multiple Structural Changes
• Estimating the number of change-points via Schwarz' criterion
• Gaussian model selection
• Greedy Kernel Change-Point Detection
• High dimensional change point estimation via sparse projection
• scientific article; zbMATH DE number 4169866 (Why is no real title available?)
• scientific article; zbMATH DE number 1048663 (Why is no real title available?)
• scientific article; zbMATH DE number 1487502 (Why is no real title available?)
• scientific article; zbMATH DE number 6303356 (Why is no real title available?)
• Inference about the change-point in a sequence of binomial variables
• Inference about the change-point in a sequence of random variables
• Minimal penalties and the slope heuristics: a survey
• Minimax rates in sparse, high-dimensional change point detection
• Multiple change-point detection: a selective overview
• Multiple Change-Point Estimation With a Total Variation Penalty
• Multiscale change point inference. With discussion and authors' reply
• Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Non-asymptotic minimax rates of testing in signal detection
• On estimation of isotonic piecewise constant signals
• On Grouping for Maximum Homogeneity
• On optimal multiple changepoint algorithms for large data
• On problems in which a change in a parameter occurs at an unknown point
• On the approximation of curves by line segments using dynamic programming
• Optimal detection of changepoints with a linear computational cost
• Seeded binary segmentation: a general methodology for fast and optimal changepoint detection
• Sequential Tests of Statistical Hypotheses
• Sparsity and Smoothness Via the Fused Lasso
• Tail-greedy bottom-up data decompositions and fast multiple change-point detection
• Testing a Sequence of Observations for a Shift in Location
• The asymptotic behavior of some nonparametric change-point estimators
• Univariate mean change point detection: penalization, CUSUM and optimality
• Wild binary segmentation for multiple change-point detection

Cited in

(18)

• OPTIMAL CHANGE-POINT DETECTION IN TREND MODELS WITH INTEGRATED MOVING AVERAGE ERRORS
• Nearly Optimal Change-Point Detection with an Application to Cybersecurity
• Change-point inference in high-dimensional regression models under temporal dependence
• Cross-validation for change-point regression: pitfalls and solutions
• Multiple change point detection in functional data with applications to biomechanical fatigue data
• Sharp phase transitions in high-dimensional changepoint detection
• Data-adaptive structural change-point detection via isolation
• An efficient algorithm for exact segmentation of large compositional and categorical time series
• Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
• Inference for change-plane regression
• Inference for change points in high dimensional mean shift models
• Bayesian uncertainty quantification and structure detection for multiple change points models
• Change-point detection in low-rank VAR processes
• Detecting sparse change in regression coefficients in the presence of dense nuisance parameters
• A note on the Cox-model based partial likelihood for change-point detection in a covariate
• Testing the distribution change in multivariate data using rank energy statistics
• ART: distribution-free and model-agnostic changepoint detection with finite-sample guarantees
• Euclidean mirrors and first-order changepoints in network time series

This page was built for publication: Optimal change-point detection and localization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183751)