{"id":"808025eb-1d0e-4ace-b56b-7df31bf0ebcf","arxiv_id":"2504.19952","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For arbitrary composite nulls and alternatives, any power-one sequential test needs at least log(1/alpha)/KL_inf samples when alpha is small, and at least a law-of-iterated-logarithm scale when the alternative is close to the null.","lead":"This paper proves lower bounds on how many samples any sequential test needs to distinguish two general families of distributions. The bounds match the known optimal rates and are shown to be tight for several parametric and nonparametric testing problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2 invokes Lemma 3.7 under a condition the constructed sequence does not satisfy: Lemma 3.7 requires Delta_i >= alpha, while Section 3.2.1 only guarantees Delta_i >= e^{-N_i} with N_i -> infinity.","rationale":"The reader identifies the same load-bearing weakness: Lemma 3.7 is applied to a sequence whose lower bound on Delta_i is e^{-N_i}, not alpha. I checked the full proof: Lemma 3.7's condition 1 is genuinely used in its final inequality through L_i <= ln(1/alpha), and Section 3.2.1 explicitly states only Delta_i >= e^{-N_i}. Since N_i -> infinity and alpha is fixed, this is an internal inconsistency in the proof as written, not merely a missing reference. The claim that 'From Lemma 3.7, we see that the events are disjoint' is therefore unsupported. The repair is clear and plausibly short: the constructed gaps have size about (1/2) ln ln N_i plus constants, which is what the proof of Lemma 3.7 needs when L_i <= N_i; replacing ln ln ln alpha^{-1} by ln ln N_i in condition 3 should close the gap. For this reason the issue does not justify rejecting the paper's main conclusions, but it does justify a conditional verdict pending the extension. I found no other concern of comparable weight: the first lower bound (Theorem 3.1) is supported by the change-of-measure argument; Lemma 3.4-3.6 are internally consistent; the upper-bound constructions are standard e-process/mixture arguments; and the acknowledged limitation around delta_{m0} in Theorem 4.3 is stated explicitly. The manuscript's self-acknowledged gaps and the typos noted by the reader do not affect the central claim as much as the Lemma 3.7 application.","tokens_in":29544,"tokens_out":4963,"duration_ms":50905,"concrete_test":"Independently re-prove the disjointness claim for the sequence constructed in Section 3.2.1 without invoking Lemma 3.7's Delta_i >= alpha condition. Specifically, verify algebraically whether c/eps F(Delta_i) < dl / KLinf(Q_{i+1}, P) follows from L_{i+1} - L_i > (ln c_gamma + ln(1/eps) - ln dl)/2 + (1/2) ln ln N_i when Delta_i >= e^{-N_i}. If the inequality holds for every i (including the boundary case i = |S|), the proof is repairable and Theorem 3.2 stands; if it fails for some regime of N_i, the lower bound needs a different argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of the second lower bound (Theorem 3.2 / Corollary 3.3) has a genuine, though likely repairable, gap. Lemma 3.7, which establishes the disjointness of the events E(Delta_i), states as condition 1 that 1/e > Delta_1 > ... > Delta_n >= alpha > 0. This condition is used in the last display of the lemma's proof: from Delta_i >= alpha it follows that L_i = ln(1/Delta_i) <= ln(1/alpha), and hence ln ln L_i <= ln ln ln(1/alpha), which justifies the form of condition 3. However, in Section 3.2.1 the constructed decreasing sequence is only asserted to satisfy Delta_1 > ... > Delta_{|S|} >= e^{-N_i} > 0, where N_i tends to infinity while alpha is fixed. For large N_i, e^{-N_i} < alpha, so condition 1 of Lemma 3.7 fails and the bound L_i <= ln(1/alpha) is unavailable. The paper then concludes 'From Lemma 3.7, we see that the events E(Delta_i) ... are disjoint' without supplying the needed extension. The repair seems straightforward: the construction's gap condition is L_{i+1} - L_i > (ln c_gamma + ln(1/eps) - ln dl)/2 + (1/2) ln ln N_i, which is exactly what a generalized Lemma 3.7 would require when Delta_i >= e^{-N_i}, replacing ln ln ln alpha^{-1} by ln ln N_i. But this generalized lemma is neither stated nor proved, so the central lower bound of Section 3.2 rests on an unproved step as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stopping times of alpha-correct power-one sequential tests between arbitrary composite null sets P and alternative sets Q, with no reference measures or compactness assumptions. It proves two asymptotic lower bounds: Theorem 3.1 gives an instance-dependent lower bound of log(1/alpha)/KLinf(Q,P) in the regime alpha -> 0, and Theorem 3.2 with Corollary 3.3 gives a lower bound of order KLinf^{-1} log log KLinf^{-1} in the regime where the separation KLinf tends to 0 with alpha fixed. Section 4 supplies matching upper bounds through e-process and confidence-sequence constructions for several parametric and nonparametric problems, including a new analysis for testing the mean of bounded distributions. Appendices contain supporting material on KLinf and a relaxed KLinf, concentration inequalities, a meta-algorithm converting high-probability bounds to expectation bounds, and a non-asymptotic version of Theorem 3.1.","tokens_in":29864,"tokens_out":10343,"duration_ms":100182,"significance":"If the results are correct, this is a substantial contribution: it generalizes classical results of Farrell and of Robbins and Siegmund to arbitrary composite hypotheses, and it provides the first matching small-gap lower bound for nonparametric mean testing. The change-of-measure proof of Theorem 3.1 is clean, and the non-asymptotic lower bound in Theorem C.1 via Wald's identity is a useful strengthening. The sufficient condition in Theorem 4.1, together with the e-process examples in Section 4, gives a principled route to matching upper bounds. The continuity and concentration results for ~KLinf in Appendix A are of independent interest. However, two load-bearing proof issues, detailed below, currently prevent the paper from being accepted as is.","major_comments":[{"comment":"The disjointness claim used to prove Theorem 3.2 is not supported as written. Lemma 3.7 condition 1 requires 1/e > Delta_1 > ... > Delta_n >= alpha, and the lemma's proof uses this only through L_i = ln(1/Delta_i) <= ln(1/alpha), hence ln ln L_i <= ln ln ln(1/alpha). In the construction of Section 3.2.1, the thinned sequence is only shown to satisfy 1/e > Delta_1 > ... > Delta_{|S|} >= e^{-N_i}, with N_i tending to infinity while alpha is fixed. For large N_i, e^{-N_i} < alpha, so condition 1 of Lemma 3.7 fails and the bound L_i <= ln(1/alpha) is unavailable. The sentence 'From Lemma 3.7, we see that the events E(Delta_i) ... are disjoint' therefore does not follow. The repair appears straightforward: one can generalize Lemma 3.7 to lower bounds of the form Delta_i >= e^{-N}, which changes the sufficient gap condition to involve ln ln N rather than ln ln ln(1/alpha), exactly matching the quantity used in the definition of b. But this generalized lemma is neither stated nor proved, so the contradiction with Lemma 3.6, and hence Theorem 3.2 and Corollary 3.3, rest on an unproved step.","section":"Section 3.2.1 and Lemma 3.7"},{"comment":"The statement of Theorem 3.1 is false or ill-posed when KLinf(Q,P)=0, a case that the proof explicitly considers. If KLinf(Q,P)=0, the right-hand side of the display is log(1/alpha)/0 = infinity under the paper's convention, so the claim becomes Q[tau_alpha >= infinity] -> 1, i.e., Q[tau_alpha = infinity] -> 1, which is incompatible with the power-one requirement Q[tau_alpha < infinity] = 1 for every Q in Q. The proof's paragraph on the KLinf=0 case only establishes a liminf statement with a strictly positive KL(Q,P) in the denominator for some P, and since KLinf is smaller than that KL(Q,P), this does not imply the displayed liminf with KLinf in the denominator. The theorem should either assume KLinf(Q,P)>0, or treat the boundary case separately with a modified statement. In addition, the final inference from a bound involving KL(Q,P) to the same bound with KLinf requires explicitly passing to a sequence P_m with KL(Q,P_m) decreasing to KLinf; this passage is not written but is needed.","section":"Section 3.1, Theorem 3.1"}],"minor_comments":[{"comment":"There are numerous typos and spacing errors; for example, 'Raydon-Nykodim' should be 'Radon-Nikodym', and the abstract contains 'te sts' with a spurious space.","section":"Throughout"},{"comment":"In the paragraph after defining the mixture e-process En, the text says 'En satisfies the condition of Theorem 3.2' when it should say 'Theorem 4.1', since the condition being verified is the growth condition of Theorem 4.1.","section":"Section 4.2"},{"comment":"The notation nu(A, c, N) is introduced with an argument A, but then the definition and the theorem statement use nu(tau_alpha, c, N). The notation should be made consistent.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing about this paper. Theorem 3.1, the alpha-to-0 lower bound, is a clean and correct generalization of the Lai-Robbins / Kaufmann-Garivier sample-complexity bounds to completely arbitrary composite null and alternative sets, with no compactness or reference-measure assumptions. That alone is a solid contribution, and the non-asymptotic version in Theorem C.1 is a nice bonus. The second thing is that Theorem 3.2, the fixed-alpha small-gap lower bound, has a genuine gap in the proof as written: the constructed sequence only guarantees Δ_i ≥ e^{-N_i} with N_i→∞, but the paper then invokes Lemma 3.7, whose first condition requires Δ_i ≥ α. The lemma's proof uses Δ_i ≥ α to get L_i ≤ ln(1/α) and hence the ln ln ln α^{-1} spacing; without it the disjointness of the E(Δ_i) events does not follow. The fix looks straightforward—state a version of the lemma with the spacing depending on ln ln N_i instead—but as written the central lower bound of Section 3.2 is not proved.\n\nThe upper-bound side is honest and mostly solid. Theorem 4.1 gives a sufficient e-process condition for matching the first lower bound, and the examples, especially the bounded-mean test in Theorem 4.3, are genuinely new. That test achieves the KL_inf^{-1} log log KL_inf^{-1} dependence for bounded distributions, though only along sequences converging to a non-degenerate limit; the authors explicitly leave the δ_{m0} corner to future work, so the upper bound does not yet fully cover the lower bound's generality. The citation pattern is fine—the authors cite their own previous work where it is directly relevant, and the novelty claim is appropriately modest (the forms were known; the generality is new). Minor issues: a few typos and a garbled reference (Berge dated 1877). The Chen-Li monotonicity condition in Theorem B.1 did worry me for a moment, but the bound is of the form C + D log(1/α), so the ratio condition holds; that concern turns out to be minor.\n\nBottom line: the paper deserves a serious referee. I would send it out with a request to repair the Theorem 3.2 proof and state a generalized Lemma 3.7. With that patch, the central claims are likely correct, and the paper is a useful advance for anyone working on sequential tests or pure exploration.","headline":"Solid general lower bounds for power-one sequential tests, but Theorem 3.2 has a repairable proof gap that should be fixed before publication.","tokens_in":30423,"tokens_out":4117,"would_cite":true,"duration_ms":37520,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62F03","60G40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every $\\alpha$-correct power-one sequential test must take at least $\\log(1/\\alpha)/\\operatorname{KL_{inf}}(Q,\\mathcal{P})$ samples as the error level $\\alpha \\to 0$, and at least a constant times…","keywords":["sequential hypothesis testing","power-one tests","stopping times","sample complexity","Kullback-Leibler divergence","e-processes","law of the iterated logarithm","composite hypotheses"],"falsifier":"Audit the proof of Theorem 3.2 at the subsequence-selection step: Lemma 3.7 demands $\\Delta_i \\ge \\alpha$, but the constructed sequence only ensures $\\Delta_i \\ge e^{-N_i}$. If one can exhibit an $\\alpha$-correct power-one test and a sequence $Q_n$ with $\\operatorname{KL_{inf}}(Q_n,\\mathcal{P}) \\to 0$ such that $E_{Q_n}[\\tau_\\alpha]/F(\\Delta_{Q_n,\\mathcal{P}}) \\to 0$, Corollary 3.3 is false; a concrete check is whether the lemma's logarithmic gap can be re-proved with $\\ln\\ln N_i$ replacing $\\ln\\ln\\ln \\alpha^{-1}$.","tokens_in":29298,"feed_emoji":"⏱️","tokens_out":12392,"duration_ms":105945,"temperature":0.7,"pith_summary":"This paper asks how many samples an $\\alpha$-correct power-one sequential test—a stopping rule that rejects the null with probability at most $\\alpha$ under every null distribution and eventually stops under every alternative—must observe before it can reject. The answer is governed by $\\operatorname{KL_{inf}}(Q,\\mathcal{P})$, the nearest Kullback–Leibler distance from the true alternative distribution $Q$ to the null set $\\mathcal{P}$. In the small-error regime the paper proves that no test can beat $\\log(1/\\alpha)/\\operatorname{KL_{inf}}(Q,\\mathcal{P})$ samples, and in the small-separation regime it proves a law-of-the-iterated-logarithm-type lower bound of order $\\operatorname{KL_{inf}}^{-1}\\log\\log\\operatorname{KL_{inf}}^{-1}$ for most alternatives. These lower bounds hold without reference measures or compactness assumptions, and the paper exhibits e-process-based tests that match them in several parametric and nonparametric settings, including testing means of bounded distributions.","feed_headline":"Sequential tests near a null need log(1/α)/KLinf samples","feed_subtitle":"Near-separated alternatives add a log-log term: cost scales as (1/KLinf) log log(1/KLinf).","key_machinery":"The central object is the separation functional $\\operatorname{KL_{inf}}(Q,\\mathcal{P}) = \\inf_{P\\in\\mathcal{P}} \\operatorname{KL}(Q,P)$, which measures how close the alternative $Q$ sits to the null set. The lower bounds are driven by a change-of-measure argument: a short expected stopping time under $Q$ would force a type-I error under a nearby null $P$, via the data-processing inequality and Wald's identity. The upper bounds are built from e-processes, nonnegative processes that are supermartingales with initial mean at most one under every null distribution, stopped at the first time they cross $1/\\alpha$; the condition that their per-sample log-growth rate is asymptotically at least $\\operatorname{KL_{inf}}(Q,\\mathcal{P})$ makes the threshold test attain the lower bound. In the small-separation regime, a truncated version of $\\operatorname{KL_{inf}}$ for bounded distributions supplies the law-of-the-iterated-logarithm concentration used to match the $\\Delta^{-2}\\log\\log\\Delta^{-1}$ rate.","core_discovery":"The paper's central claim is that the expected stopping time of any $\\alpha$-correct power-one sequential test is governed by the same separation functional in two asymptotic regimes. For a fixed alternative $Q$, every test satisfies $\\liminf_{\\alpha\\to 0} E_Q[\\tau_\\alpha]/\\log(1/\\alpha) \\ge 1/\\operatorname{KL_{inf}}(Q,\\mathcal{P})$, with the stronger high-probability statement $Q[\\tau_\\alpha \\ge \\log(1/\\alpha)/\\operatorname{KL_{inf}}(Q,\\mathcal{P})] \\to 1$. When $\\alpha$ is fixed and the alternative approaches the null, every test must use $\\Omega(F(\\Delta_{Q,\\mathcal{P}}))$ samples for most alternatives, where $F(\\Delta)=\\Delta^{-2}\\log\\log\\Delta^{-1}$. The lower bounds require no reference measures, compactness, or parametric assumptions; matching e-process-based tests are exhibited for several composite and nonparametric problems.","pith_inferences":["The shell-counting method behind the small-separation lower bound—partitioning alternatives by dyadic intervals of $\\Delta$ and counting how many admit a fast test—could transfer to instance-dependent lower bounds in time-uniform estimation or pure-exploration bandits, though the paper does not pursue that connection.","The non-asymptotic expectation lower bound suggests that the $\\log(1/\\alpha)/\\operatorname{KL_{inf}}$ constant is exact at every fixed $\\alpha$, not only in the limit; a fully quantitative version of the small-separation bound would make Corollary 3.3 non-asymptotic.","A single e-process combining the $\\alpha$-threshold used for the upper bound with a LIL-type boundary would likely achieve both lower bounds simultaneously; the paper explicitly leaves the construction of such a test to future work."],"forward_implications":["In the small-error regime, the ratio $E_Q[\\tau_\\alpha]/\\log(1/\\alpha)$ cannot fall below $1/\\operatorname{KL_{inf}}(Q,\\mathcal{P})$ for any test, so the information-theoretic constant is fixed by the closest null distribution.","In the small-separation regime, any test trying to save samples on most near-null alternatives is doomed: at most a sparse set of alternatives can be handled faster than the $\\Delta^{-2}\\log\\log\\Delta^{-1}$ rate.","When an e-process has per-sample log-growth at least $\\operatorname{KL_{inf}}$ almost surely, the simple stopping rule “stop when the e-process exceeds $1/\\alpha$” attains the lower bound; this covers point nulls, sub-Gaussian nulls, and constraint-defined hypotheses.","For bounded-mean testing, the paper provides the first sample-complexity analysis with the correct dependence on separation, using a truncated KL divergence whose empirical version satisfies LIL-type concentration."],"supporting_citations":[{"why":"Provides the classical Gaussian and exponential-family tests and asymptotic sample-size formulas that the paper's upper bounds are designed to match.","marker":"[Robbins and Siegmund, 1974]"},{"why":"Establishes the parametric law-of-the-iterated-logarithm lower bound that Corollary 3.3 generalizes to arbitrary composite classes.","marker":"[Farrell, 1964]"},{"why":"Supplies the change-of-measure lower-bound technique used in the proof of Theorem 3.1.","marker":"[Lai and Robbins, 1985]"},{"why":"Provides the data-processing inequality lemma used in the non-asymptotic expectation lower bound of Appendix C.","marker":"[Kaufmann et al., 2016]"},{"why":"Gives the dual formulation and continuity properties of KLinf needed for the bounded-mean upper bound and the KLinf analysis.","marker":"[Honda and Takemura, 2010]"},{"why":"Supplies the time-uniform confidence sequences used to construct the matching test in Section 4.2.","marker":"[Howard et al., 2021]"},{"why":"Gives the confidence sequence for the truncated KLinf statistic that underlies Theorem 4.3.","marker":"[Orabona and Jun, 2023]"},{"why":"Provides Ville's inequality, which is the standard mechanism turning e-process thresholds into α-correct stopping rules.","marker":"[Ville, 1939]"}],"fun_headline_variants":["KLinf sets the cost for power-one sequential tests","Sequential test cost: log(1/α)/KLinf, then a log-log term","No reference measures, same KLinf stopping-time bounds","Power-one tests: tight KLinf bounds in both regimes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the nearly null alternatives used in the contradiction can be spaced far enough apart that the corresponding stopping rules act on disjoint sets of sample paths; the lemma used for this requires the distance from the null to stay above a fixed fraction of the error level, while the construction only guarantees it decays gradually to zero.","fun_headline_variants_meta":{"raw":{"variants":["KLinf sets the cost for power-one sequential tests","Sequential test cost: log(1/α)/KLinf, then a log-log term","No reference measures, same KLinf stopping-time bounds","Power-one tests: tight KLinf bounds in both regimes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001861,"raw_usage":{"total_tokens":7301,"prompt_tokens":935,"completion_tokens":6366,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":6293}},"tokens_in":551,"tokens_out":6366,"duration_ms":48052,"temperature":1.0,"reasoning_tokens":6293,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:41:07.911810+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Audit the proof of Theorem 3.2 at the subsequence-selection step: Lemma 3.7 demands $\\Delta_i \\ge \\alpha$, but the constructed sequence only ensures $\\Delta_i \\ge e^{-N_i}$. If one can exhibit an $\\alpha$-correct power-one test and a sequence $Q_n$ with $\\operatorname{KL_{inf}}(Q_n,\\mathcal{P}) \\to 0$ such that $E_{Q_n}[\\tau_\\alpha]/F(\\Delta_{Q_n,\\mathcal{P}}) \\to 0$, Corollary 3.3 is false; a concrete check is whether the lemma's logarithmic gap can be re-proved with $\\ln\\ln N_i$ replacing $\\ln\\ln\\ln \\alpha^{-1}$.","supporting_citations":[],"review_version":1}