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

arXiv:2504.19952 · math.ST, cs.LG, stat.ML, stat.TH · Submitted 2026-08-17 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds".

Jane: The paper was written by Shubhada Agrawal, Ashwin Ram and Aaditya Ramdas from Indian Institute of Science and Carnegie Mellon University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back to the channel, everyone. Today we're digging into a fresh arXiv paper called "On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds," from Shubhada Agrawal at IISc and Aaditya Ramdas at Carnegie Mellon.

Jane: And Tom, I have to say, the title alone tells you we're in for something pretty fundamental. "Power-one sequential tests" — that's the idea that when the alternative hypothesis is true, you're guaranteed to eventually stop and reject the null. You never miss it.

Tom: Right, and the "stopping time" is just how long you have to wait before you're confident enough to make that call. The paper is asking a really basic question: how many samples do you need, at minimum, before you can stop?

Jane: Exactly. And what I love about this work is that they're not assuming the distributions are nice and simple. They're not saying "assume everything is Gaussian" or "assume the data fits some clean parametric family." They're proving lower bounds that hold for basically any null and alternative sets you can think of.

Tom: That's the part that got me excited. I mean, we've known for decades that Wald's sequential probability ratio test is optimal for simple-vs-simple testing. But once you go composite — where the null or alternative contains many distributions — things get murky. This paper clears a lot of that murk.

Jane: And they do it in two different regimes. One is when your error probability α gets tiny, and the other is when the alternative gets really close to the null. Both are practically important, and both get tight bounds here.

Tom: I want to bring in Lu from Tsinghua, because I know you've been thinking about the implications of these bounds for the broader statistics community.

Lu: Thanks, Tom. I think the most striking thing is the generality. The authors prove these lower bounds without any distributional assumptions — no reference measures, no compactness conditions, nothing. That's rare in this literature. Most prior work needed some structure to even state the problem cleanly.

Jane: And the bounds themselves — they involve this quantity they call KLinf, which is the infimum of KL divergences between your alternative distribution and the null set. It's a natural measure of how hard the testing problem is for that particular alternative.

Tom: So if KLinf is small, the alternative is close to the null, and you need more samples. If it's large, you can stop quickly. That's intuitive.

Lu: Exactly. And the first lower bound says the expected sample size has to grow at least like log(one/α) divided by KLinf. The second one, for the small-gap regime, gives you a log-log correction that's reminiscent of the law of the iterated logarithm.

Jane: That second bound is the one that surprised me, honestly. It says that when the alternative approaches the null, you need roughly KLinf−1 log log(KLinf−1) samples. That log-log factor is the difference between a good test and a great test.

Tom: And the authors don't just prove lower bounds — they show matching upper bounds for a bunch of concrete problems. That's what makes this a complete story. We'll get into those details in a moment.

Jane: Before we do, let me just say: this paper feels like it's filling a real gap. There's been a lot of work on sequential testing in specific settings, but having a unified theory that covers everything from Gaussian means to bounded distributions to general constraint-based hypotheses — that's a big deal.

Lu: It really is. And I think the fact that the bounds are instance-dependent, not just worst-case, makes them much more useful for practitioners who want to know how long their experiment will take for their specific situation.

Tom: Great setup. Let's dig into the actual results next.

Summary of Results: Tom: So we've established the setup — power-one sequential tests, stopping times, and this KLinf quantity that measures problem hardness. Now let's talk about what the paper actually proves.

Jane: Right. The first main theorem is a lower bound that holds in the regime where the error probability α goes to zero. It says that for any α-correct power-one test, the stopping time has to satisfy a liminf bound: the probability that you stop before log(one/α) divided by KLinf goes to zero.

Tom: In plain English: you can't stop too early when the error bar is tiny. The bound on the expected sample size is exactly log(one/α) divided by KLinf. And that's tight — they show matching upper bounds for a wide range of problems.

Lu: What I find elegant is the proof technique. It's a change-of-measure argument, similar to what you see in the multi-armed bandit literature. You compare what happens under the alternative Q with what happens under a null distribution P that's close to Q. If the test stops too early under Q, then under P it would also stop early with probability at least something — and that violates α-correctness.

Jane: And the second theorem is the one for the small-gap regime. Here α is fixed, but you let the alternative approach the null. The bound involves this F(Δ) function, which is essentially (one/Δ2) log log(one/Δ2) where Δ2 is KLinf.

Tom: So the sample complexity blows up as the gap shrinks — but the blow-up has that extra log-log factor. That's the law-of-the-iterated-logarithm flavor I mentioned earlier.

Jane: And the theorem is stated in a slightly unusual way. It's not "for every test, there exists a hard instance." It's stronger: for any test, the number of intervals of Δ values where the test performs well is sub-polynomial. So most alternatives that are close to the null will be hard for any test.

Lu: That's a really nice way to state it, actually. It avoids the problem of "there exists a bad instance" which might be a measure-zero set. Instead, it says the bad instances are dense — you can't escape them by picking a clever test.

Tom: And then they prove tightness. For the α→zero regime, they give a general sufficient condition: if you have an e-process whose log-growth rate is at least KLinf almost surely, then the stopping time achieves the lower bound. That's Theorem four point one.

Jane: And they show this condition is met in several cases. For point-vs-point testing, the likelihood ratio works. For the one-sided sub-Gaussian null with a Gaussian alternative, the numeraire e-variable works. For the composite Gaussian alternative, a mixture e-process works.

Tom: Then there's the nonparametric case — testing the mean of bounded distributions. That's Theorem four point three, and it's where things get really interesting because the analysis is delicate.

Jane: I want to bring in Meng here, because I know you're always asking about whether these theoretical bounds actually translate into algorithms people can run.

Meng: Yeah, that's exactly my question. The paper gives these beautiful lower bounds, but for the bounded-mean case, they use a specific sequential test based on a confidence sequence. How practical is that?

Lu: Actually, the test they analyze is quite practical. It's based on a confidence sequence for the mean, which you can compute online. The stopping rule is simply: stop when the confidence interval excludes the null mean. That's something you can implement in a few lines of code.

Meng: And the sample complexity bound — they show it matches the lower bound up to constants, right? Along sequences where the alternative converges to a non-degenerate distribution.

Jane: Yes, with a caveat. They handle the case where the limit distribution has positive variance. The degenerate case, where the alternative converges to a point mass at the null mean, is left open. They mention it in Remark three.

Tom: So there's a gap there — but it's a narrow one, and the tools they develop for the non-degenerate case are already quite substantial. Let's talk about those tools next.

Improvements and Techniques: Tom: We're back, and I want to focus on what this paper adds to the toolbox. Because beyond the bounds themselves, there are some genuinely useful technical contributions here.

Jane: Absolutely. The appendix is where the real depth is. They develop a whole set of properties for this modified KLinf function, which they call KL-inf-hat. It's a version of the KL divergence where the dual variable λ is restricted to a bounded interval.

Lu: That restriction is what makes it tractable for nonparametric problems. The usual KLinf for bounded distributions can have optimizers that blow up — the λ can go to infinity. By restricting λ to-one one, you get a function that's continuous in the distribution, with a unique optimizer, and that satisfies nice concentration inequalities.

Meng: And that's what you need for the sequential test, right? You need the empirical version of KLinf to concentrate around the true value quickly enough.

Jane: Exactly. They prove a one-time concentration bound in Lemma A.three and then they bootstrap it into a time-uniform bound using the Duchi-Haque estimator. That's the key to getting the log-log factor in the sample complexity.

Tom: And there's also the continuity result — Lemma A.one — which shows that both KL-inf-hat and its optimizer are continuous functions of the distribution, as long as the mean is strictly below the threshold. That's not obvious, and it requires some careful analysis.

Lu: The subtlety is at the boundary. If the distribution is exactly a point mass at the threshold, the optimizer is not unique — it's the whole interval-one one. So you get continuity on the open set but not on the closed set. They handle that carefully in Remark four.

Meng: So for a practitioner, what does this mean? If I'm testing whether the mean of a bounded distribution is below some threshold, I can use this KL-inf-hat statistic, and the theory tells me exactly how many samples I need.

Jane: And not just for the mean — the last section generalizes to hypotheses defined by finitely many constraints. You can test quantiles, tail risks, all sorts of things, as long as the constraints define a convex, compact null set.

Tom: The e-variable representation there is beautiful. They show that admissible e-variables are exactly linear combinations of the constraint functions, with coefficients chosen to keep the variable nonnegative. Then a mixture over all such coefficients gives you an e-process that achieves the lower bound.

Lu: That's a very clean connection between optimization duality and sequential testing. The dual of the KLinf problem gives you the e-variables, and the primal gives you the hard distributions. It's the same kind of duality you see in information theory.

Meng: And the practical upshot is that you can design optimal tests for a huge class of problems without having to reinvent the wheel each time. The framework is general enough that you just plug in your constraints.

Jane: One thing I appreciate is that they're honest about what's not covered. The degenerate case for the bounded-mean problem is left open. And they don't have a single test that's simultaneously optimal in both regimes — they use different tests for the α→zero regime and the small-gap regime.

Tom: That's a natural direction for future work, and they say so explicitly. Finding a unified test that achieves both bounds would be the next big step.

Lu: I'd also love to see extensions to non-i.i.d. data — martingales, Markov chains, that sort of thing. The current framework is i.i.d., but the e-process machinery is quite flexible.

Meng: And I'm curious about the computational side. For the constraint-based hypotheses, you need to compute a mixture over the parameter space Π. If that space is high-dimensional, the integral might be expensive.

Jane: Good point. But for many practical cases, Π is low-dimensional or has special structure. And you could always use Monte Carlo approximations.

Tom: Alright, let's start wrapping up. We've covered a lot of ground.

Conclusion: Tom: So let's pull it all together. "On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds" gives us a unified theory for how long sequential tests need to run, in two important regimes.

Jane: The first regime is when you want very small error probabilities. The bound is log(one/α) divided by KLinf, and it's tight across a huge range of problems — from simple Gaussian tests to nonparametric mean testing to general constraint-based hypotheses.

Tom: The second regime is when the alternative gets close to the null. There you need KLinf−1 log log(KLinf−1) samples, and again they show this is tight for several important cases.

Lu: The technical contributions are substantial — the continuity properties of the modified KLinf, the concentration inequalities, the time-uniform bounds. These will be useful beyond this paper, I think.

Meng: And the practical message is clear: if you're designing a sequential test, you now have a benchmark. You know what's achievable, and you know when your test is leaving performance on the table.

Jane: I also appreciate that the paper is careful about what it doesn't prove. The degenerate case is left open, and the question of a single test that's optimal in both regimes remains. That's honest science.

Tom: For the field, I think this is going to be a reference point. Anyone working on sequential testing, confidence sequences, or even bandit algorithms will want to know these bounds.

Lu: Absolutely. And I'd bet the techniques — especially the e-process framework and the KLinf duality — will find applications in online decision-making, A/B testing, and any setting where you need to stop early with guarantees.

Meng: From an engineering standpoint, the fact that these tests are implementable with a few lines of code makes the theory immediately actionable. That's rare in this literature.

Jane: So we're saying goodbye to this paper, but I suspect we'll be citing it for a long time. It's a clean, general, and useful piece of work.

Tom: Thanks to Shubhada Agrawal and Aaditya Ramdas for this contribution. And thanks to all of you for listening. Next up, we'll be looking at a paper on time-uniform estimation — should be a nice follow-up to today's discussion.

Jane: Until then, keep testing, and remember: the right stopping time makes all the difference. See you next time.

Shubhada Agrawal, Ashwin Ram, Aaditya Ramdas

Indian Institute of Science · Carnegie Mellon University

math.ST, cs.LG, stat.ML, stat.TH

Submitted: 2026-08-17

Updated: 2026-08-18

Comments: 36 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 77/100

The gist: The paper studies the problem of sequential hypothesis testing with power-one (one-sided) tests.

Key concepts

Power-one sequential tests: These are tests where, if the alternative hypothesis is true, you are guaranteed to eventually stop and reject the null hypothesis. The stopping time refers to how long you wait before making this decision.
KLinf: This quantity measures how hard a testing problem is for a particular alternative. It is defined as the infimum of KL divergences between the alternative distribution and the null set, indicating how much data is needed to distinguish them.
Small-gap regime: This regime occurs when the alternative hypothesis approaches the null hypothesis. In this situation, sample complexity increases significantly, requiring a log-log correction factor in the required number of samples.

Terminology

Sample Complexity — 32× in this paper · explained in 15 episodes
Regret — 6× in this paper · explained in 3 episodes
Generalization — 5× in this paper · explained in 13 episodes
alpha — 3× in this paper · explained in 1 episode
Strong Law of Large Numbers — 2× in this paper
Benchmark — 1× in this paper · explained in 2 episodes
Exchangeability — 1× in this paper · explained in 2 episodes
Robustness — 1× in this paper · explained in 5 episodes

Summary

The paper studies the problem of sequential hypothesis testing with power-one (one-sided) tests. Given two non-intersecting sets of probability distributions P (null) and Q (alternative), and observing i.i.d. data X1, X2,..., the goal is to test P against Q. An α-correct power-one sequential test is a stopping time τα satisfying:

P[τα < ∞] ≤ α for all P ∈ P (α-correctness)
Q[τα < ∞] = 1 for all Q ∈ Q (power-one)

The paper focuses on deriving tight lower bounds on τα and EQ[τα] (the expected sample complexity), and demonstrating tightness via matching upper bounds.

For Q ∈ Q and α ∈ (0, 1), the stopping time τα of any α-correct power-one sequential test satisfies:

lim inf α→0 Q[τα ≥ log(1/α)/KLinf(Q, P)] = 1,

and hence,

lim inf α→0 EQ[τα]/log(1/α) ≥ 1/KLinf(Q, P),

where KLinf(Q, P):= inf P∈P KL(Q, P).

The paper also provides a non-asymptotic version in Theorem C.1: EQ[τα] ≥ log(1/α)/KLinf(Q, P) for any α > 0.

For P and Q such that inf Q∈Q KLinf(Q, P) = 0, α ∈ (0, 0.5), and γ > 0, there exists a constant cγ such that:

lim N→∞ sup τα ν(τα, cγ, N)/N γ = 0,

where ν(τα, c, N) counts the number of intervals [e-i, e-i+1) containing a distribution Q ∈ Q with EQ[τα(ΔQ,P)] < cF(ΔQ,P), and F(Δ):= (1/2) log(1/Δ) log log(1/Δ).

Corollary 3.3 states that any α-correct power-one sequential test satisfies:

lim sup Q:ΔQ,P→0 EQ[τα]/F(ΔQ,P) > 0.

This shows the sample complexity is Ω(KLinf(Q,P)-1 log log KLinf(Q,P)-1) in this regime.

The paper proves that if there exists an e-process En for P such that for all Q ∈ Q:

lim inf n→∞ (1/n) log En ≥ KLinf(Q, P) Q-a.s.,

then the stopping time τα = min n: En ≥ 1/α satisfies:

Q[lim sup α→0 τα/log(1/α) ≤ 1/KLinf(Q, P)] = 1.

For measures Q, P with KL(Q, P) < ∞, the likelihood ratio e-process achieves the lower bound.

For P = P: EP[e θX-θ2/2] ≤ 1, ∀θ ≥ 0 (one-sided 1-sub-Gaussian distributions) and Q = N(m, 1) with m > 0, the numeraire e-variable E* Q(X):= e mX-m2/2 yields KLinf(Q, P) = m2/2, and the corresponding test matches the lower bound.

For the same null P and Q = N(m, 1): m > 0, a mixture e-process achieves the lower bound in the α → 0 regime. A separate test based on confidence sequences achieves the lower bound in the KLinf → 0 regime.

For P = P ∈ P[0,1]: mP = m0 and Q = Q ∈ P[0,1]: mQ < m0, the paper presents two tests. Theorem 4.3 proves that for any sequence Qn ∈ Q converging to Q∞ ∈ P with Var[Q∞] > 0 and KLinf(Qn, P) → 0:

lim sup n→∞ EQn[τ̃α]/(KLinf(Qn, P)-1 log log KLinf(Qn, P)-1) ≤ c

for some constant c > 0.

For null and alternative generated by constraint functions φ1,..., φK:

P = P: max i EP[φ i(X)] < ∞, max i∈[K-1] EP[φ i(X)] ≤ 0, EP[φ K(X)] = 0,

Q = Q: max i EQ[φ i(X)] < ∞, max i∈[K-1] EQ[φ i(X)] ≤ 0, EQ[φ K(X)] < 0,

the paper shows that a mixture e-process over admissible e-variables achieves the lower bound in the α → 0 regime.

E-variables and e-processes: The paper uses test supermartingales and e-processes for constructing α-correct sequential tests.
KLinf as separation measure: The infimum KL divergence between Q and P characterizes the hardness of the testing problem.
Change-of-measure arguments: Lower bounds use data processing inequality and change-of-measure techniques.
Lemma 3.4: Relates probabilities of events under two measures via KL divergence and expected stopping time.
Lemma 3.5: Shows that for appropriate constants, Q[E(ΔQ,P)] ≥ 0.5 for the event E(ΔQ,P) = τα < ∞ ∩ d l/KLinf(Q,P) ≤ τα < (1/ε)EQ[τα].
Lemma 3.6: Provides a key inequality for sequences of alternative distributions with disjoint events.
Lemma 3.7: Gives sufficient conditions for disjointness of events E(Δi).

The paper includes an appendix with:

Properties of KL̂inf for bounded distributions (Lemma A.1, A.2)
Concentration inequalities for empirical KL̂inf (Lemmas A.3, A.4)
Asymptotic expansions (Proposition A.5)
Time-uniform concentration via Duchi-Haque estimator (Lemma A.7)
A meta-algorithm converting high-probability bounds to expectation bounds (Theorem B.1)
Non-asymptotic lower bound proof (Theorem C.1)
Technical lemma for bounding stopping times (Lemma D.1)

The paper establishes tight lower bounds on expected sample complexity for any α-correct power-one sequential test in two regimes, without any distributional assumptions on P or Q. The bounds are shown to be tight for various parametric and nonparametric problems. The paper notes that two different sequential tests are used to achieve the two lower bounds for a given null and alternative, and identifies as future work the design of a single test optimal in both regimes.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems, particularly in sequential decision-making, hypothesis testing, and online learning:

Improvement: Implement the paper's lower bounds to determine the minimum number of observations required before an AI system can reliably detect distribution shift or model degradation at a given confidence level.
Specific capability: An AI monitoring system can now compute a theoretical lower bound on detection time using KLinf(Q, P) (the KL divergence between the shifted distribution and the training distribution). This prevents premature or overly conservative decisions—the system knows it cannot reliably detect a shift before this bound, so it avoids false alarms while also knowing when waiting longer is futile.
Improvement: Use Theorem 3.2's lower bound to design AI systems that automatically adjust sample sizes when the alternative hypothesis is not a single point but a family of distributions.
Specific capability: In A/B testing or reinforcement learning, when the effect size is unknown and potentially small, the AI system can use the KLinf-based bound to decide: "If the true effect is this close to the null, I need at least c * (1/KLinf) * log log(1/KLinf) samples." This prevents under-powered experiments that lead to false negatives.
Improvement: Implement the e-process construction from Section 4.4 for AI systems that must detect anomalies under composite null hypotheses (e.g., the system is operating normally defined by multiple constraints).
Specific capability: An AI system can monitor multiple safety constraints simultaneously (e.g., fairness metrics, resource usage, output toxicity) using a single e-process that is valid under all null distributions. The stopping time min n: En ≥ 1/α provides a principled, anytime-valid alarm that matches the theoretical lower bound, avoiding both false positives and delayed detection.
Improvement: Apply Theorem 4.3's sequential test to AI systems that process bounded data (e.g., probabilities, normalized scores, pixel values) without assuming Gaussianity.
Specific capability: An AI system can test whether the mean of a bounded random variable (e.g., click-through rates, sentiment scores) has shifted, achieving the optimal O((1/KLinf) log log(1/KLinf)) sample complexity. This is robust to heavy tails and does not require knowing the distribution family.
Improvement: Use the paper's lower bounds to design AI systems that identify the best among multiple options (e.g., hyperparameter tuning, model selection) with guaranteed sample efficiency.
Specific capability: An AI system can now compute the instance-dependent lower bound for each candidate arm using KLinf(Q, P) and stop when the empirical evidence exceeds the bound. This yields asymptotically optimal stopping times, reducing wasted computation while maintaining correctness guarantees.
Improvement: Implement the confidence sequence construction from Section 4.3 (using KLinf-based e-processes) for AI systems that must make decisions at every time step.
Specific capability: An AI system can maintain a valid confidence interval for a parameter (e.g., model accuracy, reward mean) that is valid at all times, not just at pre-specified checkpoints. The interval width shrinks at the optimal rate, and the system can stop when the interval excludes the null value, with the stopping time matching the theoretical lower bound.
Improvement: Use the paper's lower bound for the KLinf → 0 regime to build AI systems that correctly identify when a problem is intrinsically hard.
Specific capability: An AI system can detect that the alternative is arbitrarily close to the null (e.g., a new model is only marginally better than the baseline) and automatically increase the sample budget according to the (1/KLinf) log log(1/KLinf) law, rather than assuming a fixed budget suffices. This prevents premature conclusions in near-tie scenarios.
Improvement: Apply Section 4.4's framework to AI systems that need to test hypotheses defined by arbitrary linear constraints on moments or quantiles.
Specific capability: An AI system can test, for example, whether a model's predictions satisfy multiple fairness constraints (e.g., equalized odds, calibration) simultaneously, using a mixture e-process over all feasible constraint weights. The stopping time is provably optimal in the α → 0 regime, and the system can handle nonparametric, heavy-tailed data without distributional assumptions.