\section{Introduction}

In the outlying sequence detection problem, one observes a number $M$ of sequences. The majority of the $M$ sequences are i.i.d. samples from a nominal distribution and the rest of the sequences are i.i.d. samples from anomalous distributions different from the nominal distribution. The universal OSD problem is to design a universal test to discern the set of outlying sequences with high probability when both nominal and anomalous distributions are \emph{unknown}. Motivated by practical applications in anomaly detection~\cite{chandola2009anomaly}, we generalize the framework of universal outlying sequence detection in~\cite{li2014} and derive fundamental limits on the performance of optimal tests. 


Here we consider multiple outlying sequences, where the number of outlying sequences is assumed known, and each outlying sequence is generated according to a potentially different anomalous distribution. Under similar assumptions, the authors of \cite{li2014} obtain the decay rate of the maximal misclassification error probability when both the lengths of observed sequences and the number of observed sequences tend to infinity. In this paper we consider a more general test that incorporates a reject option, which is a decision to not make a classification decision. Such an option is formulated as an additional hypothesis that none of the hypothesized classes are true, similarly to the simultaneous detection and classification problem~(\cite{fredriksen1972simultaneous,baygun1995optimal}) with control on false alarms. With this reject option, we obtain tight bounds on the exponent of maximum misclassification error and false alarm probabilities for \emph{any} number of observed sequences, subject to a constraint on the maximum false reject probability, when the lengths of observed sequences tend to infinity. Our results are not directly comparable to \cite{li2014} since our problem formulation is different. Note that in \cite[Section III.B]{li2014}, when there is at most one outlying sequence, the authors defined the ``misclassification error probability'' as the combination of the misclassification error and false reject probabilities and they derived the exponent of this probability subject to a vanishing false alarm probability. In contrast, as demonstrated in Theorem \ref{result:1outlier} below, we provide an exact second-order asymptotic characterization of the homogeneous exponent of the misclassification error and false alarm probabilities subject to a \emph{non-vanishing} constraint on the false reject probability and our results are tight for \emph{any} number of observed sequences and \emph{moderately} large sequence length.


The reject option~(cf. \cite{herbei2006classification,bartlett2008classification}) is often incorporated as a safeguard against decisions that are not supported by sufficient evidence. For example, in binary Bayesian classification with reject option~\cite{herbei2006classification}, a decision to reject the sample is made when the posterior probabilities of each class is close to $\frac{1}{2}$. Such a reject decision is commonly used in ML applications when the cost of incorrect classification is high (cf. \cite{huang2015hierarchical,bartlett2008classification,fumera2003classification,mesquita2016classification}). Our adoption of the reject option is inspired by works on classification using empirical distributions, e.g., \cite{gutman1989asymptotically,unnikrishnan2015asymptotically,zhou2018binary}.

\subsection{Main Contributions}
Our main contribution is the exact characterization of the second-order asymptotic tradeoff among misclassification error, false alarm and false reject probabilities of optimal tests for universal outlying sequence detection with reject option.

To be specific, we derive second-order asymptotically optimal bounds on on the decay rate of maximum misclassification error and false alarm probabilities for universal tests that satisfy the following three constraints: (i) the misclassification error probability under each hypothesis decays exponentially fast for all pairs of nominal and anomalous distributions, (ii) the false alarm probability decays exponentially fast for all pairs of nominal and anomalous distributions, and (iii) the false reject probability under each hypothesis is upper bounded by a constant $\varepsilon$ for a particular pair of nominal and anomalous distributions. Our bound is tight for any number of observed sequences and any constant $\varepsilon$ when the lengths of observed sequences are moderately large. Our results provide insights for the design of practical detection rules where the number of samples is often limited. We propose an asymptotically optimal test (cf. \eqref{test1outlier}) that is a function of the empirical distributions of the observed sequences.


We then put a more stringent condition on false reject probabilities and consider universal tests that satisfy constraints (i), (ii) and an additional constraint that the false reject probability under each hypothesis decays exponentially fast for a particular pair of distributions. Out of all such tests, we are interested in optimal tests that have the fastest homogeneous decay rate in the misclassification error and in the false alarm probabilities subject to a constraint on the decay rate of false reject probabilities (equivalently, the false reject exponent). Our main result is the exact characterization of this asymptotic homogeneous misclassification and false alarm decay rate under the false reject decay rate constraint.

\subsection{Related Works}
The most closely related work to ours is that of \cite{li2014}, where the authors formulated the OSD problem, therein called the outlier hypothesis testing problem, and derived asymptotic decay rates of misclassification error probabilities for optimal tests under several different settings. Subsequently, a low complexity algorithm was proposed in~\cite{bu2019linear} and the result in \cite{li2014} was generalized to a sequential scenario in~\cite{li2017universal}. Other works on OSD include \cite{Zou2017TSP,Niti2015ISIT,tajer2014outlying,cohen2015active}.

Our setting differs from \cite{li2014} and the subsequent papers in that we allow a reject option and and we also provide an analysis of the tradeoff among misclassification error, false alarm and false reject probabilities. Our formulation incorporating a reject option is inspired by the early work of \cite{gutman1989asymptotically} where the reject option was called the ``mismatch'' decision.
In \cite{gutman1989asymptotically}, the author studied a binary sequence classification problem and showed that a certain test using empirical distributions of training and testing data is asymptotically optimal with exponentially decreasing misclassification probabilities. The result in \cite{gutman1989asymptotically} was generalized to classification of multiple testing sequences in~\cite{unnikrishnan2015asymptotically} and to distributed detection in~\cite{he2019distributed}. Finally, a finite sample analysis for the setting of~\cite{gutman1989asymptotically} was provided in~\cite{zhou2018binary}.

We apply a novel analysis that applies to the general OSD problem with reject option and multiple outlying sequences. Our main results are Theorems \ref{result:1outlier} and \ref{result:Toutlier}, which provide tight bounds on the exponential decay rate of misclassification error and false alarm probabilities.

\subsection{Organization for the Rest of the Paper}
The rest of the paper is organized as follows. In Section \ref{sec:pf}, we set up the notation, formulate the universal outlying sequence detection problem with at most one outlying sequence, propose fundamental limits and  present our main results concerning the performance of optimal universal tests. In Section \ref{sec:Tout}, we generalize our results to the case of multiple outlying sequences where the number of outlying sequences is known and each outlying sequence is generated according to a potentially different anomalous distribution. Finally, we conclude the paper and discuss future research directions in Section \ref{sec:conclude}. The proofs of all theorems are deferred to appendices.

\section{Case of At Most One Outlying Sequence}
\label{sec:pf}
\subsection*{Notation}

Random variables and their realizations are in upper (e.g.,  $X$) and lower case (e.g.,  $x$) respectively. All sets are denoted in calligraphic font (e.g.,  $\mathcal{X}$). We use superscripts to denote the vectors, like $X^n:=(X_1,\ldots,X_n)$. All logarithms are base $e$. 
We use $\Phi(\cdot)$ to denote the cumulative distribution function (cdf) of the standard Gaussian, where $\Phi^{-1}(\cdot)$ is its inverse, and $\mathrm{Q}(\cdot)$ to denote the complementary cdf of the standard Gaussian. 
The set of all probability distributions on a finite set $\mathcal{X}$ is denoted as $\mathcal{P}(\mathcal{X})$. Notation concerning the method of types follows~\cite{Tanbook}. Given a vector $x^n = (x_1,x_2,\ldots,x_n) \in\mathcal{X}^n$, the {\em type} or {\em empirical distribution} is denoted as $\hat{T}_{x^n}(a)=\frac{1}{n}\sum_{i=1}^n \mathbbm{1}\{x_i=a\},a\in\mathcal{X}$. The set of types formed from length-$n$ sequences with alphabet $\mathcal{X}$ is denoted as $\mathcal{P}_{n}(\mathcal{X})$. Given $P\in\mathcal{P}_{n}(\mathcal{X})$, the set of all sequences of length $n$ with type $P$, the {\em type class}, is denoted as $\mathcal{T}^n_P$. We use $\mathbb{R}$, $\mathbb{R}_+$, and $\mathbb{N}$ to denote the set of real numbers, non-negative real numbers, and  natural numbers respectively. Given any number $a\in\mathbb{N}$, we use $[a]$ to denote the collection of natural numbers between $1$ and $a$. Given any set $\mathcal{B}\subset\mathbb{N}$, define the function $\jmath_\mathcal{B}(\cdot)$ as a mapping from $\mathcal{B}$ to $|\mathcal{B}|$ such that for any $i\in\mathcal{B}$, $\jmath_\mathcal{B}(i)=j$ if $i$ is the $j$-th largest item in $\mathcal{S}$. Furthermore, for any $M\in\mathbb{N}$, given any set $\mathcal{B}\subset\mathcal{M}=[M]$, let $\mathcal{M}_\mathcal{B}$ denote the set difference $\mathcal{M}\setminus\mathcal{B}$. If $\mathcal{B}$ is a singleton, i.e., $\mathcal{B}=\{j\}$ for some $j\in[M]$, we use $\mathcal{M}_\mathcal{B}$ and $\mathcal{M}_j$ interchangeably.

\subsection{Problem Formulation}
Given a set of $M$ observed sequences $\mathbf{X}^n:=\{X_1^n,\ldots,X_M^n\}$, the goal of outlying sequence detection is to discern a subset of sequences which are generated according to an anomalous distribution $P_\mathrm{A}\in\mathcal{P}(\mathcal{X})$. This distribution is different from the nominal distribution $P_\mathrm{N}$ that generates the majority of sequences. Throughout this paper, we consider the problem of universal outlying sequence detection where both the nominal distribution $P_\mathrm{N}$ and the anomalous distribution $P_\mathrm{A}$ are \emph{unknown}. 

We start by assuming that there is at most one outlying sequence. In such a setting, the objective is to design a test to classify between the following $M+1$ hypotheses:
\begin{itemize}
\item $\mathrm{H}_i,~i\in[M]$: the $i$-th sequence $X_i^n$ is the outlying sequence, i.e., $X_i^n\sim P_\mathrm{A}$ and $X_j^n\sim P_\mathrm{N}$ for all $j\in[M]$ such that $j\neq i$;
\item $\mathrm{H}_\mathrm{r}$: there is no outlying sequence, i.e., $X_j^n\sim P_\mathrm{N}$ for all $j\in[M]$,
\end{itemize}
where $\mathrm{H}_\mathrm{r}$ is called the reject hypothesis, alternatively the ``reject option''  \cite{herbei2006classification}, and corresponds to the ``no signal present'' hypothesis in the framework of simultaneous detection and classification~\cite{baygun1995optimal,fredriksen1972simultaneous}. When an outlying sequence is present, any reject decision is a false reject, which might indicate that further investigation is required before a reliable classification (detection) can be made.


The main task in the above OSD problem is to design a decision rule (test) $\phi_n:\mathcal{X}^{Mn}\to\{\mathrm{H}_1,\ldots,\mathrm{H}_M,\mathrm{H}_\mathrm{r}\}$ with ``good'' performance in a sense to be specified later. Note that a test $\phi_n$ partitions the sample space $\mathcal{X}^{Mn}$ into $M+1$ disjoint regions: $\mathcal{A}_i(\phi_n)$ for each $i\in[M]$ where $X^{Mn}\in\mathcal{A}_i(\phi_n)$ implies hypothesis $\mathrm{H}_i$ and a reject region $\mathcal{A}_\mathrm{r}(\phi_n)=(\cup_{i\in[M]}\mathcal{A}_i(\phi_n))^\mathrm{c}$ where $X^{Mn}\in\mathcal{A}_i(\phi_n)$ implies hypothesis $\mathrm{H}_\mathrm{r}$.

Given any test $\phi_n$ and any pair of nominal and anomalous distributions $(P_\mathrm{N},P_\mathrm{A})\in\mathcal{P}(\mathcal{X})^2$, the performance of the test $\phi_n$ is evaluated by the following misclassification error, false reject and false alarm probabilities:
\begin{align}
\beta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})
&:=\mathbb{P}_i\{\phi_n(\mathbf{X}^n)\notin\{\mathrm{H}_i,\mathrm{H}_\mathrm{r}\}\}\label{def:error},~i\in[M]\\
\zeta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})
&:=\mathbb{P}_i\{\phi_n(\mathbf{X}^n)=\mathrm{H}_\mathrm{r}\}\label{def:reject},~i\in[M]\\
\mathrm{P}_{\mathrm{fa}}(\phi_n|P_\mathrm{N},P_\mathrm{A})
&:=\mathbb{P}_\mathrm{r}\{\phi_n(\mathbf{X}^n)\neq \mathrm{H}_\mathrm{r}\}
\label{def:falarm},
\end{align}
where for each $i\in[M]$, we define $\mathbb{P}_i\{\cdot\}:=\Pr\{\cdot|\mathrm{H}_i\}$ where $X_i^n$ is distributed i.i.d. according to $P_\mathrm{A}$ and for $X_j^n$ is distributed according to $P_\mathrm{N}$ for each $j\in\mathcal{M}_i$ and we define $\mathbb{P}_\mathrm{r}\{\cdot\}:=\Pr\{\cdot|\mathrm{H}_\mathrm{r}\}$ where all sequences are generated i.i.d. from $P_\mathrm{N}$ for all $i\in[M]$. Consistent with the literature on hypothesis testing~(e.g., \cite{lehmann2006testing}), we define $\beta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})$ and $\zeta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})$ as type-$i$ misclassification error and false reject probabilities, respectively, and we define $\mathrm{P}_{\mathrm{fa}}(\phi_n|P_\mathrm{N},P_\mathrm{A})$ as the false alarm probability. In the sequel, we focus on tradeoff among the probabilities of misclassification error in \eqref{def:error}, false rejection in \eqref{def:reject} and false alarm in \eqref{def:falarm}.


\subsection{Fundamental Limits of Interest}
We focus on the following fundamental limits of \emph{universal} OSD tests. Motivated by existing works on statistical classification (e.g.,~\cite{gutman1989asymptotically,zhou2018binary,he2019distributed}), we consider any test satisfying the following conditions: (i) for each $i\in[M]$, the type-$i$ misclassification error probability decays exponentially fast with speed at least $\lambda\in\mathbb{R}_+$ for all pairs of nominal and anomalous distributions, (ii) the false alarm probability decays exponentially fast with speed at least $\lambda\in\mathbb{R}_+$ for all pairs of nominal and anomalous distributions, and (iii) for each $i\in[M]$, the type-$i$ false reject probability is upper bounded by a constant $\varepsilon\in\mathbb{R}_+$ for a particular pair of nominal and anomalous distributions. The question we address is: \emph{what is the largest achievable error exponent $\lambda$ of any such test?} More specifically, given $\varepsilon\in\mathbb{R}_+$ and a particular pair of distributions $(P_\mathrm{N},P_\mathrm{A})$, we are interested in the following fundamental limit:
\begin{align}
\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})
\nn:=\sup\Big\{\lambda\in\mathbb{R}_+:~\exists~\phi_n~\mathrm{s.t.~}\forall~i\in[M],~\zeta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})&\leq \varepsilon,~\mathrm{and}\\*
\nn\forall~(\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})\in\mathcal{P}(\mathcal{X})^2,~\beta_i(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})&\leq \exp(-n\lambda)\\*
\mathrm{P}_{\mathrm{fa}}(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})&\leq\exp(-n\lambda)\Big\}\label{def:l^*}.
\end{align}
Note that in \eqref{def:l^*}, we constrain the false reject probability under each hypothesis to be upper bounded by a constant $\varepsilon$ for a particular pair of nominal and anomalous distributions $(P_\mathrm{N},P_\mathrm{A})$ and then study the largest decay rate of misclassification error and false alarm probabilities $\beta_i(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})$ and $\mathrm{P}_{\mathrm{fa}}(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})$ for any pair of distributions $(\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})$. This is the partially universal setting adopted in \cite{zhou2018binary,he2019distributed}. The motivation for such a setting is that posing asymmetric constraints is tantamount to assuming that the misclassification error and false alarm probabilities are more important than the false reject probability, which is controlled by the user. One can easily modify the setting of \eqref{def:l^*} by constraining the false reject probabilities for a finite set of known nominal and anomalous distributions and our results can be generalized to such a setting in a straightforward manner.

A more stringent constraint on the false reject probability is an exponential decay constraint for a particular chosen pair of distributions $(P_\mathrm{N},P_\mathrm{A})$. The fundamental limit of interest for this case is as follows. Given any false reject exponent $E\in\mathbb{R}_+$, we seek the following maximal decay rate of the misclassification error and false alarm probabilities:
\begin{align}
\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})
\nn:=\sup\Big\{\lambda\in\mathbb{R}_+:~\exists~\phi_n~\mathrm{s.t.~}\forall~i\in[M],~\zeta_i(\phi_n|P_\mathrm{N},P_\mathrm{A})&\leq \exp(-nE),~\mathrm{and}\\*
\nn\forall~(\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})\in\mathcal{P}(\mathcal{X})^2,~\beta_i(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})&\leq \exp(-n\lambda)\\
\mathrm{P}_{\mathrm{fa}}(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A}))&\leq\exp(-n\lambda)\Big\}
\label{def:tau*},
\end{align}
which is analogous to \eqref{def:l^*}.


We derive an asymptotically tight characterization of both $\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})$ and $\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})$, which provide benchmarks and insights for optimal test design for the outlying sequence detection problem.


\subsection{Preliminaries}


Here we provide several definitions needed to state our main results. Given any pair of distributions $(P_\mathrm{N},P_\mathrm{A})$, for any $x\in\mathcal{X}$, define the following two information densities:
\begin{align}
\imath_1(x|P_\mathrm{N},P_\mathrm{A})
&:=\log\frac{(M-1)P_\mathrm{A}(x)}{(M-2)P_\mathrm{N}(x)+P_\mathrm{A}(x)},\label{def:id1}\\
\imath_2(x|P_\mathrm{N},P_\mathrm{A})
&:=\log\frac{(M-1)P_\mathrm{N}(x)}{(M-2)P_\mathrm{N}(x)+P_\mathrm{A}(x)}\label{def:id2}.
\end{align}

As we shall see, the following linear combinations of the expectations and variances of these two information densities play an important role in characterizing the fundamental limits:
\begin{align}
\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})
&:=\mathbb{E}_{P_\mathrm{A}}[\imath_1(X|P_\mathrm{N},P_\mathrm{A})]+(M-2)\mathbb{E}_{P_\mathrm{N}}[\imath_2(X|P_\mathrm{N},P_\mathrm{A})],\label{def:GD}\\
\mathrm{V}_M(P_\mathrm{N},P_\mathrm{A})
&:=\mathrm{Var}_{P_\mathrm{A}}[\imath_1(X|P_\mathrm{N},P_\mathrm{A})]+(M-2)\mathrm{Var}_{P_\mathrm{N}}[\imath_2(X|P_\mathrm{N},P_\mathrm{A})]\label{def:V}.
\end{align}
Furthermore, define the following covariance function of the information densities
\begin{align}
\mathrm{Cov}_M(P_\mathrm{N},P_\mathrm{A})
\nn&:=-\big(\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})\big)^2+\mathbb{E}_{P_\mathrm{A}}\Big[\big(\imath_1(X|P_\mathrm{N},P_\mathrm{A})\big)^2\Big]+2(M-2)\mathbb{E}_{P_\mathrm{A}}[\imath_1(X|P_\mathrm{N},P_\mathrm{A})]\mathbb{E}_{P_\mathrm{N}}[\imath_2(X|P_\mathrm{N},P_\mathrm{A})]\\
&\qquad+(M^2-5M+7)\big(\mathbb{E}_{P_\mathrm{N}}[\imath_2(X|P_\mathrm{N},P_\mathrm{A})]\big)^2+(M-3)\mathbb{E}_{P_\mathrm{N}}\Big[\big(\imath_2(X|P_\mathrm{N},P_\mathrm{A})\big)^2\Big]\label{def:cov}.
\end{align}
We can then define the covariance matrix $\mathbf{V}_M(P_\mathrm{N},P_\mathrm{A})=\{V_{i,j}(P_\mathrm{N},P_\mathrm{A})\}_{(i,j)\in[M-1]^2}$ as follows
\begin{align}
V_{i,j}(P_\mathrm{N},P_\mathrm{A})
&=\left\{
\begin{array}{ll}
\mathrm{V}_M(P_\mathrm{N},P_\mathrm{A})&\mathrm{if~}i=j\\
\mathrm{Cov}_M(P_\mathrm{N},P_\mathrm{A})&\mathrm{otherwise}.
\end{array}
\right.
\label{defdispersionmatrix}
\end{align}
For any $k\in\mathbb{N}$, we define the multivariate generalization of the complementary Gaussian cdf as follows
\begin{align}
\mathrm{Q}_k(x_1,\ldots,x_k;\bm{\mu},\bSigma)
&:=\int^{\infty}_{x_1}\ldots\int^{\infty}_{x_k}\mathcal{N}(\mathbf{x};\bm{\mu};\bSigma)\mathrm{d} \mathbf{x}\label{def:kQ},
\end{align}
where $\mathcal{N}(\mathbf{x}; \bm{\mu};\bSigma)$ is the pdf of a $k$-variate Gaussian with mean $\bm{\mu}$ and covariance matrix $\bSigma$~\cite{tan2015asymptotic}. Furthermore, for any $k\in\mathbb{N}$, we use $\mathbf{1}_k$ to denote a row vector of length $k$ with all elements being one and we use $\mathbf{0}_k$ similarly. Then, for any $\varepsilon\in(0,1)$, let
\begin{align}
L_M^*(\varepsilon|P_\mathrm{N},P_\mathrm{A})
&:=\max\Big\{L\in\mathbb{R}:\mathrm{Q}_{M-1}(L\times\mathbf{1}_{M-1};\mathbf{0}_{M-1};\mathbf{V}_M(P_\mathrm{N},P_\mathrm{A}))\geq 1-\varepsilon\Big\}\label{def:L*PNPA},
\end{align}



Given a sequence of distributions $\mathbf{Q}=(Q_1,\ldots,Q_M)\in\mathcal{P}(\mathcal{X})^M$, for each $i\in[M]$, define the following linear combination of KL Divergence terms between a single distribution and a mixture distribution
\begin{align}
\mathrm{G}_i(\mathbf{Q})
&:=\sum_{t\in\mathcal{M}_i}D\left(Q_t\bigg\|\frac{\sum_{l\in\mathcal{M}_i}Q_l}{M-1}\right)\label{def:gi},
\end{align}
where $\mathcal{M}_i$ denotes the set of all indices in $[1:M]$ except $i$ (cf. Section Notation).
Finally, given any $\lambda\in\mathbb{R}_+$ and any pair of distributions $(P_\mathrm{N},P_\mathrm{A})$, for each $i\in[M]$, define the following quantity
\begin{align}
\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})
&:=\min_{(j,k)\in[M]^2:j\neq k}\min_{\substack{\mathbf{Q}\in(\mathcal{P}(\mathcal{X}))^M:\\\mathrm{G}_j(\mathbf{Q})\leq\lambda,~\mathrm{G}_k(\mathbf{Q})\leq\lambda}}\Big(D(Q_i\|P_\mathrm{A})+\sum_{l\in\mathcal{M}_i}D(Q_l\|P_\mathrm{N})\Big)\label{def:LDi}.
\end{align}
As we shall see, $\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})$ will be critical in characterizing the asymptotic value of $\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})$ (cf. \eqref{def:tau*}).


\subsection{Second-Order Asymptotic Characterization of $\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})$}
Our first result concerns the universal misclassification error and false alarm exponent for all pairs of distributions, called $\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})$, when false reject probabilities are upper bounded by a constant $\varepsilon$ for a particular pair of nominal and anomalous distributions $(P_\mathrm{N},P_\mathrm{A})$.

\begin{theorem}
\label{result:1outlier}
Given any $(P_\mathrm{N},P_\mathrm{A})\in\mathcal{P}(\mathcal{X})^2$, for any $\varepsilon\in(0,1)$, we have
\begin{align}
\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})
&=\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})+\frac{L_M^*(\varepsilon|P_\mathrm{N},P_\mathrm{A})}{\sqrt{n}}+O\left(\frac{\log n}{n}\right)\label{1outlier}.
\end{align}
Furthermore, the performance (decay rate) in \eqref{1outlier} is achieved by the following test:
\begin{align}
\psi_n(\mathbf{x}^n)
&:=\left\{
\begin{array}{cc}
\mathrm{H}_i&\mathrm{if}~\mathrm{S}_i(\mathbf{x}^n)<\min_{j\in\mathcal{M}_i}S_i(\mathbf{x}^n)\mathrm{~and~}\min_{j\in\mathcal{M}_i}S_j(\mathbf{x}^n)>\tilde{\lambda}\\
\mathrm{H}_\mathrm{r}&\mathrm{otherwise},
\end{array}
\right.\label{test1outlier}
\end{align}
where we use $\mathbf{x}^n$ to denote the collection of $M$ observed sequences $(x_1^n,\ldots,x_M^n)$, $\tilde{\lambda}$ is a judiciously chosen threshold (cf. \eqref{choosetlambda}) and $\mathrm{S}_i(\mathbf{x}^n)$ is a scoring function defined as
\begin{align}
\mathrm{S}_i(\mathbf{x}^n)&:=\mathrm{G}_i(\hat{T}_{x_1^n},\ldots,\hat{T}_{x_M^n})\label{def:scoref}.
\end{align}

\end{theorem}
The proof of Theorem \ref{result:1outlier} is provided in Appendix \ref{proof:result:1outlier}. Several remarks are in order.


Theorem \ref{result:1outlier} indicates that the test in \eqref{test1outlier} is second-order asymptotically optimal for simultaneous detection and identification of the outlying sequence. The result in \eqref{1outlier} can be contrasted with \cite{li2014} in which the results are only tight when \emph{both} the length of sequences $n$ and the total number of sequences $M$ tend to \emph{infinity}. Note that our problem formulations are different from those in \cite{li2014}. In \cite[Section III.B]{li2014}, when there is at most one outlying sequence, the authors defined the ``misclassification error probability'' as the combination of the misclassification error and false reject probabilities and derived the exponent of this probability subject to a vanishing false alarm probability. However, Theorem \ref{result:1outlier} provides an exact second-order asymptotic characterization of the exponent of misclassification error and false alarm probabilities subject to a non-vanishing constraint on the false reject probability. The approximation in \eqref{1outlier} is tight for any number of sequences as the length of sequences become moderately large. Furthermore, our test decides reject $\mathrm{H}_\mathrm{r}$ if there exists two competitive hypotheses that require further investigation, i.e., $\exists~(j,k)\in\mathcal{M}^2$ such that $j\neq k$ and $\mathrm{S}_j(\mathbf{x}^n)<\tilde{\lambda}$, $\mathrm{S}_k(\mathbf{x}^n)<\tilde{\lambda}$. We remark that the scoring function $\mathrm{S}_i(\mathbf{x}^n)$ was also used in \cite{li2014} to construct a universal test.

Furthermore, Theorem \ref{result:1outlier} implies that a phase transition holds for outlying sequence detection with reject option. In particular, if the desired decay rate is greater than $\mathrm{GD}_M(P_N,P_A)$ for the misclassification error and false alarm probabilities, then asymptotically the false reject probabilities tend to one. On the other hand, if the desired decay rate less than $\mathrm{GD}_M(P_N,P_A)$, then asymptotically the false reject probabilities vanish. See Figure \ref{phasetransition} for a numerical illustration.
\begin{figure}[tb]
\centering
\includegraphics[width=.6\columnwidth]{osd_pt2.eps}
\caption{
Illustration of phase transition for outlying sequence detection with reject option. Here we consider Bernoulli sources $P_\mathrm{N}=\mathrm{Bern}(0.2)$ and $P_\mathrm{A}=\mathrm{Bern}(0.4)$. We assume that there are $M=4$ observed sequences and one sequence is the outlier. We plot the false reject probability under each hypothesis, i.e., $\beta_i(\psi_n|P_\mathrm{N},P_\mathrm{A})$. From the figure, we observe that when the length of observed sequences tend to infinity, if the decay rate (exponent) of misclassification error and false alarm probabilities is less than the critical rate $\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})$, then the false reject probability vanish under each hypothesis with respect to $(P_\mathrm{N},P_\mathrm{A})$. Furthermore, when the length of observed sequences tends to infinity, if the decay rate (exponent) of misclassification error and false alarm probabilities is greater than the critical rate $\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})$, then the false reject probability tends to one under each hypothesis with respect to $(P_\mathrm{N},P_\mathrm{A})$. This sharp transition of the false reject probability is known as phase transition.}

\label{phasetransition}
\end{figure}

Theorem \ref{result:1outlier} also captures the influence of the number of sequences $M$ on the performance of the optimal test~\eqref{test1outlier}. Intuitively, when one has a larger number of sequences, it should be easier to learn the nominal distribution, achieving better performance. To verify this intuition, the second-order result in Theorem \ref{result:1outlier} for Bernoulli distributions with different values of $M$ is plotted in Figure \ref{maffect}.
\begin{figure}[tb]
\centering
\includegraphics[width=.6\columnwidth]{m_affect2.eps}
\caption{
Illustration of the effect of the number of sequences $M$ in the performance for outlying sequence detection with reject option. Here we consider Bernoulli sources $P_\mathrm{N}=\mathrm{Bern}(0.2)$ and $P_\mathrm{A}=\mathrm{Bern}(0.4)$. We assume that there are $M=4$ observed sequences and that only one sequence is an outlier. We plot $\lambda^*(n,\varepsilon|P_\mathrm{N},P_\mathrm{A})$ without the $O(\log n)$ term.}
\label{maffect}
\end{figure}
The influence of $M$ on the performance of the optimal test is dominated by $\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})$. In fact, 
\begin{align}
\frac{\partial \mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})}{\partial M}
&=D\left(P_\mathrm{N}\bigg\|\frac{(M-2)P_\mathrm{N}+P_\mathrm{A}}{M-1}\right)>0.
\end{align}
Thus, as the number of sequences $M$ increases, the performance of the optimal test improves. In the extreme case, as $M\to\infty$, we have
\begin{align}
\lim_{M\to\infty}\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})=D(P_\mathrm{A}\|P_\mathrm{N}).
\end{align}
This implies that the maximum asymptotic decay rate of the misclassification and false alarm probabilities of an optimal test is $D(P_\mathrm{A}\|P_\mathrm{N})$ as the number of sequences $M$ tends to infinity.

From the perspective of maximum robustness, Theorem \ref{result:1outlier} sheds light on the least favorable pairs of nominal and anomalous distributions for the outlying sequence detection problem. Consider a set of distributions $(P_\mathrm{N},P_\mathrm{A})$ which are separated according to the KL-divergence, i.e., $D(P_\mathrm{N}\|P_\mathrm{A})\geq \delta$ for a specified $\delta>0$. Then, according to Theorem \ref{result:1outlier}, asymptotically the least favorable pair of distributions for the case of at most one outlying sequence is obtained by solving the following optimization problem
\begin{align}
\argmin_{(P_\mathrm{N},P_\mathrm{A}):D(P_\mathrm{N}\|P_\mathrm{A})\geq\delta}\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})\label{opt:leastf}.
\end{align}
The optimization problem in \eqref{opt:leastf} is non-convex, and thus the exact solution to \eqref{opt:leastf} is challenging and will be addressed in future work.


An additional remark of Theorem \ref{result:1outlier} is that it implies that the proposed test in \eqref{test1outlier} has the asymptotically smallest reject region out of all tests which ensure exponential decay of the misclassification error and false alarm probabilities for all tuples of distributions. More specifically, given any $\tilde{\lambda}\in\mathbb{R}_+$, for any test $\phi_n$ such that
\begin{align}
\liminf_{n\to\infty}-\frac{1}{n}\log\beta_i(\phi_n|\tilde{P}_\mathrm{N},\tilde{P}_\mathrm{A})\geq \tilde{\lambda},
\end{align}
the reject region (defined as the set of observed sequences where a reject decision is made) of our test $\psi_n$ in \eqref{test1outlier} is smaller than $\phi_n$, i.e.,
\begin{align}
\mathcal{A}_\mathrm{r}(\psi_n)\subseteq\mathcal{A}_\mathrm{r}(\phi_n).
\end{align}
This result is is implicit in the proof of Theorem \ref{result:1outlier} (cf. Corollary \ref{coro}) and can be derived similarly to the proofs of \cite[Theorem 1]{gutman1989asymptotically} and \cite[Theorem 3.1]{unnikrishnan2015asymptotically}.


Finally, we remark that Theorem \ref{result:1outlier} is relevant to $M$-ary hypothesis testing with empirically observed statistics~\cite{gutman1989asymptotically,unnikrishnan2015asymptotically,zhou2018binary}. In fact, our proof technique for Theorem \ref{result:1outlier} can be used to strengthen \cite[Theorem 4.1]{zhou2018binary} by removing the condition in \cite[Section 4.2]{zhou2018binary} on the uniqueness of the minimizing distribution for the scoring function in \cite[Eq. (4.4)]{zhou2018binary}. However, the results in~\cite{gutman1989asymptotically,unnikrishnan2015asymptotically,zhou2018binary}
do not directly apply to our setting since the two problems are significantly different. In the $M$-ary hypothesis testing problem with empirically observed statistics, one is given $M$ training sequences and one test sequence. The task there is to identify the true distribution of the test sequence among the empirical distributions of the training sequences. In contrast, in the outlying sequence detection problem addressed in Theorem \ref{result:1outlier}, we are given $M$ sequences and our task is to identify those outlying sequences which have different distributions from the nominal class. 


\subsection{Asymptotic Characterization of $\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})$}

Here we give an asymptotic characterization of the exponential rate $\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})$. Specifically, we specify the limit of the homogeneous exponent of misclassification error and false alarm probabilities of an optimal universal test whose false reject probabilities for a particular pair of distributions $(P_\mathrm{N},P_\mathrm{A})$ decay exponentially fast, at speed of at least $E\in\mathbb{R}_+$. For simplicity, let
\begin{align}
f(E,P_\mathrm{N},P_\mathrm{A})
&:=\sup\Big\{\lambda\in\mathbb{R}_+:\min_{i\in[M]}
\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})\geq E\Big\}\label{def:fexponent}.
\end{align}

\begin{theorem}
\label{result:exp1out}
For any $(P_\mathrm{N},P_\mathrm{A})\in\mathcal{P}(\mathcal{X})^2$ and any $E\in\mathbb{R}_+$,
\begin{align}
\lim_{n\to\infty}\tau^*(n,E|P_\mathrm{N},P_\mathrm{A})=f(E,P_\mathrm{N},P_\mathrm{A}).
\end{align}
\end{theorem}
The proof of Theorem \ref{result:exp1out} is provided in Appendix \ref{proof:result:exp1out}. 

Note that in the achievability par of the proof, we make use of the test in \eqref{test1outlier} and thus establish its asymptotic optimality. Furthermore, as can be gleaned in the proof of Theorem \ref{result:exp1out}, for each $i\in[M]$, $\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})$ is the exponent of the $i$-th false reject probability. Secondly, we comment on the tradeoff between the false reject exponent $E$ and the error and false alarm exponent $f(E,P_\mathrm{N},P_\mathrm{A})$. Note that given any $(P_\mathrm{N},P_\mathrm{A})$, for each $i\in[M]$, $\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})$ (cf. \eqref{def:LDi}) is non-increasing in $\lambda$ and $\mathrm{LD}_i(\lambda,P_\mathrm{N},P_\mathrm{A})=0$ if and only if $\lambda\geq \mathrm{GD}_M(P_N,P_A)$. 

Theorem \ref{result:exp1out} implies the following:
\begin{proposition}
\label{prop:expexponents}
The following claims hold.
\begin{enumerate}
\item For any $(P_\mathrm{N},P_\mathrm{A})$, the homogeneous exponent $f(E,P_\mathrm{N},P_\mathrm{A})$ of misclassification error and false alarm probabilities is non-increasing in the false reject exponent $E$;
\item To ensure any positive false reject exponent $E\in\mathbb{R}_+$, the misclassification error and false alarm exponent cannot be greater than $\mathrm{GD}_M(P_N,P_A)$ since
\begin{align}
\sup_{E\in\mathbb{R}_+}f(E,P_\mathrm{N},P_\mathrm{A})<\mathrm{GD}_M(P_N,P_A)\mathrm{~and~}f(0,P_\mathrm{N},P_\mathrm{A})=\mathrm{GD}_M(P_N,P_A)\label{toprove1};
\end{align}
\item To ensure a positive misclassification error and false alarm exponent, the false reject exponent $E$ cannot be too large, i.e., $f(E,P_\mathrm{N},P_\mathrm{A})=0$ if and only if
\begin{align}
E\geq \min_{Q\in\mathcal{P}(\mathcal{X})} \Big(D(Q\|P_\mathrm{A})+\sum_{l\in\mathcal{M}_i}D(Q\|P_\mathrm{N})\Big)\label{toprove2}.
\end{align}
\end{enumerate}
\end{proposition}
The proof of Proposition \ref{prop:expexponents} is provided in Appendix \ref{sec:just}.


\subsection{A Numerical Example}
In this subsection, we present a numerical example to illustrate Theorem \ref{result:1outlier}. Consider the binary alphabet $\mathcal{X}={0,1}$ and $M=4$. Assume that there is exactly one outlier sequence and let $\mathrm{Bern}(p)$ denote a Bernoulli distribution with parameter $p\in(0,1)$. For any $(p,q)\in(0,1)^2$ such that $p\neq q$, we set the nominal distribution $P_\mathrm{N}$ as $\mathrm{Bern}(p)$ and the anomalous distribution $P_\mathrm{A}$ as $\mathrm{Bern}(q)$. Then the information densities (cf. \eqref{def:id1} and \eqref{def:id2}) satisfy
\begin{align}
\imath_1(x|P_\mathrm{N},P_\mathrm{x})
&:=\mathbbm{1}(x=0)\log\frac{(M-1)(1-q)}{(M-2)(1-p)+1-q}+\mathbbm{1}(x=1)\log\frac{(M-1)q}{(M-2)p+q},\\
\imath_2(x|P_\mathrm{N},P_\mathrm{x})
&:=\mathbbm{1}(x=0)\log\frac{(M-1)(1-p)}{(M-2)(1-p)+1-q}+\mathbbm{1}(x=1)\log\frac{(M-1)p}{(M-2)p+q}.
\end{align}
Furthermore, 
\begin{align}
\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})
&=D_b\bigg(q\Big\|\frac{(M-2)p+q}{M-1}\bigg)+(M-2)D_b\bigg(p\Big\|\frac{(M-2)p+q}{M-1}\bigg),
\end{align}
where $D_b(p\|q)=p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}$ is the binary KL divergence function.
The variance $\mathrm{V}_M(P_\mathrm{N},P_\mathrm{A})$ is given by
\begin{align}
\mathrm{V}_M(P_\mathrm{N},P_\mathrm{A})
\nn&=\mathbb{E}_{P_\mathrm{A}}[(\imath_1(X|P_\mathrm{N},P_\mathrm{x}))^2]+(M-2)\mathbb{E}_{P_\mathrm{N}}[(\imath_2(X|P_\mathrm{N},P_\mathrm{A}))^2]\\*
&\qquad-\bigg(D_b\bigg(q\Big\|\frac{(M-2)p+q}{M-1}\bigg)\bigg)^2-(M-2)\bigg(D_b\bigg(p\Big\|\frac{(M-2)p+q}{M-1}\bigg)\bigg)^2.
\end{align}
Similarly, we can also calculate $\mathrm{Cov}_M(P_\mathrm{N},P_\mathrm{A})$ (cf. \eqref{def:cov}) and thus the covariance matrix $\mathbf{V}_M(P_\mathrm{N},P_\mathrm{A})$.


For the case of $p=0.2$, $q=0.4$ and $M=4$, we have
\begin{align}
\mathbf{V}_M(P_\mathrm{N},P_\mathrm{A})
&=\left[
\begin{array}{cccc}
0.1331&0.1106&0.1106\\
0.1106&0.1331&0.1106\\
0.1106&0.1106&0.1331
\end{array}
\right].
\end{align}
\begin{figure}[tb]
\centering
\includegraphics[width=.6\columnwidth]{simulate_fr.eps}
\caption{Simulated false reject probability when there is one outlying sequence out of $M=4$ sequences. The nominal distribution is $P_\mathrm{N}=\mathrm{Bern}(0.2)$ and the anomalous distribution is $P_\mathrm{A}=\mathrm{Bern}(0.4)$. The error bar denotes two standard deviations below and above the mean value. As observed, the simulated false reject probability approaches the target value as the lengths of observed sequences become moderate. This implies that our theoretical characterization in Theorem \ref{result:1outlier} is tight for this numerical example.}
\label{numericalSim}
\end{figure}


In Figure \ref{numericalSim}, the simulated false reject probability of our test in \eqref{test1outlier} is plotted versus a target value $\varepsilon=0.1$ for the case where there is only one outlying sequence out of $M=4$ observed sequences. For each $n\in\{100,125,\ldots,200,300,\ldots,1500\}$, the threshold in our test is chosen as
\begin{align}
\lambda=\mathrm{GD}_M(P_\mathrm{N},P_\mathrm{A})+\frac{L_M^*(\varepsilon|P_\mathrm{N},P_\mathrm{A})}{\sqrt{n}}.
\end{align}
Furthermore, for each data point, our test is run independently $10^7$ times and the false reject probability is calculated. From Figure \ref{numericalSim}, we observe that the simulated false reject probability meets the desired value when the length of the sequences is moderate. This illustrates that our theoretical characterization in Theorem \ref{result:1outlier} is tight, at least for this numerical example.


\section{Case of Multiple Outlying Sequences}
\label{sec:Tout}
In this section, we generalize the results in Section \ref{sec:pf} to the case of multiple outlying sequences where each outlying sequence can be generated according to a potentially different anomalous distribution. 

\subsection{Problem Formulation}
Assume that there are $T$ outlying sequences out of $M$ observed sequences $\mathbf{X}=(X_1^n,\ldots,X_M^n)$. Throughout the section, we assume $T<\frac{M}{2}$ since otherwise the problem is ill-posed.  Note that there are in total ${M \choose T}$ possible configurations of outlying sequences. For simplicity, let $\mathcal{S}_T$ denote the set of all subsets of $[M]$ of size $T$, i.e.,
\begin{align}
\mathcal{S}_T
&:=\{\mathcal{B}\subset[M]:|\mathcal{B}|=T\}.
\end{align}
The multiple anomaly sequence detection task is to identify the set of outlying sequences, i.e., the set of sequences that are from an anomalous distribution.  We assume that each outlying sequence is generated i.i.d. according to a potentially unique anomalous distribution, i.e., there exists a sequence of anomalous distributions $(P_{\mathrm{A},1},\ldots,P_{\mathrm{A},T})\in(\mathcal{P}(\mathcal{X})^T$ and if $\mathcal{B}\in\mathcal{S}_T$ denotes the indices of $T$ outlying sequences, then for any $t\in\mathcal{B}$, $X_t^n$ is generated i.i.d. from $P_{\mathrm{A},\jmath_\mathcal{B}(t)}$. Recall for any $i\in\mathcal{B}$, $\jmath_\mathcal{B}(i)=j$ if $i$ is the $j$-th largest element in $\mathcal{B}$ (cf. the Notation Section).

Formally, the task is to design a test $\phi_n:\mathcal{X}^{Mn}\to \{\{\mathrm{H}_\mathcal{B}\}_{\mathcal{B}\in\mathcal{S}_T},\mathrm{H}_\mathrm{r}\}$ to classify between the following ${M \choose T}+1$ hypotheses:
\begin{itemize}
\item $\mathrm{H}_\mathcal{B}$ where $\mathcal{B}\in\mathcal{S}_T$: the set of outlying sequences are sequences $X_j^n$ with $j\in\mathcal{B}$;
\item $\mathrm{H}_\mathrm{r}$: there is no outlying sequence.
\end{itemize}
Similarly to Section \ref{sec:pf}, the reject option is introduced as in \cite{gutman1989asymptotically,unnikrishnan2015asymptotically,zhou2018binary}.

Given any test $\phi_n$, for any tuple of nominal and anomalous distributions $\mathbf{P}_M:=(P_\mathrm{N},P_{\mathrm{A},1},\ldots,P_{\mathrm{A},T})$, the performance of $\Phi_n$ is evaluated by the following misclassification error, false reject and false alarm probabilities:
\begin{align}
\beta_{\mathcal{B}}(\phi_n|\mathbf{P}_M)
&:=\mathbb{P}_{\mathcal{B}}\{\phi_n(\mathbf{X}^n)\notin\{\mathrm{H}_\mathcal{B},\mathrm{H}_\mathrm{r}\}\}\label{def:errorsetS},\\
\zeta_{\mathcal{B}}(\phi_n|\mathbf{P}_M)
&:=\mathbb{P}_{\mathcal{B}}\{\phi_n(\mathbf{X}^n)=\mathrm{H}_\mathrm{r}\}\label{def:rejectsetS},\\
\mathrm{P}_{\mathrm{fa}}(\phi_n|\mathbf{P}_M)
&:=\mathbb{P}_\mathrm{r}\{\phi_n(\mathbf{X}^n)\neq\mathrm{H}_\mathrm{r}\}\label{def:falarmM},
\end{align}
where $\mathcal{B}\in\mathcal{S}_T$ and we define $\mathbb{P}_{\mathcal{B}}(\cdot):=\Pr\{\cdot|\mathrm{H}_\mathcal{B}\}$ where for $i\in\mathcal{M}_\mathcal{S}$, $X_i^n$ is generated i.i.d. from the nominal distribution $P_\mathrm{N}$ and for $i\in\mathcal{S}$, $X_i^n$ is generated i.i.d. from an nominal distribution $P_{\mathrm{A},\jmath_\mathcal{S}(i)}$, and we define $\mathbb{P}_\mathrm{r}(\cdot):=\Pr\{\cdot|\mathrm{H}_\mathrm{r}\}$, where all sequences are generated i.i.d. from the nominal distribution $P_\mathrm{N}$. Recall that $\mathcal{M}_\mathcal{S}$ denotes the set $\mathcal{M}\setminus\mathcal{S}$. For simplicity, we let $\mathcal{P}_T(\mathcal{X})$ denote the collection of distributions $(\tilde{P}_\mathrm{N},\tilde{P}_{\mathrm{A},1},\ldots,\tilde{P}_{\mathrm{A},T})\in(\mathcal{P}(\mathcal{X}))^{T+1}$ such that $\tilde{P}_\mathrm{N}\neq \tilde{P}_{\mathrm{A},t}$ for all $t\in[T]$.



Parallel to \eqref{def:l^*} and \eqref{def:tau*}, for any $n\in\mathbb{N}$, $\varepsilon\in(0,1)$ and $E\in\mathbb{R}_+$, we are interested in the following fundamental limits of universal tests which ensure that (i) the misclassification error probability under each hypothesis for all tuples of nominal and anomalous distributions decay exponentially fast, (ii) the false alarm probability decays exponentially fast for all tuples of distributions and (iii) the false reject probability under each hypothesis for a particular tuple of distributions is subject to either constant or exponential type constraints, i.e.,
\begin{align}
\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)
\nn&:=\sup\{\lambda\in\mathbb{R}_+:~\exists~\phi_n~\mathrm{s.t.~}\forall~\mathcal{B}\in\mathcal{S}_T,~\zeta_\mathcal{B}(\phi_n|\mathbf{P}_M)\leq \varepsilon,~\mathrm{and}\\*
&\forall~\tilde{\mathbf{P}}_M\in\mathcal{P}_T(\mathcal{X}),~\beta_\mathcal{B}(\phi_n|\tilde{\mathbf{P}}_M)\leq \exp(-n\lambda),~\mathrm{P}_{\mathrm{fa}}(\phi_n|\tilde{\mathbf{P}}_M)\leq \exp(-n\lambda)\}\label{def:L^*}
\end{align}
and
\begin{align}
\xi^*(n,E|T,\mathbf{P}_M)
\nn&:=\sup\{\lambda\in\mathbb{R}_+:~\exists~\phi_n~\mathrm{s.t.~}\forall~\mathcal{B}\in\mathcal{S}_T,~\zeta_\mathcal{B}(\phi_n|\mathbf{P}_M)\leq \exp(-nE),~\mathrm{and}\\*
&\forall~\tilde{\mathbf{P}}_M\in\mathcal{P}_T(\mathcal{X}),~\beta_\mathcal{B}(\phi_n|\tilde{\mathbf{P}}_M)\leq \exp(-n\lambda),~\mathrm{P}_{\mathrm{fa}}(\phi_n|\tilde{\mathbf{P}}_M)\leq \exp(-n\lambda)\}\label{def:xi*}.
\end{align}
The purpose of this section is to provide tight asymptotic characterizations of both $\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)$ and $\xi^*(n,E|T,\mathbf{P}_M)$.

\subsection{Preliminaries}
Recall the definition of $\jmath_{\mathcal{S}}(\cdot)$ in the notation section. Paralleling \eqref{def:id1} and \eqref{def:id2}, given any tuple of distributions $\mathbf{P}_M=(P_\mathrm{N},P_{\mathcal{A},1},\ldots,P_{\mathrm{A},T})\in(\mathcal{P}(\mathcal{X}))^{T+1}$, for any $T\in[M]$ and any two sets $(\mathcal{B},\mathcal{C})\in\mathcal{S}_T$, for each $x\in\mathcal{X}$, define the following mixture distribution
\begin{align}
P_{\rm{Mix}}^{(\mathcal{B},\mathcal{C},\mathbf{P}_M)}(x)
&:=\frac{1}{M-T}\Big(\sum_{i\in(\mathcal{B}\cap\mathcal{M}_{\mathcal{C}})}P_{\mathrm{A},\jmath_\mathcal{B}(i)}(x)+\sum_{i\in(\mathcal{M}_{\mathcal{B}}\cap\mathcal{M}_{\mathcal{C}})}P_\mathrm{N}(x)\Big)\label{def:Pmix}
\end{align}
and the following information densities (log likelihoods)
\begin{align}
\imath_{1,t}(x|\mathcal{B},\mathcal{C},\mathbf{P}_M)&:=\log\frac{P_{\mathrm{A},t}(x)}{P_{\rm{Mix}}^{(\mathcal{B},\mathcal{C},\mathbf{P}_M)}(x)},~t\in[T]\label{def:i1T},\\
\imath_{2,T}(x|\mathcal{B},\mathcal{C},\mathbf{P}_M)&:=\log\frac{P_\mathrm{N}(x)}{P_{\rm{Mix}}^{(\mathcal{B},\mathcal{C},\mathbf{P}_M)}(x)}\label{def:i2T}.
\end{align}
Similarly to \eqref{def:GD} to \eqref{def:cov}, define the following linear combinations of expectations and variances of information densities:
\begin{align}
\nn&\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)\\*
&:=\sum_{i\in(\mathcal{B}\cap\mathcal{M}_{\mathcal{C}})}\mathbb{E}_{P_{\mathrm{A},\jmath_\mathcal{B}(i)}}[\imath_{1,\jmath_\mathcal{B}(i)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]+\sum_{i\in(\mathcal{M}_{\mathcal{B}}\cap\mathcal{M}_{\mathcal{C}})}\mathbb{E}_{P_\mathrm{N}}[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\\
&=\sum_{i\in(\mathcal{B}\cap\mathcal{M}_{\mathcal{C}})}D(P_{\mathrm{A},\jmath_\mathcal{B}(i)}\|P_{\rm{Mix}}^{(\mathcal{B},\mathcal{C},\mathbf{P}_M)})+\sum_{i\in(\mathcal{M}_{\mathcal{B}}\cap\mathcal{M}_{\mathcal{C}})}D(P_{\mathrm{N}}\|P_{\rm{Mix}}^{(\mathcal{B},\mathcal{C},\mathbf{P}_M)})\label{def:GDBC},\\
\nn&\mathrm{V}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)\\*
&:=\sum_{i\in(\mathcal{B}\cap\mathcal{M}_{\mathcal{C}})}\mathrm{Var}_{P_{\mathrm{A},\jmath_\mathcal{B}(i)}}[\imath_{1,\jmath_\mathcal{B}(i)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]+\sum_{i\in(\mathcal{M}_{\mathcal{B}}\cap\mathcal{M}_{\mathcal{C}})}\mathrm{Var}_{P_\mathrm{N}}[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\label{def:VBC},
\end{align}
and the covariance
\begin{align}
\mathrm{Cov}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)
\nn&:=-\big(\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)\big)^2+\sum_{j\in(\mathcal{B}\cap\mathcal{M}_\mathcal{C}\cap\mathcal{M}_\mathcal{D})}\mathbb{E}_{P_{\jmath_\mathcal{B}(j)}}\Big[\big(\imath_{1,\jmath_\mathcal{B}(j)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)\big)^2\Big]\\*
\nn&\qquad+\sum_{j\in(\mathcal{B}\cap\mathcal{M}_\mathcal{C})}\sum_{l\in(\mathcal{B}\cap\mathcal{M}_\mathcal{D}\cap\mathcal{M}_j)}\mathbb{E}_{P_{\jmath_\mathcal{B}(j)}}[\imath_{1,\jmath_\mathcal{B}(j)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\mathbb{E}_{P_{\jmath_\mathcal{B}(l)}}[\imath_{1,\jmath_\mathcal{B}(l)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\\*
\nn&\qquad+\sum_{j\in(\mathcal{B}\cap\mathcal{M}_\mathcal{C})}\sum_{\bar{l}\in(\mathcal{M}_\mathcal{B}\cap\mathcal{M}_\mathcal{D})}
\mathbb{E}_{P_{\jmath_\mathcal{B}(j)}}[\imath_{1,\jmath_\mathcal{B}(j)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\mathbb{E}_{P_{\jmath_\mathcal{B}(l)}}[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\\*
\nn&\qquad+\sum_{\bar{j}\in(\mathcal{M}_\mathcal{B}\cap\mathcal{M}_\mathcal{C})}\sum_{l\in(\mathcal{B}\cap\mathcal{M}_\mathcal{D})}\mathbb{E}_{P_{\jmath_\mathcal{B}(\bar{j})}}[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\mathbb{E}_{P_{\jmath_\mathcal{B}(l)}}[\imath_{1,\jmath_\mathcal{B}(l)}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\\
&\qquad+
\sum_{\bar{j}\in(\mathcal{M}_\mathcal{B}\cap\mathcal{M}_\mathcal{C})}\sum_{\bar{l}\in(\mathcal{M}_\mathcal{B}\cap\mathcal{M}_\mathcal{D}\cap\mathcal{M}_{\bar{j}})}
\mathbb{E}_{P_{\jmath_\mathcal{B}(\bar{j})}}\big[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\big]\mathbb{E}_{P_{\jmath_\mathcal{B}(\bar{l})}}\big[\imath_{2,T}(X|\mathcal{B},\mathcal{C},\mathbf{P}_M)]\big].
\end{align}


Similarly to \eqref{defdispersionmatrix}, define a covariance matrix $\mathbf{V}(\mathcal{B},\mathcal{C},\mathbf{P}_M)=\{V_{i,j}(\mathbf{P}_M)\}_{(i,j)\in[|\mathcal{S}_T|-1]^2}$ where
\begin{align}
V_{i,j}(\mathbf{P}_M)\}_{(i,j)\in[|\mathcal{S}_T|-1]^2}
&=\left\{
\begin{array}{ll}
\mathrm{V}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)&\mathrm{if~}i=j,\\
\mathrm{Cov}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)&\mathrm{otherwise.}
\end{array}
\right.
\end{align}
Recall the definition of the complementary cdf $\mathrm{Q}_k(\cdot)$ in \eqref{def:kQ}. Similar to \eqref{def:L*PNPA}, we let
\begin{align}
L_{M,T}^*(\varepsilon|\mathcal{B},\mathcal{C},\mathbf{P}_M)
&:=\max\Big\{L\in\mathbb{R}:\mathrm{Q}_{|\mathcal{S}_T|-1}(L\times\mathbf{1}_{|\mathcal{S}_T|-1};\mathbf{0}_{|\mathcal{S}_T|-1};\mathbf{V}(\mathcal{B},\mathcal{C},\mathbf{P}_M))\geq 1-\varepsilon\Big\}\label{def:L*PT},
\end{align}


Using \eqref{def:GDBC}, we define the following minimal value of $\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)$:
\begin{align}
\mathrm{GD}_T(\mathbf{P}_M)
&:=\min_{(\mathcal{B},\mathcal{C})\in\mathcal{S}_T^2:\mathcal{C}\neq\mathcal{B}}\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)\label{def:rmGDPT}.
\end{align}
Given $n\in\mathbb{N}$ and $\varepsilon\in(0,1)$, let
\begin{align}
\mathrm{GD}_T(n,\varepsilon,\mathbf{P}_M)
&:=\min_{(\mathcal{B},\mathcal{C})\in\mathcal{S}_T^2:\mathcal{C}\neq\mathcal{B}}\bigg(\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M)+\frac{L_{M,T}^*(\varepsilon|\mathcal{B},\mathcal{C},\mathbf{P}_M)}{\sqrt{n}}\bigg)\label{def:rmGD}.
\end{align}
As we shall show, $\mathrm{GD}_T(\mathbf{P}_M)$ is the asymptotic homogeneous decay rate of misclassification error and false alarm probabilities of universal tests whose false reject probabilities with respect to $\mathbf{P}_M$ are upper bounded by a constant, i.e., $\lim_{n\to\infty}\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)$.

Furthermore, given a sequence of distributions $\mathbf{Q}=(Q_1,\ldots,Q_M)\in\mathcal{P}(\mathcal{X})^M$ and each $\mathcal{B}\in\mathcal{S}_T$, define the following linear combination of KL Divergence terms
\begin{align}
\mathrm{G}_B(\mathbf{Q})
&:=\sum_{t\in\mathcal{M}_{\mathcal{B}}}D\left(Q_t\bigg\|\frac{\sum_{l\in\mathcal{M}_\mathcal{B}}Q_l}{M-T}\right)\label{def:gB}.
\end{align}

Finally, given any $\lambda\in\mathbb{R}_+$ and any tuple of distributions $\mathbf{P}_M=(P_\mathrm{N},P_{\mathrm{A},1},\ldots,P_{\mathrm{A},T})\in\mathcal{P}_T(\mathcal{X})$, for each $\mathcal{B}\in\mathcal{S}_T$, define the following quantity:
\begin{align}
\mathrm{LD}(\lambda,\mathbf{P}_M)
&:=\min_{(\mathcal{B},\mathcal{C})\in\mathcal{S}_T^2:\mathcal{B}\neq\mathcal{C}}\min_{\substack{\mathbf{Q}\in(\mathcal{P}(\mathcal{X}))^M:\\\mathrm{G}_\mathcal{B}(\mathbf{P}_M)\leq \lambda,~\mathrm{G}_\mathcal{C}(\mathbf{P}_M)\leq\lambda}}\Big(\sum_{i\in\mathcal{B}}D(Q_i\|P_{\mathrm{A},\jmath_\mathcal{B}(i)})+\sum_{i\in\mathcal{M}_\mathcal{B}}D(Q_i\|P_\mathrm{N})\Big)\label{def:LDT}.
\end{align}



\subsection{Main Results}

Our first result characterizes $\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)$, the decay rate of misclassification error and false alarm probabilities of universal tests whose false reject probabilities with respect to distributions $\mathbf{P}_M$ are upper bounded by a constant $\varepsilon$.

\begin{theorem}
\label{result:Toutlier}
Given any tuple of distributions $\mathbf{P}_M=(P_\mathrm{N},P_1,\ldots,P_M)\in(\mathcal{P}(\mathcal{X}))^{M+1}$, for any $\varepsilon\in(0,1)$, we have
\begin{align}
\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)&=\mathrm{GD}_T(n,\varepsilon,\mathbf{P}_M)+O\left(\frac{\log n}{n}\right)\label{perform:Tout}.
\end{align}
Furthermore, the performance (decay rate) in \eqref{perform:Tout} is achieved by the following test:
\begin{align}
\label{test:Toutlier}
\Psi_n(\mathbf{x}^n)
&:=\left\{
\begin{array}{cc}
\mathrm{H}_\mathcal{B}&\mathrm{if~}\mathrm{S}_\mathcal{B}(\mathbf{x}^n)\leq \tilde{\lambda}<\min_{\mathcal{C}\in\mathcal{S}_T:\mathcal{C}\neq\mathcal{B}}\mathrm{S}_\mathcal{C}(\mathbf{x}^n)\\
\mathrm{H}_\mathrm{r}&\mathrm{otherwise},
\end{array}
\right.
\end{align}
where $\mathbf{x}^n$ denotes the collection of the observed sequences $(x_1^n,\ldots,x_M^n)$, $\tilde{\lambda}$ is a chosen threshold (cf. \eqref{chooselambda2}) and $\mathrm{S}_\mathcal{C}(\cdot)$ is a scoring function defined as
\begin{align}
\mathrm{S}_\mathcal{C}(\mathbf{x}^n)
&:=\mathrm{G}_\mathcal{C}(\hat{T}_{x_1^n},\ldots,\hat{T}_{x_M^n}).
\end{align}
\end{theorem}
The proof of Theorem \ref{result:Toutlier} is similar to Theorem \ref{result:1outlier} and is provided in Appendix \ref{proof:result:Toutlier}.  The remarks made for Theorem \ref{result:1outlier} are also valid here, for example, the existence of phase transition phenomenon and the least favorable set of distributions.


Theorem \ref{result:Toutlier} elucidates the effect of the total number of sequences $M$ and the number of the outliers $T$ on the performance of an optimal test. To do so, it suffices to analyze the dominant term in the exponent, i.e., $\mathrm{GD}_T(\mathbf{P}_M)$, since our result implies that for any $\varepsilon\in(0,1)$,
\begin{align}
\lim_{n\to\infty}\Lambda^*(n,\varepsilon|T,\mathbf{P}_M)
&=\mathrm{GD}_T(\mathbf{P}_M)\\
&=\min_{(\mathcal{B},\mathcal{C})\in\mathcal{S}_T^2:\mathcal{C}\neq\mathcal{B}}\mathrm{GD}_T(\mathcal{B},\mathcal{C},\mathbf{P}_M).
\end{align}
However, in general, it is hard to analyze the property of $\mathrm{GD}_T(\mathbf{P}_M)$ as a function of $M$ and $T$. Thus, we specialize to the special case of homogeneous anomalous distributions, i.e., $P_{\mathrm{A},i}=P_\mathrm{A}$ for all $i\in[T]$ where $P_\mathrm{A}$ is an anomalous distribution. Under such a case, we have  
\begin{align}
\mathrm{GD}_T(\mathbf{P}_M)
&=\min_{t\in[T]}\Big(t D(P_\mathrm{A}\|P_{\mathrm{Mix}}^{t,P_\mathrm{N},P_\mathrm{A}})+(M-T-t)D(P_\mathrm{N}\|P_{\mathrm{Mix}}^{t,P_\mathrm{N},P_\mathrm{A}})\Big)\label{simplifytohomo},
\end{align}
where
\begin{align}
P_{\mathrm{Mix}}^{t,P_\mathrm{N},P_\mathrm{A}}=\frac{1}{M-T}\Big(tP_{\mathrm{A},\jmath_\mathcal{B}(i)}(x)+(M-T-t)P_\mathrm{N}(x)\Big).
\end{align}
For simplicity, let $f(M,T,t)$ denote the objective function in \eqref{simplifytohomo}.
Note that for ant $t\in[T]$,
\begin{align}
\frac{\partial f(M,T,t)}{\partial M}&=D(P_\mathrm{N}\|P_{\mathrm{Mix}}^{t,P_\mathrm{N},P_\mathrm{A}})>0,\\
\frac{\partial f(M,T,t)}{\partial T}&=-D(P_\mathrm{N}\|P_{\mathrm{Mix}}^{t,P_\mathrm{N},P_\mathrm{A}})<0.
\end{align}
Therefore, the performance of the optimal test in \eqref{test:Toutlier} increases in $M$ and decreases in $T$. In other words, when the total number of sequences $M$ is fixed, the performance of the optimal test degrades when the number of outlying sequences $T$ increases. On the other hand, when $T$ is fixed, the performance of the optimal test improves when $M$ increases.

Theorem \ref{result:Toutlier} also implies that the test in \eqref{test:Toutlier} is second-order asymptotically optimal for the simultaneous detection and identification of $T$ outliers. Note that our test outputs a reject decision if there are two competitive sets of candidate outliers whose scoring functions are both below a given threshold $\tilde{\lambda}$.

The optimality of the test~\eqref{test:Toutlier} continues to hold if the number of outliers is \emph{unknown} but an upper bound, say $\hat{T}$, is known. Using a slight modification of our test in \eqref{test:Toutlier}, one can verify that our result holds with $T$ replaced by $\hat{T}$. Under such a case, we have a total number of $\sum_{t\in[\hat{T}]} {M \choose t}+1$ number of hypotheses. Our test in \eqref{test:Toutlier} should be modified by replacing $\min_{\mathcal{C}\in\mathcal{S}_T:\mathcal{C}\neq\mathcal{B}}$ by $\min_{\mathcal{C}\in\bigcup_{t\in[\hat{T}]}\mathcal{S}_t:\mathcal{C}\neq\mathcal{B}}$ to account for all possible sets of outliers.



Our next result concerns the asymptotic characterization of $\xi^*(n,E|T,P_\mathrm{N},\mathbf{P}_M)$, the decay rate of misclassification error and false alarm probabilities of universal tests whose false reject probabilities with respect to distributions $\mathbf{P}_M$ decay exponentially fast with speed of at least $E$.
For simplicity, given any $E\in\mathbb{R}_+$ and any tuple of distributions $\mathbf{P}_M\in\mathcal{P}_T(\mathcal{X})$, let
\begin{align}
f_T(E,\mathbf{P}_M)&:=\sup\Big\{\lambda\in\mathbb{R}_+:\min_{\mathcal{B}\in\mathcal{S}_T}\mathrm{LD}(\lambda,\mathbf{P}_M)\geq E\Big\}\label{def:fEPT}.
\end{align}

\begin{theorem}
\label{result:Tout:exp}
For any $\mathbf{P}_M\in\mathcal{P}_T(\mathcal{X})$ and any $E\in\mathbb{R}_+$, we have 
\begin{align}
\lim_{n\to\infty}\xi^*(n,E|T,\mathbf{P}_M)=f(E,\mathbf{P}_M).
\end{align}
\end{theorem}
The proof of Theorem \ref{result:Tout:exp} is similar to that of Theorems \ref{result:exp1out} and \ref{result:Toutlier} and is  omitted for simplicity. 

We make use of the test in \eqref{test:Toutlier} in the achievability part of the proof and thus demonstrate its optimality. Furthermore, in the achievability analysis, the exponent of the false reject probability under hypothesis $\mathrm{H}_\mathcal{B}$ is $\mathrm{LD}(\lambda,\mathbf{P}_M)$ for each $\mathcal{B}\in\mathcal{S}_T$. Theorem \ref{result:Tout:exp} illustrates the tradeoff between the false reject exponent $E$ and the homogeneous exponent $f_T(E,\mathbf{P}_M)$ of misclassification error and false alarm probabilities. Similar remarks as those for Theorem \ref{result:exp1out} apply here.

\section{Conclusion}
\label{sec:conclude}
In this paper, we obtained tight bounds on asymptotic decay rates of misclassification error and false alarm probabilities subject to constraints on false reject probabilities for outlying sequence detection with reject option. The tradeoff among misclassification error, false alarm and false reject probabilities of optimal universal tests was established. Our results provide benchmarks for practical algorithms and can potentially guide the design of low-complexity algorithms to achieve optimal performance. Furthermore, we generalize our results to the case of multiple outlying sequences where each outlying sequence can follow a different anomalous distribution.

There are several avenues for future research. One can consider a sequential setting under our formulation by incorporating ideas from~\cite{li2017universal} to derive the asymptotic limits of an optimal sequential test. Furthermore, it is also of interest to study the case where each nominal sample is generated from a potentially different distribution in a neighborhood of a nominal distribution and then derive the performance of the optimal test. In this case, we also need to assume that any anomalous distribution lies outside the neighborhood of the nominal distribution since otherwise the problem is ill-posed.



