📊 statistics

Non-partitioned e-detectors for nonparametric sequential change detection

This paper proposes a general class of non-partitioned e-detectors for nonparametric sequential change detection that aggregate point-null e-processes to achieve first-order asymptotically optimal detection delay while controlling false alarms under unknown pre- and post-change distributions.

Original authors: Aytijhya Saha, Aaditya Ramdas

Published 2026-07-31

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Aytijhya Saha, Aaditya Ramdas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to spot a thief in a crowded room. Usually, you know exactly what the thief looks like: maybe they wear a red hat and carry a blue bag. You also know what the innocent people look like: they wear green hats and carry nothing. This is the classic way scientists look for changes in data. They set up a "before" list and an "after" list, and they wait for the data to jump from one list to the other.

But what if you don't know what the thief looks like? What if the "innocent" people might actually look a lot like the thief, or if the thief could look like anyone in the room? This is the tricky puzzle of "non-partitioned" change detection. In the world of statistics, this means we are watching a stream of numbers (like temperatures, stock prices, or heartbeats) and we know they come from a general family of possibilities, but we don't know which specific rule they are following before the change, and we don't know which rule they switch to after the change. The old tools fail here because they get confused when the "before" and "after" possibilities overlap. We need a new kind of detective that can handle total uncertainty without getting tricked by false alarms.

This paper introduces a clever new detective tool called a "non-partitioned e-detector." Instead of guessing the thief's outfit, the authors build a massive team of tiny, specialized detectives. Each tiny detective is an expert at spotting a change from one specific, known rule to everything else. The main detective then asks all these tiny experts to start watching from every single moment in time. If any of them start seeing something suspicious, they raise their hands. The main detective then looks at the whole team and asks, "Is there any possible rule for the 'before' time that could explain all this data without a change?" If the answer is "No," then the main detective sounds the alarm.

The authors prove that this method works even when the "before" and "after" rules are completely unknown and could be almost identical. They show that this approach is mathematically guaranteed to avoid false alarms (sounding the alarm when nothing happened) while still being fast enough to catch the real change quickly. They tested this idea on several specific scenarios, like when numbers are "sub-Gaussian" (a fancy way of saying they don't have wild, crazy outliers), when they are stuck between 0 and 1, and when they follow a bell curve but we don't know how wide the curve is. In all these cases, their new method performed as well as the best possible theoretical limit, meaning it is as fast as a detective could possibly be without knowing the rules in advance.

The paper also tackles a tough question: how fast can we really detect a change if we don't know the rules? They prove that if the change happens very early, it might be impossible to be sure without waiting a long time, but if the change happens after we've seen enough data, their method catches it almost instantly. They didn't just guess this; they built the math to prove it and ran computer simulations to show it works in practice. For example, in one test with Gaussian data, their detector found changes significantly faster than older methods, often coming very close to the theoretical speed limit.

The beauty of this work is that it removes the need to guess the "before" and "after" categories. In the past, if you wanted to detect a change in a Markov chain (a system that changes states based on probabilities, like a weather pattern), you had to assume you knew the starting probabilities. This new method says, "We don't need to know that. We'll just test every possibility." The authors even showed how to apply this to dependent data, like a two-state Markov chain, proving that the method holds up even when the data points aren't independent.

Ultimately, this paper gives us a robust, flexible way to watch for changes in a chaotic world where we don't have a rulebook. It turns a problem that was previously very hard—detecting a change when you don't know what the change looks like or what the normal state looks like—into a solvable puzzle with a clear, optimal solution. The authors have shown that by aggregating many simple tests and taking the most conservative view, you can build a detector that is both safe (rarely cries wolf) and sharp (catches the wolf fast).

Technical Summary: Non-partitioned e-detectors for Nonparametric Sequential Change Detection

1. Problem Formulation

The paper addresses the problem of sequential change detection (SCD) over a general class of probability distributions $\mathcal{P}$ on a Polish space $\mathcal{X}$ . Unlike classical formulations, this work considers a non-partitioned setting where:

Both the pre-change distribution $P$ and the post-change distribution $Q$ are unknown.
Both $P$ and $Q$ belong to the same composite class $\mathcal{P}$ .
There is no pre-specified partition of $\mathcal{P}$ into disjoint pre-change ( $\mathcal{P}_0$ ) and post-change ( $\mathcal{P}_1$ ) families.
The null hypothesis $H_0$ is composite: the data $X_1, X_2, \dots$ are i.i.d. from some unknown $R \in \mathcal{P}$ .
The alternative hypothesis involves a changepoint $T$ where $X_1, \dots, X_T \sim P$ and $X_{T+1}, \dots \sim Q$ , with $P, Q \in \mathcal{P}$ and $P \neq Q$ .

This setting presents a fundamental challenge: the post-change law $Q$ is an admissible no-change law. Consequently, the Kullback-Leibler (KL) divergence $\inf_{R \in \mathcal{P}} D_{KL}(Q \| R)$ is zero, rendering classical information-theoretic lower bounds (which rely on positive separation) inapplicable. Furthermore, standard worst-case Conditional Average Detection Delay (CADD) metrics can degenerate because an immediate change to $Q$ is indistinguishable from the no-change law $Q^\infty$ .

2. Methodology

The authors propose a general framework for constructing composite e-detectors by aggregating point-null e-processes.

Core Construction

Point-Null Primitives: For every candidate no-change distribution $R \in \mathcal{P}$ and every potential start time $s$ , the method utilizes an $s$ -delay e-process $\{M^R_{s:t}\}_{t \ge s-1}$ . This process tests the simple null $H_{0,R}: X_i \sim R$ against the complement. The existence of such processes is guaranteed for weakly compact null classes (Ram and Ramdas, 2026b).
Aggregation and Minimization: The detector statistic aggregates these point-null processes over all possible start times $s \le t$ $s \leq t$ and takes an infimum over all candidate no-change distributions $R \in \mathcal{P}$ $R \in P$ .
- For ARL Control: The statistic is $D^{\text{ARL}}_t = \inf_{R \in \mathcal{P}} \sum_{s=1}^t M^R_{s:t}$ .
- For PFA Control: The statistic uses deterministic weights $\pi_s$ (summing to $\le 1$ ): $D^{\text{PFA}}_t = \inf_{R \in \mathcal{P}} \sum_{s=1}^t \pi_s M^R_{s:t}$ .
Stopping Rule: The detector stops at $\tau = \inf \{t \ge 1 : D_t \ge A\}$ , where $A$ is a threshold determined by the desired false-alarm level (e.g., $A$ for ARL, $1/\alpha$ for PFA).

Technical Innovations

Adjusters: To ensure the statistic retains evidence from the pre-change block (which is necessary to reject $R=Q$ ), the authors apply "adjusters" (Choe and Ramdas, 2026) to the running maximum of the e-processes. This creates a non-decreasing process that preserves the e-validity while maintaining evidence against candidates far from the true pre-change law.
Local REGROW Witnesses: Since the global class $\mathcal{P}$ may not be weakly compact, the authors introduce the concept of a countable local REGROW witness basis. This allows the derivation of uniform growth rates for the infimum over $\mathcal{P}$ by leveraging local compactness and separation properties near the true distributions $P$ and $Q$ .

3. Key Contributions

General Framework: Introduction of e-detectors for the fully non-partitioned SCD problem, providing finite-sample false-alarm guarantees (both Average Run Length and Probability of False Alarm) over arbitrary distribution classes.
Asymptotic Optimality: Proof that under suitable assumptions (existence of a countable local REGROW witness basis), the proposed methods achieve first-order asymptotically optimal detection delays. The delay is governed by the instance-specific information rate $I^* = D_{KL}(Q \| P)$ .
Concrete Examples: Development of explicit detectors for:
- Sub-Gaussian mean changes.
- Bounded mean changes (using universal portfolios).
- Gaussian mean changes with unknown variance.
- Changes in the transition matrix of a two-state Markov chain (dependent data).
Theoretical Bounds: Derivation of matching lower bounds for detection delay, establishing that the proposed upper bounds are pointwise optimal. The analysis distinguishes between "late changes" (where classical rates apply) and "early changes" (where insufficient pre-change data makes reliable detection impossible).

4. Results and Performance

Sub-Gaussian Means: The detector achieves a delay of approximately $(1+o(1)) \frac{\log A}{I}$ , where $I = \frac{(\mu-\nu)^2}{2\sigma^2}$ . For PFA control, an additional $O(\log T_\alpha)$ penalty is incurred compared to ARL control.
Bounded Means: Using a continuous mixture of universal portfolios (Jeffreys prior), the method achieves delays governed by the betting information $I_{\text{bet}}(Q, a) = \inf_{R: E[R]=a} D_{KL}(Q \| R)$ .
Gaussian with Unknown Variance:
- A "studentized" detector (testing mean only) achieves optimality relative to the reverse information projection when variance is unrestricted.
- A "full Gaussian" detector (testing mean and variance) achieves the instance-specific rate $D_{KL}(Q \| P)$ , adapting to the true pre-change variance learned from the prefix.
Markov Chains: The framework extends to dependent data, providing explicit detectors for changes in transition matrices with similar delay guarantees.
Experiments: Simulations on Gaussian mean shifts and bounded observations demonstrate that the proposed e-detectors consistently outperform repeated CUSUM baselines and closely match the theoretical information-theoretic lower bounds.

5. Significance and Claims

The paper claims to resolve a gap in the literature regarding non-partitioned sequential change detection. While classical methods and recent e-detector frameworks (Shin et al., 2023) rely on disjoint pre- and post-change families, this work handles the case where the post-change distribution is indistinguishable from a potential no-change distribution without prior knowledge of the direction or nature of the change.

The authors emphasize that their reduction from point-null e-processes to instance-optimal non-partitioned detectors is a general theoretical contribution. They do not claim to solve the "early change" impossibility (where $T$ is too small to distinguish $P$ from $Q$ ) but rather characterize the fundamental limits of detection in this setting. The work provides a unified, nonparametric framework that achieves optimal detection delays without requiring parametric assumptions or pre-specified partitions, applicable to broad classes including sub-Gaussian, bounded, and Gaussian distributions, as well as dependent Markov processes.