Robust Quickest Change Detection with Sampling Control

Hoda Bidkhori; Taposh Banerjee; Yingze Hou

REVIEW 2 major objections 4 minor 27 references

Robust Quickest Change Detection with Sampling Control

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sampling control matches optimal asymptotic change detection speed.

desk verdict Sensible algorithm and honest simulations, but the main optimality proof divides by a fixed constant q<1 and then drops it, so the headline theorem is not proven as written. read the letter →

arxiv 2412.20207 v1 pith:WEIQ73N7 submitted 2024-12-28 stat.ME

Yingze Hou , Hoda Bidkhori , Taposh Banerjee This is my paper · ORCID

classification stat.ME MSC 62L1062F3560G4062C20

keywords quickestchangedetectionsamplingcontrolleastfavorablelawrobustoptimalityCUSUMpre-changedutycycleobservationcostasymptotic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how to detect a change in distribution as fast as possible when the post-change distribution is not known precisely and every observation has a cost. It proposes RDE-CUSUM, a CUSUM-type statistic built from a least favorable law $\bar g$ (the most difficult post-change distribution inside the family), with an on-off rule that skips observations whenever the statistic is negative. The central claim is that for every fixed observation-cost constraint $\beta$, as the false-alarm rate $\alpha$ goes to zero the algorithm's worst-case delay is asymptotically optimal, with the universal constant $|\log\alpha|/D_{\mathrm{KL}}(\bar g\|f)$. If true, this means a robust detector can save a fixed fraction of observations without changing the asymptotic detection speed, and the false-alarm and cost constraints can be tuned almost independently.

What carries the argument

The central object is the least favorable law $\bar g$, a distribution inside the post-change family $\mathcal G$ whose log-likelihood ratio with respect to the pre-change law stochastically dominates the same ratio under every other $G\in\mathcal G$. RDE-CUSUM runs the CUSUM recursion on $\log(\bar g(X)/f(X))$, but negative values are floored at $-h$, and once the statistic is negative the algorithm skips samples, adding a drift $\mu$ on each skipped step until the statistic returns to zero. The LFL carries the worst-case analysis: delay bounds, crossing probabilities, and false-alarm bounds can all be evaluated at $\bar g$ rather than over the whole family. The parameters $h$ and $\mu$ control the pre-change duty cycle, and the threshold $A=|\log\alpha|$ controls the false-alarm rate, so the two constraints are nearly separable.

What would settle it

Run RDE-CUSUM under the conditions of Theorem 4.5, e.g. $f=\mathcal N(0,1)$, $\bar g=\mathcal N(1,1)$, and a fine grid of Gaussian post-change means, and measure the empirical worst-case delay for shrinking $\alpha$; if $\sup_G \mathrm{WADD}_G$ grows faster than $|\log\alpha|/D_{\mathrm{KL}}(\bar g\|f)$ as $\alpha\to0$, the asymptotic optimality claim is falsified, and a family violating the stochastic-boundedness condition should already show the same failure.

Watch

Extended reading notes

Core claim

Under Assumption 1, the paper claims that RDE-CUSUM is asymptotically robust optimal for every fixed observation-cost constraint $\beta$ as the false-alarm rate $\alpha$ tends to zero. With $A=|\log\alpha|$ and $\mu$ chosen so that the pre-change duty cycle is at most $\beta$, the worst-case delay satisfies $\sup_{G\in\mathcal G}\mathrm{WADD}_G(\bar\Psi_{\mathrm{RDC}}) \le |\log\alpha|/D_{\mathrm{KL}}(\bar g\|f)(1+o(1))$, while Theorem 4.1 gives the matching lower bound for any policy with $\mathrm{FAR}\le\alpha$ and $\mathrm{PDC}\le\beta$. The optimal constant is the Kullback-Leibler divergence from the least favorable law to the pre-change law, the same constant that governs classical CUSUM when the post-change law is known. The result contains the data-efficient CUSUM and robust CUSUM as limiting special cases.

Load-bearing premise

The proof requires Assumption 1: the post-change family has a least favorable law $\bar g$ that stochastically dominates every member of the family, and the log-likelihood ratios have finite positive second moments; if the real family is not bounded by $\bar g$, the worst-case delay bound need not hold.

Editorial extensions

If this is right

For any fixed cost constraint $\beta$, the asymptotic worst-case detection delay is the same as if every observation were taken, so the on-off control does not degrade the large-sample optimal detection speed.
The false-alarm and duty-cycle constraints are nearly decoupled: choosing $A=|\log\alpha|$ meets the false-alarm bound, and $\mu$ can then be selected to meet $\beta$ without changing $A$.
In the regime $A\to\infty$ and $h\to\infty$, choosing $\mu \le \frac{\beta}{1-\beta} D_{\mathrm{KL}}(f\|\bar g)$ satisfies the duty-cycle constraint, giving a tuning rule that uses only the two densities.
With a singleton post-change family and $\mu>0,h>0$, RDE-CUSUM reduces to the data-efficient CUSUM algorithm; with $\mu=h=0$ it reduces to the robust CUSUM algorithm, so the new result contains both earlier asymptotic optimality statements as special cases.
Simulated Gaussian and Poisson examples and the COVID-19 application indicate that the skipped-observation test detects the change within about a week of onset while using fewer observations than the all-sample robust CUSUM.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the independence of the FAR and PDC constraints suggests a practical tuning recipe as $A\to\infty$ and $h\to\infty$: fix $\beta$, set $\mu$ from the simple formula using $D_{\mathrm{KL}}(f\|\bar g)$, and only then choose $A$ from $\alpha$, without evaluating the constants $C_1$ and $C_2$.
Beyond the paper: because the duty-cycle constants $C_1$ and $C_2$ depend on $\bar g$, a misspecified least favorable law should first inflate the realized sampling fraction before it changes the asymptotic delay, so monitoring the empirical duty cycle in deployment would expose misspecification early.
Beyond the paper: the same on-off construction might extend to non-i.i.d. or multi-stream post-change models, provided the stochastic-dominance condition is re-derived for the new dependence structure.
Beyond the paper: since the delay constant is $D_{\mathrm{KL}}(\bar g\|f)$, candidate least favorable laws could be compared by their KL divergence to the pre-change law, and the one that best respects the cost constraint could be selected.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: RDE-CUSUM is a sensible merger of robust CUSUM and DE-CUSUM, and the simulations support the qualitative claim that on-off sampling control saves a fixed fraction of observations with modest delay cost. The paper is a legitimate contribution to sequential analysis. But the proof of the headline asymptotic optimality result (Theorem 4.5, via Theorem 4.4) has a real gap.

In Appendix B, the renewal argument counts cycles where the statistic goes below zero, with success probability q = P(the LFL random walk never goes negative). Equation (B.12) then gives an upper bound of [A/DKL(1+o(1)) + O(1)]/q + O(1), and the proof simply drops the division by q to claim Theorem 4.4. Since q is a fixed constant strictly below 1 (roughly 0.6 for the Gaussian example in Section 6.1), the written argument does not establish the 1/DKL constant. The additive O(1) terms are not the issue; the 1/q factor is. I suspect the theorem is true — a correct renewal decomposition should show the failed cycles contribute only O(1) total time, leaving A/DKL as the leading term — but the displayed inequality in the paper contradicts its own conclusion, so the proof as written is unsound.

There is also a smaller algebra slip in Appendix A. After (A.5), the denominator picks up a P(Z<0)^2 that should cancel out. That shifts the constant C2 but doesn't destroy the existence claim; it just needs to be made consistent.

The lower bound in Theorem 4.1 is fine: it applies Lorden's bound to the LFL \bar G, which is in G, so no circularity there. The heavy reliance on lemmas from Banerjee and Veeravalli (2013) is acceptable, since those are published results and the adaptation is clear. The COVID-19 analysis simply postulates Pois(2) as the LFL without validating stochastic boundedness; that is a limitation of the illustration, not a fatal flaw in the theory.

What is genuinely new is the combination of robust CUSUM with sampling control and the attempt at a robust optimality theorem. The numerical work is honest: 5000 runs, confidence bands, and a fair comparison against fractional sampling. The citation pattern is appropriate, including the authors' own DE-CUSUM work, which is directly relevant.

Who is this for? Researchers in quickest change detection, data-efficient monitoring, and public health surveillance. It deserves a serious referee, but not acceptance yet. I would send it to peer review with a clear request to fix the Theorem 4.4 proof and clean up Appendix A.

Referee Report

2 major / 4 minor

Summary. The paper studies quickest change detection with on-off observation control under a robust formulation where the post-change distribution is known only to belong to a family. The authors propose the RDE-CUSUM algorithm, which uses a least favorable law to design a CUSUM-type statistic with a lower truncation at -h and skips consecutive samples whenever the statistic is below zero. They prove (or attempt to prove) that the false-alarm and pre-change duty-cycle constraints can be met independently, and they claim asymptotic robust optimality as the false-alarm rate tends to zero for any fixed observation-cost constraint. The paper includes Gaussian and Poisson examples of least favorable laws and validates the empirical behavior on simulated data and U.S. COVID-19 daily case counts.

Significance. If the central optimality result were established, the paper would make a useful contribution: it extends the data-efficient CUSUM framework of Banerjee and Veeravalli to a robust setting with unknown post-change distribution, using a simple and computationally efficient statistic. The separate design of the false-alarm threshold and the sampling-control parameter is practically attractive, and the simulations support the qualitative claim that the algorithm can skip a large fraction of samples without losing much detection speed. However, the main theorem's proof currently contains a mathematical error that breaks the asymptotic optimality claim, so the contribution is conditional on a substantial revision.

major comments (2)

[Appendix B, Eq. (B.12); Theorem 4.4] The proof of Theorem 4.4 does not establish the stated bound. The derivation ends with sup_G WADD_G(τrdc) ≤ [A/D_KL(gbar||f)(1+o(1)) + ⌈h/µ⌉]/q + ⌈h/µ⌉, where q is defined in (B.10) as a fixed positive probability. The theorem claims sup_G WADD_G(τrdc) ≤ A/D_KL(gbar||f)(1+o(1)). To pass from the displayed inequality to the theorem statement, the 1/q factor must be removed, but q is generally strictly less than 1 and does not approach 1 as A→∞. For example, in the Gaussian family of Section 5, the first increment has positive probability of being negative, so q < 1. Thus the upper-bound constant is inflated by 1/q and does not match the lower bound of Theorem 4.1. Since Theorem 4.5 relies directly on Theorem 4.4, the paper's central asymptotic-optimality claim is not proven as written.
[Appendix B, Eqs. (B.9)-(B.10)] The event defining q is ambiguous and appears misstated. The expression "max_{1≤≤n} ∑_{i=k}^n log[gbar(X_i)/f(X_i)] ≥ 0, for all n" lacks a well-defined index range, and as written it does not correspond to the usual CUSUM statistic, which is always nonnegative because it includes the empty sum. The equality (c) in (B.9), which identifies this event with the condition that the RDE-CUSUM statistic never goes below zero, is therefore not directly verifiable. Because q underpins the crucial lower bound inf_G P_G(D_{λA} ≥ A) ≥ q > 0, this ambiguity is load-bearing for the proof.

minor comments (4)

[Section 6.2] The COVID-19 analysis simply postulates Pois(2) as the least favorable law without checking stochastic boundedness of the true case-count family against this LFL; the authors should clarify that this is a design assumption for illustration, not an empirical validation of Assumption 1.
[Figure captions, Section 6.1] The caption of Figure 2 says "Gaussian data processes (6.2)" but the example in (6.2) is Poisson; this should be corrected.
[Appendix B, Eq. (B.10)] There is a typo in the index range "max_{1≤≤n}"; the intended range for k and the precise event should be restated clearly.
[Appendix A, Eq. (A.1)] The claim that FAR of RDE-CUSUM is no larger than FAR of robust CUSUM is cited from Lemma 4 of Banerjee and Veeravalli (2013) but not argued; a short explanation or a restatement of the lemma's applicability would make the proof more self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 4.5 follows from the LFL Assumption 1 and external minimax results, not from its own conclusion; the q-factor gap in Eq. (B.12) is a proof error, not circularity.

full rationale

The derivation is self-contained against independent minimax theory. The universal lower bound (Theorem 4.1) is Lorden/Lai's bound evaluated at \bar G, an external result, and the upper bound (Theorem 4.4) rests on Assumption 1 and the published robust-CUSUM identity sup_G E_G[\tau_rc] = E_{\bar G}[\tau_rc] (Unnikrishnan et al. 2011), not on the paper's conclusion. The LFL definition is an assumption on the family G; it makes \bar G the worst case and therefore fixes the KL constant D_KL(\bar g||f) in both bounds, which is the theorem's content rather than a tautology. The Gaussian and Poisson LFL examples are proved directly in Section 5. The FAR and PDC arguments in Appendix A cite lemmas from Banerjee and Veeravalli (2013); although Banerjee is a co-author, those are published, proof-backed results and thus are real evidence, not self-referential support. The COVID-19 illustration assumes Pois(2) as the LFL as an application modeling choice, not a fitted input later called a prediction. A separate, non-circular concern is that Eq. (B.12) yields an upper bound divided by q>0, while Theorem 4.4 states the bound without the 1/q factor; this is a possible correctness gap in the proof, but it does not make the derivation circular.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The central result rests on the existence of an LFL and on a set of renewal-theoretic lemmas imported from prior work. No new physical entities are postulated. The proof gap in Appendix B is separate from the axiom ledger.

free parameters (3)

mu (sampling control increment) = Not fitted; user-set. Asymptotic guideline: mu <= beta/(1-beta) D_KL(f || gbar)
Controls how many consecutive samples are skipped after the statistic goes below zero; the PDC constraint is met by choosing mu small enough. Not fitted to data.
h (undershoot truncation) = Not fitted; fixed by user, e.g., h = 10 in simulations
Truncates the undershoot below zero for mathematical convenience; delays are bounded in terms of ceil(h/mu). Not fitted to data.
A (stopping threshold) = |log alpha|
Set by the false-alarm constraint to ensure FAR <= alpha; not fitted to data.

assumptions (7)

domain assumption A least favorable law gbar exists in the family G (Assumption 1.1).
All theorems and the algorithm require an LFL satisfying Definition 2; the paper gives Gaussian and Poisson examples.
domain assumption Likelihood ratios are continuous with finite positive moments up to second order (Assumption 1.2).
Needed for renewal-theoretic bounds and CUSUM asymptotics; excludes heavy-tailed or irregular cases.
standard math Lorden's minimax lower bound applies to any sampling-control policy (Theorem 4.1).
Imported from Lorden (1971) and Lai (1998); the paper does not prove it for the PDC-constrained class.
domain assumption FAR(RDE-CUSUM) <= FAR(CUSUM), from Banerjee and Veeravalli (2013) Lemma 4.
Used to set A = |log alpha| in Theorem 4.2; cited but not proved.
standard math PDC renewal formula (A.2) from Banerjee and Veeravalli (2013) Theorem 5.1.
Gives the PDC as a ratio of expected sojourn times.
standard math Stochastic dominance of partial sums under the LFL (Unnikrishnan et al. (2011) Lemma III.1).
Used in Eq. (B.9) to bound worst-case G by gbar.
standard math Wald's lemma and positivity of the never-negative probability q for positive-drift random walks.
Used in Corollary 4.3 and Appendix B.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robust Quickest Change Detection with Sampling Control." pith.science (2026). https://pith.science/paper/WEIQ73N7

@misc{pith2026241220207,
  author       = {Pith},
  title        = {Pith review of: Robust Quickest Change Detection with Sampling Control},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WEIQ73N7}},
  note         = {Machine review of arXiv:2412.20207}
}

read the original abstract

The problem of quickest detection of a change in the distribution of a sequence of random variables is studied. The objective is to detect the change with the minimum possible delay, subject to constraints on the rate of false alarms and the cost of observations used in the decision-making process. The post-change distribution of the data is known only within a distribution family. It is shown that if the post-change family has a distribution that is least favorable in a well-defined sense, then a computationally efficient algorithm can be designed that uses an on-off observation control strategy to save the cost of observations. In addition, the algorithm can detect the change robustly while avoiding unnecessary false alarms. It is shown that the algorithm is also asymptotically robust optimal as the rate of false alarms goes to zero for every fixed constraint on the cost of observations. The algorithm's effectiveness is validated on simulated data and real public health data.

Figures

Figures reproduced from arXiv: 2412.20207 by the authors.

**Figure 2.** Comparison of RDE-CUSUM algorithm, robust CUSUM algorithm, and the fractional [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Robust test for detecting COVID-19 outbreak in Allegheny County. [Left] Daily increase [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Robust test for detecting COVID-19 outbreak in St. Louis County. [Left] Daily increase [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

[1]

Banerjee, T., Gurram, P., and Whipps, G. T. (2021). A Bayesian theory of change detection in statistically periodic random processes. IEEE Transactions on Information Theory , 67(4):2562--2580

work page 2021
[2]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2012). Data-efficient quickest change detection with on--off observation control. Sequential Analysis , 31(1):40--77

work page 2012
[3]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2013). Data-efficient quickest change detection in minimax settings. IEEE Transactions on Information Theory , 59(10):6917--6931

work page 2013
[4]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2015). Data-efficient minimax quickest change detection with composite post-change distribution. IEEE Transactions on Information Theory , 61(9):5172--5184

work page 2015
[5]

Brucks, T., Banerjee, T., and Mishra, R. (2023). Modeling and quickest detection of a rapidly approaching object. To appear in Sequential Analysis

work page 2023
[6]

Guo, J., Yan, H., and Zhang, C. (2023). A bayesian partially observable online change detection approach with thompson sampling. Technometrics , 65(2):179--191

work page 2023
[7]

Hou, Y., Bidkhori, H., and Banerjee, T. (2024a). Robust quickest change detection in multi-stream non-stationary processes. arXiv preprint arXiv:2412.04493

work page Pith review arXiv 2024
[8]

Hou, Y., Oleyaeimotlagh, Y., Mishra, R., Bidkhori, H., and Banerjee, T. (2024b). Robust quickest change detection in nonstationary processes. Sequential Analysis , 43(3):275--300

work page 2024

Show all 27 references

[9]

Lai, T. L. (1998). Information bounds and quick detection of parameter changes in stochastic systems. IEEE Transactions on Information Theory , 44(7):2917 --2929

1998
[10]

S., Tay, W

Lau, T. S., Tay, W. P., and Veeravalli, V. V. (2018). A binning approach to quickest change detection with unknown post-change distribution. IEEE Transactions on Signal Processing , 67(3):609--621

2018
[11]

G., and Veeravalli, V

Liang, Y., Tartakovsky, A. G., and Veeravalli, V. V. (2022). Quickest change detection with non-stationary post-change observations. IEEE Transactions on Information Theory , 69(5):3400--3414

2022
[12]

Lorden, G. (1971). Procedures for reacting to a change in distribution. Annals of Mathematical Statistics , 42(6):1897--1908

1971
[13]

Moustakides, G. V. (1986). Optimal stopping times for detecting changes in distributions. Annals of Statistics , 14(4):1379--1387

1986
[14]

and Dey, S

Naha, A. and Dey, S. (2024). Bayesian quickest change-point detection with an energy harvesting sensor and asymptotic analysis. IEEE Transactions on Signal Processing

2024
[15]

Oleyaeimotlagh, Y., Banerjee, T., Taha, A., and John, E. (2023). Quickest change detection in statistically periodic processes with unknown post-change distribution. Sequential Analysis , 42(4):404–437

2023
[16]

Page, E. S. (1954). Continuous inspection schemes. Biometrika , 41(1/2):100--115

1954
[17]

Pollak, M. (1985). Optimal detection of a change in distribution. Annals of Statistics , 13(1):206--227

1985
[18]

Pollak, M. (1987). Average run lengths of an optimal method of detecting a change in distribution. Annals of Statistics , 15(2):749--779

1987
[19]

Poor, H. V. and Hadjiliadis, O. (2009). Quickest detection . Cambridge University Press

2009
[20]

Reynolds Jr, M. R. and Stoumbos, Z. G. (2004). Control charts and the efficient allocation of sampling resources. Technometrics , 46(2):200--214

2004
[21]

Shiryaev, A. N. (1963). On optimum methods in quickest detection problems. Theory of Probability and Its Applications , 8:22--46

1963
[22]

Tartakovsky, A. (2019). Sequential change detection and hypothesis testing: general non-iid stochastic models and asymptotically optimal rules . CRC Press

2019
[23]

G., Nikiforov, I

Tartakovsky, A. G., Nikiforov, I. V., and Basseville, M. (2014). Sequential Analysis: Hypothesis Testing and Change-Point Detection . Statistics. CRC Press

2014
[24]

Tartakovsky, A. G. and Veeravalli, V. V. (2005). General asymptotic Bayesian theory of quickest change detection. Theory of Probability and its Applications , 49(3):458--497

2005
[25]

V., and Meyn, S

Unnikrishnan, J., Veeravalli, V. V., and Meyn, S. P. (2011). Minimax robust quickest change detection. IEEE Transactions on Information Theory , 57(3):1604 --1614

2011
[26]

Veeravalli, V. V. and Banerjee, T. (2014). Quickest Change Detection . Academic Press Library in Signal Processing: Volume 3 -- Array and Statistical Signal Processing

2014
[27]

Woodroofe, M. (1982). Nonlinear renewal theory in sequential analysis . SIAM

1982

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Banerjee, T., Gurram, P., and Whipps, G. T. (2021). A Bayesian theory of change detection in statistically periodic random processes. IEEE Transactions on Information Theory , 67(4):2562--2580

work page 2021

[2] [2]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2012). Data-efficient quickest change detection with on--off observation control. Sequential Analysis , 31(1):40--77

work page 2012

[3] [3]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2013). Data-efficient quickest change detection in minimax settings. IEEE Transactions on Information Theory , 59(10):6917--6931

work page 2013

[4] [4]

and Veeravalli, V

Banerjee, T. and Veeravalli, V. V. (2015). Data-efficient minimax quickest change detection with composite post-change distribution. IEEE Transactions on Information Theory , 61(9):5172--5184

work page 2015

[5] [5]

Brucks, T., Banerjee, T., and Mishra, R. (2023). Modeling and quickest detection of a rapidly approaching object. To appear in Sequential Analysis

work page 2023

[6] [6]

Guo, J., Yan, H., and Zhang, C. (2023). A bayesian partially observable online change detection approach with thompson sampling. Technometrics , 65(2):179--191

work page 2023

[7] [7]

Hou, Y., Bidkhori, H., and Banerjee, T. (2024a). Robust quickest change detection in multi-stream non-stationary processes. arXiv preprint arXiv:2412.04493

work page Pith review arXiv 2024

[8] [8]

Hou, Y., Oleyaeimotlagh, Y., Mishra, R., Bidkhori, H., and Banerjee, T. (2024b). Robust quickest change detection in nonstationary processes. Sequential Analysis , 43(3):275--300

work page 2024