It suggests that, for any m { k,...,n 1 } and z R, L A.2 Proofs for Lemma 2 and 3 for the case when K is unknown in 4 Lemma 2 . It suggests that, for any m { 0,...,n 1 } and z R, L For any m { 0,...,n 1 } and z R, we have L A.3 Additional tricks for methods proposed in 3. Finding optimal CP vector when z = in paraCP(n,k, ˆ T Additional pruning condition for parametric DP when K is fixed. In 3.3, we showed that Lemma 4. F orn [ N ], and k [ K ], let T Therefore, it fails to control the false positive rate. This is asymptotic test for multiple detected CPs. Fused Lasso (proposed by the same authors), is worse than BinSeg-SI. BinSeg-SI had been considered as a computationally efficient approximation of the problem in (7), where the authors additionally condition on extra information for computational tractability, e.g., the order that CPs are detected.

Changepoint (CP) detection is a fundamental problem and has been studied in many areas.

There is a vast body of literature related to methods for detecting changepoints (CP). However, less attention has been paid to assessing the statistical reliability of the detected CPs. In this paper, we introduce a novel method to perform statistical inference on the significance of the CPs, estimated by a Dynamic Programming (DP)-based optimal CP detection algorithm. Based on the selective inference (SI) framework, we propose an exact (non-asymptotic) approach to compute valid p-values for testing the significance of the CPs. Although it is well-known that SI has low statistical power because of over-conditioning, we address this disadvantage by introducing parametric programming techniques. Then, we propose an efficient method to conduct SI with the minimum amount of conditioning, leading to high statistical power. We conduct experiments on both synthetic and real-world datasets, through which we offer evidence that our proposed method is more powerful than existing methods, has decent performance in terms of computational efficiency, and provides good results in many practical applications.