{"id":"739b15b5-5011-4536-84d9-bf5c44ddd4ae","arxiv_id":"2602.11406","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An anytime CUSUM tracker with a logarithmically growing threshold achieves O(σ²(S+1) log T) dynamic regret for piecewise-constant mean tracking and nearly matches a new Ω(σ²(S+1) log(T/(S+1))) minimax lower bound.","lead":"This paper proves that an online algorithm called ATC can track a suddenly-shifting average (like a demand or load signal) with total squared error that grows only logarithmically in time, even without knowing how many shifts will occur. It also proves a matching lower bound, establishing that this logarithmic cost is nearly the best any tracker can achieve.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's claimed universal lower bound fails when the mean diameter M is small; the unqualified near-minimax claim needs an M >= c*sigma condition.","rationale":"The reader's weakest assumption was Lemma 3.1/Claim A.12, the SNR-degradation inequality. On close reading, this is not the most load-bearing point: App. A.4.3 bounds the deterministic bias term directly through the event H_t and the true split k=tau_j (Eqs. 50-52), obtaining Delta^2 + 4*sigma^2 gamma^2 without invoking the SNR-degradation lemma. The stochastic-deviation term is controlled by Lemma A.2's union bound. So the upper bound appears sound without Claim A.12. The genuinely load-bearing weakness is in the lower bound theorem: its 'universal' constant contradicts small-M instances, as the constant-predictor upper bound shows. This is a theorem-statement error, not a failure of the algorithm: the upper bound still holds, and the lower bound is valid in the standard fixed-M asymptotic regime once M>=c*sigma is imposed. The appendix itself flags the M>c*sigma assumption, so the fix is narrow. Because the paper's central 'nearly minimax-optimal' claim is unqualified in the abstract, the theorem should be corrected; this supports the reader's CONDITIONAL verdict rather than changing it.","tokens_in":35945,"tokens_out":28984,"duration_ms":288610,"concrete_test":"Verify the small-M failure directly: set sigma=1, S=1, T=10^6, M=10^-3 and compare the constant predictor mu_hat_t=0 against the claimed lower bound. The constant predictor has worst-case regret <= T M^2/4 = 0.25, while Theorem 4.2 would require at least c*2*(1+log(10^6/2)) ~ 28.2 c. For any universal c>0.009 this is contradicted. More generally, compute the single-segment minimax cumulative squared error for bounded mean mu in [-M/2,M/2] via the Bayes-van Trees sum sigma^2 * sum_{t=1}^T 1/(t-1+4*pi^2*sigma^2/M^2); check that for M=sigma/sqrt(T) this is O(1) while sigma^2 log T = Theta(log T), showing the claimed 'for all T' lower bound cannot hold without an explicit lower bound on M (or T >= sigma^2/M^2).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.2 asserts a universal constant c>0 such that for every T>=3, every 1<=S<=T, and every M, R*_T(E) >= c sigma^2 (S+1)(1+log(T/(S+1))). This is false as stated for small M. Take S=1, sigma fixed, M=sigma/sqrt(T). The class E contains only means in [-M/2, M/2]; the policy that always predicts 0 achieves worst-case squared error at most M^2/4 per step, hence R*_T <= T M^2/4 = sigma^2/4. For large T, the claimed lower bound is c sigma^2(1+log(T/2)), which exceeds sigma^2/4 for any fixed c>0. So no universal c can exist. The appendix half-acknowledges the issue: App. A.5 says 'we assume M > c*sigma when deriving the variance lower bound', and Lemma A.10's van Trees prior has Fisher information 4*pi^2/M^2, so the variance lower-bound constant shrinks like (M/sigma)^2 when M << sigma. The theorem statement omits this assumption; the abstract's unqualified 'nearly minimax-optimal' therefore overstates the result. The upper bound (Thm 4.1) is unaffected; the lower bound needs either an explicit M>=c*sigma condition or a min(T M^2, sigma^2 log T) correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online tracking of a piecewise-constant mean with S change points under sub-Gaussian noise, without knowledge of the horizon T or the number of changes S. It proposes the Anytime Tracking CUSUM (ATC) algorithm, which uses a time-varying CUSUM threshold and a selective detection principle. The main theoretical claims are: (i) an upper bound R_ATC ≤ C_V σ²(S+1+α)(1+log T) + C_B σ² S log(T/α) + M²(α+S) (Theorem 4.1); and (ii) a lower bound R*_T(E) ≥ c σ²(S+1)(1+log(T/(S+1))) for a universal constant c (Theorem 4.2), giving a near-minimax characterization. The analysis introduces the notion of endogenous confounding caused by missed detections and quantifies it via an SNR-degradation lemma (Lemma 3.1). Experiments on synthetic data and the NAB benchmark are reported.","tokens_in":36200,"tokens_out":15426,"duration_ms":154311,"significance":"If correct, the paper would provide the first horizon-free, minimax near-optimal algorithm for multiple change-point tracking without any detectability or spacing assumptions, and would quantify the fundamental cost of missed detections. The upper-bound proof is detailed and appears internally consistent, with a plausible variance/bias decomposition and union-bound concentration. The lower-bound construction is also novel and mostly convincing. However, the unqualified minimax claim is marred by the small-M issue identified below; the lower bound requires a separation condition on the mean diameter M that is absent from the theorem statement and abstract. The algorithmic contribution and the upper-bound analysis remain valuable, and the flaw appears fixable by amending the statement to include M ≥ cσ or by refining the lower bound.","major_comments":[{"comment":"The theorem asserts a universal constant c>0 for all T≥3, 1≤S≤T, and every M. This is false when M is small. Take S=1 and M=σ/√T. The policy that always predicts 0 has worst-case squared error at most T·M²/4 = σ²/4, while the claimed lower bound is cσ²(1+log(T/2)), which exceeds σ²/4 for any fixed c>0 once T is large. The appendix implicitly acknowledges this: App. A.5.3 states \"we assume M > cσ when deriving the variance lower bound\", and Lemma A.10's van Trees prior gives a bound that degrades when M≪σ. The theorem statement must include an explicit M ≥ cσ condition (with c at least 2 to cover the bias construction in App. A.5.1, which uses Δ=2σ), or the lower bound must be corrected to include a min(T·M², σ² log T) term. Without this, the \"nearly minimax-optimal\" claim is unsupported for small-M environments.","section":"§4.2, Theorem 4.2"},{"comment":"The proof of the bias lower bound restricts to a subclass with Δ=2σ (μ0=0, μ1=2σ) and claims this is without loss because restricting to any subclass only decreases the supremum. This is only valid if the subclass is contained in E_{S,T}(σ²,M); when M<2σ, that hard instance is outside the class, so the lower bound does not apply. The same issue affects the multi-block extension in Lemma A.9. The final theorem therefore requires the stated M ≥ cσ condition, or a separate argument for small M.","section":"App. A.5.1, Remark A.8"},{"comment":"Lemma 3.1 as stated says \"Under the ATC algorithm\" without qualification, but the proof (App. A.6, Step 2) assumes that ATC raises no alarm on the interval (r, τ_j]. As written, the lemma is broader than the proven statement. In addition, the additive M² term in Eq. (14) is dimensionally inconsistent: the left side is a dimensionless SNR difference, while M² has units of squared mean. The proof normalizes σ=1 and derives the bound without any M² term. Although the upper-bound proof in Lemma A.3 does not rely on this lemma directly (footnote 7 says so), the misstatement should be corrected for clarity and to avoid a false impression of the lemma's scope.","section":"Lemma 3.1 / App. A.6"}],"minor_comments":[{"comment":"In the problem formulation, \"variance proxy σ21\" should read σ².","section":"§2"},{"comment":"The abstract and the discussion in §4.3 claim a regret of O(σ²(S+1)log T), but Theorem 4.1 also has the term M²(α+S). This is fine when M is a fixed constant, but the manuscript should clarify that the O(·) statement assumes M is constant (independent of T,S).","section":"§4.1 / Thm 4.1"},{"comment":"The sensitivity experiment shows that when σ is underestimated by a factor of 2, ATC diverges due to excessive false alarms. This is a useful caveat; the main text says ATC \"only requires knowledge of the sub-Gaussian proxy σ\" without mentioning this fragility. A sentence acknowledging the misspecification sensitivity would strengthen the presentation.","section":"App. A.1.5"},{"comment":"As noted in the major comments, the M² term in Lemma 3.1 seems spurious. If intended as a universal bound under alarms, it needs a proof; otherwise it should be deleted or replaced with (M/σ)² if a dimensionless quantity is desired.","section":"§3.3 / Eq. (14)"},{"comment":"The informal bound R(t) ≤ min{aΔ², σ²(γ_t^r)²} is stated without derivation. While it is illustrative, it would be helpful to state that this is an informal heuristic and not a formal inequality for the cumulative regret up to time t.","section":"App. A.1.6"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a substantial contribution and the upper-bound proof appears sound. The main obstacle is the small-M gap in Theorem 4.2: the theorem as stated is false, and the needed condition (M ≥ cσ) is only implicit in an appendix remark. This is fixable by amending the theorem and abstract, or by adding a refined lower bound. The other concerns are local. I recommend major revision, not rejection, because the central algorithmic idea and the upper-bound analysis are likely correct and the flaw is a statement-level issue rather than a fundamental flaw in the method."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a real contribution: an anytime CUSUM-style algorithm (ATC) that tracks a piecewise-constant mean with regret O(σ²(S+1) log T), knowing neither T nor S, plus a genuine lower-bound attempt. The ingredients are mostly standard — GLR scan statistics, time-varying thresholds, van Trees — but the SNR-degradation inequality (Lemma 3.1 / Claim A.12) that controls cascading missed detections is the genuinely new idea, and the upper-bound proof is carefully structured. I checked the union-bound threshold and the bias/variance decomposition; they close.\n\nThe soft spots, in proportion: the biggest one is the lower-bound theorem. As stated, Theorem 4.2 asserts a universal constant for all M, and that is false. With M = σ/√T and S = 1, the policy that always predicts 0 has regret at most σ²/4, while the claimed bound is cσ² log T. The appendix does say \"we assume M > cσ\" when deriving the variance lower bound, but the theorem statement and the abstract don't. That overstates the near-minimax claim. It is fixable — add the condition or use min(TM², σ² log T) — but it is not cosmetic, since the paper's headline is optimality.\n\nNext, the extension of Lemma 3.1 to arbitrary missed-detection prefixes is the most delicate step. The two-change proof is clean, but the general case compresses the entire prefix into an aggregate mean, which is exact only for the aligned split; the paper itself concedes other splits can dominate. I would not call it a fatal gap, but I would want a more careful treatment before fully trusting the S-dependent bias bound.\n\nMinor: code is promised but not shipped; the NAB evaluation is a stress test with hand-labeled change points and offline-tuned σ, not an independent benchmark; the L1 lower bound is \"details omitted.\" The log(S) gap between upper and lower bounds is honestly acknowledged — a limitation, not a flaw.\n\nBottom line: a serious referee should see this. The upper bound and the algorithm are worth engaging with, and the lower bound is likely repairable. This deserves peer review and revision, not a desk reject.","headline":"Solid upper-bound analysis and a genuinely new SNR-degradation lemma, but Theorem 4.2's minimax claim is overstated because the lower bound silently assumes M ≥ cσ.","tokens_in":36831,"tokens_out":2711,"would_cite":true,"duration_ms":29472,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62C20","62G05","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Near-minimax tracking of a changing mean is achievable without knowing the horizon or number of changes.","keywords":["online learning","change point detection","dynamic regret","CUSUM","minimax lower bound","non-stationary environments","sequential detection","piecewise stationary"],"falsifier":"Run ATC on a three-segment Gaussian environment with segment lengths (n0, n1, n2) = (1000, 10, 100) and means (0, 0.1, 1), so that the first change is just below the detection threshold and is missed; then measure the effective SNR for the second change over time. If the SNR loss (SNR⋆_2 − SNR^eff_2) ever exceeds the SNR of the missed first change evaluated at τ2, Lemma 3.1 is violated, and the O(σ²S log T) bound would not hold in that regime. A less algorithmic test: directly compute the two SNRs from the formulas in Claim A.12 with these parameters.","tokens_in":35631,"feed_emoji":"🎯","tokens_out":7300,"duration_ms":70113,"temperature":0.7,"pith_summary":"Classical change-point detectors that aim to identify every shift with high confidence can fail catastrophically in environments with multiple changes: a missed change contaminates the reference distribution, making it harder to detect the next change, and this contamination cascades. The paper attributes this to a phenomenon it calls endogenous confounding and argues that attempting to detect every change is neither necessary nor desirable. It proposes Anytime Tracking CUSUM (ATC), a horizon-free algorithm that uses a time-varying threshold to ignore small or short-lived shifts while reacting quickly to large ones. The main result is that ATC's expected cumulative squared error is O(σ²(S+1) log T) for any piecewise-stationary sub-Gaussian environment with S changes, and a matching lower bound shows every algorithm must incur Ω(σ²(S+1) log(T/(S+1))) regret. Hence ATC is nearly minimax optimal up to a log(S) gap, and the unavoidable worst-case cost of S changes is Θ(σ²S log(T/S)).","feed_headline":"Each change point adds only a logarithmic regret cost","feed_subtitle":"A CUSUM-style algorithm achieves near-optimal tracking without knowing the horizon or the number of shifts.","key_machinery":"The central object is the ATC detection statistic, a CUSUM-style scan over split points whose threshold grows logarithmically with time since the last restart. The mechanism that carries the argument is the SNR-degradation bound: after a missed change, the loss in detection signal-to-noise ratio for the next change is bounded by the signal-to-noise ratio of the missed change itself (Lemma 3.1, with the two-change algebraic identity in Claim A.12). This caps the cascading 'endogenous confounding' effect at a logarithmic scale, which is what converts the bias term from a potential linear cost into O(σ²S log T).","core_discovery":"The paper's central claim is that the minimax dynamic regret for online tracking of a piecewise-constant mean with S changes is Θ(σ²S log(T/S)) (up to lower-order terms), and that this rate is achievable by a specific anytime algorithm, ATC, that does not know T or S. The proof relies on a novel bound on the degradation of detection signal-to-noise ratio after missed detections: the loss in SNR for a change is at most the SNR of the most recently missed change. This quantization of the confounding effect leads to a logarithmic bias term and establishes that missed detections are analytically benign if the detector's threshold grows logarithmically. The lower bound formalizes the intuition th","pith_inferences":["The log(S) gap between the upper and lower bounds is likely closable by a horizon-aware algorithm that restarts on a fixed schedule of T/(S+1) rounds, as the authors conjecture; constructing such an algorithm and proving the matching O(σ²S log(T/S)) bound would tighten the result.","The SNR-degradation principle may transfer to other sequential decision problems, such as bandits with switching or online compression, where a missed change contaminates a reference statistic; a testable extension is to check whether analogous logarithmic bounds hold under different losses (the paper notes L1 leads to Ω(√(ST))).","The appendix's observation that an underestimated variance proxy σ causes false alarms to diverge suggests a practical research direction: designing an adaptive, data-driven σ calibration to make ATC robust to misspecification, with the goal of preserving the logarithmic guarantee.","The moving-boundary analysis in the adversarial experiments hints at a sharp characterization of the hardest instances: shifts with magnitude Δ ≈ σ √(log a / a) where a is the segment length. A formal minimax analysis around this boundary could yield tighter constants."],"forward_implications":["ATC achieves near-minimax regret without knowing the horizon T or the number of changes S, and without any detectability or spacing assumptions.","The lower bound identifies the unavoidable cost of non-stationarity: each of the S changes contributes a logarithmic factor to the worst-case regret.","Sublinear regret is achievable for any vanishing density of changes (S = o(T)); when S is proportional to T, regret becomes linear, as expected.","The results imply that selective detection—deliberately missing small or brief shifts—is not just a heuristic but a principled strategy for online tracking.","In practice, the algorithm's only required inputs are the noise proxy σ and an error budget α, making it a ready-to-use anytime method."],"fun_headline_variants":["Multiple change points? ATC logs only logarithmic regret","New algorithm achieves near-optimal regret under many shifts","Anytime CUSUM tracker keeps regret near-optimal without horizon","Each change point costs only logarithmic regret","Robust to multiple change points: near-optimal regret"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof depends on the inequality that after a missed change, the detection signal-to-noise ratio for the following change degrades by no more than the signal of the missed change itself; if that inequality fails in some multi-change path, the logarithmic regret guarantee breaks.","fun_headline_variants_meta":{"raw":{"variants":["Multiple change points? ATC logs only logarithmic regret","New algorithm achieves near-optimal regret under many shifts","Anytime CUSUM tracker keeps regret near-optimal without horizon","Each change point costs only logarithmic regret","Robust to multiple change points: near-optimal regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2721,"prompt_tokens":691,"completion_tokens":2030,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":435,"completion_tokens_details":{"reasoning_tokens":1952}},"tokens_in":435,"tokens_out":2030,"duration_ms":14244,"temperature":1.0,"reasoning_tokens":1952,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T00:11:50.077509+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run ATC on a three-segment Gaussian environment with segment lengths (n0, n1, n2) = (1000, 10, 100) and means (0, 0.1, 1), so that the first change is just below the detection threshold and is missed; then measure the effective SNR for the second change over time. If the SNR loss (SNR⋆_2 − SNR^eff_2) ever exceeds the SNR of the missed first change evaluated at τ2, Lemma 3.1 is violated, and the O(σ²S log T) bound would not hold in that regime. A less algorithmic test: directly compute the two SNRs from the formulas in Claim A.12 with these parameters.","supporting_citations":[],"review_version":1}