Consistent selection of the number of change-points via sample-splitting

Changliang Zou, Guanghui Wang, Runze LiThe Annals of Statistics 2020 · DOI

Abstract

In multiple change-point analysis, one of the major challenges is to estimate the number of change-points. Most existing approaches attempt to minimize a Schwarz information criterion which balances a term quantifying model fit with a penalization term accounting for model complexity that increases with the number of change-points and limits overfitting. However, different penalization terms are required to adapt to different contexts of multiple change-point problems and the optimal penalization magnitude usually varies from the model and error distribution. We propose a data-driven selection criterion that is applicable to most kinds of popular change-point detection methods, including binary segmentation and optimal partitioning algorithms. The key idea is to select the number of change-points that minimizes the squared prediction error, which measures the fit of a specified model for a new sample. We develop a cross-validation estimation scheme based on an order-preserved sample-splitting strategy, and establish its asymptotic selection consistency under some mild conditions. Effectiveness of the proposed selection criterion is demonstrated on a variety of numerical experiments and real-data examples.

Introduction

Change-point analysis is a fundamental task in time-series modeling, aimed at identifying moments when the underlying statistical properties of a process—such as mean, variance, or regression coefficients—undergo sudden shifts. While numerous algorithms exist to locate these shifts, determining the total number of change-points ($K$) remains a notoriously difficult problem.

Traditional methods typically rely on Information Criteria, such as the Bayesian Information Criterion (BIC), which balance goodness-of-fit against a penalty for model complexity. However, these penalties often require manual tuning and are highly sensitive to the underlying noise distribution (e.g., Gaussian vs. heavy-tailed). This paper introduces COPSS (Cross-validation with Order-Preserved Sample-Splitting), a robust, data-driven framework that automates the selection of $K$ without the need for manually specified penalty terms.

The Challenge of Model Selection

In the context of change-point detection, the primary risk is either overfitting—identifying "ghost" change-points that are actually artifacts of noise—or underfitting—missing genuine structural shifts. The "perfect" penalty for an Information Criterion depends heavily on the specific characteristics of the data, which are rarely known a priori. If the penalty is too small, the model overfits; if it is too large, it lacks the power to detect subtle changes. COPSS addresses this by replacing static mathematical penalties with a dynamic validation process.

Methodology: The COPSS Framework

The core innovation of the paper is a cross-validation scheme tailored for temporal data. Standard random cross-validation is unsuitable for time series because it destroys the temporal structure and local dependence necessary for change-point detection.

Order-Preserved Sample-Splitting (OPSS)

To preserve the data's structure, the authors utilize a "parity-split" strategy. The original sequence $Z_1, Z_2, \dots, Z_n$ is divided into two sub-sequences:

  1. The Odd Set: $Z_1, Z_3, Z_5, \dots$
  2. The Even Set: $Z_2, Z_4, Z_6, \dots$

This splitting ensures that both sub-sequences "see" the same underlying change-point structure at nearly the same relative locations, while their noise components remain independent.

Training and Validation

The selection process follows a classic cross-validation logic. One set (e.g., the Odd set) is used to estimate the locations of a candidate number of change-points ($L$). The model's performance is then evaluated by calculating the "squared prediction error" on the other set (the Even set). This error serves as a natural, data-driven penalty: a "fake" change-point identified in the training set due to noise is unlikely to improve the fit on the validation set, causing the prediction error to increase.

Score-Function Criterion and Consistency

The authors develop a unified criterion based on score functions (the derivative of the loss function). This mathematical abstraction allows COPSS to be "algorithmically agnostic," meaning it can be used as a wrapper for various detection methods like Binary Segmentation (BS), Optimal Partitioning (OP), or PELT. Furthermore, the paper provides a rigorous mathematical proof of asymptotic consistency, demonstrating that as the sample size increases, COPSS will select the true number of change-points with a probability approaching one.

Experimental Results

Simulation Studies

The authors evaluated COPSS across seven distinct scenarios (Models I-VII), including univariate and multivariate mean shifts, variance changes, and nonparametric settings. The results showed that while traditional BIC performed well only when the penalty was perfectly tuned to the noise type, COPSS remained highly accurate across normal, light-tailed, and heavy-tailed noise distributions. It significantly outperformed BIC in scenarios involving heterogeneous or heavy-tailed noise.

Real-World Applications

  • FTSE100 Index: Analyzing daily returns from 1984 to 2012, COPSS identified 30 change-points in market volatility. This result was notably more stable than BIC, which produced results ranging from 32 to 80 points depending on the penalty setting.
  • Human Chromosome Sequence: In a nonparametric biological context, COPSS successfully identified shifts in G+C composition, demonstrating its versatility beyond standard financial or physical time series.

Discussion and Limitations

While COPSS offers a powerful alternative to traditional criteria, it is not without trade-offs. Because the method splits the data in half, the effective sample size for training is $n/2$. In very small datasets with high-frequency changes, this may lead to a slight loss of power compared to a perfectly tuned BIC using the full dataset. Additionally, the computational cost is approximately doubled, as the model must be trained and validated twice (swapping the roles of the odd and even sets).

Future research directions include extending the framework to non-stationary segments—where data properties evolve between shifts—and investigating its application in high-dimensional data environments.

Conclusion

COPSS represents a significant step forward in making change-point analysis more accessible and reliable. By leveraging the temporal structure of the data through order-preserved splitting, it provides a truly data-driven way to determine model complexity, ensuring robustness across diverse statistical environments.

Summary updated

Abstract

In multiple change-point analysis, one of the major challenges is to estimate the number of change-points. Most existing approaches attempt to minimize a Schwarz information criterion which balances a term quantifying model fit with a penalization term accounting for model complexity that increases with the number of change-points and limits overfitting. However, different penalization terms are required to adapt to different contexts of multiple change-point problems and the optimal penalization magnitude usually varies from the model and error distribution. We propose a data-driven selection criterion that is applicable to most kinds of popular change-point detection methods, including binary segmentation and optimal partitioning algorithms. The key idea is to select the number of change-points that minimizes the squared prediction error, which measures the fit of a specified model for a new sample. We develop a cross-validation estimation scheme based on an order-preserved sample-splitting strategy, and establish its asymptotic selection consistency under some mild conditions. Effectiveness of the proposed selection criterion is demonstrated on a variety of numerical experiments and real-data examples.
BibTeX
@article{zou2020consistent,
  author = {Changliang Zou and Guanghui Wang and Runze Li},
  title = {{Consistent selection of the number of change-points via sample-splitting}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/19-aos1814},
}
Figure