acceptodds
Under review as a conference paper at ICLR 2027

Wasserstein Online Change Point Detection with Neural Networks

Abstract

Online change point detection (CPD) is a fundamental problem in statistics and machine learning. Kernel methods are theoretically principled but are limited by the choice of kernel and lose power in high dimensions. Learning-based approaches, on the other hand, typically lack the same level of theoretical guarantees. To bridge this gap, we propose an online CPD algorithm approximating the Wasserstein distance between two consecutive sliding windows through a Lipschitz-constrained neural network. The network is trained recursively using a small number of gradient iterations per time step, making the detector unsupervised and online. We derive non-asymptotic concentration bounds for the test statistic under the null hypothesis and under the alternative with a partially contaminated window, leveraging a refined analysis with Rademacher complexity bounds. This yields a constant threshold choice that guarantees any prescribed average run length, a logarithmically growing threshold that controls the false alarm probability over an infinite horizon, and an exponential tail bound on the detection delay. These are, to our knowledge, the first results for an online detector whose statistic is computed by a neural network. Simulation results show that the proposed algorithm achieves lower detection delays per average run length than several state-of-the-art detectors.

Primary area:
learning on time series and dynamical systems
Keywords:
change point detection, Wasserstein distance, neural network, Rademacher complexity, theoretical guarantee

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_gmXQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes WONDER, an unsupervised online change-point detector that compares consecutive sliding windows using a neural approximation to the Wasserstein distance. The critic is updated incrementally with a gradient penalty. The authors derive concentration bounds and guarantees for false alarms and detection delay for the idealized statistic. Experiments on synthetic data and MNIST report lower detection delays than five baselines.

Critical strengths

1.The method combines an adaptive discrepancy with incremental neural training, providing a practical approach to detecting distributional changes without labeled change events.

2.The analysis explicitly handles partially contaminated windows and dependence between overlapping tests. These considerations improve its relevance to online detection.

Critical weaknesses
  1. The guarantees do not adequately cover the implemented detector. The theory assumes an exact supremum over strictly Lipschitz, norm-bounded networks, whereas the implementation uses a soft gradient penalty and eight updates per step. At target ARL 1,000, the theoretical thresholds exceed the statistic’s maximum possible value under both experimental window configurations, making them uninformative about detection performance. Even if the trained critic satisfies the assumed constraints, false-alarm bounds transfer, but detection guarantees require control of the optimization gap.

  2. The experimental comparisons do not establish matched actual ARL. Thresholds are calibrated using marginal statistic quantiles rather than measured first-alarm times. With temporally dependent statistics, this does not establish the claimed ARL. Calibration at ARL 100,000 also relies on approximately 100,000 observations, providing very limited information about the relevant tail.

Questions for authors

Which guarantees apply to the implemented statistic, and how are the Lipschitz and layer-norm assumptions ensured?

Are independently measured ARLs available? Does WONDER retain its advantage when methods are compared at matched achieved ARL?

Can the authors demonstrate a configuration where the theoretical threshold provides both meaningful false-alarm control and nontrivial detection power?

3 comments
AuthorsOpenReview ↗

Response to Reviewer gmXQ

We thank the Reviewer for reading our work and for the constructive comments. Shared concerns are answered in parts (A) and (B) of the general response.

Replies to weaknesses:

The guarantees do not cover the implemented detector, and the theoretical thresholds are uninformative about detection.

As the Reviewer notes, false-alarm bounds transfer once the trained critic satisfies the Lipschitz and layer norm constraints, and detection requires control of the optimization gap. Part (A) makes both statements exact: a normalization places the trained critic in FNN\mathcal F_{\rm NN} by construction, and Theorem 4.11 then holds with WNN(P,Q)W_{\rm NN}(P,Q) replaced by the separation sts_t that the critic achieves.

The Reviewer's computation is correct. At γ=103\gamma=10^3 and with ∏ℓMℓ=1\prod_\ell M_\ell=1, the threshold of Theorem 4.9 equals 17.0,B17.0\\,B for (n,m)=(32,2)(n,m)=(32,2) and 9.5,B9.5\\,B for (256,5)(256,5) (16.0,B16.0\\,B for the re-tuned (64,2)(64,2)), whereas a 1-Lipschitz statistic cannot exceed 2B2B. With such small test windows the theorems say nothing about detection, and the experiments rely on Monte Carlo thresholds only: the analysis provides the scaling of the threshold in nn, mm, the depth and γ\gamma, not a value that leads to an immediate empirical threshold.

The comparisons are not made at matched actual ARL.

The thresholds follow the standard protocol (part (B)), with the rule and code of [R1], which guarantees E∞[T]≥γ/2\mathbb E_\infty[T]\ge\gamma/2 for every method when the quantile is exact but, as the Reviewer notes, not equal achieved ARLs; we thus also measured it from first-alarm times. The concern about the tail is justified: with that code's default (100 null streams of 1,023 samples), the quantile at nominal 10510^5 rests on about one exceedance, and the measured ARL of that threshold for WONDER is about 3.6×1043.6\times10^4 on the synthetic streams and 1.0×1041.0\times10^4 on MNIST (where the statistic also drifts upward). The thresholds at measured ARL 10410^4 reported here rest on 60 to 340 simulated false alarms per method.

Replies to questions:

Which guarantees apply to the implemented statistic, and how are its assumptions ensured?

Theorems 4.9–4.10, for the normalized statistic g~t\tilde g_t of part (A) or, equivalently, for the statistic g^t\hat g_t of Algorithm 1 with its threshold multiplied by the current weight norms. The Lipschitz and layer-norm assumptions are then ensured by the normalization itself: the rescaled weights have unit Frobenius norm, hence spectral norm at most 1. The delay bound holds only with WNN(P,Q)W_{\rm NN}(P,Q) replaced by the achieved separation sts_t, which cannot be verified a priori.

Does WONDER keep its advantage at matched measured ARL?

At measured ARL 10410^4, reported as an example (table in part (B)), it does on the synthetic streams and, on average over the digits, on MNIST. On the synthetic streams, the re-tuned WONDER has a smaller detection delay than every baseline (2.07 / 1.12 / 1.10 against 3.29 / 1.15 / 1.17 for RFF-MMD, the best of them).

On MNIST, at matched measured ARL 10410^4, the EDD per digit is:

Post-change digit123456789Mean
WONDER3.814.534.784.257.034.754.224.634.334.70
RFF-MMD3.215.365.314.417.465.174.165.344.404.98

WONDER is faster than RFF-MMD on digits 2, 3, 4, 5, 6, 8 and 9, and slower on digits 1 and 7. The four other baselines are slower than WONDER on every digit.

Is there a configuration where the theoretical threshold controls false alarms and still detects changes?

Yes, but only for large windows and large changes. For the normalized function class, Theorems 4.9 and 4.11 give E∞[T]≥γ\mathbb E_\infty[T]\ge\gamma together with detection within mm post-change samples with probability at least 1−β1-\beta as soon as

WNN(P,Q)B ≥ (1n+1m)(2Cd+32ln⁡(6γ)+2ln⁡(1/β)).\frac{W_{\rm NN}(P,Q)}{B}\ \ge\ \Big(\frac{1}{\sqrt n}+\frac{1}{\sqrt m}\Big)\Big(2C_d+3\sqrt{2\ln(6\gamma)}+\sqrt{2\ln(1/\beta)}\Big).

For d=2d=2, γ=103\gamma=10^3 and β=0.05\beta=0.05, the last factor equals 25.625.6. For this class WNN(P,Q)≤BW_{\rm NN}(P,Q)\le B, with equality for two point masses at antipodal points of norm BB. Even this largest change requires n=m≥2,626n=m\ge 2{,}626, and a change with WNN(P,Q)=B/2W_{\rm NN}(P,Q)=B/2 requires n=m≥10,504n=m\ge 10{,}504. These large windows reflect that the results are distribution-free: they hold for every pair of distributions on the ball of radius BB with the given WNN(P,Q)W_{\rm NN}(P,Q).

The constants can be reduced: Proposition 4.4 bounds the population Rademacher complexity directly, so Corollary 4.6 follows from Lemma A.2 alone. The threshold of Theorem 4.9 then becomes Cn,mCd+B2(1/n+1/m)ln⁡(2γ)C_{n,m}C_d+B\sqrt{2(1/n+1/m)\ln(2\gamma)}, and the requirements above drop to n=m≥918n=m\ge 918 and 3,6723{,}672.

[R1] Kalinke and Gavioli-Akilagun, NeurIPS, 2025.

Thank you for the clarification and the additional experiments. I have two follow-up questions.

The guarantees can be directly transferred to the detector that is run by normalizing its statistic.

Does the table in part (B) use this normalized statistic, or the original statistic with a fixed threshold?

The thresholds at measured ARL 10410^4 reported here rest on 60 to 340 simulated false alarms per method.

Could you report each method’s measured ARL and uncertainty intervals for both ARL and EDD? Could the remaining ARL mismatch explain the smaller delay differences?

AuthorsOpenReview ↗

Further Response to Reviewer gmXQ

We thank the Reviewer for the follow-up questions.

Replies to questions:

Does the table in part (B) use the normalized statistic, or the original statistic with a fixed threshold?

The original statistic g^t\hat g_t of Algorithm 1 with a constant threshold, set by Monte Carlo as for every baseline. We thank the Reviewer for this insightful question, which led us to also run g~t\tilde g_t under the protocol of part (B), with a constant Monte Carlo threshold. EDD at measured ARL 10410^4:

StatisticMixed normalLaplaceUniformMNIST mean
g^t\hat g_t2.061.111.094.70
g~t\tilde g_t2.021.141.175.12

Here the gradient steps, step size and penalty of g~t\tilde g_t are re-tuned on separate streams, which changes the step size only. The two statistics behave similarly: they differ by at most 0.08 sample on the synthetic data, and g~t\tilde g_t is 0.4 sample slower on MNIST. We therefore keep g^t\hat g_t in the experiments.

Measured ARLs, uncertainty intervals, and the remaining ARL mismatch.

Each threshold is matched to a measured ARL of 10410^4 on its method's null streams, so the six measured ARLs are equal by construction and their uncertainty is the sampling error of the calibration. With 500 null streams and 1,000 delay runs per method on the synthetic data (MNIST: 200 and 100 per digit), each threshold now rests on 310 to 336 false alarms (MNIST: 77 to 80). The table gives 95% bootstrap intervals. The threshold is re-matched on each resample, so the EDD intervals include the calibration error.

WONDERRFF-MMDOKCUSUMNEWMAScanBNN-CUSUM
Synthetic: ARL (×104\times10^4)1.00 [0.90, 1.12]1.00 [0.89, 1.13]1.00 [0.89, 1.12]1.00 [0.90, 1.12]1.00 [0.90, 1.13]1.00 [0.91, 1.10]
EDD, mixed normal2.06 [1.98, 2.15]3.29 [3.12, 3.49]8.41 [8.18, 8.68]8.99 [8.78, 9.21]17.4 [17.2, 17.7]42.7 [41.3, 43.8]
EDD, Laplace1.11 [1.09, 1.14]1.15 [1.13, 1.18]3.93 [3.90, 3.97]4.16 [4.09, 4.22]10.3 [10.1, 10.4]16.6 [16.0, 17.0]
EDD, Uniform1.09 [1.08, 1.11]1.17 [1.14, 1.21]3.96 [3.94, 3.98]4.73 [4.66, 4.80]10.6 [10.5, 10.8]21.4 [20.6, 22.1]
MNIST: ARL (×104\times10^4)1.01 [0.83, 1.27]1.01 [0.81, 1.26]1.01 [0.82, 1.29]1.00 [0.81, 1.26]1.01 [0.81, 1.30]1.02 [0.82, 1.30]
EDD, MNIST mean4.70 [4.56, 4.82]4.98 [4.85, 5.13]6.53 [6.31, 6.65]8.24 [8.08, 8.37]14.3 [14.0, 14.5]14.0 [13.5, 15.0]

The remaining mismatch does not explain the differences with RFF-MMD, the closest baseline. The 95% intervals of the EDD difference (RFF-MMD minus WONDER), which also include the calibration error, exclude zero.

Reviewer_hEe1OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes WONDER, Wasserstein online change-point detection with neural networks, which is a non-parametric online change-point detection procedure that trains a neural network to estimate the Wasserstein distance between consecutive sliding windows. The paper also derives concentration inequalities, average run length, and a detection-delay tail bound. Experiments on synthetic data and MNIST demonstrate smaller detection delays than several kernel baselines.

Critical strengths
  • The recursively trained critic network provides a simple approach to learn the Wasserstein-type discrepancy for the data streams without any pre-specified post-change model.
  • For the ideal Wasserstein-distance statistic, the analysis explicitly characterizes the false-alarm performance including average run length and the detection delay under the post-change window.
Critical weaknesses

The guarantees are not established for the actual detector. The analysis is mostly for the ideal Wasserstein distance statistic gtg_t in eq(12), whereas Algorithm 1 uses a few gradient-penalty updates. The learned fθf_\theta is therefore only approximately 1-Lipschitz and does not necessarily lie in the class of 1-Lipschitz NNs. Although the authors acknowledge the optimization gap, the implementation also does not ensure the layer-norm constraints required by Assumption 4.1. Overall, my impression is that although the paper aims to overcome the kernel limitations of kernel methods and the theoretical limitations of learning methods, the analysis does not fully address these limitations. It is for the theoretical counterpart, while the actual implementation might still inherit the well-known difficulty of analyzing neural network learning methods.

Questions for authors

In addition to the weakness above, I also have some questions/comments below.

  • The experimental comparisons needs more clarification. Section 5 selects thresholds as quantiles of pooled test statistics, which are dependent due to overlapping windows. It is unclear whether these thresholds achieve the target ARL γ\gamma and ensure fair comparisons in Figs. 2–3. If possible, the authors could directly simulate the ARL; although more time-consuming, this might be doable over a smaller ARL range.

  • The detection-delay guarantee in Theorem 4.11 is a bit different and narrower from what one typically expects for sequential detection. Theorem 4.11 applies only to the first mm post-change positions, before the reference window becomes contaminated, and does not provide a full delay-tail bound or establish the expected-delay objective in Eq. (5). Relatedly, the delay in Eq. (5) depends on the true change point τ\tau, while a common practice is to consider the worst-case delay by taking the supremum over τ≥1\tau \ge 1. It would be useful if the author could clarify whether the probability in Eq. (24) depends on τ\tau and what upper bound on detection delay Theorem 4.11 implies.

  • I also have a conceptual question about whether the proposed framework is the most efficient for online detection. The paper uses the Wasserstein distance between neighboring windows to perform detection, which is more like a Shewhart chart-type detection rule, while for online change detection especially when the change magnitude is small, the CUSUM-type mechanism may exhibit stable and smaller delays as it can accumulate small changes over time. In this paper's setting, when the window size m is large enough, it will guarantee that the detection stops within the first post-change window with high probability; however it may not be the most efficient mechanism to minimize the detection delay (nearly or asymptotically). This is not a weakness of the proposed method, but it would be useful to briefly comment on whether it can be extended to a CUSUM-type mechanism to detect smaller changes more efficiently.

  • Also a small suggestion that the stopping time in eq(23) should be moved to Section 3 as it is part of the proposed monitoring method.

3 comments
AuthorsOpenReview ↗

Response to Reviewer hEe1

We thank the Reviewer for reading our work and for the constructive suggestions. Shared concerns are answered in parts (A) and (B) of the general response.

Replies to weaknesses:

The guarantees hold for the ideal statistic, not for the implemented detector.

The Reviewer is right on both points: the penalty does not make the critic 1-Lipschitz, and no layer-norm constraint is imposed. Part (A) closes this gap on the false-alarm side. Dividing the statistic by the product of the Frobenius norms of the current weights gives a critic that satisfies Assumptions 4.1–4.2 by construction, so Theorems 4.9–4.10 hold for the network actually trained, with no assumption on the optimization. Equivalently, only the threshold of Algorithm 1 is rescaled. The difficulty of analyzing neural network training then remains only in the detection bound, through the separation sts_t achieved by the trained critic.

Replies to questions:

Do the quantile-based thresholds achieve the target ARL?

The quantile rule is that of [R1] and is standard in this literature (part (B)). With an exact quantile it guarantees E∞[T]≥γ/2\mathbb E_\infty[T]\ge\gamma/2 for every method, but the Reviewer is right that it does not equalize the achieved ARL. As suggested, we simulated first-alarm times. With the quantile rule, the measured ARL at nominal 10310^3 on the synthetic streams was 880 for WONDER and between 3,100 and 25,000 for the baselines, whose statistics are more autocorrelated (1,000 against 3,000 to 18,000 on MNIST). We then matched all methods on the measured ARL and re-tuned WONDER under this calibration. At measured ARL 10410^4 (table in part (B)), it remains the fastest method on the synthetic streams (2.07 / 1.12 / 1.10 against 3.29 / 1.15 / 1.17 for RFF-MMD, the best baseline). On MNIST it has the smallest detection delay on average over the nine digits (4.70 against 4.98 for RFF-MMD). Figures 2–3 will show both calibrations.

Does Theorem 4.11 depend on the change point, and what delay bound does it imply?

Below, t0t_0 is the change point (τ\tau in Eq. (5)) and γ\gamma the ARL level, as in the paper.

Dependence on the change point. Lemma A.4 holds for any threshold. With the constant threshold of Theorem 4.9, the right-hand side of (24) is the same for every t0t_0, because for k≤mk\le m the reference window is entirely pre-change. It is therefore a worst-case bound over the change point. With the thresholds of Theorem 4.10, t0t_0 enters only through ln⁡(3tk(tk+1)/α)\ln(3t_k(t_k+1)/\alpha), as in the kernel counterpart [R1, Theorem 3], and conditioning on no false alarm before the change costs at most a factor 1/(1−α)1/(1-\alpha).

Implied bound. For β∈(0,1)\beta\in(0,1), let kβ=⌈m,(ν+Cn,mCd+cxyln⁡(1/β)/2)/WNN(P,Q)⌉k_\beta=\lceil m\\,(\nu+C_{n,m}C_d+c_{xy}\sqrt{\ln(1/\beta)/2})/W_{\rm NN}(P,Q)\rceil. If kβ≤mk_\beta\le m, the change is detected within kβk_\beta samples with probability at least 1−β1-\beta, and E[min⁡(D,m)]≤kβ+mβ\mathbb E[\min(D,m)]\le k_\beta+m\beta. With the threshold of Theorem 4.9, kβ≤⌈m,Cn,m(2Cd+32ln⁡(6γ)+2ln⁡(1/β))/WNN(P,Q)⌉k_\beta\le\lceil m\\,C_{n,m}(2C_d+3\sqrt{2\ln(6\gamma)}+\sqrt{2\ln(1/\beta)})/W_{\rm NN}(P,Q)\rceil.

Scope. The Reviewer is right that this does not bound the objective (5). After n+m−1n+m-1 positions both windows are post-change and the statistic returns to its null level, so Eτ[(T−τ)+]\mathbb E_\tau[(T-\tau)_+] also contains the miss probability multiplied by the post-change run length. This is inherent to rules that compare recent samples with the preceding ones without a fixed pre-change reference, such as NEWMA [R3], not specific to WONDER. We will restate Theorem 4.11 with these three points.

Can the method be extended to a CUSUM-type rule to detect small changes?

WONDER is indeed a Shewhart-type rule: evidence is accumulated over mm samples only. The bound above requires kβ≤mk_\beta\le m, i.e., m≳B2ln⁡γ/WNN(P,Q)2m\gtrsim B^2\ln\gamma/W_{\rm NN}(P,Q)^2. With mm of this order the delay is of the same order, the ln⁡γ\ln\gamma over squared-signal scaling of CUSUM, but mm must then be matched to an unknown change size. Two extensions avoid this. (i) Run the statistic on a geometric grid of JJ window sizes mm: Theorems 4.9–4.10 extend by a union bound, with γ\gamma and α\alpha replaced by JγJ\gamma and α/J\alpha/J. (ii) Use a CUSUM recursion as in NN-CUSUM [R2]: each step adds the critic's mean difference between the two windows, which must be computed on samples not used for training. Our experiments agree with this picture: small windows are best on the synthetic streams, where changes are large (m=2m=2), whereas on MNIST m=5m=5 gives shorter delays than m=2m=2, 33 or 88. We will add this discussion and leave (ii) for future work.

The stopping time in Eq. (23) should be moved to Section 3.

We agree: the stopping time will be defined in Section 3.2 with Algorithm 1, and Section 4 will refer to it.

[R1] Kalinke and Gavioli-Akilagun, NeurIPS 2025. [R2] Gong et al., arXiv:2210.17312, 2022. [R3] Keriven et al., IEEE TSP 2020.

Thank you to the authors for the clarification and additional discussion. I have increased my original score accordingly.

Thank you for your thoughtful feedback and careful reassessment. We are pleased that our clarifications and additional discussion have addressed your concerns. We sincerely appreciate your time and effort!

Reviewer_g9TuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes WONDER, an online change point detector that compares consecutive windows using a neural approximation to Wasserstein-1 distance. The critic is updated recursively with a gradient penalty. For an idealized statistic defined by exact optimization over a constrained network class, the authors derive concentration bounds and false-alarm guarantees, together with a finite-window detection bound. Experiments on synthetic data and MNIST report improvements over several baselines.

Critical strengths

The method provides a reasonable way to learn an adaptive discrepancy without labeled change events. The concentration analysis explicitly handles partial contamination and does not require independence between successive tests.

Critical weaknesses
  1. The contribution is incremental, and the theory does not establish the advertised guarantees for the implementation. The method combines a standard neural Wasserstein critic with a sliding-window detector. The analysis primarily applies existing Rademacher complexity and bounded-difference tools. It assumes exact optimization, global Lipschitz control, and layerwise norm bounds, whereas the implementation uses a few gradient steps and a sampled gradient penalty. Moreover, Theorem 4.11 applies only within the first (m) post-change positions and does not provide a full delay-tail or expected-delay guarantee. These results do not sufficiently distinguish the paper from existing learned-discrepancy detectors.

  2. The empirical advantage is not established at matched ARL. Thresholds are selected from marginal quantiles of pooled null statistics. For temporally dependent statistics, this does not generally calibrate the expected first-alarm time. Without independently measured ARLs and clear treatment of missed detections, the reported delay comparisons are inconclusive.

Questions for authors
  1. Which guarantees apply to the actual finite-step, gradient-penalized implementation, and under what verifiable assumptions?

  2. What are the independently measured ARLs for the reported thresholds, and how are missed detections and pre-change alarms handled?

  3. What is the precise theoretical advance over existing neural online detectors, particularly Puchkin and Shcherbakova (2023), which already provide running-length and detection-delay guarantees with a neural-network specialization?

1 comment
AuthorsOpenReview ↗

Response to Reviewer g9Tu

We thank the Reviewer for reading our work and for the constructive comments. Shared concerns are answered in parts (A) and (B) of the general response.

Replies to weaknesses:

The contribution is incremental, and the theory does not cover the actual implementation.

We agree that the tools (Rademacher complexity, bounded differences) are standard. What is new is their use for a sequential neural detector: (i) Theorem 4.7 treats a partially contaminated window, i.e., independent but not identically distributed samples, and isolates the signal ϵ,WNN(P,Q)\epsilon\\,W_{\rm NN}(P,Q); (ii) Theorems 4.9–4.10 give explicit thresholds without independence between overlapping tests; (iii) the network enters only through its depth and norm product, not its width or the input dimension. The implementation gap can be closed, this is discussed in part (A).

The Reviewer is right about Theorem 4.11: it covers the first mm post-change positions. For k>mk>m it only gives P(D≥k)≤P(D≥m)\mathbb P(D\ge k)\le\mathbb P(D\ge m), and it implies E[min⁡(D,m)]≤∑k=1mexp⁡(−2(Δtk)+2/cxy2)\mathbb E[\min(D,m)]\le\sum_{k=1}^m\exp(-2(\Delta_{t_k})_+^2/c_{xy}^2) but no bound on Eτ[(T−τ)+]\mathbb E_\tau[(T-\tau)_+]: once both windows are post-change the statistic returns to its null level, so a missed change costs the post-change run length. This is inherent to detectors that compare the most recent samples with the preceding ones without a fixed pre-change reference, not specific to WONDER, for example, NEWMA [R3] bounds its statistic only at a time when the last BB samples are post-change.

The empirical advantage is not shown at matched ARL.

Our thresholds follow the standard protocol of this literature (part (B)): each is the (1−1/γ)(1-1/\gamma)-quantile of null statistics, as in [R1], which guarantees E∞[T]≥γ/2\mathbb E_\infty[T]\ge\gamma/2 for every method when the quantile is exact. We agree that this does not equalize the achieved ARL, so we also calibrated all methods on first-alarm times and re-tuned WONDER under this calibration. At matched measured ARL 10410^4 (table in part (B)), WONDER is the fastest method on the three synthetic alternatives (2.07 / 1.12 / 1.10 against 3.29 / 1.15 / 1.17 for RFF-MMD, the best baseline) and on MNIST on average over the nine digits.

Replies to questions:

Which guarantees apply to the actual implementation?

Theorems 4.9–4.10 apply to Algorithm 1 as implemented, with SS penalized gradient steps, once the threshold on g^t\hat g_t is multiplied by the current weight norms (part (A)); their assumptions then hold by construction. The delay bound applies with WNN(P,Q)W_{\rm NN}(P,Q) replaced by the separation sts_t achieved by the trained critic, which cannot be verified a priori.

What are the measured ARLs, and how are missed detections and pre-change alarms handled?

With the first-alarm calibration of part (B), all methods have the same measured ARL by construction; we take 10410^4 as an example. A run with no exceedance within the 64 post-change samples is recorded with delay 65. The statistic is inspected only after the change, as in [R1], so a run with an earlier exceedance is not discarded. At matched ARL 10410^4, no run is missed on either data set except for NN-CUSUM (24% on the mixed normal), and at most 2% of the runs have an exceedance within the 64 pre-change samples (about 0.6% is expected).

What is the theoretical advance over Puchkin and Shcherbakova (2023)?

Thank you for pointing to this prior analysis [R2], which we will discuss. For a contrastive statistic, [R2] shows that no false alarm occurs before a fixed horizon TT with probability 1−δ1-\delta, for a threshold given up to an absolute constant, and bounds the delay with high probability. To our knowledge, our analysis remains the first to give explicit thresholds for the ARL and for the false-alarm probability over an infinite horizon, together with a delay bound, for an online detector with a neural-network statistic. Further differences are:

  • Discrepancy. [R2] maximizes a classification (Jensen–Shannon) functional whose target is ln⁡(p/q)\ln(p/q). Its neural result (Corollary 3.1) assumes densities on [0,1]p[0,1]^p with a Hölder-smooth log-ratio, which excludes singular changes such as a change of support. Our statistic is an integral probability metric and only requires a bounded domain.
  • Complexity. [R2] relies on covering numbers of sparse, truncated ReLU networks, and its delay bound scales as JS(p,q)−(2β+p)/(2β)\mathrm{JS}(p,q)^{-(2\beta+p)/(2\beta)} with a factor eBe^B. Our bounds involve only the depth and the norm product; in return they are relative to WNNW_{\rm NN}, not WW.

Both analyses assume exact maximization over the class of functions; with part (A), our false-alarm guarantees no longer need this limiting assumption and apply to the actual implementation.

[R1] Kalinke and Gavioli-Akilagun, NeurIPS 2025. [R2] Puchkin and Shcherbakova, AISTATS 2023. [R3] Keriven et al., IEEE TSP 2020.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers

We thank the three reviewers for their careful reading and constructive comments. Two concerns are shared: (A) the guarantees are proved for the ideal statistic gtg_t and not for the detector that is run, and (B) thresholds taken from pooled quantiles of null statistics may not correspond to the same ARL for all methods.

(A) Guarantees for the implemented detector. The guarantees can be directly transferred to the detector that is run by normalizing its statistic. Let W^ℓ,t\hat{\mathbf W}_{\ell,t} be the weights returned by Algorithm 1 at time tt, for any SS, λ\lambda and warm start, and define the normalized statistic g~t=g^t/∏ℓ∣W^ℓ,t∣F\tilde g_t=\hat g_t/\prod_\ell\\|\hat{\mathbf W}_{\ell,t}\\|_F. The critic is a bias-free ReLU network, so by positive homogeneity f~t=fθ^t/∏ℓ∣W^ℓ,t∣F\tilde f_t=f_{\hat\theta_t}/\prod_\ell\\|\hat{\mathbf W}_{\ell,t}\\|_F is the network with weights W^ℓ,t/∣W^ℓ,t∣F\hat{\mathbf W}_{\ell,t}/\\|\hat{\mathbf W}_{\ell,t}\\|_F. It satisfies Assumption 4.1 with Mℓ=1M_\ell=1 and, since ∣⋅∣2≤∣⋅∣F\\|\cdot\\|_2\le\\|\cdot\\|_F, it is 1-Lipschitz (Assumption 4.2). Both assumptions hold by construction, and g~t≤gt\tilde g_t\le g_t on every sample path.

  • False alarms. g~t>νt⊆gt>νt\\{\tilde g_t>\nu_t\\}\subseteq\\{g_t>\nu_t\\}, so Theorems 4.9 and 4.10 hold verbatim for the detector that thresholds g~t\tilde g_t, for any number of gradient steps and with no assumption on the optimization.
  • Detection. The argument of Theorem 4.7 holds uniformly over FNN\mathcal F_{\rm NN} (McDiarmid applied to the uniform deviation, same constants): with probability at least 1−δ1-\delta, g~t≥ϵtst−Cn,mCd−cxyln⁡(1/δ)/2\tilde g_t\ge\epsilon_t s_t-C_{n,m}C_d-c_{xy}\sqrt{\ln(1/\delta)/2}, where st=EPf~t−EQf~t≤WNN(P,Q)s_t=\mathbb E_P\tilde f_t-\mathbb E_Q\tilde f_t\le W_{\rm NN}(P,Q) is the separation between PP and QQ achieved by the trained critic. Theorem 4.11 thus holds for g~t\tilde g_t with WNN(P,Q)W_{\rm NN}(P,Q) replaced by any lower bound on sts_t. The optimization gap WNN(P,Q)−stW_{\rm NN}(P,Q)-s_t enters only here; we do not bound it a priori, since training is non-convex.

Equivalently, training and statistic are unchanged and only the threshold is rescaled: g~t>νt\tilde g_t>\nu_t if and only if g^t>νt∏ℓ∣W^ℓ,t∣F\hat g_t>\nu_t\prod_\ell\\|\hat{\mathbf W}_{\ell,t}\\|_F. Both results thus hold for the statistic g^t\hat g_t of Algorithm 1 itself, whatever the scale of the trained critic, which is absorbed by the threshold. We will add this normalized detector and its guarantees to the revision as Section 4.4, and leave a bound on the optimization gap for future work.

(B) Calibration of the thresholds. We follow the standard protocol of the online CPD literature: thresholds are set under the null hypothesis to meet a target ARL, and methods are compared through their EDD at these thresholds. The original papers of four of our five baselines do so [R1, R3–R5]: the threshold comes from an analytical ARL approximation checked by simulation in [R1] and from Monte Carlo simulation under the null in [R3–R5]. The fifth [R2] presents ARL calibration under the null as a classical way to set it. We used the rule and code of [R5] for all methods: the threshold for a target ARL γ\gamma is the (1−1/γ)(1-1/\gamma)-quantile of the statistics over null streams. By the union bound of Theorem 4.9, an exact quantile guarantees E∞[T]≥γ/2\mathbb E_\infty[T]\ge\gamma/2 for every method whose null statistics are identically distributed, whatever their dependence.

The reviewers are right that this rule does not equalize the achieved ARL across methods; references [R1, R3, R4] calibrate on the stopping time itself. As suggested by Reviewer hEe1, we did so as well, from simulated first-alarm times (ARL estimated as monitored time per false alarm). Under this calibration, the EDD at matched measured ARL 10410^4 as an example is:

Post-changeWONDERRFF-MMDOKCUSUMNEWMAScanBNN-CUSUM
Mixed normal2.073.297.958.9717.743.5
Laplace1.121.153.914.1310.216.7
Uniform1.101.173.964.6810.620.9
MNIST digits 1–9 (mean)4.704.986.418.2414.414.0

WONDER has the smallest detection delay in every case. Per-digit MNIST results are shown in our response to Reviewer gmXQ; the full ARL range will be reported in the revised Figures 2–3.

In the revision, we will (i) add part (A) as Section 4.4 and rewrite the limitations; (ii) report both threshold calibrations, with missed detections and pre-change alarms; (iii) state the scope of Theorem 4.11 and the delay bound it implies; (iv) compare with Puchkin and Shcherbakova (2023); (v) state when the theoretical thresholds are informative.

[R1] Li et al., Sequential Analysis, 2019. [R2] Keriven et al., IEEE TSP, 2020. [R3] Wei and Xie, JRSS-B, 2026. [R4] Gong et al., arXiv:2210.17312. [R5] Kalinke and Gavioli-Akilagun, NeurIPS, 2025.

AuthorsOpenReview ↗

Further response to all reviewers

We would like to sincerely thank you again for the time and effort you have devoted to reviewing our paper. Your insightful feedback and suggestions have helped us improve our paper. We have uploaded the revised manuscript, with the changes marked in blue. In summary, we have added:

  • Guarantees for the implemented detector (Section 4.4, proofs in Appendix A.2.3): the false alarm guarantees of Theorems 4.9–4.10 hold for the trained critic after normalization by its weight norms (Proposition 4.13), and the delay bound of Theorem 4.11 holds with WNN(P,Q)W_{\rm NN}(P, Q) replaced by the separation achieved by this critic.
  • Experiments at matched measured ARL: the thresholds of all methods are now calibrated on simulated first-alarm times, in place of the quantile rule (Figures 2, 3, 5 and 6). The experiments use the original statistic g^t\hat g_t, see Further Response to Reviewer gmXQ for comparisons with the normalized statistic g~t\tilde g_t.
  • Scope of the theory: Theorem 4.11 now states the delay bound it implies, Remark 4.12 gives its scope, and Remark 4.14 says when the theoretical thresholds are informative.
  • Further changes: a comparison with Puchkin and Shcherbakova (2023) (Appendix A.2.4), the stopping time defined in Section 3.2, and rewritten limitations (Section 6).

We fully understand how demanding it is to review multiple submissions in such a short period. As the discussion deadline approaches, however, we would be very grateful if you could take a moment to share your thoughts on our responses. We would be happy to address any remaining concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.