Detection and estimation of parameters in high dimensional multiple change point regression models via ${\ell }_1/{\ell }_0$ regularization and discrete optimization

Abstract

Binary segmentation, which is sequential in nature is thus far the most widely used method for identifying multiple change points in statistical models. Here we propose a top down methodology called arbitrary segmentation that proceeds in a conceptually reverse manner. We begin with an arbitrary superset of the parametric space of the change points, and locate unknown change points by suitably filtering this space down. Critically, we reframe the problem as that of variable selection in the change point parameters, this enables the filtering down process to be achieved in a single step with the aid of an ${\ell }_0$ regularization, thus avoiding the sequentiality of binary segmentation. We study this method under a high dimensional multiple change point linear regression model and show that rates convergence of the error in the regression and change point estimates are near optimal. We propose a simulated annealing (SA) approach to implement a key finite state space discrete optimization that arises in our method. Theoretical results are numerically supported via simulations. The proposed method is shown to possess the ability to agnostically detect the `no change' scenario. Furthermore, its computational complexity is of order $O(N{p}^2)$+SA, where SA is the cost of a SA optimization on a $N$(no. of change points) dimensional grid. Thus, the proposed methodology is significantly more computationally efficient than existing approaches. Finally, our theoretical results are obtained under weaker model conditions than those assumed in the current literature.

References in corpus (11)

• Simultaneous analysis of Lasso and Dantzig selector
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• High-dimensional instrumental variables regression and confidence sets
• Change-Point Estimation in High-Dimensional Markov Random Field Models
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• Computationally efficient change point detection for high-dimensional regression
• Reconstruction from anisotropic random measurements
• Pivotal Estimation via Self-Normalization for High-Dimensional Linear Models with Error in Variables
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• A Scalable Algorithm for Gaussian Graphical Models with Change-Points

Cited by in corpus (1)

• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees