Second-Order Asymptotics of Hoeffding-Like Hypothesis Tests

We consider a binary statistical hypothesis testing problem, where $n$ independent and identically distributed random variables $Z^n$ are either distributed according to the null hypothesis $P$ or the alternate hypothesis $Q$, and only $P$ is known. For this problem, a well-known test is the Hoeffding test, which accepts $P$ if the Kullback-Leibler (KL) divergence between the empirical distribution of $Z^n$ and $P$ is below some threshold. In this paper, we consider Hoeffding-like tests, where the KL divergence is replaced by other divergences, and characterize, for a large class of divergences, the first and second-order terms of the type-II error for a fixed type-I error. Since the considered class includes the KL divergence, we obtain the second-order term of the Hoeffiding test as a special case.


I. INTRODUCTION
Statistical hypothesis testing is known to have applications in areas such as information theory, signal processing, and machine learning. The most simple form of hypothesis testing is binary hypothesis testing, where the goal is to determine the distribution of a random variable Z between a null hypothesis P and an alternate hypothesis Q. There can be two types of errors in a binary hypothesis testing: The type-I error is the probability of declaring the hypothesis as Q when the true distribution is P . The type-II error is the probability of declaring the hypothesis as P when the true distribution is Q. In general, we are interested in analyzing the trade-off between these two types of errors for a given test. This test may have full or only partial access to the distributions P and Q.
When both P and Q are known, the likelihood ratio test (also known as Neyman-Pearson test [1]) achieves the optimal error trade-off between type-I and type-II errors. The Neyman-Pearson test is also investigated in an asymptotic setting, where one observes n independent copies of Z and the errors are analyzed asymptotically as n tends to infinity. In this case, we are often interested in the behaviour of the type-II error β n for a fixed type-I error α n . It is known that for α n ≤ ǫ, ǫ ∈ (0, 1), the corresponding type-II error satisfies [2,Prop. 2.3] − ln β n = nD(P Q) − nV (P Q)Q −1 (ǫ) + o( √ n), as n → ∞ where D(P Q) is the Kullback-Leibler (KL) divergence between P and Q, defined as Q −1 (·) denotes the inverse of the tail probability of the standard Normal distribution, and o( √ n) denotes a term that grows more slowly than √ n as n → ∞. Thus the first-order term of − ln β n , defined as lim n→∞ − ln βn n and sometimes referred to as the error exponent, is given by D(P Q). The second-order term, defined as − ln βn−nD(P Q) √ n , is given by − V (P Q)Q −1 (ǫ). The case where the test has only partial access to the distributions P and Q is generally studied under the name of composite hypothesis testing. Here, the assumption is that P and Q belong to certain classes of distributions denoted by P and Q, respectively. Several special cases of composite hypothesis testing have been investigated in the literature. Two such cases are: 1) P is known and Q can be any distributions but P ; 2) P is known and Q belongs to a special class Q. A test proposed by Hoeffding [3], known as the Hoeffding test, is suitable for these two cases. In the Hoeffding test, the null hypothesis P is accepted if the KL divergence between the type t Z n (the empirical distribution) of the observations Z n = (Z 1 , · · · , Z n ) and P is below some threshold c. Otherwise, the alternative hypothesis is accepted. Mathematically, if D(t Z n P ) < c, then accept H 0 ; otherwise accept H 1 .
In [4,Th. III.2], it was shown that the Hoeffding test achieves the same first-order term of − ln β n as the Neyman-Pearson test. Consequently, not having access to the distribution of the alternate hypothesis does not affect the first-order term. To analyze the second-order term of − ln β n in the above two cases of composite hypothesis testing, Watanabe proposed a test that is second-order optimal in some sense [5].
The Hoeffding test does not require side information about the special class Q to which Q belongs. It is therefore perhaps not surprising that tests that have knowledge of Q (case 2 of composite hypothesis testing) may outperform the Hoeffding test. Such tests include the generalized likelihood ratio test (GLRT) [6] and test via mismatched divergence [7]. For example, it has been observed through simulations that the test via mismatched divergence performs better than the Hoeffding test [7]. However, an analytical comparison between the Hoeffding test and other tests is missing since refined asymptotics of the Hoeffding are not available.
In this paper, we wish to understand the behavior of the second-order term of the Hoeffding test as well as of Hoeffding-like tests where the KL divergence is replaced by other divergences, in the following referred to as divergence test. For a large class of divergences, we demonstrate that the second-order term is given by− V (P Q)Q −1 χ 2 ,k−1 (ǫ), where Q −1 χ 2 ,k−1 (·) denotes the inverse of the tail probability of the chi-squared distribution with k − 1 degrees of freedom. This class of divergences includes the KL divergence, so we obtain the second-order term of the Hoeffding test, as a special case.
The rest of this paper is organized as follows. Section II presents notations and the problem formulation. Section III discusses our main results. Section IV presents the proof of our results. Section V concludes the paper with a summary and discussion of our results.

II. NOTATIONS AND PROBLEM FORMULATION A. Notations
Let f (x) and g(x) be two real-valued functions.
Let {a n } be a sequence of positive real numbers. We say that a sequence of random variables is X n = o p (a n ) if for every ǫ > 0, we have lim n→∞ P X n a n > ǫ = 0.
Similarly, we say that X n = O p (a n ) if for every ǫ > 0 there exist M ǫ > 0 and N ǫ ∈ N such that P X n a n > M ǫ ≤ ǫ, n ≥ N ǫ .

B. Divergence and Divergence Test
We consider a divergence test on a random variable Z that takes value in a discrete set Z = {a 1 , · · · , a k }, where k ≥ 2. We denote the probability distribution function of Z by a k-length vector P = (P 1 , · · · , P k ) T , where be the set of all such probability distributions. The set of all positive probability distributions with P i > 0, i = 1, · · · , k on Z is denoted by P(Z). Let Z n = (Z 1 , · · · , Z n ) denote an n-length i.i.d. sequence of Z. By denoting the realization of Z n by z n , we define the type distribution t z n = (t z n (a 1 ), · · · , t z n (a k )) T of the sequence z n as (t z n (a 1 ), · · · , t z n (a k )) T N a 1 |z n n , · · · , N a k |z n n T where N a i |z n , i = 1, · · · , k denotes the number of times a i occurs in the sequence z n . Since k i=1 P i = 1, a probability vector P = (P 1 , · · · , P k ) T ∈ P(Z) can be represented by any (k − 1) components of P . With this representation, the set P(Z) can be identified as a (k − 1)-dimensional manifold; see [8]. In this paper, we choose the coordinate system of the probability distribution P = (P 1 , · · · , P k ) T as the first (k − 1) components denoted by P = (P 1 , · · · , P k−1 ) T .
Given any two probability distributions P, Q ∈ P(Z), one can define a non-negative binary functioñ D(P Q) called a divergence which represents a measure of discrepancy between them. A divergence is not necessarily symmetric in its arguments and also need not satisfy the triangle inequality; see [8], [9] for more details. Mathematically, a divergence is defined as follows.
Definition 1 Consider two points P and Q in P(Z) whose coordinates are P = (P 1 , · · · , P k−1 ) T and Q = (Q 1 , · · · , Q k−1 ) T . A divergenceD(P Q) between P and Q is a smooth function of P and Q (we may writeD(P Q) =D(P Q)) satisfying the following conditions: 1)D(P Q) ≥ 0 for any P, Q ∈ P(Z).
There are many classes of divergences that are widely used in various fields of science and engineering; see, e.g., [10] for more details. A well-known example of a divergence is the f -divergence defined as follows: Let f : (0, ∈ ∞) → R be a convex function with f (1) = 0. Then, the f -divergence between P and Q is defined as When f (u) = u log u, D f is the Kullback-Leibler divergence. For the f -divergence is the α-divergence given by We next define a divergence test for case 1 of composite hypothesis testing (see Section I), That is, it is known that under hypothesis H 0 the distribution is P , while under hypothesis H 1 the distribution is anything but P . A Hoeffding-like test or divergence test TD n (r) for testing H 0 :P = P against the alternative H 1 :P = Q is defined as follows: Upon observing z n , ifD(t z n P ) < r for some r > 0, then the null hypothesis P is accepted; else P is rejected. For r > 0, define the acceptance region for P as AD n (r) z n |D(t z n P ) < r .
Then, the type-I and the type-II errors are given by α n (TD n (r)) P n AD n (r) c β n (TD n (r)) Q n (AD n (r)).
Our goal is to analyze the asymptotics of the type-II error when the type-I error satisfies α n ≤ ǫ, 0 < ǫ < 1.
Following the discussion in Section I, we define the first-order term β ′ and the second-order term β ′′ for the divergence test as follows: if the limits exist. For the Hoeffding test, it is known that β ′ = D(P Q). In this paper, we generalize this result to the divergence test for a class of divergences defined in Definition 2. We further obtain β ′′ for the divergence test.
III. SECOND-ORDER ASYMPTOTICS OF THE DIVERGENCE TEST We shall consider the following class of divergences.
Definition 2 Let Ξ denote the class of divergences satisfying the following conditions: 1) For any P, T ∈ P(Z), the second-order Taylor approximation ofD(T P ) around T = P is given byD for some constant η > 0 (that possibly depends on P ). In (7), T = (T 1 , · · · , T k−1 ) T , P = (P 1 , · · · , P k−1 ) T , and d χ 2 is the χ 2 -divergence defined as 2) For any P, T ∈ P(Z), the divergenceD satisfies the Pinsker-type inequalitỹ 3) The CDF of the statistic η −1 nD(t z n P ) can be approximated as for some positive sequence δ n satisfying lim n→∞ δ n = 0, where F χ 2 ,k−1 is the CDF of the chi-squared random variable χ 2 k−1 with k − 1 degrees of freedom. The following theorem characterizes β ′ and β ′′ of the divergence test for any divergenceD in Ξ.
Theorem 1 LetD ∈ Ξ and 0 < ǫ < 1. Consider the divergence test TD n (r) for testing H 0 : P against the alternative H 1 : Q, where P, Q ∈ P(Z) and P = Q. Then, the type-II error satisfies the following: Part 1: There exists a threshold value r n satisfying α n (TD n (r n )) ≤ ǫ (11) such that, as n → ∞, Part 2: For all r n > 0 satisfying (11), we have as n → ∞ where Q −1 Since the sequence δ n in (12) and (13) tends to zero as n → ∞, we have that O(max{δ n √ n, ln n}) = o( √ n). Consequently, (12) and (13) imply that, for the optimal threshold value r n , − ln β n (TD n (r n )) = nD(P Q) − nV (P Q)Q −1 Thus, Theorem 1 characterizes the first and second-order terms of the divergence test for anyD ∈ Ξ. It can be verified that Q −1 Consequently, the second-order term β ′′ of the divergence test is strictly smaller than the second-order term of the Neyman-Pearson test.
For certain divergences in Ξ, we can obtain more precise asymptotics than the one in (14) by tightening the o( √ n) term. To this end, we shall first discuss the three conditions stated in Definition 2, which we shall do one by one.

Condition 1:
WhenD is the f -divergence D f , it follows from a Taylor-series expansion of D f (T P ) around T = P that D f satisfies (7) with η = f ′′ (1) 2 [11,Th. 4.1]. Since both the α-divergence and the KL divergence D belong to the f -divergence class with f ′′ (1) = 1, we obtain thatD = {D α , D} satisfy (7) with η = 1 2 [12]. Furthermore, for the Renyi divergence of order α > 0, defined as There are many more divergences that satisfy (7), such as the Battacharya divergence, the Tsallis divergence, and the Sharma-Mittal divergence; see [10] for more details. In information geometry, such divergences are referred to as invariant divergences [10, Eq. 2.29].
Condition 2: It is well-known that the KL divergence D satisfies Pinsker's inequality [13, Lemma 11.6.1]. From [14,Th. 3], it further follows that Pinsker's inequality can be generalized to many fdivergences under some conditions on f . In particular, it follows from [14,Cor. 6] that the α-divergence satisfies a Pinsker-type inequality when 3 ≤ α ≤ 3, α = ±1: It follows from the same corollary that the Renyi divergence I α also satisfies (9). Furthermore, for any for some positive sequence a n such that a n → 0, then T −P 1 = O( √ a n ), which is sufficient to prove Theorem 1. In fact, condition 2 can be replaced by the condition that, ifD(T, P ) = O(a n ) for some positive sequence a n such that a n → 0, then T − P 1 = O( √ a n ). Condition 3: Note that this condition is a Berry-Esseen-type convergence of the statistic η −1 nD(t Z n P ) to the chi-squared distribution with k − 1 degrees of freedom. For both the α-divergence and the KL divergence, we have η = 1 2 . The following result implies that, for these divergences, (10) See [18] for more details.
From the above discussion, we conclude thatD = {D, D α } with −3 ≤ α ≤ 3, α = ±1 satisfy all three conditions in Definition 2 with δ n = 1 √ n and thus belong to the class Ξ. We thus have the following corollary to Theorem 1, which sharpens the third-order term in (14).
for testing H 0 : P against the alternative H 1 : Q, where P, Q ∈ P(Z) and P = Q. Then, the type-II error of TD n (r n ) minimized over all the threshold values r n satisfying α n (TD n (r n )) ≤ ǫ can be characterized as Note that, whenD is the KL divergence, the divergence test TD n (r) is the Hoeffding test. Hence, the above corollary recovers the second-order asymptotics of the Hoeffding test as a special case.
IV. PROOF OF THEOREM 1 A. Proof of Part 1 of Theorem 1 From (10), it follows that there exist M 0 > 0 and N 0 ∈ N such that For 0 < ǫ < 1, let Then, from (16), it follows that the type-I error is upper-bounded by ǫ: We next consider the type-II error for r n in (17). To this end, define Then, where the last step follows from [13,Th. 11.1.4]. In (18), P n denotes the set of types with denominator n and T (P ) is the type class ofP , defined as We next derive a lower bound on D(P Q) forP ∈ P n ∩AD(r n ). To this end, we shall use the following auxiliary results.
Lemma 3 For any two probability distributions Q = (Q 1 , · · · , Q k ) T and T = (T 1 , · · · , T k ) T , the secondorder Taylor approximation of the function T → D(T Q) around the null hypothesis T = P is given by Proof: See Appendix A. By the Pinsker-type inequality, we obtain that, for every T ∈ AD(r), we have T − P 1 ≤k √ r for some constantk. This implies that T − P 1 ≤k 1 √ r for some constantk 1 . Since any two norms on a finite-dimensional Euclidean space are equivalent, there exists a constant C 0 > 0 such that the Euclidean distance is bounded by Thus, for any T ∈ AD(r n ) with r n in (17), it follows that Then, for any T ∈ AD(r n ) with r n in (17), (7) and (20) and can be written as The expansion (23) implies that there exist M > 0 and N 1 ≥ N 0 such that, for all n ≥ N 1 and T ∈ AD(r n ), Next define We have the following lemma.
Lemma 4 Let r n be given in (17). Then, we have Proof: It follows from (25) that, for T ∈ AD(r n ) and n ≥ N 1 , ηd χ 2 (T, P ) − M n 3/2 ≤D(T P ) < r n . This implies that We next use (24) to lower-bound the term D(P Q) forP ∈ P n ∩ A D (r). Indeed, it follows from (24) that there exist M 2 > 0 andN 2 ∈ N such that, for all n ≥N 2 and T ∈ AD(r n ), Consequently, for all n ≥N 2 and T ∈ AD(r n ), where the last inequality follows since d χ 2 (T, P ) is non-negative.
To proceed further, let us consider the following function, defined for a probability distribution Γ = (Γ 1 , · · · , Γ k ) T ∈ P(Z) where For n ≥ N 1 andP ∈ P n ∩ AD(r n ), we have that where the last inequality follows from (26).
To compute the right-most minimum in (30), we define the following quantities: We then have the following result.
Remark 1 Since Γ * and P are probability distributions, by taking summation on both sides of (34), we obtain By the assumption of Theorem 1, we have that P = Q. Hence, D(P Q) − α i cannot be zero for all i = 1, · · · , k. This implies that there exist two distinct indices l, l ′ ∈ {1, · · · , k}, such that D(P Q)−α l < 0 and D(P Q) − α l ′ > 0. It follows that l ∈ I, which in turn yields that B is a non-empty set. Let Since r ′ n is vanishing as n → ∞, we can chooseN such that, for n ≥N , r ′ n satisfies √ r ′ n < √ V (P Q) τ with τ defined in (33). Then, (30) and (35) yield that, forP ∈ P n ∩ AD(r n ) and n ≥ N 2 max{N 1 ,N 2 ,N}, It follows that, for anyP ∈ P n ∩ AD(r n ), (27) can be further lower-bounded as Applying (39) to (18), the type-II error can be upper-bounded as β n (TD n (r n )) ≤ P ∈Pn∩AD(rn) where the last inequality follows since |P n | ≤ (n + 1) |Z| [13, Th. 11.1.1]. By taking logarithms on both sides of (40), we obtain ln β n (TD n (r n )) ≤ |Z| ln(n + 1) − nD(P Q) + n V (P Q)r ′ n + By (17) and (37), A Taylor-series expansion of √ x + δ around x > 0 yields then that where the last inequality holds since the function Q −1 χ 2 ,k−1 (·) is monotonically decreasing. It follows that (41) can be further upper-bounded as ln β n (TD n (r n )) ≤ |Z| ln(n + 1) − nD(P Q) + n V (P Q)r ′ n + Using a Taylor-series expansion of Q −1 Consequently, (44) can be expanded as ln β n (TD n (r n )) ≤ |Z| ln(n + 1) − nD(P Q) + nV (P Q) Q −1 This proves Part 1 of Theorem 1.

B. Proof of Part 2 of Theorem 1
Define for 0 < ǫ < 1 and n ∈ N, Lemma 6 For M 0 and δ n given in (16), we have Proof: For any r > 0, we can write P n D (t Z n P ) ≥ r = P n n ηD (t Z n P ) ≥ nr η .
Then, it follows from (16) that, for n ≥ N 0 and any r > 0, Substituting the value ofṙ n in (49), we get for n ≥ N 0 , Thus, by the definition of r ǫ n r ǫ n ≤ṙ n = η n Q −1 Furthermore, (50) implies that r ǫ n exists. Indeed, the set R ǫ n is lower-bounded by 0. Then, it follows from (50) that, for n ≥ N 0 , we haveṙ n ∈ R ǫ n . This implies that R ǫ n is a non-empty subset of the real numbers R that has a lower bound. Hence, by the completeness property of R, r ǫ n exists. We next derive a lower bound on r ǫ n . Leẗ Substituting the value ofr n in (49), we get for n ≥ N 0 , P n (D(t Z n P ) ≥r n ) ≥ ǫ + M 0 δ n > ǫ.
The above equation implies thatr n does not belong to the set R ǫ n . It follows from the property of the infimum that r ǫ n ≥r n = η n Q −1 Thus, from (50) and (52) we obtain η n Q −1 Taylor-series expansions of Q −1 χ 2 ,k−1 (ǫ + 2M 0 δ n ) and Q −1 For any T ∈ AD(r ǫ n ) with r ǫ n in (54), it follows from (21) that 13 Then, (7) and (20) can be written as The first equation (56) implies that there existM ′ 0 > 0 andN ′ 0 ∈ N such that, for all n ≥N ′ 0 and for T ∈ AD(r ǫ n ), Furthermore, by the definition of the χ 2 -divergence in (8) and the fact that P i < 1, i = 1, · · · , k, we have that d χ 2 (T, P ) ≥ T − P 2 2 . Since r ǫ n = O 1 n , these two inequalities imply that T − P 2 = O 1 √ n and, hence, also T − Then we have the following lemma.
Then, using (59), we have for T ∈Ā χ 2 r ǫ n η − n . Hence, we obtain T ∈ AD(r ǫ n ). From (57), we obtain that, for T ∈ AD(r ǫ n ), there exist M ′ 2 > 0 and N ′ 2 ∈ N such that If r < r ǫ n , then, by definition of r ǫ n , the type-I error α n (TD) exceeds ǫ. Hence such a threshold violates (11). We thus assume without loss of optimality that r ≥ r ǫ n . In this case, Together with Lemma 7, this implies that, for r ǫ n and n ≥ N ′ 1 , the type-II error of the divergence test TD n (r) can be lower-bounded as β n (TD n (r)) ≥ Q n (D(t Z n P ) < r ǫ n ) = z n : t z n ∈AD(r ǫ n ) By (54),r n vanishes as n → ∞. We can therefore find anÑ ′ such that, for n ≥Ñ ′ , we have that √r n < √ V (P Q) τ with τ defined in (33). To lower-bound the type-II error further, let us consider the following lemma.
V. CONCLUSIONS For the divergence test and for a large class of divergences, we established the first-order and the second-order terms of the type-II error given that the type-I error is upper-bounded by a given value. The divergence test does not require the knowledge of the distribution of the alternative hypothesis, hence, it is suitable for problems where we only have access to the distribution of the null hypothesis. The class of divergences considered in this paper includes well-known divergences such as the KL divergence and the α-divergence, and our divergence test specializes to the Hoeffding test if the chosen divergence is the KL divergence. It is well-known that the Hoeffding test is first-order optimal in the sense that its first-order term is equal to the first-order term of the Neyman-Pearson test. However, our results demonstrate that the second-order term of the divergence test for the class of divergences considered in this paper, and therefore also of the Hoeffding test, is strictly smaller than the second-order term of the optimal Neyman-Pearson test. The question whether there exists a test that only requires the knowledge of the distribution of the null hypothesis and that achieves the second-order term of the Hoeffding test for the some Q's while it achieves a higher second-order term for the remaining Q's is yet to be explored.

APPENDIX A PROOF OF LEMMA 3
For the probability distribution T = (T 1 , · · · , T k ) T and Q ∈ P(Z), the function f Q (T ) D(T P ) is a smooth function of T = (T 1 , · · · , T k−1 ) T given by The partial derivatives of f Q (·) with respect to T i , i = 1, · · · , k − 1 up to third orders are given by Consequently, the second-order Taylor approximation of f Q (T) around P is given by where the remainder term R 3 (T) in Lagrange's form is given by for Π = P + t(T − P), t ∈ (0, 1). The absolute value of this term can be upper-bounded by When T − P 2 → 0, we have that P i − δ < T i < P i + δ for an arbitrary δ > 0 and i = 1, · · · , k − 1. and Using (83), (84), and (79), one can show that, for any T satisfying 0 < T − P 2 < δ, Hence, from (82), where C ′ 1 3! C 1 (k −1) 3 and the last inequality follows since |T i −P i | ≤ T−P 2 for all i = 1, · · · , k −1. and Thus, by (88), (89), and the definition of the χ 2 -divergence, (80) can be written as as T − P 2 → 0.