We revisit sequential outlier hypothesis testing and derive bounds on achievable exponents when both the nominal and anomalous distributions areunknown. The task of outlier hypothesis testing is to identify the set of outliers that are generated from an anomalous distribution among all observed sequences where the rest majority are generated from a nominal distribution. In the sequential setting, one obtains a symbol from each sequence per unit time until a reliable decision could be made. For the case with exactly one outlier, our exponent bounds are tight, providing exact large deviations characterization of sequential tests and strengthening a previous result of Li, Nitinawarat and Veeravalli (2017). In particular, the average sample size of our sequential test is bounded universally under any pair of nominal and anomalous distributions and our sequential test achieves larger Bayesian exponent than the fixed-length test, which could not be guaranteed by the sequential test of Li, Nitinawarat and Veeravalli (2017). For the case with at most one outlier, we propose a threshold-based test that has bounded expected stopping time under mild conditions and we bound the exponential decay rate of error probabilities, a.k.a., error exponents, under each non-null hypothesis and the null hypothesis. Our sequential test resolves the tradeoff among the exponential decay rates of misclassification, false reject and false alarm probabilities for the fixed-length test of Zhou, Wei and Hero (TIT 2022). Finally, with a further step towards practical applications, we generalize our results to the cases of multiple outliers and show that there is a penalty in the error exponents when the number of outliers is unknown.

We revisit sequential outlier hypothesis testing and derive bounds on the achievable exponents. Specifically, the task of outlier hypothesis testing is to identify the set of outliers that are generated from an anomalous distribution among all observed sequences where most are generated from a nominal distribution. In the sequential setting, one obtains a sample from each sequence per unit time until a reliable decision could be made. We assume that the number of outliers is known while both the nominal and anomalous distributions are unknown. For the case of exactly one outlier, our bounds on the achievable exponents are tight, providing exact large deviations characterization of sequential tests and strengthening a previous result of Li, Nitinawarat and Veeravalli (2017). In particular, we propose a sequential test that has bounded average sample size and better theoretical performance than the fixed-length test, which could not be guaranteed by the corresponding sequential test of Li, Nitinawarat and Veeravalli (2017). Our results are also generalized to the case of multiple outliers.

The task of outlier hypothesis testing is to identify outliers from a set of observed sequences, where most sequences named nominal samples are generated from nominal distributions and the rest sequences called outliers are generated from anomalous distributions. Inspired by the study of binary classification with distribution mismatch by Hsu and Wang (ISIT 2020), we study outlier hypothesis testing with distribution uncertainty. Specifically, each nominal sequence is generated from a distribution close to a centered nominal distribution and each outlier is generated from a distribution close to a centered anomalous distribution, where the closeness is measured via L-norms. Both nominal and anomalous distributions are unknown. To solve the above problem, we propose a threshold-based test and characterize the performance of our test in both the Chernoff's and Stein's regimes. Furthermore, in the Stein's regime, we analyze the impact of distribution uncertainty on the asymptotic performance of our result and show that the dominant term is a function of the likelihood ratio between centered nominal and anomalous distributions.

We revisit multiple hypothesis testing and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive achievable error exponents of error probabilities under each hypothesis and show that our two-phase test bridges over fixed-length and sequential tests in both Neyman-Pearson and Bayesian settings in the similar spirit of Lalitha and Javidi [1] for binary hypothesis testing. Specifically, our test may achieve the performance close to a sequential test with the asymptotic complexity of a fixed-length test and such test is named the almost fixed-length test. Our results generalize the design and analysis of the almost fixed-length test for binary hypothesis testing to account for more than two outcomes.

We revisit the multiple classification problem and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive the achievable error exponent under each hypothesis and show that our two-phase test bridges over the fixed-length test of Gutman (TIT, 1989) and the sequential test of Haghifam, Tan, and Khisti (TIT 2021). In contrast to the fixed-length test of Gutman that requires an additional reject option, with proper choices of test parameters, our test achieves error exponents close to the sequential test of Haghifam, Tan, and Khisti without a reject option. We generalize the result of Lalitha and Javidi (ISIT 2016) for binary hypothesis testing to the more practical families of M-ary statistical classification, where the test outcome is more than two and the generating distribution under each hypothesis is unknown.

We revisit the binary classification problem where the generating distribution under each hypothesis is unknown and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive the achievable error exponents of both type-I and type-II error probabilities. Furthermore, we illustrate our results via numerical examples and show that the performance close to sequential test can be achieved with the much simpler and less complex almost fixed-length test. Our results generalize the design and analysis of the almost fixed-length test for binary hypothesis testing (Lalitha and Javidi, ISIT 2016) to the more practical setting of binary classification.