A large-scale multichannel sequential detection problem is considered, where an event occurs at some unknown time and affects the distributions of an unknown subset of data streams, possibly at a different time each of them. The goal is to detect this change as quickly as possible, while controlling the false alarm rate. An adaptive CuSum procedure is proposed, whose number of computations at each time instant is linear in the number of streams. Its performance is analyzed in various asymptotic regimes where the number of streams, the unknown number of affected streams, and the unknown delays in the emergence of the change all go to infinity as the false alarm rate goes to zero. The proposed scheme is shown to be asymptotically optimal in sparse and moderately high-dimensional regimes, and to enjoy a superior asymptotic performance to existing procedures in non-sparse or very high-dimensional regimes. Finally, it is compared with existing schemes in the literature in a simulation study.

The problem of testing a finite number of possibly composite hypotheses is considered, when it is required to control the probability of every type of wrong decision below a user-specified level. A general strategy is proposed for constructing a 3-stage test, in which the size of the second stage depends on the data collected in the first stage. Sufficient conditions are established for such an adaptive 3-stage test to achieve the optimal expected sample size, among all admissible sequential tests, to a first-order asymptotic approximation as the error probabilities go to zero at relatively symmetric rates. This general framework is applied to the case of general simple hypotheses, where the data are not necessarily i.i.d., as well as to the case of composite hypotheses of i.i.d. data coming from a one-parameter exponential family.

A setup with multiple, independent, sequentially monitored data streams is considered. For each of them, two composite hypotheses are postulated, with the interpretation that the stream is anomalous if the corresponding alternative hypothesis holds. It is of interest to detect as quickly as possible whether there is at least one anomalous stream, and also to identify upon stopping the subset of anomalous streams. To address this joint sequential detection and isolation problem, we propose a sequential multiple testing framework where the probabilities of four kinds of error are controlled below distinct, user-specified levels. Two of them refer to the detection task, and the other two to the isolation task. A testing policy is proposed and it is shown to achieve the minimum possible expected sample size, under each point of the parameter space, to a first order asymptotic approximation as the four target error probabilities go to 0. The general theory is illustrated in the case that the data streams generate iid observations that belong to a multiparameter exponential family.

A multistage test is proposed for the problem of testing an arbitrary number of simple hypotheses regarding the distribution of a sequence of i.i$\mathbf{d}$. random elements. The proposed test is shown to control the probability of each possible error under an arbitrary, user-specified level. Most importantly, it is shown to achieve the optimal expected sample size under every hypothesis, in the class of all sequential tests with the same levels of error control, to a first-order asymptotic approximation as these levels go to zero. These theoretical results are illustrated in a simulation study, where the proposed multistage test is compared with an asymptotically optimal fully-sequential test.

This paper considers the problem of sequentially detecting a change in the joint distribution of multiple data sources under a sampling constraint. Specifically, the channels or sources generate observations that are independent over time, but not necessarily across channels. The joint distribution of an unknown subset of sources changes at an unknown time instant. Moreover, there is a hard constraint that only a fixed number of sources can be sampled at each time instant, but the sources can be selected dynamically based on the already collected data. The goal is to sequentially observe the sources according to the constraint, and stop sampling as quickly as possible after the change while controlling the false alarm rate below a user-specified level. Thus, a policy for this problem consists of a joint sampling and change-detection rule. A non-randomized policy is studied, and an upper bound is established on its worst-case conditional expected detection delay with respect to both the change point and the observations from the affected sources before the change. In certain cases, this rule achieves first-order asymptotic optimality as the false alarm rate tends to zero, simultaneously under every possible post-change distribution and among all schemes that satisfy the same sampling and false alarm constraints. These general results are subsequently applied to the problems of (i) detecting a change in the marginal distributions of (not necessarily independent) information sources, and (ii) detecting a change in the covariance structure of Gaussian information sources.

The problem of sequential change diagnosis is considered, where a sequence of independent random elements is accessed sequentially, there is an abrupt change in its distribution at some unknown time, and there are two main operational goals: to quickly detect the change, and to accurately identify upon stopping the post-change distribution among a finite set of alternatives. The focus is on the min-CuSum algorithm, which raises an alarm as soon as a CuSum statistic that corresponds to one of the post-change alternatives exceeds a certain threshold. We obtain, under certain assumptions, non-asymptotic upper bounds on its conditional probability of misidentification given that a false alarm did not occur. When, in particular, the data are generated over independent channels and the change can occur in only one of them, its worst-case—with respect to the change point—conditional probability of misidentification given that there was not a false alarm is shown to decay exponentially fast in the threshold. As a corollary, in this setup, the min-CuSum is shown to asymptotically minimize Lorden’s detection delay criterion, simultaneously for every post-change scenario, within the class of schemes that satisfy prescribed bounds on both the false alarm rate and the worst-case conditional probability of misidentification, in a regime where the latter does not go to zero faster than the former. Finally, these theoretical results are also illustrated in simulation studies.

The problem of sequential anomaly detection is considered, where multiple data sources are monitored in real time and the goal is to identify the “anomalous” ones among them, when it is not possible to sample all sources at all times. A detection scheme in this context requires specifying not only when to stop sampling and which sources to identify as anomalous upon stopping, but also which sources to sample at each time instance until stopping. A novel formulation for this problem is proposed, in which the number of anomalous sources is not necessarily known in advance and the number of sampled sources per time instance is not necessarily fixed. Instead, an arbitrary lower bound and an arbitrary upper bound are assumed on the number of anomalous sources, and the fraction of the expected number of samples over the expected time until stopping is required to not exceed an arbitrary, user-specified level. In addition to this sampling constraint, the probabilities of at least one false alarm and at least one missed detection are controlled below user-specified tolerance levels. A general criterion is established for a policy to achieve the minimum expected time until stopping to a first-order asymptotic approximation as the two familywise error rates go to zero. Moreover, the asymptotic optimality is established of a family of policies that sample each source at each time instance with a probability that depends on past observations only through the current estimate of the subset of anomalous sources. This family includes, in particular, a novel policy that requires minimal computation under any setup of the problem.

A signal recovery problem is considered, where the same binary testing problem is posed over multiple, independent data streams. The goal is to identify all signals (resp. noises), i.e., streams where the alternative (resp. null) hypothesis is correct, subject to prescribed bounds on classical or generalized familywise error probabilities of both types. It is not required that the exact number of signals be a priori known, only upper bounds on the numbers of signals and noises are assumed instead. A decentralized formulation is adopted, according to which the sample size and the decision for each testing problem must be based only on observations from the corresponding data stream. A novel multistage testing procedure is proposed for this problem and is shown to enjoy a high-dimensional asymptotic optimality property. Specifically, it achieves the optimal, average over all streams, expected sample size, uniformly in the true number of signals, as the maximum possible numbers of signals and noises go to infinity at arbitrary rates, in the class of all sequential tests with the same global error control. In contrast, existing multistage tests in the literature are shown to achieve this high-dimensional asymptotic optimality property only under additional sparsity or symmetry conditions. These results are based on an asymptotic analysis for the fundamental binary testing problem as the two error probabilities go to zero. Moreover, they are supported by simulation studies and extended to problems with non-iid data and composite hypotheses.

In the problem of quickest change detection, a change occurs at some unknown time in the distribution of a sequence of random vectors that are monitored in real time, and the goal is to detect this change as quickly as possible subject to a certain false alarm constraint. In this work we consider this problem in the presence of parametric uncertainty in the post-change regime and controlled sensing. That is, the post-change distribution contains unknown parameters, and the distribution of each observation, before and after the change, is affected by a control action. In this context, in addition to a stopping rule that determines the time at which it is declared that the change has occurred, one also needs to determine a sequential control policy, which chooses the control action at each time based on the already collected observations that is "best" for the unknown post-change parameter. We formulate this problem mathematically using Lorden’s minimax criterion, and assuming that there are finitely many possible actions and post-change parameter values. We establish a universal lower bound on the worst-case detection delay, as the mean time to false alarm goes to infinity, which needs to be satisfied by any procedure for quickest change detection with controlled sensing. We then propose a specific procedure for this problem, which we call the Chernoff-CuSum procedure, for which the conditional expected detection delay, for any fixed value of the change-point, matches the universal lower bound up to a first-order asymptotic approximation as the mean time to false alarm goes to infinity.

The problem of sequential change diagnosis is considered, where a sequence of independent random elements is accessed sequentially, there is an abrupt change in its distribution at some unknown time, and there are two main operational goals: to quickly detect the change and to accurately identify the post-change distribution among a finite set of alternatives. A standard algorithm is considered, which does not explicitly address the isolation task and raises an alarm as soon as the CuSum statistic that corresponds to one of the post-change alternatives exceeds a certain threshold. It is shown that in certain cases, such as the so-called multichannel problem, this algorithm controls the worst-case conditional probability of false isolation and minimizes Lorden’s criterion, for every possible post-change distribution, to a first-order asymptotic approximation as the false alarm rate goes to zero sufficiently faster than the worst-case conditional probability of false isolation. These theoretical results are also illustrated with a numerical study.

The problem of testing two simple hypotheses about the distribution of iid random elements is considered. In particular, the focus is on multistage tests that control the two error probabilities below arbitrary, user-specified levels. A novel multistage test is proposed, analyzed, and shown to achieve the optimal expected sample size under both hypotheses, in the class of all sequential tests with the same error control, to a first-order approximation as the two target error probabilities go to zero at arbitrary rates. The proposed test is compared, both theoretically and numerically, with a multistage test that enjoys the same asymptotic optimality property under one of the two hypotheses, while performing much worse under the other.

The problem of sequentially detecting a change in the correlation structure of multiple Gaussian information sources is considered when it is possible to sample only two of them at each time instance. It is assumed that all sources are initially independent and that at least two of them become positively correlated after the change. The problem is to stop sampling as quickly as possible after the change, while controlling the false alarm rate and without assuming any prior information on the number of sources that become correlated. A joint sampling and change-detection rule is proposed and is shown to achieve the smallest possible worst-case conditional expected detection delay among all processes that satisfy the same constraints, to a first order approximation as the false alarm rate goes to 0, for any possible number of post-change correlated sources.

The problem of detecting and isolating a correlated pair among multiple Gaussian information sources is considered. It is assumed that there is at most one pair of correlated sources and that observations from all sources are acquired sequentially. The goal is to stop sampling as quickly as possible, declare upon stopping whether there is a correlated pair or not, and if yes, to identify it. Specifically, it is required to control explicitly the probabilities of three kinds of error: false alarm, missed detection, wrong identification. We propose a procedure that not only controls these error metrics, but also achieves the smallest possible average sample size, to a first-order approximation, as the target error rates go to 0. Finally, a simulation study is presented in which the proposed rule is compared with an alternative sequential testing procedure that controls the same error metrics.

The problem of sequential anomaly detection is considered under sampling constraints and generalized error control. It is assumed that there is no prior information on the number of anomalies. It is required to control the probability at least k errors, of any kind, upon stopping, where k is a user specified integer. It is possible to sample only a fixed number of processes at each sampling instance. The processes to be sampled are determined based on the already acquired observations. The goal is to find a procedure that consists of a stopping rule and a decision rule and a sampling rule that satisfy the sampling and error constraints, and have as small as possible average sample size for every possible scenario regarding the subset of anomalous processes. We characterize the optimal expected sample size for this problem to a first order approximation as the error probability vanishes to zero, and we propose procedures that achieve it. The performance of those procedures is compared in a simulation study for different values of k.

The problem of anomaly detection is considered when multiple processes are observed sequentially, but it is possible to sample only a subset of them at a time according to an adaptive sampling policy. The problem is to stop sampling as soon as possible and identify the anomalous processes, while controlling appropriate error probabilities. We consider two versions of this problem: in the first one there is no assumption regarding the anomalous processes, in the second their number is assumed to be known a priori. For each version, we obtain the optimal asymptotic performance as the error probabilities vanish and characterize the sampling rules that lead to asymptotic optimality. Moreover, we present two sampling rules for each setup, which differ in terms of the computational complexity and the actual performance they imply.

The problem of quickest change detection under transient dynamics is studied, where the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of transient phases. The observations within the different phases are generated by different distributions. The objective is to detect the change as quickly as possible, while controlling the average run length (ARL) to false alarm, when the durations of the transient phases are completely unknown. Two algorithms are considered: the dynamic Cumulative Sum (CuSum) algorithm, proposed in earlier work, and a newly constructed weighted dynamic CuSum algorithm. Both algorithms admit recursions that facilitate their practical implementation, and they are adaptive to the unknown transient durations. Specifically, their asymptotic optimality is established with respect to both Lorden's and Pollak's criteria as the ARL to false alarm and the durations of the transient phases go to infinity at any relative rate. Numerical results are provided to demonstrate the adaptivity of the proposed algorithms and to validate the theoretical results.

In the multisensor sequential change detection problem, a disruption occurs in an environment monitored by multiple sensors. This disruption induces a change in the observations of an unknown subset of sensors. In the Byzantine version of this problem, which is the focus of this work, it is further assumed that the postulated change-point model may be misspecified for an unknown subset of sensors. The problem then is to detect the change quickly and reliably, for any possible subset of affected sensors, even if the misspecified sensors are controlled by an adversary. Given a user-specified upper bound on the number of compromised sensors, we propose and study three families of sequential change-detection rules for this problem. These are designed and evaluated under a generalization of Lorden's criterion, where conditional expected detection delay and expected time to false alarm are both computed in the worst-case scenario for the compromised sensors. The first-order asymptotic performance of these procedures is characterized as the worst-case false alarm rate goes to 0. The insights from these theoretical results are corroborated by a simulation study.

In multichannel sequential change detection, multiple sensors monitor a system in which an abrupt change occurs at some unknown time and is perceived by an unknown subset of sensors. The goal is to detect this change quickly, while controlling the rate of false alarms. In the traditional asymptotic analysis of this problem, the false alarm rate goes to 0 while all other parameters remain fixed. We argue that this framework is not very informative, as the corresponding asymptotic optimality property cannot differentiate between universal and parsimonious rules. We propose an asymptotic framework in which the number of sensors also goes to infinity, and we show that in this context universal rules may fail to be asymptotically optimal when the number of streams is not very small. On the other hand, parsimonious rules are shown to be asymptotically optimal under reasonable sparsity conditions.

The problem of joint sequential change detection and isolation in a multichannel system is considered. It is assumed that a disruption occurs at some unknown time, and changes the distributions of the observations in an unknown subset of channels. The problem is to quickly detect the change, and at the same time to reliably isolate the affected channels. A novel scheme is proposed for this task, which admits a recursive structure, is scalable with respect to the number of channels, and does not require any prior information about the change-point. Its performance is analyzed in the special case that the number of affected channels is known. Specifically, explicit critical values are obtained for the control of the false alarm rate and the conditional probability of wrong isolation below arbitrary levels to be prescribed by the practitioner. Finally, the asymptotic optimality of the average detection delay of the proposed scheme is established as the error probabilities go to 0 and the effect of the prior distribution for the change point vanishes in the limit.

The problem of quickest change detection (QCD) under transient dynamics is studied, in which the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of cascading transient phases. It is assumed that the durations of the transient phases are deterministic but unknown. The goal is to detect the change as quickly as possible subject to a constraint on the average run length to false alarm. The dynamic CuSum (D-CuSum) algorithm is investigated, which is based on reformulating the QCD problem into a dynamic composite hypothesis testing problem, and has a recursion that facilitates implementation. We show that this algorithm is adaptive to the unknown change point, as well as the unknown transient duration. And under mild conditions of the pre-change and post-change distributions, its asymptotic optimality is demonstrated for all possible asymptotic regimes as the transient duration and the average run length to false alarm go to infinity.

We consider the problem of sequential signal detection in a multichannel system assuming that the number and location of signals are either unknown or only partially known a priori. We focus on the design and analysis of two sequential hypothesis tests: the generalized sequential likelihood ratio test and the mixture sequential likelihood ratio test. We develop an asymptotic theory for a general stochastic model, where the various data streams can be coupled and correlated, and the data in each stream can be dependent and non-identically distributed. Specifically, we show that the two proposed sequential detection procedures asymptotically minimize the expected sample size and even higher moments of the sample size in the class of hypothesis tests with given probabilities of errors under weak distributional assumptions. We also propose efficient importance sampling algorithms for estimating error probabilities of the sequential tests by Monte Carlo simulation. The general theory is illustrated with several practical examples, such as the detection of signals, in Gaussian hidden Markov models, white Gaussian noises with unknown intensity, and testing of the first-order autoregression's correlation coefficient. Finally, we illustrate our asymptotic results and compare the two proposed procedures with a simulation study.

We consider the problem of decentralized sequential change detection, in which K sensors monitor a system in real time, and at some unknown time there is an anomaly in the environment that changes the distribution of the observations in all sensors. The sensors communicate with a fusion center that is responsible for quickly detecting the change, while controlling the false alarm rate. We focus on two families of decentralized detection rules with minimal communication requirements. First, we assume that each sensor runs a local CUSUM algorithm and communicates with the fusion center only once, when it detects the change. The fusion center then declares that a change has occurred when m of the K sensors have raised an alarm. Assuming that all sensors have the same signal strength, we show that the asymptotic performance of these one-shot schemes is free of m to a first order, but decreases with m to a second-order, suggesting that the best strategy for the fusion center is to detect the change with the first alarm. Second, we consider schemes that detect the change when m of the K sensors agree simultaneously that the change has occurred. While a first-order asymptotic analysis suggests that it is optimal for the fusion center to wait for all sensors to agree simultaneously, a second-order analysis reveals that it can be better to wait fewer (but more than half) of the sensors to agree. The insights from these asymptotic results are supported by a simulation study.

A generalized multisensor sequential change detection problem is considered, in which a number of (possibly correlated) sensors monitor an environment in real time, the joint distribution of their observations is determined by a global parameter vector, and at some unknown time there is a change in an unknown subset of components of this parameter vector. The goal is to detect the change as soon as possible, while controlling the rate of false alarms. We establish the second-order asymptotic optimality (with respect to Lorden's criterion) of various generalizations of the CUSUM rule; that is, we show that their additional expected worst case detection delay (relative to the one that could be achieved if the affected subset was known) remains bounded as the rate of false alarm goes to 0, for any possible subset of affected components. This general framework incorporates the traditional multisensor setup in which only an unknown subset of sensors is affected by the change. The latter problem has a special structure which we exploit in order to obtain feasible representations of the proposed schemes. We present the results of a simulation study where we compare the proposed schemes with scalable detection rules that are only first-order asymptotically optimal. Finally, in the special case that the change affects exactly one sensor, we consider the scheme that runs in parallel the local CUSUM rules and study the problem of specifying the local thresholds.

An asymptotically optimum test for the problem of decentralized sequential hypothesis testing is presented. The induced communication between sensors and fusion center is asynchronous and limited to 1-bit data. When the sensors observe continuously stochastic processes with continuous paths, the proposed test is order-2 asymptotically optimal, in the sense that its inflicted performance loss is bounded. When the sensors take discrete time observations, the proposed test achieves order-1 asymptotic optimality, i.e., the ratio of its performance over the optimal performance tends to 1. Moreover, we show theoretically and corroborate with simulations that the performance of the suggested test in discrete time can be significantly improved when the sensors sample their underlying continuous time processes more frequently, a property which is not enjoyed by other centralized or decentralized tests in the literature.