betaFeedback

WorksMathematics

Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing

Abstract

When testing a composite null P\mathcal{P} against a composite alternative Q\mathcal{Q}, it has been known since Huber and Strassen (1973) that if a least favorable distribution (LFD) pair exists, then a version of its likelihood ratio yields a minimax optimal test, and Huber (1965) derived a similar result in the sequential setting for a specific robust testing problem that is the focus of the current paper; the same likelihood ratio is log-optimal in the worst case; its expected logarithm under the alternative equals inf⁡P∈P,S∈QKL(S∥P)\inf_{P \in \mathcal{P},S \in \mathcal{Q}} KL(S\|P), whose inverse also determines the stopping time of the test under the alternative. These results focus on optimizing worst-case performance, but the resulting methods have lower power if the data come from simpler alternatives. This paper studies an arguably more practical goal of achieving asymptotic instance optimality for ``power-one'' sequential tests, which remarkably may even be possible when Q=Pc\mathcal{Q} = \mathcal{P}^c. This means that when the data are drawn from any S∈PcS \in \mathcal{P}^c, the test has power one, and its stopping time is determined by the larger information number inf⁡P∈PKL(S∥P)\inf_{P \in \mathcal{P}} KL(S\|P), which governs the performance of an oracle that knows SS. To demonstrate this point, our paper focuses on the case of testing a TV ball around a discrete distribution with dd components, and designs a computationally and memory efficient algorithm that is also asymptotically instance-optimal. Specifically, we consider two different asymptotic settings: one is the "Wald setting", where the type-1 error level αα approaches zero for a fixed alternative SS and the second is the "Farrell setting", where αα is fixed and inf⁡P∈PKL(S∥P)\inf_{P \in \mathcal{P}} KL(S\|P) approaches 00. Our sequential test is simultaneously optimal in both regimes.

Introduction

Consider sequential testing of a composite null class P\mathcal{P} of probability laws on a measurable space X\mathcal{X}. In the classical formulation, one specifies a composite alternative Q\mathcal{Q} and seeks a test with strong worst-case performance over Q\mathcal{Q}. If there is a least-favorable pair (P⋆,Q⋆)∈P×Q(P^\star,Q^\star)\in\mathcal{P}\times\mathcal{Q}, then the corresponding likelihood ratio provides a minimax test: it is designed against the hardest alternative Q⋆Q^\star and protects against the hardest null P⋆P^\star. Robust likelihood-ratio tests of this form go back to Huber’s censored probability-ratio construction for neighborhood models ([8]), while Huber and Strassen later developed a broad minimax theory in terms of least-favorable pairs and capacities ([9]). More recently, Saha and Ramdas [16] formulated this principle in terms of e-values for arbitrary composite nulls and alternatives and showed how one can perform one-sided sequential tests for Huber-contamination and total-variation neighborhoods, including sequentially adaptive contamination. The minimax criterion is compelling when performance at the hardest alternative is the primary objective. It can, however, leave substantial power on the table when the realized data-generating distribution is easier than the least-favorable one. A test optimized for Q⋆Q^\star has no reason to exploit the additional separation of a particular Q∈QQ \in\mathcal{Q} from the null class. In sequential problems, this loss appears directly as slower exponential growth of the evidence process and hence a larger detection delay. Moreover, in many testing problems there is no naturally separated alternative class for which a nontrivial least-favorable pair exists. A canonical example is testing a composite null against its complement.

This motivates a different objective. Instead of fixing a composite class and optimizing the worst case over it, take the alternative to be simply the complement

Q=Pc,\mathcal{Q} = \mathcal{P}^{c},

and ask for a single valid sequential test that adapts to whichever S∈PcS \in\mathcal{P}^{c} actually generates the data, given a level α∈(0,1)\alpha\in(0,1). We construct an e-process and a “power-one” sequential test that can control the type-1 error at a prespecified level α\alpha and, for a fixed alternative S∉PS \notin\mathcal{P}, the e-process asymptotically achieves the oracle growth rate,

Γ(S):=inf⁡R∈PDKL(S∥R),(1)\Gamma(S) := \inf_{R \in\mathcal{P}} D_{\mathrm{KL}}(S \mathbin\Vert R), \tag*{(1)}

which is known to be optimal for testing P\mathcal{P} ([11, 12]). Here DKLD_{\mathrm{KL}} denotes the KL divergence. See § 1.1 for a detailed discussion on the e-process and its growth rate.

We develop this idea for a canonical robust-testing model. For some d∈Nd \in\mathbb{N}, let X={1,…,d}\mathcal{X} = \{1,\ldots,d\} be the observation space and consider a discrete distribution with dd components with probability mass function

P=(P1,…,Pd),P = (P_1,\ldots,P_d),

with Pi>0P_i > 0, for all i=1,…,di = 1,\ldots,d. Take the null hypothesis to be the total-variation neighborhood ([8]) around PP:

P0:=BTV(P,ϵ0)={R∈Δd:DTV(R,P)≤ϵ0},(2)\mathcal{P}_0 := \mathcal{B}_{\mathrm{TV}}(P,\epsilon_0) = \{R \in\Delta_d : D_{\mathrm{TV}}(R,P) \le\epsilon_0\}, \tag*{(2)}

where Δd\Delta_d is the probability simplex, DTV(R,P)D_{\mathrm{TV}}(R,P) is the total variation distance between RR and PP:

DTV(R,P)=12∑i=1d∣Ri−Pi∣.D_{\mathrm{TV}}(R,P) = \frac{1}{2}\sum_{i=1}^{d} |R_i-P_i|.

With a slight abuse of notation, we will denote the probability distributions by their dd-dimensional probability mass functions. The radius ϵ0\epsilon_0 has a direct interpretation: under any distribution in the null, the probability of every event differs from its nominal probability by at most ϵ0\epsilon_0. It therefore specifies the discrepancies against which the test must protect, even when evidence is monitored continuously.

But in contrast to Huber [8]; Saha and Ramdas [16], our alternative is not another prespecified ball; it is the entire complement Δd∖P0\Delta_d \setminus\mathcal{P}_0. Our goal here is to approach the instance-optimal information rate defined in (1), instead of the minimax information rate, inf⁡P∈P,S∈QDKL(S∥P)\inf_{P \in\mathcal{P},S \in\mathcal{Q}} D_{\mathrm{KL}}(S\mathbin\Vert P) as in Saha and Ramdas [16].

We also construct e-processes for both Wald and Farrell optimality for testing P0\mathcal{P}_0 against its entire complement P0c=Δd∖P0\mathcal{P}_0^c = \Delta_d \setminus\mathcal{P}_0. Specifically, we seek a single e-process whose threshold-crossing times define level-α\alpha tests with power one under every alternative, and whose expected stopping times are optimal in two complementary regimes. In the Wald regime, the alternative S∉P0S \notin\mathcal{P}_0 is fixed and α↓0\alpha\downarrow0; for every fixed full-support SS, we aim to attain

ES[τα]∼log⁡(1/α)Γ(S).\mathbb{E}_S[\tau_\alpha] \sim\frac{\log(1/\alpha)}{\Gamma(S)}.

In the Farrell regime, α∈(0,1/2)\alpha\in(0,1/2) is fixed and the alternative approaches the null boundary, so that Γ(S)↓0\Gamma(S) \downarrow0; with P\mathcal{P}, ϵ0\epsilon_0, dd fixed, we aim for

ES[τα]=O(log⁡log⁡(1/Γ(S))Γ(S)).\mathbb{E}_S[\tau_\alpha] = O\left(\frac{\log\log(1/\Gamma(S))}{\Gamma(S)}\right).

The first guarantee attains the exact information-theoretic leading constant, while the second matches the Farrell lower bound in order in its sequence-wise sense. We obtain both guarantees by averaging an adaptive clipped-Kelly e-process with a complementary e-process designed for alternatives near the null boundary.

The remainder of this introduction reviews the required background, discusses related work, and states these contributions precisely.

Background on e-values, test supermartingales, one-sided tests, growth rate and consistency

An e-variable is a nonnegative random variable whose expectation is bounded above by one under every distribution in the null class. Specifically, BB is an e-variable for P\mathcal{P} if

EP[B]≤1for all P∈P.\mathbb{E}_{P}[B] \le1 \qquad\text{for all } P \in\mathcal{P}.

The observed realization of an e-variable is called an e-value.

Let M={Mn}n≥0M = \{M_n\}_{n\ge0} be an integrable process adapted to a filtration F={Fn}n≥0\mathcal{F} = \{\mathcal{F}_n\}_{n\ge0}. We call MM a martingale for PP if, for every n≥1n \ge1,

EP[Mn∣Fn−1]=Mn−1,∀P∈P.(3)\mathbb{E}_{P}[M_n \mid\mathcal{F}_{n-1}] = M_{n-1}, \qquad\forall P \in\mathcal{P}. \tag*{(3)}

Similarly, MM is a supermartingale for PP, if, for every n≥1n \ge1,

EP[Mn∣Fn−1]≤Mn−1,∀P∈P.(4)\mathbb{E}_{P}[M_n \mid\mathcal{F}_{n-1}] \le M_{n-1}, \qquad\forall P \in\mathcal{P}. \tag*{(4)}

A test (super)martingale is a process that satisfies the corresponding condition under every distribution in P\mathcal{P}, is nonnegative, and starts at M0=1M_0 = 1. A stopping time τ\tau is a nonnegative integer-valued, possibly infinite random variable satisfying {τ≤n}∈Fn\{\tau\le n\} \in\mathcal{F}_n for every n∈Nn \in\mathbb{N}. We write T\mathcal{T} for the collection of all such stopping times, including those that may never stop.

Ville’s inequality (Ville, [18]) guarantees that a test (super)martingale satisfies

sup⁡P∈PP(∃n∈N:Mn≥1/α)≤α.(5)\sup_{P \in\mathcal{P}} P(\exists n \in\mathbb{N}: M_n \ge1/\alpha) \le\alpha. \tag*{(5)}

A short proof appears in Howard et al. [6]. Equivalently, P(Mτ≥1/α)≤αP(M_\tau\ge1/\alpha) \le\alpha for every τ∈T\tau\in\mathcal{T} and every P∈PP \in\mathcal{P}; see Howard et al. [7]. Consequently, stopping and rejecting at

τα=inf⁡{n≥1:Mn≥1/α}(6)\tau_\alpha= \inf\{n \ge1 : M_n \ge1/\alpha\} \tag*{(6)}

defines a level-α\alpha sequential test. Under the null, the probability of ever stopping with a false rejection is at most α\alpha; equivalently, τα=∞\tau_\alpha= \infty with probability at least 1−α1-\alpha.

This formulation differs from Wald’s classical sequential testing framework [19], in which the procedure may terminate by either accepting or rejecting the null, with the stopping rule calibrated to specified Type-I and Type-II error probabilities. Our setting instead follows Robbins’ theory of “power-one” or one-sided tests [4, 15]: only a target Type-I error level is specified, and sampling stops exclusively to reject the null. Such a test is called consistent under an alternative QQ if it has power one under QQ.

A test (super)martingale is called consistent, or power one, for an alternative QQ if

Mn⟶∞Q-almost surely.M_n \longrightarrow\infty\quad Q\text{-almost surely}.

Under each alternative, the process then accumulates unbounded evidence against the null and eventually crosses every finite rejection threshold. In i.i.d. settings, evidence can accumulate exponentially, as emphasized by Kelly [10]. This motivates measuring performance through the worst-case logarithmic growth rate

lim inf⁡n→∞log⁡Mnn\liminf_{n\to\infty}\frac{\log M_n}{n}

[17, 5, 21]. A positive growth rate implies consistency. A test (super)martingale attaining the largest possible growth rate is called log-optimal. This optimality criterion has been studied and advocated by Breiman [2], Cover [3], Shafer [17], and Grünwald et al. [5], among others.

Agrawal et al. [1] provides upper and lower bounds for power-one sequential tests in two different asymptotic settings: one is the “Wald setting”, where the type-1 error level α\alpha approaches zero for a fixed alternative SS. The second lower bound applies to the “Farrell setting”, where α\alpha is fixed and Γ(S)\Gamma(S) approaches 0 along a sequence of alternatives.

Related work

Robust/minimax hypothesis testing. Robust likelihood-ratio testing begins with Huber’s censored probability-ratio test [8], which clips individual likelihood-ratio factors to prevent a small number of contaminated observations from dominating the evidence. Huber and Strassen [9] developed a general minimax theory of hypothesis testing under capacities and least-favorable distributions. These works establish the classical principle that, when an appropriate least-favorable pair exists, testing can be reduced to a likelihood-ratio test between that pair.

E-values and e-processes. The second thread of literature that is relevant involves recent fundamental advances in composite hypothesis testing. For example, Grünwald et al. [5] introduce growth-rate optimal (GRO) e-variables for testing problems with composite null and alternative. The universal inference method [20] used an e-value to propose a level-α\alpha test for any composite null without requiring any regularity conditions, but requiring reference measures. Reverse information projections and numeraire e-variables characterize pointwise log-optimal evidence under composite nulls [11, 12]. See Ramdas et al. [14] for a detailed review.

Our contribution is to turn this static pointwise characterization into an adaptive sequential procedure with explicit stopping-time and computational guarantees in the finite-alphabet robust model. The closest modern precursor is Saha and Ramdas [16]. They prove that least-favorable pairs yield log-optimal e-values for arbitrary composite nulls and alternatives, construct Huber-robust and TV-robust versions of such tests, and obtain sequential validity even when the contamination mechanism varies adaptively with the past, extending Huber and Strassen [9]. In particular, their theory already gives the least-favorable clipped likelihood ratio for two separated TV neighborhoods. Our question is orthogonal: rather than optimizing the worst case over a prespecified alternative class, we take the alternative to be Pc\mathcal{P}^{c} and ask whether one valid procedure can asymptotically attain the oracle rate (1) at every realized alternative.

Ram and Ramdas [13] show the existence of relatively growth-rate optimal e-processes and thus power-one tests under rather general conditions, including the TV ball. However, their work is abstract and their constructions are far from practical, and they do not have stopping time guarantees or regret bounds. Our work extends theirs by adding the specific contributions (i), (ii), (iii), and (iv) mentioned in the next subsection.

Contributions

(i) Finite-sample adaptive regret. For testing the null P\mathcal{P} in (2) against an unknown full-support alternative S∈PcS \in\mathcal{P}^{c}, we construct an e-process {MnCK}n\{M_{n}^{\mathrm{CK}}\}_{n} and show the finite-sample bound on the regret

0≤nΓ(S)−ESlog⁡MnCK≤log⁡(n+d−1d−1).(7)0 \le n\Gamma(S) - \mathbb{E}_{S}\log M_{n}^{\mathrm{CK}} \le\log\left(\frac{n+d-1}{d-1}\right). \tag*{(7)}

Consequently, the expected regret is O(dlog⁡n)O(d\log n) and the normalized expected and almost-sure log wealth converge to Γ(S)\Gamma(S).

(ii) Wald-optimal expected stopping time. For the level-α\alpha test using the that e-process, ταCK:=inf⁡{n:MnCK≥α−1}\tau_{\alpha}^{\mathrm{CK}} := \inf\{n : M_{n}^{\mathrm{CK}} \ge\alpha^{-1}\}, we prove that

ESταCK=log⁡(1/α)Γ(S)(1+o(1)),α↓0.\mathbb{E}_{S}\tau_{\alpha}^{\mathrm{CK}} = \frac{\log(1/\alpha)}{\Gamma(S)}(1+o(1)), \qquad\alpha\downarrow0.

It is well known that no level-α\alpha sequential test can improve the first-order constant 1/Γ(S)1/\Gamma(S) at the same instance [1].

(iii) Farrell-optimal expected stopping time. We construct another e-process {MnF}n\{M_{n}^{\mathrm{F}}\}_{n} for adaptation near the null boundary for which the level α\alpha stopping time, ταF\tau_{\alpha}^{\mathrm{F}}, is Farrell-optimal:

ESταF=OP,ϵ0,d(d+log⁡(1/α)+log⁡log⁡(ee/Γ(S))Γ(S)),0<Γ(S)≤1,\mathbb{E}_{S}\tau_{\alpha}^{\mathrm{F}} = O_{P,\epsilon_{0},d}\left(\frac{d+\log(1/\alpha)+\log\log(e^{e}/\Gamma(S))}{\Gamma(S)}\right), \qquad0 < \Gamma(S) \le1,

that is, for fixed α∈(0,1/2)\alpha\in(0,1/2), we have ESταF=O(Γ(S)−1log⁡log⁡(1/Γ(S)))\mathbb{E}_{S}\tau_{\alpha}^{\mathrm{F}} = O(\Gamma(S)^{-1}\log\log(1/\Gamma(S))), as Γ(S)↓0\Gamma(S) \downarrow0. At fixed α∈(0,1/2)\alpha\in(0,1/2), it matches the optimal Farrell order in the sequence-wise sense of the lower bound. Averaging this process with clipped Kelly retains the exact Wald constant and increases the expected-regret bound by at most log⁡2\log2.

(iv) Exact logarithmic-time implementation. A naive fresh oracle computation sorts all dd ratios and costs O(dlog⁡d)O(d\log d) per round. We show that, after a rescaling, only the coordinate corresponding to the newly observed symbol changes. Maintaining these quantities in an augmented balanced binary search tree yields the same fresh every-round clipped-Kelly oracle in O(log⁡d)O(\log d) worst-case update time, after O(dlog⁡d)O(d\log d) initialization, using O(d)O(d) memory.

Our adaptive process instead learns the oracle corresponding to the realized alternative, enjoys logarithmic finite-sample regret, achieves the information-theoretically optimal first-order stopping time at that instance, and can be implemented efficiently.

Organization. Section 2 constructs an adaptive e-process showing that its expected stopping time achieves Wald optimality as the type-I error converges to zero. Section 3 studies adaptation near the null boundary and Farrell-type optimality, and combines the two regimes. Section 4 gives efficient dynamic implementation of both e-processes. Section 5 shows a simulation experiment, and Section 6 discusses the scope of the results. Proofs of the theoretical results appear in Section A. An alternative oracle-mixture construction is provided in Section B.

Adaptive clipped-Kelly e-process

From this point onward we specialize to the finite-alphabet TV-robust model in (2). We assume throughout that d≥2d \ge2, Pi>0P_i > 0 for every ii, and

References

  1. [1]Agrawal, S., Ram, A., and Ramdas, A. (2025). On stopping times of power-one sequential tests: Tight lower and upper bounds. arXiv preprint arXiv:2504.19952.arxiv.org/abs/2504.19952
  2. [2]Breiman, L. (1961). Optimal gambling systems for favorable games. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability.
  3. [3]Cover, T. M. (1987). Log optimal portfolios. In Chapter in “Gambling Research: Gambling and Risk Taking,” Seventh International Conference, volume 4.
  4. [4]Darling, D. A. and Robbins, H. (1968). Some nonparametric sequential tests with power one. Proceedings of the National Academy of Sciences, 61(3):804–809.pubmed.ncbi.nlm.nih.gov/16591711
  5. [5]Grünwald, P., de Heide, R., and Koolen, W. (2024). Safe testing. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(5):1091–1128.
  6. [6]Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2020). Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys.DOI
  7. [7]Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. Annals of Statistics.DOI
  8. [8]Huber, P. J. (1965). A robust version of the probability ratio test. The Annals of Mathematical Statistics, pages 1753–1758.DOI
  9. [9]Huber, P. J. and Strassen, V. (1973). Minimax tests and the neyman-pearson lemma for capacities. The Annals of Statistics, pages 251–263.DOI
  10. [10]Kelly, J. L. (1956). A new interpretation of information rate. the bell system technical journal, 35(4):917–926.
  11. [11]Lardy, T., Grünwald, P., and Harremoës, P. (2024). Reverse information projections and optimal e-statistics. IEEE Transactions on Information Theory, 70(11):7616–7631.arxiv.org/abs/2306.16646
  12. [12]Larsson, M., Ramdas, A., and Ruf, J. (2025). The numeraire e-variable and reverse information projection. The Annals of Statistics, 53(3):1015 – 1043.arxiv.org/abs/2402.18810
  13. [13]Ram, A. and Ramdas, A. (2026). Power one sequential tests for 𝒫 against 𝒫ᶜ. arXiv preprint arXiv:2604.03218.
  14. [14]Ramdas, A., Grünwald, P., Vovk, V., and Shafer, G. (2023). Game-theoretic statistics and safe anytime-valid inference. Statistical Science.arxiv.org/abs/2210.01948
  15. [15]Robbins, H. (1970). Statistical methods related to the law of the iterated logarithm. The Annals of Mathematical Statistics, 41(5):1397–1409.
  16. [16]Saha, A. and Ramdas, A. (2025). Huber-robust likelihood ratio tests for composite nulls and alternatives. IEEE Transactions on Information Theory.arxiv.org/abs/2408.14015
  17. [17]Shafer, G. (2021). Testing by betting: A strategy for statistical and scientific communication. Journal of the Royal Statistical Society Series A: Statistics in Society, 184(2):407–431.DOI
  18. [18]Ville, J. (1939). Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):824.
  19. [19]Wald, A. (1945). Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2):117–186.
  20. [20]Wasserman, L., Ramdas, A., and Balakrishnan, S. (2020). Universal inference. Proceedings of the National Academy of Sciences, 117(29):16880–16890.DOI
  21. [21]Waudby-Smith, I. and Ramdas, A. (2023). Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B (Methodology), with discussion.

Paper details

vlnc:W_mac5exe9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents