{"id":"74a2dc0a-5867-4ee3-8958-b0a199dcf73a","arxiv_id":"2412.20207","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"RDE-CUSUM combines robust CUSUM with on-off sampling control to detect distribution changes with unknown post-change laws while skipping a controlled fraction of observations, and is claimed asymptotically robust optimal.","lead":"The paper introduces RDE-CUSUM, a change-detection algorithm that decides when to look at data as well as when to raise an alarm, for settings where the post-change distribution is unknown. It claims the algorithm is asymptotically as good as the best possible detector while using fewer observations, and tests it on simulated and COVID-19 data.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4's proof drops a q<1 factor: Eq. (B.12) yields a delay bound divided by q, so the 1/D_KL constant in Theorem 4.5 is not established.","rationale":"The reader's central rationale identified the same load-bearing error: the delay bound is divided by a constant q < 1 that is later dropped, so the stated 1/D_KL constant is not actually derived. However, the reader's explicitly labeled weakest assumption was Assumption 1 (existence of a least favorable law), not the Appendix B algebraic gap. I agree that Assumption 1 is important for the robust reduction, but the more immediate fatal-to-the-proof issue is the q factor in Theorem 4.4. The proof of Theorem 4.5 simply uses Theorem 4.4 to match the lower bound; if Theorem 4.4 has a fixed multiplicative gap 1/q, the asymptotic optimality claim does not follow. This is not a disagreement with external consensus or a matter of unvalidated assumptions; it is an internal derivation error. The result may be repairable, and the simulations suggest practical usefulness, but as written the strongest claim is unproved. Therefore the reader's CONDITIONAL verdict remains appropriate, and no verdict adjustment is needed.","tokens_in":12957,"tokens_out":5777,"duration_ms":61425,"concrete_test":"Simulate RDE-CUSUM under the least favorable law for the Gaussian example f = N(0,1), \\bar g = N(0.5,1), with h = 10, \\mu chosen via (4.3) for \\beta = 0.5, and a large threshold, say A = 100. Estimate q defined in (B.10) by Monte Carlo as the fraction of robust CUSUM runs whose statistic never falls below zero. Compare the empirical WADD of RDE-CUSUM against A / D_KL(\\bar g \\| f) and against A / (q D_KL(\\bar g \\| f)). If the empirical delay follows the 1/q-corrected constant rather than the stated 1/D_KL constant, Theorem 4.4's bound is false as stated and Theorem 4.5 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is asymptotic robust optimality (Theorem 4.5), and its proof rests on the delay upper bound in Theorem 4.4. In Appendix B, the proof introduces q in (B.10) as a fixed positive probability, independent of A, that the robust CUSUM statistic never falls below zero under the least favorable law. It then uses the bound inf_G P_G(\\bar D_{\\lambda_A} \\ge A) \\ge q > 0 to control the expected number of below-zero cycles. The resulting inequality (B.12) is:\n\nsup_G WADD_G \\le [ E_{\\bar G}[\\tau_{rc}] + \\lceil h/\\mu \\rceil ] / q + \\lceil h/\\mu \\rceil \\le [ A / D_KL(\\bar g \\| f) (1+o(1)) + \\lceil h/\\mu \\rceil ] / q + \\lceil h/\\mu \\rceil.\n\nTo conclude Theorem 4.4's stated bound sup_G WADD_G \\le A / D_KL(\\bar g \\| f) (1+o(1)), one must drop the division by q. But q is generally strictly less than 1. For example, in the Gaussian case f = N(0,1), \\bar g = N(0.5,1), the first increment has mean 0.125 and variance 0.25, so P(Z_1 \\ge 0) < 1 and q \\le P(Z_1 \\ge 0) < 1. Dividing by q inflates the asymptotic delay constant to 1/q times 1/D_KL, which does not match the universal lower bound of Theorem 4.1. The additive \\lceil h/\\mu \\rceil terms are o(A) and are not the issue; the 1/q factor is a fixed multiplicative loss. Since q does not approach 1 as A grows, the proof as written does not establish asymptotic optimality.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13273,"tokens_out":12516,"duration_ms":137553,"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":[{"comment":"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.","section":"Appendix B, Eq. (B.12); Theorem 4.4"},{"comment":"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.","section":"Appendix B, Eqs. (B.9)-(B.10)"}],"minor_comments":[{"comment":"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.","section":"Section 6.2"},{"comment":"The caption of Figure 2 says \"Gaussian data processes (6.2)\" but the example in (6.2) is Poisson; this should be corrected.","section":"Figure captions, Section 6.1"},{"comment":"There is a typo in the index range \"max_{1≤≤n}\"; the intended range for k and the precise event should be restated clearly.","section":"Appendix B, Eq. (B.10)"},{"comment":"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.","section":"Appendix A, Eq. (A.1)"}],"recommendation":"major_revision","confidential_remarks":"The core contribution is promising, but the proof gap in Theorem 4.4 is not a minor technicality: the derived bound has the wrong asymptotic constant. I believe a careful renewal-theoretic analysis may repair the proof, but the current manuscript is not ready for publication in its present form. The heavy citation of the authors' earlier work is appropriate in this research line, and I see no concern beyond the technical correctness issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nIn 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.\n\nThere 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.\n\nThe 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.\n\nWhat 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.\n\nWho 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.","headline":"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.","tokens_in":13907,"tokens_out":7147,"would_cite":false,"duration_ms":82544,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62F35","60G40","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Sampling control matches optimal asymptotic change detection speed.","keywords":["quickest change detection","sampling control","least favorable law","robust optimality","CUSUM","pre-change duty cycle","observation cost","asymptotic optimality"],"falsifier":"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.","tokens_in":104,"feed_emoji":"📉","tokens_out":16949,"duration_ms":273226,"temperature":0.7,"pith_summary":"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.","feed_headline":"Skip half the samples, keep the optimal detection speed","feed_subtitle":"RDE-CUSUM skips half the observations yet keeps the same worst-case delay as alpha vanishes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the WADD and FAR metrics and supplies the classical CUSUM delay bounds that set the asymptotic constant.","marker":"Lorden (1971)"},{"why":"Introduces the robust CUSUM test built on a least favorable law and the stochastic-dominance lemma used to reduce worst-case bounds to $\\bar g$.","marker":"Unnikrishnan et al. (2011)"},{"why":"Gives the data-efficient CUSUM recursion and the A-independent bounds on false-alarm and pre-change duty cycle used in Theorem 4.2.","marker":"Banerjee and Veeravalli (2013)"},{"why":"Provides nonlinear renewal results used to establish finiteness of $E_\\infty[\\lambda_\\infty]$ and the Wald-lemma limit behind the simple choice of $\\mu$.","marker":"Woodroofe (1982)"},{"why":"Gives the information lower bound on worst-case delay used in Theorem 4.1.","marker":"Lai (1998)"}],"fun_headline_variants":["Skip half the observations, keep the optimal detection delay","Robust quickest detection: same delay, half the observation cost","Sampling control in CUSUM: robust, optimal, and cost-effective","Skip half the data, detect changes just as fast","Optimal change detection with fewer observations: robust CUSUM with sampling control"],"cache_read_input_tokens":15744,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Skip half the observations, keep the optimal detection delay","Robust quickest detection: same delay, half the observation cost","Sampling control in CUSUM: robust, optimal, and cost-effective","Skip half the data, detect changes just as fast","Optimal change detection with fewer observations: robust CUSUM with sampling control"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002418,"raw_usage":{"total_tokens":9272,"prompt_tokens":896,"completion_tokens":8376,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":8287}},"tokens_in":512,"tokens_out":8376,"duration_ms":61131,"temperature":1.0,"reasoning_tokens":8287,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:30:27.702642+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the WADD and FAR metrics and supplies the classical CUSUM delay bounds that set the asymptotic constant."},{"cited_title":"V., and Meyn, S","cited_arxiv_id":null,"evidence_quote":"Introduces the robust CUSUM test built on a least favorable law and the stochastic-dominance lemma used to reduce worst-case bounds to $\\bar g$."},{"cited_title":"and Veeravalli, V","cited_arxiv_id":null,"evidence_quote":"Gives the data-efficient CUSUM recursion and the A-independent bounds on false-alarm and pre-change duty cycle used in Theorem 4.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides nonlinear renewal results used to establish finiteness of $E_\\infty[\\lambda_\\infty]$ and the Wald-lemma limit behind the simple choice of $\\mu$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the information lower bound on worst-case delay used in Theorem 4.1."}],"review_version":1}