Technical Summary: ARC (Augmented-Rank Conformalization) for Changepoint Localization

1. Problem Statement

Changepoint localization aims to identify the time index $\tau$ where the distribution of a data stream changes. While practitioners often receive a point estimate $\hat{\tau}$, the associated uncertainty is rarely quantified. Recent advances in conformal changepoint localization have solved the problem of validity: by using an arbitrary score function within a permutation-based framework (e.g., CONCH [14], MCP [6]), one can construct a confidence set $C_{1-\alpha}$ that guarantees finite-sample coverage $P(\tau \in C_{1-\alpha}) \geq 1-\alpha$ under the assumption of within-segment exchangeability, regardless of the underlying distribution.

However, a critical gap remains regarding efficiency. Theoretical results (e.g., conformal Neyman–Pearson lemmas) indicate that the optimal score is the likelihood ratio between pre- and post-change densities. In practice, these densities are unknown, necessitating plug-in estimators (e.g., classifiers or density ratio estimators). While these estimators preserve the coverage guarantee (universality), their set lengths (efficiency) are fragile. They deteriorate silently under heavy tails, skewness, and distribution shifts (where the deployment distribution differs from the training distribution). No existing theory guarantees that a set length certified under one distribution holds under another, particularly when the plug-in score is misspecified.

2. Methodology: The ARC Pipeline

The authors propose ARC (Augmented-Rank Conformalization), a family of score functions designed to achieve both finite-sample validity and distribution-robust efficiency.

Core Mechanism

ARC scores depend only on the within-segment ranks of the data, rather than raw values. The pipeline operates as follows:

1. Input: A window of observations $X = (X_1, \dots, X_n)$ with a candidate changepoint $t$.
2. Rank Transformation: For any candidate split $t$, the segments $X_{1:t}$ and $X_{t+1:n}$ are converted to rank vectors $R$.
3. Score Computation: The score $A(R)$ is computed using one of the following components:
   • Location Channel: A rank-based CUSUM statistic derived from the two-sample Wilcoxon evidence ($Z_{loc}$).
   • Scale Channel: A Mood-type squared-rank statistic ($Z_{sc}$) sensitive to variance changes.
   • Fixed Combinations: The maximum of the two channels ($A_{comb} = \max(A_{loc}, A_{sc})$) or a convex combination with weights learned on synthetic data and frozen.
   • Frozen Neural Network: A single-hidden-layer network ($16 \to 64 \to 1$) trained on synthetic Gaussian data (downsampled rank paths) and frozen before deployment.
4. Conformal Backend: The score is fed into the standard conformal localization framework (e.g., Hore and Ramdas [14]). P-values are computed via within-segment permutations of the rank-based statistics.
5. Output: A confidence set $C_{1-\alpha} = \{t : p_t > \alpha\}$, a point estimate $\hat{\tau}$, and a change-type label.

Key Design Choices

• Frozen Weights: All learned components (neural network weights, combination weights) are trained on synthetic data and frozen before the test window is observed. This ensures the score is independent of the test data, preserving the validity of the permutation argument.
• Type-Awareness without Adaptivity: Instead of adaptively selecting a channel based on the test data (which would invalidate the permutation test), ARC uses a fixed combination rule (e.g., max or pre-trained weights). This incurs no cost to validity.

3. Key Theoretical Contributions

Theorem 1: Finite-Sample Validity for Any Frozen Score

The paper proves that for any frozen weight configuration (including random initialization, early stopping, or training on adversarially labeled data), the resulting ARC score yields finite-sample coverage $P(\tau \in C_{1-\alpha}) \geq 1-\alpha$.

• Significance: Validity is inherited solely from the permutation backend and the independence of the score from the test window. No assumptions are made about the quality of the training or the correctness of the model.

Theorem 2: Efficiency Transfer via Rank Invariance

This is the paper's central theoretical result. Because ranks are invariant under strictly increasing transformations $g$, the entire ARC confidence set is almost surely invariant under such transforms: $C_{1-\alpha}(g(X)) = C_{1-\alpha}(X)$.

• Efficiency Transfer: Consequently, the distribution of the set length depends on the data pair $(F_0, F_1)$ only through its rank structure. A length distribution certified on a specific rank experiment (e.g., Gaussian shift) holds verbatim for any monotone transformation of that experiment (e.g., Lognormal, Cauchy, or logistic transforms), regardless of tail heaviness or skewness.
• Contrast: Plug-in scores (e.g., likelihood ratios) change with every re-expression of the data, causing their set lengths to fluctuate unpredictably under distribution shifts.

Price of Invariance

The paper acknowledges that rank-based scores pay a "price of invariance" compared to the oracle likelihood ratio. However, classical rank-test theory suggests this price is bounded (e.g., Wilcoxon has an asymptotic relative efficiency of $\approx 0.955$ against the t-statistic for Gaussian shifts). ARC trades a small, bounded loss in efficiency at a fixed model for exact efficiency transfer across the entire monotone orbit of that model.

4. Empirical Results

Simulation Studies

Experiments were conducted with window length $n=120$ across Gaussian, $t_3$, Cauchy, and Lognormal distributions.

• Coverage: All ARC scores maintained nominal coverage ($\approx 0.90$) across all distributions, including "sabotaged" networks (random weights, mistrained labels).
• Invariance: Under strictly increasing transforms (exp, cube, logistic), ARC sets remained exactly identical in 80/80 replications. In contrast, plug-in t-statistic sets inflated significantly (e.g., mean length increased from 6.8 to 22.1 under the exp transform).
• Robustness to Heavy Tails: Under Cauchy distributions, plug-in sets became vacuous (mean length $\approx 85$ out of 101 candidates), while ARC sets remained informative (mean length $\approx 26$).
• Transfer: Scores trained on Gaussian data and frozen performed robustly on heavy-tailed test data. The growth in set length for ARC was driven by the rank experiment itself, not by training mismatch, whereas plug-in scores suffered catastrophic degradation.
• Type Adaptivity: The "max" combination or learned convex combination incurred a minimal efficiency penalty (at most 15%) compared to an oracle that knew the change type (location vs. scale) in advance.

Real-Data Application: Well-Log Data

Applied to the Turing Change Point Dataset (well-log drilling series):

• ARC localized annotated shifts to 3–5 candidates with 90% confidence.
• Model Misfit Detection: In a window where human annotators disagreed and the change was gradual, ARC produced an empty set. The authors interpret this not as a failure, but as a valid certificate of model misfit (probability $\leq \alpha$), signaling that the single-changepoint piecewise-i.i.d. assumption was violated.

Dependence Handling

Under AR(1) dependence, standard i.i.d. permutations failed (coverage dropped to $\approx 0.30$). The authors propose circular block permutations as a repair, which restored coverage to $\approx 0.84$–$0.86$ at the cost of longer sets. The paper notes that exactness is lost under dependence, and block permutations are an approximation.

5. Significance and Claims

The paper claims to bridge the gap between universal validity and transferable efficiency in conformal changepoint localization.

• Universality of Validity: It confirms that validity is robust to score misspecification, provided the score is independent of the test window.
• Invariance as a Design Principle: It establishes that using rank-based scores renders the efficiency of the localization procedure invariant to marginal distribution changes. This allows practitioners to certify set lengths on synthetic or simple data (e.g., Gaussian) and trust those guarantees hold for complex, heavy-tailed, or skewed real-world data, provided the rank structure is similar.
• Practical Utility: The method provides actionable uncertainty statements (confidence sets) that do not silently fail under distribution shift, and it offers a mechanism (empty sets) to flag when the underlying model assumptions are violated.

6. Limitations

The authors explicitly bound their claims:

1. Single Changepoint: The theory assumes a single changepoint in an offline window.
2. Independence: Exact coverage requires within-segment independence; serial dependence requires approximate block permutation repairs.
3. Marginal Coverage: The sets provide marginal coverage, not conditional coverage given a detection event (which requires more complex machinery).
4. Model Scope: The piecewise-exchangeable model excludes trend-type alternatives (deterministic drifts).
5. Type Adaptivity: While the price of not knowing the change type is bounded, it is not zero.