Sequential anomaly identification with observation control under generalized error metrics

In many scientific and engineering applications, measurements from various data sources are collected sequentially, aiming to identify in real-time the sources, if any, with “anomalous” statistical behavior. In internet security systems [2], for example, the data streams may refer to the transition rate of a link, where a meager rate warns of a possible intrusion. In finance, the data streams may refer to prices in the stock market [3], where we need to detect an unusual rate of return of a stock price.

Such applications, among many others, motivate the formulation of sequential multiple testing problems where multiple data sources are monitored sequentially, a binary hypothesis testing problem is formulated for each of them, and the goal is to simultaneously solve these testing problems as quickly as possible, while controlling certain error metrics. In some works, e.g.,[4, 5, 6], it is assumed that all sources can be monitored at each sampling instant upon stopping. In others, e.g., [7, 8, 9, 10, 11, 12, 13, 14, 15], a sampling constraint is imposed, according to which it is possible to observe only a subset of sources at each time instant, but the decision maker selects which ones to sample based on the already collected data. In the latter case, in addition to a stopping rule and a decision rule that determine when to stop sampling and which sources to identify as anomalous upon stopping, it is also required to specify a sampling rule, which determines the sources to be sampled at each time instant until stopping. This sampling constraint leads to a sequential multiple testing problem with adaptive sampling design, which lies in the field of “sequential testing with controlled sensing”, or “sequential design of experiments” [16], [17], [18], [19]. Hence, methods and results from these works are applicable as well.

In the above works, the problem formulation requires, implicitly or explicitly, control of the “classical” misclassification error rate, i.e., the probability of at least one error, of any kind, or of the two “classical” familywise error rates, i.e., the probabilities of at least one false alarm and at least one missed detection. However, such error metrics can be impractical, especially when there is a common stopping time at which the decision is made for all data sources, as in the above papers. Indeed, even with a relatively small number of data sources, a single “difficult” hypothesis may determine, even inflate, the overall time required for the decisions to be made.

This inflexibility has motivated the adoption of more lenient error metrics, which are prevalent in the fixed-sample-size literature of multiple testing [20, 21, 22]. As it was shown in [22], the methodology and asymptotic optimality theory in [6], [9] for the sequential identification problem under classical familywise error rates remain valid with other error metrics as long as the latter are bounded above and below up to a multiplicative constant by the corresponding classical familywise error rates. ¹¹1The authors in [22] focus in the full sampling case, but exactly the same arguments apply in the case of sampling constraints. This is indeed the case for many error metrics, such as the false discovery rate (FDR) and the false non-discovery rate (FNR) [23]. However, it is not the case for others, such as the generalized misclassification error rate, which requires control of the probability of at least $k$ errors of any kind, and the generalized familywise type-I and type-II errors [24, 25, 26], which require control of the probabilities of at least $k_{1}$ false alarms and at least $k_{2}$ missed detections. As it was shown in [27] in the case of full sampling, that is, when all data sources are continuously monitored and there are no sampling constraints, the sequential identification problem with these generalized error metrics when $k>1$ or $k_{1}+k_{2}>2$ requires a distinct methodology and pose additional mathematical challenges compared to their corresponding classical versions, where $k=1$ or $k_{1}=k_{2}=1$.

In the present work, we address the same sequential anomaly identification problem as in [27], but in the presence of sampling constraints. That is, unlike [27], we assume that it is not possible to observe all data sources at all times. Instead, we impose an upper bound on the average number of samples collected from all sources up to stopping. For each of the two resulting problem formulations, i.e., for each of the two generalized error metrics under consideration, (i) we establish a universal lower bound on the optimal expected time for stopping, to a first-order asymptotic approximation as the corresponding error probabilities go to zero, (ii) we show that this lower bound is attained by a policy that utilizes the stopping and decision rules in [27], as long as the long-run sampling frequency of each source is greater than or equal to a certain value, which is computed explicitly and depends both on the source and on the true subset of anomalous sources, (iii) we show that the latter can be achieved by a probabilistic sampling rule.

The methodology and the theory that we develop in the present work is based on an interplay of techniques, ideas, and methods from the sequential multiple testing problem with full sampling and generalized error control in [27], and the sequential multiple testing problem with sampling constraints and “classical” familywise error control in [9]. However, there are various interesting special features that arise in the present work, both from a technical but also from a methodological point of view. First, there are certain technical challenges which force us to strengthen some of our assumptions compared to [9]. Specifically, we require a stronger moment assumption on the log-likelihood ratio statistics than the finiteness of the Kullback-Leibler information numbers, and we have to postulate a harder sampling constraint (which is still weaker than the usual constraint in the literature that fixes the number of sources that are sampled at each time instant). Second, while in [9] it is shown that there is no need for “forced exploration”, as in the general sequential testing problem with controlled sensing [16, 17], this turns out to be needed in this work.

The remainder of the paper is organized as follows. In Section II, we formulate the two problems we consider in this work. In Section III, we state and solve two auxiliary max-min optimization problems, which play a key role in the formulation of our main results. In Section IV, we state the universal asymptotic lower bound for each of the two problems. In Section V, for each of the two problems, we introduce a family of policies that satisfies the error constraints, and we state a criterion on the sampling rule that guarantees the asymptotic optimality of such a policy. In Section VI, we present a class of probabilistic sampling rules for which the aforementioned criterion is satisfied. In Section VII, we present a simulation study that illustrates our theoretical results, and in Section VIII, we state our conclusions and discuss future research directions.

We end this section with some notations we use throughout the paper. We use $:=$ to indicate the definition of a new quantity and $\equiv$ to indicate the equivalence of two notions. We set $\mathbb{N}:=\{1,2\ldots,\}$, $\mathbb{N}_{0}:=\{0\}\cup\mathbb{N}$, and $[n]:=\{1,\ldots,n\}$ for $n\in\mathbb{N}$. We denote by $|A|$ the size and by $2^{A}$ the powerset of a set $A$, and by $A\triangle B$ the symmetric difference of two sets $A,B$. The $\lfloor a\rfloor$, $\lceil a\rceil$ stand for the floor and the ceiling of a positive number $a$. The indicator function is denoted by $\mathbf{1}$. In a summation, if the lower limit is larger than the upper limit, then the summation is assumed to be equal to $0$. For positive sequences $(x_{n})$ and $(y_{n})$, we write $x_{n}\sim y_{n}$ when $\lim_{n}(x_{n}/y_{n})=1$, $x_{n}\gtrsim y_{n}$ when $\liminf_{n}(x_{n}/y_{n})\geq 1$, and $x_{n}\lesssim y_{n}$ when $\limsup_{n}(x_{n}/y_{n})\leq 1$. Finally, iid stands for independent and identically distributed.

Let $(\mathbb{S},\mathcal{S})$ be a measurable space and let $(\Omega,\mathcal{F},\mathsf{P})$ be a probability space that hosts $M$ independent sequences of iid, $\mathbb{S}$-valued random elements, $\{X_{i}(n),n\in\mathbb{N}\}$, $i\in[M]$, which are generated by $M$ distinct data sources, and $M$ independent sequences of random variables, $\{Z_{i}(n):n\in\mathbb{N}\}$, $i\in[M]$, uniformly distributed in $(0,1)$, to be used for randomization purposes. For each $i\in[M]$, we assume that each $X_{i}(n)$ has a density with respect to some $\sigma$-finite measure $\nu_{i}$ that is equal to either $f_{1i}$ or $f_{0i}$, and we say that source $i$ is “anomalous” if its density is $f_{1i}$. We denote by $\mathsf{P}_{A}$ the underlying probability measure, and by $\mathsf{E}_{A}$ the corresponding expectation, when the subset of anomalous sources is $A\subseteq[M]$. We simply write $\mathsf{P}$ and $\mathsf{E}$ whenever the identity of the subset of anomalous sources is not relevant.

The problem we consider is the identification of the anomalous sources, if any, on the basis of sequentially acquired observations from all sources when it is not possible to observe all of them at every sampling instant. Specifically, we have to specify (i) the random time, $T$, at which sampling is terminated, (ii) the subset of sources, $\Delta$, that are declared as anomalous upon stopping, and, for each $n\leq T$, (iii) the subset, $R(n)$, of sources that are sampled at time $n$. At any time instant, the decision whether to stop or not, as well as the subsets of sources that are identified as anomalous in the former case, or sampled next in the latter, must be determined based on the already collected data.

Therefore, we say that $R:=\{R(n):n\in\mathbb{N}\}$ is a sampling rule if $R(n)$ is $\mathcal{F}^{R}_{n-1}$-measurable for every $n\in\mathbb{N}$, where

and $Z(n):=(Z_{1}(n),\ldots,Z_{M}(n))$. Moreover, we say that the triplet $(R,T,\Delta)$ is a policy if

• (i)

  $R$ is a sampling rule,

• (ii)

  $T$ is a stopping time with respect to filtration $\{\mathcal{F}^{R}_{n}\,:\,n\in\mathbb{N}\}$,

• (iii)

  $\Delta$ is $\mathcal{F}^{R}_{T}$-measurable, i.e.,

  $$\{T=n,\Delta=D\}\in\mathcal{F}^{R}_{n},\quad\forall\;n\in\mathbb{N}\quad\text{and}\quad D\subseteq[M],$$

in which case we refer to $T$ as a stopping rule and to $\Delta$ as a decision rule.

We denote by $\mathcal{C}$ the family of all policies, and we focus on policies that satisfy a sampling constraint and control the probabilities of certain types of error. To define these, we need to introduce some additional notation. Thus, for any sampling rule $R$ and time instant $n\in\mathbb{N}$, we denote by $R_{i}(n)$ the indicator of whether source $i$ is sampled at time $n\in\mathbb{N}$, i.e.,

by $\pi_{i}^{R}(n)$ the proportion of times source $i$ has been sampled in the first $n$ time instants, i.e.,

and we note that the average number of observations from all sources in the first $n$ time instants is

In this section, we formulate and solve two auxiliary max-min optimization problems. These will be used in Section IV to express the asymptotic lower bounds for (8) and (10), and in Section V to design procedures that achieve these lower bounds.

To be specific, we denote by $\boldsymbol{L}:=\{L_{i}\,:\,i\in[|\boldsymbol{L}|]\}$ an ordered set of positive numbers, i.e.,

for each $i\in[|\boldsymbol{L}|]$, we denote by $\widetilde{L}_{i}$ the harmonic mean of the $|\boldsymbol{L}|-i+1$ largest elements in $\boldsymbol{L}$, i.e.,

and we also set $\widetilde{L}_{|\boldsymbol{L}|+1}:=\infty$. Then, assuming that $|\boldsymbol{L}|\leq M$, we introduce the following function,

where

• •

  $\kappa$ is a positive integer in $[|\boldsymbol{L}|]$,

• •

  $\boldsymbol{c}:=(c_{1},\ldots,c_{|\boldsymbol{L}|},0,\ldots,0)$ is a vector in

  $$\mathcal{D}(K):=\left\{(c_{1},\ldots,c_{M})\in[0,1]^{M}:\sum_{i=1}^{M}c_{i}\leq K\right\}.$$

  (17)

The constants $M$ and $K$ are defined as in the previous section, i.e., $M$ is a positive integer, and $K$ a real number in $(0,M]$.

In this section, we fix an arbitrary $A\subseteq[M]$, and $k,k_{1},k_{2},K$ as in Section II, and we establish a universal asymptotic lower bound for (8) and (10), as $\alpha\to 0$, and $\alpha,\beta\to 0$ respectively, under the moment assumption (12).