Computer Science-2021.gz:143433
Computer Science
e6db8cc13e43fdea93d8e890191e6df99138eb29
Second-Order Asymptotically Optimal Universal Outlier Hypothesis Testing

We revisit the universal outlier hypothesis testing (Li et al., TIT 2014) and derive fundamental limits for the optimal test. In outlying hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated according to anomalous distributions. The nominal and anomalous distributions are unknown. We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. Specifically, we propose a threshold-based universal test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probabilities, one is that it be a non-vanishing constant and the other is that it have an exponential decay rate. For both cases, we characterize bounds on the false reject probability, as a function of the threshold, for each pair of nominal and anomalous distributions and demonstrate the optimality of our test in the generalized Neyman-Pearson sense. We first consider the case of at most one outlier and then generalize our results to the case of multiple outliers where the number of outliers is unknown and each outlier can follow a different anomalous distribution. Index Terms Second-order asymptotic approximations, Error exponents, Misclassification error, False alarm, False reject,


I. INTRODUCTION
In the outlier hypothesis testing (OHT) problem, one observes a number M of sequences. The majority of the M sequences are i.i.d. samples from a nominal distribution and the rest of the sequences are i.i.d. samples from anomalous distributions different from the nominal distribution. The task in the universal OHT problem is to design a test to discern the set of outlying sequences with high probability when both nominal and anomalous distributions are unknown. Motivated by practical applications in anomaly detection [1], we revisit the OHT problem studied in [2] when the outlier might not be present and derive the performance tradeoff between the probabilities of misclassification error, false alarm and false reject for universal tests. Furthermore, we show that such tests are optimal in the generalized Neyman-Pearson sense for both a second-order asymptotic regime and a large deviations regime. Our second-order asymptotic result provides an approximation to the finite sample performance of the tests. Throughout the paper, we consider the case where the sequences have a finite alphabet.
We first consider the case when there is at most one outlier. Under this setting, the null hypothesis is that there is no outlying sequence while a non-null hypothesis specifies the index of the outlying sequence. Li et al. [2,Theorem 5] showed that the error probability under non-null hypothesis decays exponentially fast and that the error probability under null hypothesis vanishes as the length of observed sequenced tends to infinity for the threshold based generalized likelihood ratio test [2,Eq. (25)]. Furthermore, the authors of [2] showed the optimality of their test when the number of observed sequences M tends to infinity. A natural question arises: whether or not it is possible to claim optimality for a universal test when the number of observed sequences M is finite and when the length of the observed sequences is non-asymptotic. Our first contribution sheds lights on the positive answer for this question. To do so, we decompose the error probability under the non-null hypothesis into the misclassification error probability and the false reject probability, where the false reject event corresponds to falsely claiming that no outlier exists and the misclassification error event corresponds to falsely claiming that a nominal sequence is an outlier. The error probability under the null hypothesis is denoted the probability of false alarm, which is the probability of falsely claiming that an observed sequence is an outlier when no outlier is present. We show that a test, inspired by sequence classification with empirical statistics [3], [4], is optimal under certain conditions, from a second-order or a first-order asymptotic perspective.
We then generalize our results to the case where the number of outliers is unknown and each outlying sequence can be generated from a potentially different anomalous distribution. When the number of outliers is known, Li et al. [2,Theorem 10] derived an achievability decay rate of the error probabilities under each hypothesis and showed asymptotic optimality of their result when the number of the sequences M tends to infinity, when the lengths of sequences n tend to infinity and when all the outlying sequences are generated from the same anomalous distribution. Furthermore, when the number of outliers is unknown and when each outlier is generated from the same anomalous distribution, Li et al. [2,Theorem 10] showed that when the null hypothesis is not taken into account, a generalized likelihood ratio test is exponentially consistent. However, the authors of [2] did not provide characterizations of the exponent. One might wonder whether it is possible to provide characterizations of the performance of a universal test where the number of outliers is unknown and where each outlier can be generated from a different anomalous distribution. Our second contribution provides a positive answer to this question and also demonstrates the optimality of the universal test in the generalized Neyman-Pearson sense.

A. Main Contributions
Our main contribution is an analysis of the tradeoff among probabilities of misclassification error, false reject and false alarm probabilities for universal tests in the outlier hypothesis testing problem. For the case with at most one outlier, our results complement [2,Theorem 5] by proposing a new threshold-based universal test, providing a second-order asymptotic approximation to the performance of the universal test with finite length sequences and relaxing the conditions for which the optimality of a universal test can be claimed using a weaker condition inspired by statistical classification [3]. Furthermore, asymptotically, our results in Theorem 3 complement [2, Proposition 4] by identifying a sufficient condition on the pair of nominal and anomalous distributions under which the universal test ensures exponential decay of all three kinds of error probabilities. Finally, the information theoretical quantity that characterizes the performance tradeoff is shown to be a generalized Jensen-Shannon divergence, which is significantly different from the constrained sum of KL divergences in [2,Eq. (26)] or the Bhattacharyya distance in [2,Corollary 6]. For the case admitting multiple outliers, we analyze the performance of a universal test ignorant of the number of outliers where each outlier can be drawn from a different distribution. We note that our results close an existing gap in the theory developed in [2, Section IV], providing explicit equations for the asymptotic performance of the outlier test.
For the case with at most one outlier, we propose a threshold-based universal test that ensures the exponential decay of misclassification error and false alarm probabilities, called the homogeneous error exponent, which simultaneously upper bounds the false reject probabilities as a function of the threshold for any pair of nominal and anomalous distributions. We first derive a second-order asymptotic result that provides an approximation to the performance of the test when the length n of each observed sequence is finite. In particular, we show that if the threshold of the test is upper bounded by a certain function of n and the nominal and anomalous distributions (P N , P A ), the false reject probability is essentially upper bounded by a constant ε ∈ (0, 1), say 10 −9 . Furthermore, among all tests that can ensure an exponential decay of misclassification error and false alarm probabilities for all pairs of nominal and anomalous distributions, our proposed test has the same homogeneous error exponent and the smallest non-vanishing false reject probability under any pair of nominal and anomalous distributions. This way, the optimality in the above generalized Neyman-Pearson sense of our universal test is ensured for any finite number of observed sequences M (see [4] for a similar result in the context of statistical classification).
In anomaly detection problems, it may be necessary to maintain a vanishingly small false reject probability when the length of each observed sequence becomes large. To resolve this problem, asymptotically when the lengths of the observed sequences tend to infinity, we derive the exponential decay rate of the false reject probability as a function of the threshold in the universal test. We show, in particular, that the homogeneous error exponent is the threshold of the test for any pair of nominal and anomalous distributions. This way, we establish that, as long as the nominal and anomalous distribution is far in certain distance measure, the universal test is exponentially consistent as all three kinds of error probabilities decay to zero exponentially fast. Conversely, we show that among all tests that can enure the same speed of exponential decay of misclassification error and false alarm probabilities for all pairs of nominal and anomalous distributions, our proposed test guarantees the largest exponential decay rate for the false reject probability regardless the pair of nominal and anomalous distributions.

B. Related Works
The most closely related work to ours is that of [2], where the authors formulated the outlier hypothesis testing problem, and derived optimal results under constraints on the number of observed sequences, the length of observed sequences and the number of anomalous distributions. Other related work on outlier hypothesis testing is the following. A low complexity test for outlier hypothesis testing was proposed and analyzed in [5]. A distribution free test based on maximum mean discrepancy was proposed in [6] and shown to be exponentially consistent when the number of outliers is known under a certain condition on the number of observed sequences and the length of each sequence. Readers may also refer to [7] for a comprehensive survey of the commonly made assumptions on distributions, definitions of outliers, types of tests, applications and results in outlying sequence detection. Furthermore, the results of [2] were generalized to a sequential setting in [8] where each sequence is observed symbol by symbol until the test is confident enough to make a decision. In [9], the authors studied the quickest outlier detection problem where outlying sequences follow an anomalous distribution after a certain unknown change time and universal tests were proposed to identify the outliers. Finally, in [10] for detecting an outlier from M sequence streams, the authors studied a special case of the sequential outlier detection problem where at each time only a subset of all sequence symbols can be observed.
Since our proof technique is inspired by statistical classification, we also mention a few works in this domain. In [3], the author studied a binary sequence classification problem and showed that a certain test using empirical distributions of training and testing data is asymptotically optimal with exponentially decreasing misclassification probabilities. The result in [3] was generalized to classification of multiple testing sequences in [11] and to distributed detection in [12]. Finally, a finite sample analysis for the setting of [3] was provided in [4].

C. Organization for the Rest of the Paper
The rest of the paper is organized as follows. In Section II, we set up the notation, formulate the universal outlying sequence detection problem with at most one outlying sequence, propose fundamental limits and present our main results concerning the performance of optimal universal tests. In Section III, we generalize our results to the case of multiple outlying sequences where the number of outlying sequences is known and each outlying sequence is generated according to a potentially different anomalous distribution. Finally, we conclude the paper and discuss future research directions in Section IV. The proofs of all theorems are deferred to appendices.

Notation
Random variables and their realizations are in upper (e.g., X) and lower case (e.g., x) respectively. All sets are denoted in calligraphic font (e.g., X ). We use superscripts to denote the vectors, like X n := (X 1 , . . . , X n ). All logarithms are base e. The set of all probability distributions on a finite set X is denoted as P(X ). Notation concerning the method of types follows [13]. Given a vector x n = (x 1 , x 2 , . . . , x n ) ∈ X n , the type or empirical distribution is denoted asT x n (a) = 1 n n i=1 ½{x i = a}, a ∈ X . The set of types formed from length-n sequences with alphabet X is denoted as P n (X ). Given P ∈ P n (X ), the set of all sequences of length n with type P , the type class, is denoted as T n P . We use R, R + , and N to denote the set of real numbers, non-negative real numbers, and natural numbers respectively. Given any number a ∈ N, we use [a] to denote the collection of natural numbers between 1 and a.

A. Preliminaries
Given a sequence of distributions Q = (Q 1 , . . . , Q M ) ∈ P(X ) M , for each i ∈ [M ], define the following linear combination of KL Divergence terms between a single distribution and a mixture distribution where M i is defined the as the set of integers in [M ] except i. The distance measure G i (Q) will be used to construct our test. To present our results on the characterization of the tradeoff among the probabilities of misclassification error, false alarm and false reject, several definitions that generalize the divergence are needed. Given any pair of distributions (P N , P A ), for any x ∈ X , define the two information densities (log likelihood ratios): The following linear combinations of the expectations and variances of these two information densities pis critical in presenting our main results: Furthermore, we need the following covariance function of the information densities Then, the covariance matrix V M (P N , For any k ∈ N, Q k (x 1 , . . . , x k ; µ, Σ) is the multivariate generalization of the complementary Gaussian cdf defined as follows: where N (x; µ; Σ) is the pdf of a k-variate Gaussian with mean µ and covariance matrix Σ [14]. Furthermore, for any k ∈ N, we use 1 k to denote a row vector of length k with all elements being one and we use 0 k similarly. The complementary Gaussian cdf with covariance matrix V M (P N , P A ) and mean values GD M (P N , P A ) bounds the probability of false reject. Finally, given any λ ∈ R + and any pair of distributions (P N , P A ), for each i ∈ [M ], define the following quantity The above quantity is key to characterize the exponential decay rate of the false reject probability.

B. Problem Formulation
We start by assuming that there is at most one outlying sequence. Consider a set of M observed sequences X n := {X n 1 , . . . , X n M } and a pair of nominal distribution P N and an anomalous distribution P A defined on the finite alphabet X . All sequences, with at most one exception, are generated i.i.d. from P N . The goal of outlying hypothesis testing is to discern the outlier that is generated i.i.d. from the anomalous distribution P A ∈ P(X ) if an outlier is present. Throughout this paper, we assume that both the nominal distribution P N and the anomalous distribution P A are unknown. Furthermore, to avoid degenerated cases, similar to [2], we consider only distributions (P N , P A ) with identical supports.
Under this setting, the objective of detecting the potential outlier is equivalent to making a correct decision in the (M +1)-ary hypothesis testing problem with following hypotheses: : the i-th sequence X n i is the outlying sequence, i.e., X n i ∼ P A and X n j ∼ P N for all j ∈ M i ; • H r : there is no outlying sequence, i.e., X n j ∼ P N for all j ∈ [M ], where H r denotes the null hypothesis.
The main task in the above OHT problem is to design a decision rule (test) φ n : X Mn → {H 1 , . . . , H M , H r } with "good" performance be specified. Any test φ n partitions the sample space X Mn into M + 1 disjoint regions: where X Mn ∈ A i (φ n ) favors the non-null hypothesis H i and a reject region A r (φ n ) = (∪ i∈[M] A i (φ n )) c where X Mn ∈ A i (φ n ) favor the null hypothesis H r .
Given any test φ n and any pair of nominal and anomalous distributions (P N , P A ) ∈ P(X ) 2 , the performance of the test φ n is evaluated by the following misclassification error, false reject and false alarm probabilities: where for each i ∈ [M ], we define P i {·} := Pr{·|H i } where X n i is distributed i.i.d. according to P A and for X n j is distributed according to P N for each j ∈ M i and we define P r {·} := Pr{·|H r } where all sequences are generated i.i.d. from P N for all i ∈ [M ]. Consistent with the literature on hypothesis testing (e.g., [15]), we define β i (φ n |P N , P A ) and ζ i (φ n |P N , P A ) as type-i misclassification error and false reject probabilities, respectively, and we define P fa (φ n |P N , P A ) as the false alarm probability. Our main results characterized the tradeoff among the probabilities of misclassification error in (10), false rejection in (11) and false alarm in (12) under different settings.

C. A Universal Test
Throughout the section, we use a threshold-based test that takes the types of each of the observed sequences as inputs and it outputs a decision among the (M + 1) hypotheses. Given M observed sequences x n = (x n 1 , . . . , x n M ) and any positive real number λ ∈ R + , the universal test operates as follows: where the scoring function S i (x n ) is where G i (·) is the function defined in (1) as the sum of the KL divergence of the empirical distribution of each sequence x n j , with the exception of x n i . Note that the threshold λ can be replaced with a function of sequence length n, e.g., λ n to emphasize the dependence of the threshold on n. This way, all our results still hold but necessary limit operations are required.
We first informally explain the test in (14) from an asymptotic point of view. Intuitively, if x n i is the anomalous sequence that is generated from the unknown distribution P A , then as the length of each observed sequence n increases, using the weak law of large numbers, we know that the empirical distribution of x n i tends to P A and the empirical distribution x n j for each j ∈ M i tends to the nominal distribution P N . Thus, the scoring function S i (x n ) tends to zero and the scoring function of S j (x n ) for each j ∈ M i tends to GD M (P N , P A ), which is strictly large than zero if P N = P A . Therefore, for any threshold λ that is positive but essentially less than GD M (P N , P A ), with high probability, it is possible to identify the outlier if it exists. On the other hand, if there is no outlier, then with the same logic, for each i ∈ [M ], the scoring function S i (x n ) tends to zero and naturally the null hypothesis is decided for any positive threshold λ. Therefore, the test in (13) is consistent asymptotically for any P N = P A such that the threshold λ < GD M (P N , P A ).
Next we explain why the test is universal with guarantees on all three error probabilities. Note that the threshold λ can be arbitrary and it is independent of the unknown nominal and anomalous distributions (P N , P A ). This is the reason why the above test is universal. However, the performance of the test under a particular pair of (P N , P A ) does depend on (P N , P A ). Our main contribution in this section lies in the analysis of the performance of the universal test in (1) for any (P N , P A ). Specifically, we show that both misclassification and false alarm probabilities decay exponentially fast, essentially with the speed of the threshold λ, and we bound the false reject probabilities under two different regimes. Furthermore, we demonstrate the optimality of the above test for both regimes in a generalized Neyman-Pearson sense to be specified.
Finally, we remark that the scoring function S i (x n ) was also used in [2,Eq. (15)] to construct a test for the case without the null hypothesis. However, for the case with the null hypothesis, a threshold-based test was given in [2,Eq. (25)] where the test relies on the pairwise difference of log likelihoods of the joint empirical distributions under different hypotheses. Note that the test in [2,Eq. (25)] is different from our test in (13) that uses different empirical distributions.

D. Second-Order Asymptotic Approximation to the Non-Asymptotic Performance
Our first set of results concern the characterization of the performance of the universal test in (13) in terms of probabilities of misclassification error, false alarm and false reject probabilities in the second-order asymptotic regime. We first demonstrate a non-asymptotic achievability result and then prove that such a result is optimal up to second-order, in a generalized Neyman-Pearson sense, in the spirit of [3], [4].
1) Achievability: Theorem 1. For every pair of nominal and anomalous distributions (P N , P A ) ∈ P(X ) 2 , given any positive real number λ ∈ R + , the universal test in (13) satisfies The proof of Theorem 1 is provided in Appendix A. We make several remarks. For any finite number of observed sequences M , as the length of each observed sequence n increases, both the maximal classification error (cf. (10)) and the false alarm (cf. (12)) probabilities decay exponentially fast with a speed lower bounded given by the threshold λ in the universal test in (13), i.e., Furthermore, asymptotically, the upper bound on the maximal false reject probability (cf. (11)) converges to lim n→∞ 1 − , which is a function of the threshold λ and the pair of distributions (P N , P A ). To better understand the seemingly complicated upper bound on the false reject probability, for any ε ∈ (0, 1), we can define Then the upper bound in (17) implies that if the threshold λ satisfies that then the maximal false reject probability under (P N , P A ) is asymptotically upper bounded by ε, for any ε ∈ (0, 1), say as small as 10 −9 . If the threshold λ further satisfies that λ < GD M (P N , P A ), then the false reject probability converges to zero. As we shall show later (in Theorem 3), actually, if λ < GD M (P N , P A ), the false reject probability converges to zero exponentially fast with a speed lower bounded by a explicit function of the threshold λ. We assume that there are M observed sequences and that only one sequence is an outlier. We plot λ * (n, ε|P N , P A ) without the O(log n/n) term.
Note that λ * (n, ε|P N , P A ) is a critical bound for the threshold in the test, which trades off a lower bound λ on the exponential decay rates of misclassification error and false alarm probabilities and a non-vanishing upper bound ε ∈ (0, 1) for the maximal false reject probability. Such a result is known as a second-order asymptotic result in information theory since it provides the second dominant term beyond the leading constant term GD M (P N , P A ) asymptotically as n → ∞. Furthermore, as shown in non-asymptotic analysis for channel coding [16], second-order asymptotic results often provide good approximation to the performance for finite length n. We provide a numerical example to illustrate the validity of this claim in Section II-D3. Furthermore, the result in (20) implies a phase transition phenomenon for our universal test. In particular, if the threshold λ is greater than GD M (P N , P A ), then asymptotically the false reject probabilities tend to one. On the other hand, if λ < GD M (P N , P A ), then asymptotically the false reject probabilities vanish. See Figure 1 for a numerical illustration.
Theorem 1 also captures the influence of the number of sequences M on the performance of the universal test (13). To study the asymptotic case of M → ∞, we need to make an assumption on the order of M and n. In fact, as long as lim n→∞ log(M) n → 0, the asymptotic lower bound in (18) holds. Intuitively, when one has a larger number of sequences, it should be easier to learn the nominal distribution and thus achieve better performance. This should imply that as M increases, the upper bound λ * (n, ε|P N , P A ) on the homogeneous error exponent λ in (20) increases as well. To verify this intuition, the second-order result in (20) for Bernoulli distributions with different values of M is plotted in Figure 2. The influence of M on the performance of the universal test in (13) is dominated by GD M (P N , P A ). In fact, Thus, as the number of sequences M increases, the performance of the test in (13) improves. In the extreme case, as M → ∞, we have This implies that the maximum asymptotic decay rate of the misclassification and false alarm probabilities of the universal test under any pair of nominal and anomalous distributions (P N , P A ) in (13) is D(P A P N ) as the number of sequences M tends to infinity, assuming that the false reject probability does not tend to one. Finally, we remark that Theorem 1 is relevant to M -ary hypothesis testing with empirically observed statistics [3], [4], [11]. In fact, our proof technique for Theorem 1 can be used to strengthen [4,Theorem 4.1] by removing the condition in [4, Section 4.2] on the uniqueness of the minimizing distribution for the scoring function in [4,Eq. (4.4)]. However, the results in [3], [4], [11] do not directly apply to our setting since the two problems are significantly different. In the M -ary hypothesis testing problem with empirically observed statistics, one is given M training sequences and one test sequence. The task there is to identify the true distribution of the test sequence among the empirical distributions of the training sequences. In contrast, in the outlying sequence detection problem addressed in Theorem 1, we are given M sequences and our task is to identify the potential outlier if it exists.
2) Converse: With the above achievability result on the performance of the universal test in (13), it remains to show that the test is in fact optimal in the generalized Neyman-Pearson sense. To prove the following, we use arguments similar to those of Gutman [3].
Theorem 2. Given any positive real number λ ∈ R + , let the test φ n satisfy the following for all pairs of nominal and anomalous distributions ( Then for any pair of nominal and anomalous distributions (P N , P A ), the minimal false reject probability satisfies The proof of Theorem 2 is provided in Appendix B. The result in Theorem 2 holds for any number of observed sequences M and when the length n of each observed sequence n is such that O( log n n ) and O( 1 √ n ) can be neglected. Furthermore, Theorem 2 implies that the test in (13) is optimal in the generalized Neyman-Pearson sense. Specifically, among all tests that ensure exponential decay of the maximal misclassification error and false alarm probabilities at a speed no less than λ, the universal test in (13) achieves the minimal false reject probability in a second-order asymptotic sense such that lim inf 3) A Numerical Example: We present a numerical example to illustrate Theorem 1. Consider the binary alphabet X = 0, 1 and M = 4. Assume that there is exactly one outlier sequence and let Bern(p) denote a Bernoulli distribution with parameter p ∈ (0, 1). For any (p, q) ∈ (0, 1) 2 such that p = q, we set the nominal distribution P N as Bern(p) and the anomalous distribution P A as Bern(q). We make the above nominal and anomalous distribution assumptions in order to demonstrate tightness of the inequality (20) in the theorem. For the above example, the information densities (cf. (2) and (3)) satisfy Furthermore, where To verify the tightness of our theoretical result, we need to assume a pair of nominal and anomalous distributions to permit the calculation of the false reject probability. For this purpose, the nominal distribution is assumed to be P N = Bern(0.2) and the anomalous distribution is assumed to be P A = Bern(0.4). The error bar denotes two standard deviations below and above the mean value. As observed, the simulated false reject probability approaches the target value ε as the lengths of observed sequences become moderate. This implies that our theoretical characterization in Theorem 1 is tight for this numerical example.
Similarly, we can also calculate Cov M (P N , P A ) (cf. (6)) and thus the covariance matrix V M (P N , P A ).
In Figure 3, the simulated false reject probability of our test in (13) From the theoretical result in Theorem 1 and the implication in (20), such a choice of the threshold ensures that the false reject probability is upper bounded by the parameter ε for any pair of anomalous distributions (P N , In particular, when (P N ,P A ) = (P N , P A ), the false reject probability should be roughly ε. To verify the tightness of our theoretical result, we simulate the false reject probability under (P N , P A ). In our simulation, for each data point, our test is run independently 10 7 times and the false reject probability is calculated as the ratios of false alarms. From Figure 3, we observe that the simulated false reject probability meets the desired value when the length of the sequences is moderate. This illustrates that the second-order asymptotic result in (20) provides a good approximation to the performance of the universal test for moderate n.

E. Asymptotic Decay Rates
For accurate anomaly detection, all error probabilities should be small to ensure that no outlier is missed or identified incorrectly. Thus, a constant or even vanishing false reject probability might not suffice when the length of the observed sequence n is extremely large. In the following theorem, we obtain an asymptotic tradeoff between the exponents of false reject probabilities and the homogeneous error exponent for misclassification error and false alarm probabilities. Recall the definition of LD i (λ, P N , P A ) in (9).
Theorem 3. For every pair of nominal and anomalous distributions (P N , P A ), given any positive real number λ ∈ R + , the universal test in (13) satisfies: Conversely, given any positive real number λ ∈ R + , for any test φ n such that for all pairs of nominal distributions (P N ,P A ), under any pair of nominal and anomalous distributions (P N , P A ), the false reject exponent satisfies The differences between the proof of Theorem 3 and the proofs of Theorems 1, 2 lie in the analysis of the false reject probability. See Appendix C.
To ensure that all three kinds of error probabilities decay exponentially, we need min{λ, (9)) is non-increasing in λ and LD i (λ, P N , P A ) = 0 if and only if λ ≥ GD M (P N , P A ) (cf. Appendix H for justification). Therefore, for any pair of nominal and anomalous distributions (P N , P A ) such that GD M (P N , P A ) > 0 and λ < GD M (P N , P A ), all three kinds of error probabilities decay to zero exponentially fast. However, in practice, one cannot know either P N or P A . Thus, the above result implies that one can choose a smaller threshold λ to ensure exponentially consistent performance under a larger set of distributions. When one has some information about the underling true pair of distributions (P N , P A ), one can choose a large enough λ to ensure good homogeneous error exponent and a positive false reject exponent.
We further discuss the tradeoff between the false reject exponent LD i (λ, P N , P A ) and the homogeneous error exponent λ under each hypothesis. Specifically, one might wonder what value is taken on by the largest false reject exponent given any positive λ. In Appendix H, we show that and thus provide an answer to the above question. Note that the right hand side in (35) The converse part states that the universal test in (13) is also optimal in the generalized Neyman-Pearson sense when the false reject probabilities decay exponentially fast. Specifically, among all tests that ensure exponential decay of misclassification error and false alarm probabilities for all possible pairs of nominal and anomalous distributions, the universal test in (13) has the largest false reject exponent under any pair of nominal and anomalous distributions.

III. CASE OF MULTIPLE OUTLYING SEQUENCES
In this section, we generalize the results in Section II to the case of multiple outlying sequences where each outlying sequence can be generated according to a potentially different anomalous distribution. We assume that the number of outliers is unknown but less than half of total number of the observed sequences and then study the performance a universal test, which generalizes (13). Furthermore, we demonstrate the optimality of such test in the generalized Neyman-Pearson sense.

A. Preliminaries
We first present necessary definitions. Note that the definitions here generalize those in Section II-A.
Then, define the union of subsets S over t ∈ [T ] as follows: Given a sequence of distributions Q = (Q 1 , . . . , Q M ) ∈ P(X ) M and each B ∈ S, analously to (1), define the following linear combination of KL divergence terms where M B is defined as the set of elements that are in and, parallel to (2) and (3), define the following information densities (log likelihoods) Analogously to (4) to (6), define the following linear combinations of expectations and variances of information densities: For simplicity, given any (B, C) ∈ S 2 and any variables (x 1 , . . . , x M ), let For ease of latter presentation, let S B denote the set S \ {B}, i.e., {C ∈ S : C = B}. Furthermore, let the elements in S B be ordered as Analogously to (7), define a covariance matrix V(B, P N , The complementary cdf Q k (·) in (8), together with GD(B, C, P N , P B ) and V(B, P N , P B ), will be critical to upper bound the false reject probabilities. Finally, given any λ ∈ R + and any tuple of distributions P B = (P N , P A,1 , . . . , P A,T ) ∈ P T (X ), for each B ∈ S, define the following quantity: The quantity LD B (λ, P N , P B ) will characterize the false reject exponent under each hypothesis.

B. Problem Formulation
Assume that there are at most T = ⌈ M 2 − 1⌉ outlying sequences out of M observed sequences X = (X n 1 , . . . , X n M ). In the outlier hypothesis testing problem with at most T outliers, the task is to decide whether there are outliers and identify the set of outlying sequences if any exist. We assume that each outlying sequence is generated i.i.d. according to a possibly different anomalous distribution. Specifically, let P T := (P A,1 , . . . , P A,T ) be a collection of T anomalous distributions that are different from the nominal distribution P N , all defined on the finite alphabet X with the same support. Furthermore, for any B ∈ S, let P B denote the collection of distributions (P 1 , . . . , P |B| ). When B ∈ S denotes the index of the outlying sequences, for any l ∈ B, X n l is generated i.i.d. from P A,B(t) . Recall that  B (l) denotes l-th largest element in B. Recall that S = t∈[T ] S. Since the exact number of outliers is unknown, there are in total |S| + 1 = t∈[T ] M t + 1 possible configurations of outlying sequences. Formally, the task is to design a test φ n : X Mn → {{H B } B∈S , H r } to classify between the following |S| + 1 hypotheses: • H B where B ∈ S: the set of outlying sequences are sequences X n j with j ∈ B; • H r : there is no outlying sequence. Similarly to Section II, the null hypothesis is introduced to model the case when there is no outlier among all M observed sequences.
Given any test φ n , under any tuple of nominal and anomalous distributions (P N , P T ) = (P N , P A,1 , . . . , P A,T ), the performance of φ n is evaluated by the following misclassification error, false reject and false alarm probabilities: where B ∈ S denotes the set of indices of outliers, and we define P B (·) := Pr{·|H B } where for i ∈ M S , X n i is generated i.i.d. from the nominal distribution P N and for i ∈ B, X n i is generated i.i.d. from an nominal distribution P A,B(i) , finally we define P r (·) := Pr{·|H r }, where all sequences are generated i.i.d. from the nominal distribution P N .

C. A Universal Test
Throughout the section, we use a threshold-based universal test that takes the empirical distribution of each observed sequence as the input and outputs a decision among all hypotheses.
Given M observed sequences x n = (x n 1 , . . . , x n M ) and any positive real number λ, the universal test operates as follows: where S B = {C ∈ S B } and S C (·) is the scoring function defined as which measures the sum of KL divergence between the empirical distribution of each sequence x n i with i / ∈ B relative to the average of the empirical distribution of all sequences x n j where j / ∈ B. For the special case of T = 1, the test in (51) reduces to the test in (13).
We first provide intuition into why the above test should be asymptotically consistent. Assume that B ∈ S denotes the set of indices of the outliers and for each l ∈ B, the outlier x n l is generated i.i.d. from P A,B(l) . Asymptotically as n tends to infinity, for any sequence x n i where i / ∈ B, the empirical distributionT x n tends to the nominal distribution P N and for each x n i where i ∈ B, the empirical distributionT x n tends to P A,B(i) . Therefore, given any C ∈ S B , the scoring function S C (x n ) converges to GD(B, C, P N , P B ) and S B (x n ) converges to zero. Note that GD(B, C, P N , P B ) > 0 for any P B where P A,j = P N for all j ∈ [|B|]. Thus, asymptotically, the set of outliers B can be identified if λ < min C∈SB GD(B, C, P N , P B ). On the other hand, when there is no outlier, for each B ∈ S, the scoring function S B (x n ) tends to zero and thus, with any positive threshold λ, the null hypothesis is decided. Therefore, the universal test in (51) is consistent asymptotically for any set of outlier indices B ∈ S and for any tuple of distributions P B where P A,j = P N for all j ∈ [|B|] such that the threshold λ < min C∈SB GD(B, C, P N , P B ).
We next explain briefly the universality of the test and its associated theoretical guarantees on the error probabilities. As in the previous case of at most one anomalous sequence, the test in (51) is universal since λ can be selected without knowledge of the distributions. However, the performance of such a test under a particular tuple of nominal and anomalous distributions does depend on P B where B ∈ S denotes the set of indices of the outliers. Our contribution in this section is two fold. We first show that the universal test in (51) has misclassification error and false alarm probabilities that decay exponentially, with a lower bound on the decay rate depending on λ. Furthermore, we bound the false reject probability as a function of λ in two regimes where the false reject probability is either upper bounded by a constant or decays exponentially. We also demonstrate the optimality of the test in (51) in the generalized Neyman-Pearson sense under both regimes.
The statistic in (38) was also used in [2, Eq. (37)] to construct a test when the number t of outliers is known and when there is no null hypothesis. In contrast, the universal test in (51) does not assume any knowledge of the number of outliers, and in addition, incorporates a null hypothesis to include the possibility of no outliers.

D. Second-Order Asymptotic Approximation to the Non-Asymptotic Performance
Our first set of results concern the characterization of the performance tradeoff among misclassification error, false alarm and false reject probabilities. Specifically, we first provide an achievability result, where the performance of the universal test in (51) is characterized in terms of misclassification and false alarm probabilities that decay exponentially fast when the false reject probability is upper bounded by a function of the threshold λ. Furthermore, we demonstrate the optimality of the test in (51) in the generalized Neyman-Pearson sense.
The proof of Theorem 4 is a generalization of the proof of Theorem 1 and is given in Appendix D.
Similarly to the result given in Theorem 1, when the number of outliers M is finite, both misclassification and false alarm probabilities decay exponentially fast, with a speed lower bounded by λ asymptotically when n tends to infinity. On the other hand, the false reject under each hypothesis H B is upper bounded by a function of λ and critical quantities GD(B, C, P N , P B ) and V(B, P N , P B ). Note that the threshold λ trades off the lower bound on the decay rate of the homogeneous error exponent of the misclassification and false alarm probabilities and the upper bound on the false reject probability. If λ increases, the homogeneous error exponent increases while the false reject probability increases as well. This implies that better performance in misclassification error and false alarm probabilities leads to a worse in false reject probabilities.
Asymptotically as n → ∞, if the threshold λ < min i∈[|S|−1] GD(B, C i , P N , P B ), then the false reject probability under hypothesis H B vanishes. One might also be interested in the more practical non-asymptotic case where n is finite. Obtaining the exact solution to such case is almost impossible. However, a second-order asymptotic approximation to the non-asymptotic performance is possible using the result in (55). For this purpose, we define If the threshold λ satisfies that then as the blocklength n increases, the upper bound on the false reject probability tends to ε ∈ (0, 1). The second-order asymptotic upper bound in (58) provides further characterization beyond the first-order asymptotic constant term GD(B, P N , P B ). The second-order asymptotic upper bound on λ trades off the homogeneous error exponent with any any non-vanishing false reject probability ε ∈ (0, 1) beyond the vanishing case with ε → 0 implied by a first-order asymptotic analysis. Finally, we discuss the influence of the number of observed sequences M on the performance of the universal test in (51). As demonstrated in the above remark, GD(B, P N , P B ) is the critical quantity that is related with the performance of the test. Thus, it suffices to study the properties of GD(B, P N , P B ) as a function of M under each hypothesis H B . However, it is challenging to obtain closed form equations for the dependence of GD(B, P N , P B ) on M when each outlier is generated from a unique anomalous distributions. Thus, we specialize our results to the case where all anomalous distributions are the same and given by P A . Under this assumption, one can verify that where P t,l mix In the following theorem, it is shown that the universal test in (51) is optimal in the generalized Neyman-Pearson sense for second-order asymptotic analysis.
Theorem 5. Given any λ ∈ R + , for any test φ n such that for all tuples of nominal and anomalous distributions (P N ,P T ), then for any tuple of nominal and anomalous distributions (P N , P T ), for each B ∈ S, The proof of Theorem 5 is similar to that of Theorem 2 and only salient differences are emphasized in Appendix E.

E. Asymptotic Decay Rates
We next study the case where the false reject probability decays exponentially fast as well and thus characterize the tradeoff between the false reject exponent and the homogeneous error exponent of the misclassification error and false alarm probabilities. Recall the definition of LD B (λ, P N , P B ) in (47).
Theorem 6. For any nominal distribution P N and anomalous distributions P T = (P A,1 , . . . , P A,T ), given any positive real number λ ∈ R + , the universal test in (51) satisfies that for each B ∈ S, Conversely, for any test that ensures the homogeneous exponential decay rate of the misclassification error and false alarm is no less than λ for all tuples of nominal and anomalous distributions, under any nominal distribution P N and anomalous distributions P T = (P Therefore, if the threshold λ < min B∈S GD(B, P N , P B ), then regardless of the number of outliers, the misclassification error, the false alarm and false reject probabilities decay exponentially fast for any tuple of distributions (P N , P T ) such that min B∈S GD(B, P N , P B ) is strictly positive, which is almost always true for finite alphabet sequences.

IV. CONCLUSION
We revisited the universal hypothesis testing problem studied by Li et al. in [2] and derived performance guarantees for universal tests when there are potentially multiple outliers. In particular, we first study the case with at most one outlier and then generalize our results to the case where there are multiple outliers, the number of outliers is unknown and each outlier can be generated from a unique anomalous distributions. For both cases, we proposed a universal test, analyzed its performance in terms of the tradeoff among the misclassification error, false alarm and false reject probabilities. Furthermore, we demonstrate the optimality of the test in the generalized Neyman-Pearson sense proposed by Gutman [3]. Our results have brought new insights beyond [2] in several aspects, including the design of a second-order asymptotic optimal test, the dominant factors affecting performance of a test and a second-order approximation to the finite sample size approximation using recently proposed finite blocklength information theoretical tools [13], [16].
There are several avenues for future research. Firstly, it might be interesting to study tests that can ensure exponential decay misclassification error probabilities for any pair of nominal and anomalous distributions and simultaneously ensure that the false alarm and false reject probabilities are upper bounded by a constant for all pairs of nominal and anomalous distributions. Secondly, it would be interesting to study the optimality of tests in regimes other than the generalized Neyman-Pearson sense as demonstrated in this paper. For example, whether the universal tests in this paper are optimal in the finite sample regime for a set of nominal and anomalous distributions, which would be stronger that the asymptotic guarantees provided by Theorems 3 and 6. Thirdly, it would be valuable to extend our theory to the scenario where each nominal sample is generated from a potentially different distribution in a neighborhood of a fixed distribution and then derive the performance of the optimal test, similarly to [17]. Fourthly, one might generalize our results to the case of continuous alphabet where each observed sequence is generated i.i.d. from a probability distribution function, e.g., a Gaussian distribution. Finally, it would be worthwhile to consider a sequential setting by incorporating ideas from [8] to derive second-order asymptotic limits of an optimal sequential test.

A. Proof of Theorem 1
Recall the definitions of information densities in (2) and (3). Given any pair of distributions (P N , P A ), define the following linear combination of the third absolute moment of information densities h(x n ) := min Note that i * (x n ) denotes the index of the minimal scoring function (unique with high probability as we shall show) and h(x n ) denotes the value of the second minimal value of the scoring functions. Using these two definitions, our proposed test in (13) is equivalently expressed as follows: We first analyze the misclassification error probabilities of our test ψ n (·) under each hypothesis. Recall that we use Q to denote a collection of M distributions (Q 1 , . . . , Q M ) defined on the alphabet X . For any pair of nominal and anomalous distributions (P N , P A ) and for each i ∈ [M ], we can upper bound the type-i misclassification error probability as follows: ≤ exp(−nλ) where (72) follows from definitions of i * (x n ) in (68) and h(x n ) in (69) which indicate that S i (x n ) ≥ h(x n ) > λ under the condition that i * (x n ) = i and h(x n ) > λ; (73) follows since under hypothesis H i , the i-th sequence X n i is generated i.i.d. according to the anomalous distribution P A while all other sequences are generated i.i.d. according to the nominal distribution P N ; (74) follows from the definitions of the scoring function S i (·) in (14) and G i (·) in (1) and method of types [18,Chapter 11]; (76) follows since for any sequence of distributions Q = (Q 1 , . . . , Q M ) and any distributionP N , the following equalities hold (77) follows since the size of the type class |T n Qj | ≤ exp(nH(Q j )); (78) follows since and (79) where (88) follows since when i * (X n ) = i, h(X n ) = min j∈Mi S j (X n ) and (92) follows from the steps analogously to those leading to the result in (80). Finally, we next analyze the false reject probabilities for any (P N , P A ). For this purpose, we need the following definition of typical sequences for each i ∈ [M ]: 16 Using Chebyshev's inequality (c.f. [19, Lemma 24]), we conclude that for each i ∈ [M ], In subsequent analysis, we need to use the following properties of G i (Q) (cf. (1)) for each i ∈ [M ] and any given vector of distributions Q = (Q 1 , . . . , Q M ) ∈ (P(X )) M , For each i ∈ [M ], define the vector of distributions P i := (Q 1 , . . . , Q M ) with Q i = P A and Q j = P N for all j ∈ M i . Under hypothesis H i , given any set of M sequences x n ∈ T i (P N , P A ), since the KL divergence is continuous, one can apply a Taylor expansion of G j (T x n 1 , . . . ,T x n M ) (cf. (14)) around P i , for each j ∈ M i , we have and for j = i, With the above definitions and results, we can now upper bound the false reject probability of our test (cf. (13)) under each hypothesis H i with i ∈ [M ] with respect to any pair of distributions (P N , P A ) as follows: where (103) follows since h(X n ) ≥ min j∈Mi G j (T X n 1 , . . . ,T X n M ), which is implied by the definition of h(x n ) in (69). For simplicity, given random variables X 1 , . . . , X M , for each i ∈ [M ] and j ∈ M i , define the information density and for each t ∈ [n], we use X t to denote the snapshot of the M sequences at time t, i.e., X 1,t , . . . , X M,t . The second term in (104) can be lower bounded as follows: . . ,T X n M ) > λ and X n ∈ T i (P N , P A ) ı i,j (X t |P N , P A ) > λ + O log n n and X n ∈ T i (P N , P A ) (107) where (107) follows from the result in (95) and the Taylor expansion in (100), and (108) follows from the result in (95).
Recall that under P i , for each t ∈ [n], X t = (X 1,t , . . . , X Mt ) are independent where X i,t ∼ P A and X j,t ∼ P N for j ∈ M i . Recalling definitions of GD M (P N , P A )in (4), V M (P N , P A ) in (5) and Cov M (P N , P A ) in (6), we have that for any i ∈ [M ] and j ∈ M i and for any k ∈ M i,j , the covariance of (ı i,j (X t |P N , where the justification of (111) is provided in Appendix I.
Recall the definition of V M (P N , P A ) in (7). Applying the multivariate Berry-Esseen theorem [20], the first term in (108) is bounded below as follows: where Q M−1 (·) is the multivariate generalization of the complementary Gaussian cdf defined in (8).
Using (104) and (112), we have that for any (P N , P A ), the false reject probability is upper bounded as follows:

B. Proof of Theorem 2
Note that the converse proof without a constraint on the false alarm probability is also a converse proof with a constraint on the false alarm probability. Therefore, in the subsequent proof, we drop the constraint on the false alarm probability and focus on the misclassification and the false reject probabilities.
We first relate the performances of any test with the type-based test (i.e., a test which uses only the types (empirical distributions) of the sequences (T X n 1 , . . . ,T X n M )), as demonstrated in the following lemma. Lemma 1. Given any test φ n , for any κ ∈ [0, 1], we can construct a type-based test φ T n such that for each i ∈ [M ] and any pair of distributions (P N , P A ), Lemma 2. Given any λ ∈ R + , for any type-based test φ T n such that for all pair of distributions (P N ,P A ), max then for any pair of distributions (P N , P A ) and for each i ∈ [M ], we have The proof of Lemma 2 is provided in Appendix G. Combining Lemmas 1 and 2 with κ = 1− 1 n and noting that g(T x n 1 , . . . ,T x n M ) = h(x n ) (cf. (69)) for any x n = (x n 1 , . . . , x n M ), we obtain the following corollary. Corollary 1. Given any λ ∈ R + , for any test φ n satisfying that for all pairs of distributions (P N , we have that for any pair of distributions (P N , P A ) and for each i ∈ [M ] Using Corollary 1, with any test φ n satisfying (121), for any pair of distributions (P N , P A ), we have that for each i ∈ [M ] and any j ∈ M i , We first focus on the second term in the bracket of (124). Given any i ∈ [M ], we have that for each j ∈ M i : where (126) follows from Taylor expansions in (100) and (101) and the upper bound on the atypical set in (95), (127) follows from the Berry-Esseen theorem [21], [22] and (128) follows since Q(x) ≤ exp(− x 2 2 ) for any x > 0. Therefore, we conclude that for each i ∈ [M ], Finally, analogously to the achievability proof, we analyze the first term in the bracket of (124): where in (134), the definition of the typical set T i (P N , P A ) was in (94), (135) follows from the result in (95) that upper bounds the probability of P i X n / ∈ T i (P N , P A )}, the Taylor expansion of G j (T X n 1 , . . . ,T X n M ) exactly the same as in (108) and the fact that η n,M = O(log n/n), and (136) follows from the multivariate Berry-Esseen theorem similarly to (112).
Combining (124) and (136), we conclude that The proof of Theorem 2 is now completed.
The analyses of the misclassification error probabilities β i (ψ n |P N ,P A ) and the false alarm probability P fa (φ n |P N ,P A ) are exactly the same as in Appendix A. It suffices to bound the false reject probability of our test for a particular pair of distributions (P N , P A ). For each i ∈ [M ], we have that We now focus on upper bound the probability term in (142). For any (j, k) ∈ [M ] 2 , given any i ∈ [M ], we have ≤ (n + 1) M|X | exp − n min Q∈(P(X )) M : Gj (Q)≤λ, G k (Q)≤λ Combining (142), (146) and using the definitions of LD i (·) in (9), we have that for each i ∈ [M ] and any pair of distributions (P N , P A ), the i-th false reject probability satisfies for any λ ∈ R + lim inf 2) Converse: For simplicity, let κ n,M := η n,M + log n + log(M − 1) n . (148) Using Corollary 1, we have that for any test φ n such that the misclassification error probabilities decay exponentially fast with speed at least λ for all pairs of distributions, given any (P N , P A ), for each i ∈ [M ], the i-th false reject probability ζ i (φ n |P N , P A ) satisfies where (150) follows from the definition of h(x n ) in (69) and (152) follows similarly to (145). Using the continuity of (P N , P A ) to LD i (λ|P N , P A ) (cf. (9)) for any λ ∈ R + , the definition of κ n,M in (148) and the results in (152), we have that for each i ∈ [M ], for any test φ n satisfying (33).

D. Proof of Theorem 4
The proof of Theorem 4 is a generalization of Theorem 1 and thus we only emphasize the differences. For subsequent analyses, define the following linear combination of third absolute moments Note that T(B, C, P N , P B ) is finite since we consider distributions (P N , P B ) with the same support on the finite alphabet X .
Note that I * (x n ) denotes the set B that minimizes the scoring function and h S (x n ) denotes the second minimal value of the scoring function. The universal rest in (51) is equivalently expressed as follows: We next analyze the performance of the test in (157). We first analyze the misclassification error probability. Given any B ∈ S, under any tuple of distributions P B = (P N , P A,1 , . . . , P A,|B| ), similarly to the case with at most one outlier, the misclassification error is upper bounded as follows: = Q∈(Pn(X )) M : GB(Q)>λ = Q∈(Pn(X )) M : GB(Q)>λ H(Q i ) We then analyze the false alarm probability. Given any nominal distribution P N , the false alarm probability is upper bounded as follows: where (170) follows from similar steps leading to (164). Finally, we analyze the false reject probability of the tests. For this purpose, we need a generalized version of the typical set in (94). For each B ∈ S and any P B , define Similarly to (95), for each B ∈ S, we have Recall the definitions of the mixture distribution in (39) and the information densities in (40) and (41). Under each hypothesis H B , given any observed sequences x n ∈ T B (P B ), applying Taylor expansions of G C (T x n 1 , . . . ,T x n M ) for C ∈ S around P B yields The false reject probability is then upper bounded as follows: where S B = {C ∈ S B } denotes the set of sets in S that are not equal to B. We now analyze the probability term in (179).
Recall that given any (B, C) ∈ S 2 and any variables (X 1 , . . . , X M ), For each t ∈ [n], we use X t to denote X 1,t , . . . , X M,t . Using Taylor expansions in (175), (176), for any B ∈ S, Note that S B denotes all subsets of [M ] with size no greater than T excluding the set B thus each element in S B is a subset of [M ]. There are in total |S| − 1 elements in the set S B and thus |S| − 1 inequalities (183) that need to be satisfied simultaneously. Recall that the elements in S B are ordered as {C 1 , . . . , C |S|−1 }. This way, the probability term in (183) is equivalent to Recall the definitions of GD(B, C, P N , P B ) in (43), V(B, C, P N , P B ) in (44). Note that for each i ∈ [|S| − 1] and each t ∈ [n], Furthermore, for any (i, k) ∈ [|S| − 1] 2 such that i = k, we have Using (183) to (187), and applying the multivariate Berry-Esseen theorem similarly to (112), we have whereμ(λ, P N , P B ) denotes the vector (λ − GD(B, C 1 , P N , P B ) + O(log n/n), . . . , λ − GD(B, C |S|−1 , P N , P B ) + O(log n/n)).

E. Proof of Theorem 5
Recall the definition of h T (x n ) in (156) and η n,M in (116). For ease of notation, let η n,M,T := η n,M + log n + log(|S|)) n .
The following corollary is key to the converse proof of Theorem 4.
Corollary 2. Given any λ ∈ R + , for any test φ n such that for all tuples of nominal and anomalous distributions (P N ,P T ), then for any tuple of nominal and anomalous distributions (P N , P T ), for each B ∈ S, The proof of Corollary 2 is similar to that of Corollary 1 and is thus omitted. Using Corollary 2, for any test φ n satisfying (191), given any tuple of distributions (P N , P T ), for each B ∈ S, the false reject probability is lower bounded by where (195) is justified in Appendix J. Analogous to (188), using the multivariate Berry-Esseen theorem, we conclude that P B min C∈SB G C (T X n 1 , . . . ,T X n M ) + η n,M,T ≤ λ = 1 − P B ∀ C ∈ S B , G C (T X n 1 , . . . ,T X n M ) + η n,M,T > λ (196) The proof of Theorem 5 is thus completed by combining (195) and (197).

F. Proof of Lemma 1
For simplicity, let Q := (Q 1 , . . . , Q M ) ∈ (P n (X )) M and for any Q, we use T n Q to denote the set of sequences x = (x n 1 , . . . , x n M ) such that x n i ∈ T n Qi for all i ∈ [M ]. Given any test φ n , the sample space X Mn is separated into (M + 1) disjoint regions: {A i (φ n )} i∈[M] and A r (φ n ) where A r (φ n ) =

i∈[M]
A i c .
We can then construct a type-based test as follows. Given any κ, for any Q ∈ (P n (X )) M , • φ T n (Q) = H r if at least κ fractions of the sequences in the type class T n Q are contained in the reject region, i.e., |T n Q ∩ A r (φ n )| ≥ κ|T n Q |.
• φ T n (Q) = H i if i) less than κ fractions of the sequences in the type class T n Q are contained in the reject region and ii) for all j ∈ [M ], A i (φ n ) contains the most number of the sequences in the type class T n Q , i.e., |T n Q ∩ A r (φ n )| < κ|T n Q |, and |T n Q ∩ A i (φ n )| ≥ max j∈Mi |T n Q ∩ A j (φ n )|.
G. Proof of Lemma 2 To prove Lemma 2, it suffices to prove that for any type-based test satisfying (119), if a tuple of types Q satisfies that g(Q) + η n,M < λ, then we must have φ T n (Q) = H r . We will prove our claim by contradiction. Suppose our claim is not true. Then there exist typesQ = (Q 1 , . . . ,Q M ) ∈ (P n (X )) M such that for some i ∈ [M ], φ T n (Q) = H i and g(Q) + η n,M < λ Note that (215) implies that there exists (j, k) ∈ M 2 such that j = k and G j (Q) + η n,M < λ and G k (Q) + η n,M < λ.
Furthermore, either j = i or k = i. Without loss of generality, we assume that j = i. Then, we have that for all pairs of distributions (P N ,P A ), the misclassification error probability under hypothesis H j can be lower bounded as follows: which contradicts that (119) holds. Therefore, we have show that for any type-based test φ T n satisfying (119), we must have φ T n (Q) = H r for any Q satisfying (214).

H. Justification of Properties of Exponent Tradeoff
We first prove that LD i (λ, P N , P A ) = 0 if and only if λ ≥ GD M (P N , P A ). Recall the definition of LD i (·) in (9) and the definition of G i (·) in (1). Note that for each i ∈ [M ], any λ ∈ R + and any (P N , P A ), LD i (λ, P N , P A ) = 0 if there exists (j, k) ∈ [M ] 2 such that j = k, G j (Q * ) ≤ λ and G k (Q * ) ≤ λ where Q * is a collection of distributions with Q * i = P A and Q * t = P N for all t ∈ M i . For any j ∈ M i , we have where (230) follows from the definition of G i (·) in (1). The proof of (35) is thus completed.