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

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.