Improving Power by Conditioning on Less in Post-selection Inference for Changepoints

Technical Summary: Improving Power by Conditioning on Less in Post-selection Inference for Changepoints

Problem Statement
The detection of changepoints in time-series and ordered data is a well-established field with applications ranging from bioinformatics to climate science. However, a significant challenge remains in quantifying the uncertainty of detected changepoints. Standard approaches that use the same data for both detection and testing suffer from "double peeking," leading to invalid p-values that are biased toward small values. While post-selection inference offers a solution by conditioning on the information used to select the test, existing methods (e.g., Hyun et al., 2021; Jewell et al., 2022) condition on a substantial amount of information—specifically, the projection of the data orthogonal to the test statistic. This excessive conditioning restricts the sample space, resulting in conservative tests and a loss of statistical power.

Methodology
The authors propose a method to improve the power of post-selection inference by conditioning on the minimum amount of information necessary to make the p-value well-defined.

1. Ideal Post-Selection P-value:
   For a change-in-mean model, standard methods condition on the entire orthogonal projection of the data. The authors argue that the null hypothesis (no change within a window $h$ around a detected changepoint $\hat{\tau}$) only requires conditioning on:

   • The data points outside the window $\{\hat{\tau}-h+1, \dots, \hat{\tau}+h\}$.
   • The sample mean of the data within that window (a sufficient statistic for the unknown constant mean under the null).

   By conditioning only on these elements, the authors define an "ideal" p-value. Theoretically, this p-value is optimal for a class of alternative hypotheses where the distribution of the test statistic depends on the magnitude of the change, as it allows for variation in the nuisance parameters (the orthogonal components) that are irrelevant to the specific change being tested.

2. Monte Carlo Approximation:
   Since the ideal p-value is analytically intractable due to the complexity of the selection event in the reduced conditioning space, the authors propose a Monte Carlo approximation.

   • The method involves simulating new data sets within the window of interest while keeping the data outside the window and the window's sample mean fixed.
   • For each simulated data set, the existing post-selection inference method (e.g., from Jewell et al., 2022) is applied to calculate a conditional p-value.
   • The final p-value is a weighted average of these conditional p-values.

3. Validity via Observed Data Inclusion:
   A critical theoretical contribution is the proof that if the set of Monte Carlo samples includes the observed data itself (i.e., one simulation corresponds to the actual observation), the resulting estimator is a valid p-value. Specifically, under the null hypothesis, the distribution of this estimator is uniform on $[0, 1]$ for any Monte Carlo sample size $N$, not just asymptotically. This ensures validity even with very modest sample sizes (e.g., $N=10$).

Key Contributions

• Theoretical Reduction of Conditioning: The paper demonstrates that conditioning on the orthogonal projection of the data is unnecessary for validity; conditioning only on the data outside the test region and the sufficient statistic within the region is sufficient.
• Optimality: The authors show that for a natural class of alternative distributions, this reduced conditioning leads to an optimal p-value with higher power than methods conditioning on more information.
• Valid Finite-Sample Approximation: They provide a simple Monte Carlo procedure that yields valid p-values for any $N$, provided the observed data is included in the simulation set.
• Generality: The approach is applicable to various changepoint detection algorithms (binary segmentation, fused lasso, $L_0$ penalized likelihood) and can be extended to other null hypotheses and models (e.g., autoregressive processes).

Results

• Simulation Studies: Empirical results on synthetic data (Gaussian noise, known and unknown variance, heavy-tailed noise) demonstrate that the proposed method achieves a noticeable increase in power compared to the method of Jewell et al. (2022) (which is equivalent to $N=1$ in the proposed framework). The power gain is most pronounced with small to moderate Monte Carlo sample sizes ($N \approx 10$), after which improvements plateau. The method maintains valid Type I error control even when variance is estimated or noise is non-Gaussian (provided a central limit theorem applies).
• Genomic Data Application: Applied to human GC content data, the method detected a significantly higher number of significant changepoints compared to the Jewell et al. (2022) approach. For instance, using binary segmentation with $K=38$ detected changepoints, the number of significant findings increased from 15 ($N=1$) to 27 ($N=10$) under Holm-Bonferroni correction.
• Multiple Testing: The method performs well under both Family-Wise Error Rate (Holm-Bonferroni) and False Discovery Rate (Benjamini-Hochberg) control, showing a higher rate of true positive detection while maintaining low error rates.

Significance and Claims
The paper claims that by reducing the amount of information conditioned upon, researchers can obtain valid post-selection p-values with substantially increased power. The authors emphasize that this improvement is achievable with very modest computational effort (small Monte Carlo sample sizes), making the method practical for real-world applications. They position their work as a refinement of existing post-selection inference frameworks, applicable to any scenario where a method exists to calculate p-values based on orthogonal projections. The authors modestly note that while the method was developed for changepoints, the underlying logic of conditioning on less information applies more broadly to other post-selection inference problems, such as clustering and regression trees.