Second-order asymptotically optimal statistical classification

Motivated by real-world machine learning applications, we analyse approximations to the non-asymptotic fundamental limits of statistical classification. In the binary version of this problem, given two training sequences generated according to two unknown distributions P1 and P2, one is tasked to classify a test sequence that is known to be generated according to either P1 or P2. This problem can be thought of as an analogue of the binary hypothesis testing problem, but, in the present setting, the generating distributions are unknown. Due to finite sample considerations, we consider the second-order asymptotics (or dispersion-type) trade-off between type-I and type-II error probabilities for tests that ensure that (i) the type-I error probability for all pairs of distributions decays exponentially fast, and (ii) the type-II error probability for a particular pair of distributions is non-vanishing. We generalize our results to classification of multiple hypotheses with the rejection option.