On composite binary hypothesis testing with training data

Motivated by an outlier detection problem, we consider the problem of testing between a known i.i.d. distribution over a finite alphabet, and a composite hypothesis consisting of all other i.i.d. distributions over the same alphabet. We wish to quantify the loss with respect to simple hypothesis testing, and further to find how much of it can be re-gained using a training sequence that is known to come from the unknown distribution. To that end, we present new optimality criteria, universal minimax with and without a training sequence. We show that under our criteria, the acceptance region of the optimal tests takes the simple form of a “sphere of types”, where the center is shifted to be “antipodal” to the type of the training sequence (if such a sequence is present). Further, noting that universality has no cost in the exponential sense, we turn to the second-order regime of fixed error probabilities, where we define a figure of merit that we call resolution tradeoff. In this regime we solve Gaussian hypothesis testing problems, that are asymptotically equivalent to the original ones, in order to derive the resolution tradeoffs with and without training sequence.