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

arXiv:2611.02130 · math.ST, stat.ML, stat.TH · Submitted 2026-11-01 · Read on arXiv

math.ST, stat.ML, stat.TH

Submitted: 2026-11-01

Updated: 2026-11-01

License: http://creativecommons.org/licenses/by/4.0/

The gist: When testing a composite null P against a composite alternative Q, it has been known since Huber and Strassen (1973) that if a least favorable distribution (LFD) pair exists…

Abstract

When testing a composite null P against a composite alternative 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 P in P,S in 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 = P c. This means that when the data are drawn from any S in P c, the test has power one, and its stopping time is determined by the larger information number P in P KL(S|P), which governs the performance of an oracle that knows S. To demonstrate this point, our paper focuses on the case of testing a TV ball around a discrete distribution with d 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 S and the second is the "Farrell setting", where α is fixed and P in P KL(S|P) approaches 0. Our sequential test is simultaneously optimal in both regimes.

Sources

Related papers