2023/07/03 by Chengde Qian, Guanghui Wang, Qian, Chengde +3
Business, Management and Accounting · Psychology · #Consumer Market Behavior and Pricing #FOS: Computer and information sciences #FOS: Mathematics #Mental Health Research Topics #Methodology (stat.ME) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2307.01150
openalex publication_date 2023/07/03 · openalex created_date 2023/07/05 · openalex updated_date 2026/07/28
Changepoint detection typically relies on a grid-search strategy for optimal data segmentation. When model fitting itself is expensive, repeatedly fitting a model on every candidate segment dominates the computation. Existing approaches mitigate this by pruning the grid, thus reducing the number of segments (and model fits). We propose Reliever, which instead cuts the number of model fits directly and nests seamlessly within standard grid-search routines. Reliever fits a small, deterministic collection of proxy models and reuses them wherever they apply, making it compatible with a wide range of existing algorithms. For high-dimensional regression with changepoints, coupling Reliever with an optimal grid-search method yields changepoint and coefficient estimators that are rate-optimal up to a logarithmic factor. Extensive numerical experiments demonstrate that Reliever rapidly and accurately detects changepoints across a wide range of high-dimensional and nonparametric models.