On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds

Aaditya Ramdas; Ashwin Ram; Shubhada Agrawal

REVIEW 2 major objections 3 minor 2 cited by

On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds

T0 review · 2 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict Solid general lower bounds for power-one sequential tests, but Theorem 3.2 has a repairable proof gap that should be fixed before publication. read the letter →

arxiv 2504.19952 v2 pith:PVDENS2W submitted 2025-04-28 math.ST cs.LGstat.MLstat.TH

Shubhada Agrawal , Ashwin Ram , Aaditya Ramdas This is my paper · ORCID

classification math.STcs.LGstat.MLstat.TH MSC 62L1062F0360G40

keywords sequentialhypothesistestingpower-onetestsstoppingtimessamplecomplexityKullback-Leiblerdivergencee-processeslawoftheiteratedlogarithmcompositehypotheses

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

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.

What carries the argument

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.

What would settle it

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}$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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.

The 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.

Bottom 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.

Referee Report

2 major / 3 minor

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.

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 (2)

[Section 3.2.1 and Lemma 3.7] 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 3.1, Theorem 3.1] 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.

minor comments (3)

[Throughout] 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 4.2] 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 3.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: both lower bounds are proved from first principles, and the upper bounds use prior e-process/CS results that do not contain the paper's target lower bounds.

full rationale

The central lower bounds are derived self-containedly. Theorem 3.1 (and its non-asymptotic version Theorem C.1) starts from the definition of an alpha-correct power-one test and uses a change-of-measure argument via log-likelihood ratios, the strong law of large numbers, and data processing; no fitted parameter or target quantity is an input to the derivation. Theorem 3.2/Collary 3.3 is proved by contradiction using Lemmas 3.4-3.7, which are proved in the paper from the alpha-correctness constraint, Markov's inequality, and KL-divergence data processing; the disjointness argument is an in-paper construction, not an import of the claimed result. The upper-bound constructions do invoke prior results, including self-citations to Agrawal et al. (2020, 2021) and Agrawal (2023), but those citations are used for supporting tools such as KLinf continuity, e-process constructions, and confidence sequences; none of them states or contains the new lower bounds, so the citations are not load-bearing for the lower-bound claims. The paper's own statement that the bounds are 'unsurprising in their form' and that the contribution is generality further indicates the results are not being relabeled from prior work. One genuine issue appears in Section 3.2.1: Lemma 3.7 requires, as condition 1, Delta_1 > ... > Delta_n >= alpha > 0, while the proof constructs only Delta_i >= e^{-N_i} with N_i -> infinity; for large N_i this can violate Delta_i >= alpha, so the lemma's bound L_i <= ln(1/alpha) is not available as written. This is a correctness/proof gap, not circularity, because the missing step does not presuppose the theorem it is meant to establish; the repair indicated by the construction's gap condition would be a generalized lemma, not a recycling of the conclusion. No step in the derivation reduces a prediction to its input by construction, and no load-bearing uniqueness or ansatz is imported solely through self-citation. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central lower bounds rely on the definition of KLinf, standard change-of-measure arguments, and a counting argument. No numeric free parameters are fitted to data; the constants in Theorem 3.2 and the upper-bound tests are universal or chosen to satisfy inequalities. The main unstated support needed is a proof extension in Theorem 3.2 for alternatives with Delta_i < alpha.

assumptions (6)

domain assumption P and Q are non-intersecting sets of probability measures, with i.i.d. observations on a filtered measurable space.
Used throughout Section 2 to define alpha-correct power-one sequential tests and the KL_inf separation.
domain assumption For the small-gap regime, inf_{Q in Q} KLinf(Q,P) = 0, meaning the alternative class accumulates on the null.
This is the premise of Theorem 3.2 and Corollary 3.3, stated in Section 3.2.
standard math Wald's identity and the data-processing inequality for stopped likelihood ratios are valid for the stopping times considered.
Used in Theorem C.1 and Lemma 3.4 to relate expected stopping time to KL divergence between path measures.
standard math Ville's inequality and the supermartingale properties of test supermartingales and e-processes give alpha-correctness for the constructed tests.
Invoked in Section 2 and used to justify the upper-bound stopping rules.
domain assumption External continuity, concentration, and confidence-sequence results from Honda-Takemura, Agrawal et al., Orabona-Jun, Chen-Li, Howard et al., and Larsson et al. are imported for the upper-bound examples.
The upper-bound sections rely on these prior results, including the e-process construction in Section 4.3 and the confidence sequence in Section 4.4.
domain assumption In Section 4.4, P is assumed convex and compact in the Levy metric, and the dual constraint set Pi is compact.
These assumptions are stated in Section 4.4 to ensure nontrivial e-variables and the dual representation of KL_inf.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds." pith.science (2026). https://pith.science/paper/PVDENS2W

@misc{pith2026250419952,
  author       = {Pith},
  title        = {Pith review of: On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PVDENS2W}},
  note         = {Machine review of arXiv:2504.19952}
}

abstract

We present two general lower bounds for stopping times of sequential tests between arbitrary composite nulls $\mathcal P$ and alternatives $\mathcal Q$. The first lower bound is for the ``Wald setting'' where the type-1 error level $\alpha$ approaches zero for a fixed alternative $Q \in \mathcal Q$, and equals $\log(1/\alpha)$ divided by a certain infimum KL divergence between $\mathcal P$ and $Q$, termed $\operatorname{KL_{inf}}$. The second lower bound applies to the ``Farrell setting'', where $\alpha$ is fixed and $\operatorname{KL_{inf}}$ approaches $0$ along a sequence of alternatives such that the required expected sample size along that sequence is of order at least $\operatorname{KL^{-1}_{inf}} \log \log \operatorname{KL^{-1}_{inf}}$. Our main contribution is the generality of these bounds, which hold in non-parametric, composite settings, without requiring a dominating reference measure, substantially generalizing the known parametric results. We also provide sufficient conditions for matching upper bounds and show that these are met in several nontrivial non-parametric cases.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Confidence Horizons
stat.ME 2026-08 conditional novelty 8.0 of 10

A new family of 'asymptotic confidence horizons' provides large-sample anytime-valid coverage on bounded time windows, with closed-form boundary quantiles and connections to group sequential methods.
Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting
cs.LG 2025-02 conditional novelty 5.0 of 10

A new 'test by betting' algorithm using interior-point barrier updates over the full decision domain rejects false null hypotheses faster than Online Newton Step while preserving anytime validity.

Pith tools

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