Finite Sample Bounds for Composite Hypothesis Testing
Information Theory
Summary
The authors study a problem where they have to decide between two groups of possibilities based on limited data, with strict rules on how often errors can happen. They use a mathematical tool called Rényi divergences to find clear boundaries on how well these decisions can be made, especially when one type of error must get smaller very fast as more data is collected. They discover a tipping point that changes how hard the problem is and describe exactly how error rates behave near this point in certain cases. Their results also connect to and improve on existing findings for similar testing problems.
binary hypothesis testingcomposite hypothesisRényi divergenceType I errorType II errorChernoff--Stein lemmaKL divergenceerror exponentfinite sample regimeleast favourable distribution
Authors
El{í}as Vera-Sig{ü}enza, Amedeo Roberto Esposito
Abstract
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.