In this paper, we derive a precise false alarm rate of the SUM-CUSUM scheme when monitoring high-dimensional data streams or large-scale local data streams in the modern asymptotic regime, where the dimensionality of data tends to infinity. Both high-level easy-to-understand arguments and rigorous proofs based on the localization Theorem from Yakir (2013) are provided. The result enables us to improve a hypothesized detection threshold of the SUM-CUSUM scheme made in Mei (Biometrika, 2010) to achieve the desired false alarm rate.

Spatio-temporal point processes (STPPs) are potent mathematical tools for modeling and predicting events with both temporal and spatial features. Despite their versatility, most existing methods for learning STPPs either assume a restricted form of the spatio-temporal distribution, or suffer from inaccurate approximations of the intractable integral in the likelihood training objective. These issues typically arise from the normalization term of the probability density function. Moreover, existing works only provide point prediction for events without quantifying their uncertainty, such as confidence intervals for the event’s arrival time and confidence regions for the event’s location, which is crucial given the considerable randomness of the data. To tackle these challenges, we introduce SMASH: a Score MAtching-based pSeudolikeliHood estimator for learning marked STPPs. Specifically, our framework adopts a normalization-free objective by estimating the pseudolikelihood of marked STPPs through score-matching and predicts confidence intervals/regions for event time and location by generating samples through a score-based sampling algorithm. The superior performance of our proposed framework is demonstrated through extensive experiments on both point and confidence interval/region prediction of events.

In this paper, we consider the quickest detection problem in high-dimensional streaming data, where the unknown regression coefficients might change at some unknown time. We propose a quickest detection algorithm based on the implicit regularization algorithm via gradient descent, and provide theoretical guarantees on the average run length to false alarm and detection delay. Numerical studies are conducted to validate the theoretical results.

Monitoring high-dimensional streaming data has a wide range of applications in science, engineering, and industry. In this work, we propose an efficient and robust sequential change-point detection algorithm for monitoring high-dimensional streaming data. It has two components. At the local level, we adopt a window-limited nonparametric Shiryaev-Roberts (WL-NPSR) statistic for detecting potential distribution changes at each dimension of the streaming data. At the global level, we fuse local WL-NPSR statistics together to construct a global monitoring statistic via quantile filtering and sum-shrinkage functions. Theoretical analysis and extensive numerical experiments demonstrate the efficiency and robustness of our proposed algorithm.

The problem of robust Sparse Linear Discriminant Analysis (LDA) in high-dimensions is studied, in which a fraction of the training data may be corrupted by an adversary. A computationally efficient algorithm is proposed by adapting robust mean estimation along with a calibration framework for LDA. Theoretical properties of the proposed algorithm are established for both the estimation error of the optimal projection vector and the mis-classification rate. Results from extensive numerical studies on both synthetic and real datasets are reported to show the usefulness of our algorithm.

We consider the linear discriminant analysis problem in the high-dimensional settings. In this work, we propose PANDA(PivotAl liNear Discriminant Analysis), a tuning insensitive method in the sense that it requires very little effort to tune the parameters. Moreover, we prove that PANDA achieves the optimal convergence rate in terms of both the estimation error and misclassification rate. Our theoretical results are backed up by thorough numerical studies using both simulated and real datasets. In comparison with the existing methods, we observe that our proposed PANDA yields equal or better performance, and requires substantially less effort in parameter tuning.

The sequential hypothesis testing problem is a class of statistical analyses where the sample size is not fixed in advance. Instead, the decision-process takes in new observations sequentially to make real-time decisions for testing an alternative hypothesis against a null hypothesis until some stopping criterion is satisfied. In many common applications of sequential hypothesis testing, the data can be highly sensitive and may require privacy protection; for example, sequential hypothesis testing is used in clinical trials, where doctors sequentially collect data from patients and must determine when to stop recruiting patients and whether the treatment is effective. The field of differential privacy has been developed to offer data analysis tools with strong privacy guarantees, and has been commonly applied to machine learning and statistical tasks. In this work, we study the sequential hypothesis testing problem under a slight variant of differential privacy, known as Renyi differential privacy. We present a new private algorithm based on Wald’s Sequential Probability Ratio Test (SPRT) that also gives strong theoretical privacy guarantees. We provide theoretical analysis on statistical performance measured by Type I and Type II error as well as the expected sample size. We also empirically validate our theoretical results on several synthetic databases, showing that our algorithms also perform well in practice. Unlike previous work in private hypothesis testing that focused only on the classical fixed sample setting, our results in the sequential setting allow a conclusion to be reached much earlier, and thus saving the cost of collecting additional samples.

We study the Stochastic Gradient Descent (SGD) algorithm in nonparametric statistics: kernel regression in particular. The directional bias property of SGD, which is known in the linear regression setting, is generalized to the kernel regression. More specifically, we prove that SGD with moderate and annealing step-size converges along the direction of the eigenvector that corresponds to the largest eigenvalue of the Gram matrix. In addition, the Gradient Descent (GD) with a moderate or small step-size converges along the direction that corresponds to the smallest eigenvalue. These facts are referred to as the directional bias properties; they may interpret how an SGD-computed estimator has a potentially smaller generalization error than a GD-computed estimator. The application of our theory is demonstrated by simulation studies and a case study that is based on the FashionMNIST dataset.

In machine learning and statistical data analysis, we often run into objective function that is a summation: the number of terms in the summation possibly is equal to the sample size, which can be enormous. In such a setting, the stochastic mirror descent (SMD) algorithm is a numerically efficient method—each iteration involving a very small subset of the data. The variance reduction version of SMD (VRSMD) can further improve SMD by inducing faster convergence. On the other hand, algorithms such as gradient descent and stochastic gradient descent have the implicit regularization property that leads to better performance in terms of the generalization errors. Little is known on whether such a property holds for VRSMD. We prove here that the discrete VRSMD estimator sequence converges to the minimum mirror interpolant in the linear regression. This establishes the implicit regularization property for VRSMD. As an application of the above result, we derive a model estimation accuracy result in the setting when the true model is sparse. We use numerical examples to illustrate the empirical power of VRSMD.

We study the multi-stream quickest detection problem under the active learning setup, It is assumed that there are p local streams in a system and s ≤ p unknown local streams are affected by an undesired event at some unknown time, but one is only able to take observations from r of these p local streams at each time instant. The objective is how to adaptively sample from these p local streams and how to use the observed data to raise a correct global alarm as quickly as possible. In this paper, we develop the first asymptotic optimality theory in the active quickest detection literature for the case when s = r = 2. To be more concrete, we propose to combine three ideas to develop efficient active quickest detection algorithms: (1) win-stay, lose-switch sampling strategy; (2) local CUSUM statistics for local monitoring; and (3) the SUM-Shrinkage technique to fuse local statistics into a global decision. We show that our proposed algorithms are asymptotically optimal in the sense of minimizing detection delay up to the second order subject to the false alarm constraint. Numerical studies are conducted to validate our theoretical results.

Fourier-transform infrared spectroscopy (FTIR) is a widely adopted technique for characterizing the chemical composition in many physical and chemical analyses. However, FTIR spectra are subject to multiple sources of uncertainty, and thus the analysis of them relies on domain experts and can only lead to qualitative conclusions. This study aims to analyze the effect of a certain treatment on FTIR spectra subject to two commonly observed uncertainties, the offset shift and the multiplicative error. Due to these uncertainties, the pre-exposure FTIR spectra are modeled according to the physical understanding of the uncertainty—observed spectra can be viewed as translating and stretchering an underlying template signal, and the post-exposure FTIR spectra are modeled as the translated and stretchered template signal plus an extra functional treatment effect. To provide engineering interpretation, the treatment effect is modeled as the product of the pattern of modification and its corresponding magnitude. A two-step parameter estimation algorithm is developed to estimate the underlying template signal, the pattern of modification, and the magnitude of modification at various treatment strengths. The effectiveness of the proposed method is validated in a simulation study. Furtherly, in a real case study, the proposed method is used to investigate the effect of plasma exposure on the FTIR spectra. As a result, the proposed method effectively identifies the pattern of modification under uncertainties in the manufacturing environment, which matches the knowledge of the affected chemical components by the plasma treatment. And the recovered magnitude of modification provides guidance in selecting the control parameter of the plasma treatment.Note to Practitioners—FTIR spectrometer is often used to characterize the surface chemical composition of a material. Due to the large uncertainties associated with the nature of spectrometer and the measurement environment, the FTIR signals are usually examined visually by experienced engineers and technicians in industrial applications, which can be both time-consuming and inaccurate. To understand the effect of plasma exposure on the surface property of carbon fiber reinforced polymer (CFRP) material, the elimination of uncertainties associated with FTIR signals is investigated, and a systematic method is proposed to quantify the effect of surface treatments on FTIR signals. A two-step analytic procedure is proposed, which provides information on how the plasma exposure distorts the FTIR signals, and how the plasma distance relates to the magnitude of the distortion. The methodology in this article can be used to analyze the treatment effect on a variety of spectroscopic measurements that are subject to uncertainties such as offset and scaling errors, which expands the applications of in situ handheld spectrometer metrology in manufacturing industries.

The multi-stream quickest detection problem with unknown post-change parameters is studied under the sampling control constraint, where there are$M$local processes in a system but one is only able to take observations from one of these$M$local processes at each time instant. The objective is to raise a correct alarm as quickly as possible once the change occurs subject to both false alarm and sampling control constraints. We propose an efficient myopic-sampling-based quickest detection algorithm under sampling control constraint, and show it is asymptotically optimal in the sense of minimizing the detection delay under our context when the number$M$of processes is fixed. Simulation studies are conducted to validate our theoretical results.

The change-point detection problem seeks to identify distributional changes at an unknown change-point $k^*$ in a stream of data. This problem appears in many important practical settings involving personal data, including biosurveillance, fault detection, finance, signal detection, and security systems. The field of differential privacy offers data analysis tools that provide powerful worst-case privacy guarantees. We study the statistical problem of change-point detection through the lens of differential privacy. We give private algorithms for both online and offline change-point detection, analyze these algorithms theoretically, and provide empirical validation of our results.

In multi-stream sequential change-point detection it is assumed that there are$M$processes in a system and at some unknown time, an occurring event changes the distribution of the samples of a particular process. In this article, we consider this problem under a sampling control constraint when one is allowed, at each point in time, to sample a single process. The objective is to raise an alarm as quickly as possible subject to a proper false alarm constraint. We show that under sampling control, a simple myopic-sampling-based sequential change-point detection strategy is second-order asymptotically optimal when the number$M$of processes is fixed. This means that the proposed detector, even by sampling with a rate$1/M$of the full rate, enjoys the same detection delay, up to some additive finite constant, as the optimal procedure. Simulation experiments corroborate our theoretical results.

In the sequential change-point detection problem for multi-stream data, it is assumed that there are M processes in a system and at some unknown time, an occurring event impacts one unknown local process in the sense of changing the distribution of observations from that affected local process. In this paper, we consider such problem under the sampling control constraint, in which one is able to take observations from only one of the local processes at each time step. Our objective is to design an adaptive sampling policy and a stopping time policy that is able to raise a correct alarm as quickly as possible subject to the false alarm and sampling control constraint. We develop an efficient sequential change-point detection algorithm under the sampling control that turns out to be second-order asymptotically optimal under the full data scenario. That is, with the sampling rate that is only 1/M of the full data scenario, our proposed algorithm has the same performance up to second-order as the optimal procedure under the full data scenario.

We propose an optimal sequential methodology for obtaining confidence intervals for a binomial proportion θ. Assuming that an independent and identically distributed sequence of Bernoulli (θ) trials is observed sequentially, we are interested in designing: 1) a stopping time T that will decide the best time to stop sampling the process and 2) an optimum estimator θ̂T that will provide the optimum center of the interval estimate of θ. We follow a semi-Bayesian approach, where we assume that there exists a prior distribution for θ, and our goal is to minimize the average number of samples while we guarantee a minimal specified coverage probability level. The solution is obtained by applying standard optimal stopping theory and computing the optimum pair (T, θ̂T) numerically. Regarding the optimum stopping time component T, we demonstrate that it enjoys certain very interesting characteristics not commonly encountered in solutions of other classical optimal stopping problems. In particular, we prove that, for a particular prior (beta density), the optimum stopping time is always bounded from above and below; it needs to first accumulate a sufficient amount of information before deciding whether or not to stop, and it will always terminate before some finite deterministic time. We also conjecture that these properties are present with any prior. Finally, we compare our method with the optimum fixed-sample-size procedure as well as with existing alternative sequential schemes.

The change-point detection problem seeks to identify distributional changes at an unknown change-point k* in a stream of data. This problem appears in many important practical settings involving personal data, including biosurveillance, fault detection, finance, signal detection, and security systems. The field of differential privacy offers data analysis tools that provide powerful worst-case privacy guarantees. We study the statistical problem of change-point problem through the lens of differential privacy. We give private algorithms for both online and offline change-point detection, analyze these algorithms theoretically, and then provide empirical validation of these results.

We consider the problem of parameter estimation under a sequential framework. Specifically we assume that an i.i.d. random process is observed sequentially with its common pdf having a random parameter that must be estimated. We are interested in designing a stopping time that will decide when is the best moment to stop sampling the process and an estimator that will use the acquired samples in order to provide the desired estimate. We follow a semi-Bayesian approach where we assign cost to the pair (estimate, true parameter) and our goal is to minimize the average sample size guaranteeing at the same time an average cost below some prescribed level. For our analysis we adopt a conditional average cost which leads to a considerable simplification in the sequential estimation problem, otherwise known to be analytically intractable. We apply our results to a number of examples and compare our method with the optimum fixed sample size but also with existing sequential schemes.

The quickest change detection problem is studied in two-state hidden Markov models (HMM), where the vector parameter θ of the HMM may change from θ0to θ1at some unknown time, and one wants to detect the true change as quickly as possible while controlling the false alarm rate. It turns out that the generalized likelihood ratio (GLR) scheme, while theoretically straightforward, is generally computationally infeasible for the HMM. To develop efficient but computationally simple schemes for the HMM, we first show that the recursive CUSUM scheme proposed in Fuh (Ann. Statist., 2003) can be regarded as a quasi-GLR scheme for some suitable pseudo post-change hypotheses. Next, we extend the quasi-GLR idea to propose recursive score schemes in a more complicated scenario when the post-change parameter θ1of the HMM involves a real-valued nuisance parameter. Finally, our research provides an alternative approach that can numerically compute the Kullback-Leibler (KL) divergence of two-state HMMs via the invariant probability measure and the Fredholm integral equation.

The quickest change detection problem is considered in the context of monitoring large-scale independent normal distributed data streams with possible changes in some of the means. It is assumed that for each individual local data stream, either there are no local changes, or there is a big local change that is larger than a pre-specified lower bound. Two different types of scenarios are studied: one is the sparse post-change case when the unknown number of affected data streams is much smaller than the total number of data streams, and the other is when all local data streams are affected simultaneously although not necessarily identically. We propose a systematic approach to develop efficient global monitoring schemes for quickest change detection by combining hard thresholding with linear shrinkage estimators to estimating all post-change parameters simultaneously. Our theoretical analysis demonstrates that the shrinkage estimation can balance the tradeoff between the first-order and second-order terms of the asymptotic expression on the detection delays, and our numerical simulation studies illustrate the usefulness of shrinkage estimation and the challenge of Monte Carlo simulation of the average run length to false alarm in the context of online monitoring large-scale data streams.

The online parallel monitoring problem is studied when one is monitoring large-scale data streams, and an event occurs at an unknown time and affects an unknown subset of data streams. Efficient online parallel monitoring schemes are developed by combining the standard sequential change-point method with hard-thresholding post-change estimation. Theoretical analysis and simulation study demonstrate the usefulness of hard-thresholding for online parallel monitoring.

It is well known that quantization cannot increase the Kullback-Leibler divergence which can be thought of as the expected value or first moment of the log-likelihood ratio. In this paper, we investigate the quantization effects on the second moment of the log-likelihood ratio. It is shown that quantization may result in an increase in the case of the second moment, but the increase is bounded above by 2/e. The result is then applied to decentralized sequential detection problems to provide a simpler sufficient condition for asymptotic optimality theory, and the technique is also extended to investigate the quantization effects on other higher-order moments of the log-likelihood ratio and provide lower bounds on higher-order moments.

The quickest change detection problem is studied in a general context of monitoring a large number of data streams in sensor networks when the “trigger event” may affect different sensors differently. In particular, the occurring event could have an immediate or delayed impact on some unknown, but not necessarily all, sensors. Motivated by censoring sensor networks, scalable detection schemes are developed based on the sum of those local CUSUM statistics that are “large” under either hard thresholding or top-r thresholding rules or both. The proposed schemes are shown to possess certain asymptotic optimality properties.

The Bayesian formulation of sequentially testingM≥ 3 hypotheses is studied in the context of a decentralized sensor network system. In such a system, local sensors observe raw observations and send quantized sensor messages to a fusion center which makes a final decision when stopping taking observations. Asymptotically optimal decentralized sequential tests are developed from a class of “two-stage” tests that allows the sensor network system to make a preliminary decision in the first stage and then optimize each local sensor quantizer accordingly in the second stage. It is shown that the optimal local quantizer at each local sensor in the second stage can be defined as a maximin quantizer which turns out to be a randomization of at mostM-1 unambiguous likelihood quantizers (ULQ). We first present in detail our results for the system with a single sensor and binary sensor messages, and then extend to more general cases involving any finite alphabet sensor messages, multiple sensors, or composite hypotheses.

This article is concerned with decentralized sequential testing of multiple hypotheses. In a sensor network system with limited local memory, raw observations are observed at the local sensors, and quantized into binary sensor messages that are sent to a fusion center, which makes a final decision. It is assumed that the raw sensor observations are distributed according to a set of M ≥ 2 specified distributions, and the fusion center has to utilize quantized sensor messages to decide which one is the true distribution. Asymptotically Bayes tests are offered for decentralized multihypothesis sequential detection by combining three existing methodologies together: tandem quantizers, unambiguous likelihood quantizers, and randomized quantizers.

This article is concerned with decentralized sequential testing of a normal mean mu with two-sided alternatives. It is assumed that in a single-sensor network system with limited local memory, i.i.d. normal raw observations are observed at the local sensor, and quantized into binary messages that are sent to the fusion center, which makes a final decision between the null hypothesis H0: mu = 0 and the alternative hypothesis H1: mu = plusmn1. We propose a decentralized sequential test using the idea of tandem quantizers (or equivalently, a one-shot feedback). Surprisingly, our proposed test only uses the quantizers of the form I(Xnges lambda), but it is shown to be asymptotically Bayes. Moreover, by adopting the principle of invariance, we also investigate decentralized invariant tests with the stationary quantizers of the form I(|Xn| > lambda), and show that lambda = 0.5 only leads to a suboptimal decentralized invariant sequential test. Numerical simulations are conducted to support our arguments.

The decentralized sequential hypothesis testing problem is studied in sensor networks, where a set of sensors receive independent observations and send summary messages to the fusion center, which makes a final decision. In the scenario where the sensors have full access to their past observations, the first asymptotically Bayes sequential test is developed having the same asymptotic performance as the optimal centralized test that has access to all sensor observations. Next, in the scenario where the sensors do not have full access to their past observations, a simple but asymptotically Bayes sequential tests is developed, in which sensor message functions are what we call tandem quantizer, where each sensor only uses two different sensor quantizers with at most one switch between these two possibilities. Moreover, a new minimax formulation of optimal stationary sensor quantizers is proposed and is studied in detail in the case of additive Gaussian sensor noise. Finally, our results show that in the simplest models, feedback from the fusion center does not improve asymptotic performance in the scenario with full local memory, however, even a one-shot, one-bit feedback can significantly improve performance in the case of limited local memory.

The main purpose of this paper is to develop an asymptotic theory for the decentralized sequential hypothesis testing problems under the frequentist framework. Sharp asymptotic bounds on the average sample numbers or sample sizes of sequential or fixed-sample tests are provided in the decentralized decision systems in different scenarios subject to error probabilities constraints. Asymptotically optimal tests are offered in the system with full local memory. Optimal binary quantizers are also studied in the case of additive Gaussian sensor noises

This paper develops sharp information-theoretic bounds and offers asymptotically optimal procedures for decentralized quickest change detection under different scenarios. A lower bound of the detection delay is developed in the system with limited local memory and it is proved that the decentralised CUSUM procedure with a monotone likelihood ratio quantiser (MLRQ) defined is asymptotically optimal.