CS Paper Radar

The Type-II Error of Test Supermartingales: e-Power versus the Chernoff-Stein Exponent

Patrick Forré

cs.IT math.STcs.LGmath.PRstat.ML ·submitted 2026-08-19 16:05 UTC · v1
theory

Abstract

In safe hypothesis testing with test supermartingales, Ville's inequality provides anytime-valid type-I error guarantees for every significance level $α\in(0,1]$, if one rejects the null hypothesis whenever the wealth process first exceeds $1/α$. Due to an inherent asymmetry, the type-II error behaves differently. We prove two things about the latter, for a simple null and alternative. First, the mean growth rate $\mathbb{E}_{P_1}[\log E]$, the e-power, that Kelly betting and growth-rate-optimal e-variables maximise, bounds nothing on its own. For every level $c>0$, every $α$ and horizon $t$ we construct e-variables of conditional e-power exactly $c$ whose probability of not rejecting by $t$ is arbitrarily close to one. It forces eventual rejection, but no finite-horizon guarantee follows. Second, the quantity that does control the type-II error is the Chernoff-Stein exponent of an e-variable, $Λ(E)=\sup_{s\ge0}\{-\log \mathbb{E}_{P_1}[E^{-s}]\}$, whose range is exactly determined: $\sup_E Λ(E)=\mathrm{KL}(P_0\|P_1)$, the classical Chernoff-Stein exponent, and so the ceiling of its own per-e-variable form. One conditional application of Hoelder's inequality per step gives it, for every test supermartingale on an arbitrary filtered space, with no independence or product structure; the i.i.d. case adds that it is matched, and attained by nothing. The e-power has its own ceiling, $\mathrm{KL}(P_1\|P_0)$, and that one is attained, $P_0$-a.s. uniquely, by the likelihood ratio $R$. The two optima are the same divergence in opposite arguments, at opposite ends of the flattened family $R^β/\mathbb{E}_{P_0}[R^β]$: the ceiling as $β\downarrow0$, $R$ at $β=1$. Which $β$ is best is settled by the horizon, exactly: $R$ is optimal at $t=\log(1/α)/\mathrm{KL}(P_1\|P_0)$ alone, beaten by sharpening $(β>1)$ below it and by flattening above.

Closest papers

Nearest neighbours by meaning across the whole index.

Type-II Error Bounds for Test Supermartingales from Lower-Tail Hypotheses

cs.IT math.STcs.LGmath.PR+1 ·2026-08-19 ·Patrick Forré
theory similarity 0.84
Abstract

In safe hypothesis testing with test supermartingals, Ville's inequality provides anytime-valid type-I error guarantees for every significance level $α\in(0,1]$, if one rejects the null hypothesis whenever the wealth process first exceeds $\frac{1}α$. Due to an inherent asymmetry, the type-II error does not have such guarantees: a heavy concentration of the probability on the lower tail of the log-increments can lead to one catastrophic bet that undoes any amount of accumulated evidence. This paper studies how different hypotheses on those lower-tail probabilities lead to different bounds on the type-II error of the sequential test. They all reduce to one master inequality, which bounds the type-II error at level $α$, at a fixed horizon and sequentially, in terms of a one-sided Legendre transform of the (inverse-)moment generating function of the e-variables, evaluated at one number: the amount by which the lower bound of the accumulated e-powers exceeds $\log\frac{1}α$. And, the step is lossless, in the sense, that it extracts exactly a constrained information projection. Every bound presented here is a corollary, obtained by a certain majorant of the above function. The hypotheses are: a finite negative moment; an exponentially small crash probability with a moment on the winning side; a wealth floor with a conditional variance, and its Bernstein variant, which interpolates between a Gaussian regime set by the variance and an exponential one set by the scale; a sub-Gaussian or bounded-tilt lower tail; bounded log-increments; and i.i.d. increments, where the majorant is the truth. We also provide an empirical-Bernstein variant. Each hypothesis may either be read as a condition on the e-variables one has, or as the price of betting with an approximation to the likelihood ratio rather than the ratio itself, which satisfies the weakest condition for free.

0.43

Competitive optimality in testing by betting via Bell-Cover randomization

cs.GT math.STcs.ITstat.ME ·2026-09-28 ·Aaditya Ramdas
similarity 0.60
Abstract · 14 pages

Bell and Cover showed that an investor who multiplies the initial unit of capital by an independent uniform random variable on $(0,2)$, and then uses the log-optimal portfolio, wins a head-to-head wealth comparison with probability at least one half against every independently randomized competitor. We explain very simply how this result transfers to testing by betting: for any composite null $\mathcal P$ and simple alternative $Q$, denoting $E^*$ as the corresponding numeraire e-variable, we show that $UE^*$ exceeds any other e-variable $E$ with probability at least half. Interestingly, we show that this competitive optimality result is actually equivalent to the numeraire inequality $\mathbb E_Q[E/E^*]\leq1$, and in general randomization only helps the numeraire and fails to improve the competitive advantage of an arbitrary e-variable. Under optional stopping with or without knowledge of $U$, we emphasize a key distinction between e-process validity and competitive optimality. We also show that competitive optimality comes at the price of expected log wealth and power: thresholding $UE^*$ at $1/α$ has sharp size at most $α/2$, but the factor of two actually disappears under optional stopping. Even after correcting for this factor of two, the test is dominated in conditional rejection probability by randomizing the testing threshold (randomized Markov's inequality). Thus, Bell-Cover randomization is optimal for a specific competitive objective, at the cost of others.

0.30

Anytime-valid simulation-based hypothesis testing

cs.LG stat.MLmath.STstat.ME ·2026-10-06 ·Patrick Forré, Lydia Brenner
similarity 0.60
Abstract

For a given data distribution $(X_t)_{t \in \mathbb{N}} \sim Q$ i.i.d., we investigate the hypothesis testing problem: $H_0: Q = P_0$ vs. $H_1: Q = P_1$, for two different model probability distributions $P_0$ and $P_1$. In contrast to the standard setting, where analytic densities $p_0$ and $p_1$ are given, here, we consider the density-free setting, where we only have access to i.i.d. simulations $(Z^0_t)_{t \in \mathbb{N}} \sim P_0$ and $(Z^1_t)_{t \in \mathbb{N}} \sim P_1$. For this simulation-based hypothesis testing setting, we construct an e-test martingale, resulting in a sequential test with anytime-valid type-I error guarantees, approximate growth optimality, geometrically decaying type-II error bounds, and asymptotic power one. Most ingredients used in our constructions are variants of well known concepts. The value of this paper lies in the compact presentation of an effective, anytime-valid solution for the density-free simulation-based sequential hypothesis testing case.

0.48

A complete characterization of sequential testability and change detectability in i.i.d. models

cs.IT math.STeess.SPstat.ME+1 ·2026-09-04 ·Aaditya Ramdas
similarity 0.58
Abstract · 33 pages

We give a necessary and sufficient condition for the existence of power-one sequential tests in an i.i.d. composite testing problem. A level-\(α\) test with power one against every alternative exists if and only if the alternatives are separated from the null by a countable family of finite-block events. We provide other equivalent conditions using randomized fixed-sample tests, bounded finite-block scores, e-processes, reduced-filtration test supermartingales, and a countable cover whose finite-block weak-$*$ closed convex hulls are positively separated in total variation. As a bonus, the constructive proof yields tests have pointwise expected sample size \(O_Q(\log(1/α))\). Exactly the same conditions also characterize i.i.d.\ change detectability under optional-horizon average-run-length control: for every \(η>0\), they are equivalent to an alarm family \((T_γ)_{γ\ge1}\) satisfying \(\Prob_{P^\infty}(T_γ\leσ)\le \E_{P^\infty}σ/γ\) for every null law and every stopping time \(σ\). In fact, when these conditions hold, we can construct a single e-detector such that every null-law average run length lies between \(γ\) and \((1+η)γ+1\), and having robust Lorden delay \(O_Q(\logγ)\).

0.22

Sample-Based Prophet Inequalities for Random Walks

cs.DS math.OC ·2026-09-22 ·Pieter Kleer, Johan van Leeuwaarden, Daan Noordenbos
publishedtheory similarity 0.58
Abstract · Accepted at the 22nd Conference on Web and Internet Economics (WINE 2026)

We study prophet inequalities for a random walk reward stopping problem with sample-based information. The goal is to stop as close as possible to the maximum of a random walk with i.i.d. increments, measuring performance by the ratio between the expected reward when stopping and the expected true maximum. We consider a sample-based model in which the increment distribution is unknown and the decision maker has access to $K$ independent sample paths of the reward process. For the infinite-horizon setting, we establish a sharp prophet inequality with constant $(K/(K+1))^{K+1}$. The guarantee is attained by a randomised stopping rule based on the ladder height decomposition of random walks. As $K\to\infty$, this recovers the classical $1/e$ prophet inequality from the full-information setting. For the finite-horizon setting, where the process terminates after $n$ steps, we first prove a tight no-information prophet inequality with constant $1/H_n$, where $H_n$ is the $n$-th harmonic number. For $K\ge1$ samples, we show that a prophet constant of $1/4$ is attainable. Finally, we prove that, with $K$ samples, the prophet constant is at most $(K/(K+1))^{K+1}+(6+6H_K)/H_n$ for $n\ge 2K^2$, implying convergence to the infinite-horizon constant as $n\to\infty$. Our approach combines random walk theory, including ladder heights and Spitzer's identity, with linear programming duality. Our results contribute to random walk stopping theory and to sample-based prophet inequalities for correlated rewards, an area that remains largely unexplored. To the best of our knowledge, our tight sample-based prophet inequalities are the first whose performance is parameterised exactly, rather than only up to constants, by the number of available samples.

0.20

Reliable Scale-Free Bandits via Empirical Likelihood

cs.LG stat.ML ·2026-10-13 ·Pratham Gupta, Alhad Sethi, Shubhada Agrawal
theory similarity 0.58
Abstract

We study stochastic bandits without knowledge of reward scales or tail parameters. Almost-sure regret guarantees describe eventual learning but do not quantify expected performance or the risk of large regret in a finite run. We introduce $\texttt{EL-F}$, an anytime empirical-likelihood (EL) extension of the $g$-Forcing policy of Cowan and Katehakis (2020), and characterize its performance at three levels. First, for integrable rewards and non-decreasing, diverging exploration schedules $g$ with vanishing increments, $\texttt{EL-F}$ preserves the $g$-Forcing asymptotics for pseudo-regret $R(T)$: $R(T)/g(T)\to\sum_{i:Δ_i>0}Δ_i$ almost surely as $T\to\infty$, where $Δ_i$ is the suboptimality gap of arm $i$. Second, on every sub-exponential instance, for non-decreasing $g(t)=ω(\log t)$ satisfying a mild feasibility condition, expected pseudo-regret is at most $g(T)\sum_{i:Δ_i>0}Δ_i+C_{\underline{P}}$, where $C_{\underline{P}}$ is an instance-dependent constant independent of $T$. Moreover, we also establish finite-time tail bounds with super-polynomial decay in regret beyond the forced-exploration budget. For slowly varying $g$, we determine the exact exponent of linear regret deviations on two-armed Gaussian instances with common variance and establish a matching lower bound among policies satisfying the same expected-regret budget on every such Gaussian instance. These quantitative guarantees also cover the greedy variant obtained at zero EL radius. A fixed positive radius introduces local optimism while preserving the leading asymptotic regret. We establish coupled pathwise dominance over the greedy variant in two-armed bandits with a deterministic suboptimal arm. Experiments demonstrate reductions in prolonged suboptimal allocation compared with $g$-Forcing on challenging instances.

0.35

Finite Sample Bounds for Composite Hypothesis Testing

cs.IT ·2026-08-28 ·Elías Vera-Sigüenza, Amedeo Roberto Esposito
similarity 0.57
Abstract · 5 figures, 34 pages

We investigate composite binary hypothesis testing in the finite sample regime under asymmetric error constraints. Using Rényi divergences, we derive explicit achievability and converse bounds for the optimal Type II error. When the Type I error is constrained to decay exponentially with sample size, the bounds identify a phase transition and yield a strong converse above it. In the composite problem, the phase transition threshold is given by the joint KL projection over the alternative and null classes. Achievability is obtained through a joint Rényi projection whose log likelihood ratio defines a single test with uniform error control over both hypothesis classes, without requiring the projected pair to be least favourable. For compact convex classes with full support on a finite alphabet, we determine the exact error exponents on both sides of the transition and show that the achievable exponent is attained at a unique Rényi order. The same framework recovers the fixed Type I composite Chernoff--Stein exponent and yields a polynomial refinement of the finite sample achievability result. We further identify conditions under which the projected pair is least favourable at finite sample size.

0.13

From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting

cs.LG ·2026-08-10 ·Jinze Zhao
theory similarity 0.56
Abstract

Betting-based sequential tests and Blackwell approachability are linked by a rate-explicit reduction through support-function residuals. For a compact convex target $S$ and vector observations $r_t$, an OCO learner selects a predictable normal $w_t$ and produces $q_t=\langle w_t,r_t\rangle-h_S(w_t)$. We prove the exact pathwise identity $$ \dist(\bar r_T,S) =\frac1T\sum_{t=1}^Tq_t+\frac{\Reg_T}{T}. $$ When $|q_t|\leq B$, composing this identity with one-sided betting yields a finite-time transfer: if the OCO and log-wealth regrets are at most $a_T$ and $\ell_T$, respectively, then a target gap exceeding \[ \frac{a_T}{T} +2B\sqrt{\frac{\log(1/α)+\ell_T}{T}} \] forces rejection by time $T$, while non-rejection certifies the converse radius. We then formulate a controlled stochastic experiment in which an action selected after $w_t$ satisfies Blackwell's supporting-halfspace condition for every null mean payoff. The resulting wealth is an e-process under adaptive nulls; sublinear OCO regret gives stochastic approachability, whereas persistent mean separation under an alternative gives exponential wealth at rate at least $δ^2/(4B^2)$. Deterministic Blackwell games and passive tests are, respectively, the noise-free and singleton-action cases of this protocol. Bounded two-sample means, kernel MMD, and active heterogeneous data sources instantiate the reduction. The resulting connection is exact algebraically, quantitative at finite time, and operational when experiments are controlled.

0.04