In the binary hypothesis testing problem, it is well known that sequentiality in taking samples eradicates the trade-off between two error exponents, yet implementing the optimal test requires the knowledge of the underlying distributions, sayP0andP1. In the scenario where the knowledge of distributions is replaced by empirically observed statistics from the respective distributions, the gain of sequentiality is less understood when subject to universality constraints over all possibleP0;P1. In this work, the gap is mended by a unified study on sequentiality in the universal binary classification problem, where the universality constraints are set on the expected stopping time as well as the type-I error exponent. The type-I error exponent is required to achieve a pre-set distribution-dependent constraint λ(P0,P1) for allP0;P1. Under the proposed framework, different sequential setups are investigated so that fair comparisons can be made with the fixed-length counterpart. By viewing these sequential classification problems as special cases of a general sequential composite hypothesis testing problem, the optimal type-II error exponents are characterized. Specifically, in the general sequential composite hypothesis testing problem subject to universality constraints, upper and lower bounds on the type-II error exponent are proved, and a sufficient condition for which the bounds coincide is given. The results for sequential classification problems are then obtained accordingly. With the characterization of the optimal error exponents, the benefit of sequentiality is shown both analytically and numerically by comparing the sequential and the fixed-length cases in representative examples of type-I exponent constraint λ.

In hypothesis testing problems, taking samples sequentially and stopping opportunistically to make the inference greatly enhances the reliability. The design of the stopping and inference policy, however, critically relies on the knowledge of the underlying distribution of each hypothesis. When the knowledge of distributions, say,$P_{0}$and$P_{1}$in the binary-hypothesis case, is replaced by empirically observed statistics from the respective distributions, the gain of sequentiality is less understood when subject to universality constraints. In this work, the gap is mended by a unified study on sequentiality in the universal binary classification problem. We propose a unified framework where the universality constraints are set on the expected stopping time as well as the type-I error exponent. The type-I error exponent is required to achieve a pre-set distribution-dependent constraint$\lambda(P_{0}, P_{1})$for all$P_{0}, P_{1}$. The framework is employed to investigate a semi-sequential and a fully-sequential setup, so that fair comparison can be made with the fixed-length setup. The optimal type-II error exponents in different setups are characterized when the function$\lambda$satisfies mild continuity conditions. The benefit of sequentiality is shown by comparing the semi-sequential, the fully-sequential, and the fixed-length cases in representative examples of$\lambda$. Conditions under which sequentiality eradicates the trade-off between error exponents are also derived.

The focus of this paper is on binary classification of a sequentially observed stream of i.i.d. samples, based on sequentially observed empirical statistics. The decision maker (classifier) sequentially observes a sequence of testing data i.i.d. sampled from one of two unknown distributions P0and P1. In addition, it receives two sequences of training data which are also sequentially sampled from the two unknown distributions in an i.i.d. fashion, respectively. Since the distributions are unknown, it is natural to put a constraint either on the expected stopping times or on the error probabilities that has to be satisfied universally over all possible pairs of distributions (P0, P1). For both settings, we develop tests that are asymptotically optimal within the class of tests that satisfy the respective universality constraints. For expected-stopping-time universality, the optimal error exponents are shown to be the Rényi divergences of order $\frac{\alpha }{{1 + \alpha }}$, where α is the ratio of the length of a training data sequence to that of the testing data sequence. For error-probability universality, the optimal expected stopping times normalized by the logarithm of the error probability are the reciprocal of the α-weighted generalized Jensen-Shannon (GJS) divergences. The proposed sequential tests are both based on threshold tests of two statistics, each of which is the α-weighted GJS divergences of the type of the testing sequence from that of a training sequence. Interestingly, to achieve asymptotic optimality, the stopping and decision rules in the two different universality setups take a "matching" and a "discriminating" viewpoint respectively in designing the threshold tests.