On the Second-Order Asymptotics of the Hoeffding Test and Other Divergence Tests

Consider a binary statistical hypothesis testing problem, where n independent and identically distributed random variables Zⁿ are either distributed according to the null hypothesis P or the alternative hypothesis Q, and only P is known. A well-known test that is suitable for this case is the so-called Hoeffding test, which accepts P if the Kullback-Leibler (KL) divergence between the empirical distribution of Zⁿ and P is below some threshold. This work characterizes the first and second-order terms of the type-II error probability for a fixed type-I error probability for the Hoeffding test as well as for divergence tests, where the KL divergence is replaced by a general divergence. It is demonstrated that, irrespective of the divergence, divergence tests achieve the first-order term of the Neyman-Pearson test, which is the optimal test when both P and Q are known. In contrast, the second-order term of divergence tests is strictly worse than that of the Neyman-Pearson test. It is further demonstrated that divergence tests with an invariant divergence achieve the same second-order term as the Hoeffding test, but divergence tests with a non-invariant divergence may outperform the Hoeffding test for some alternative hypotheses Q. Potentially, this behavior could be exploited by a composite hypothesis test with partial knowledge of the alternative hypothesis Q by tailoring the divergence of the divergence test to the set of possible alternative hypotheses.