Universal outlier hypothesis testing

The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the “outlier” distribution, distinct from the common “typical” distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.