Search

High-dimensional self-exciting point processes have been widely used in many application areas to model discrete event data in which past and current events affect the likelihood of future events. In this paper, we are concerned with detecting abrupt changes of the coefficient matrices in discrete-time high-dimensional self-exciting Poisson processes, which have yet to be studied in the existing literature due to both theoretical and computational challenges rooted in the non-stationary and high-dimensional nature of the underlying process. We propose a penalized dynamic programming approach which is supported by a theoretical rate analysis and numerical evidence.

This paper studies multivariate nonparametric change point localization and inference problems. The data consists of a multivariate time series with potentially short range dependence. The distribution of this data is assumed to be piecewise constant with densities in a H\"{o}lder class. The change points, or times at which the distribution changes, are unknown. We derive the limiting distributions of the change point estimators when the minimal jump size vanishes or remains constant, a first in the literature on change point settings. We are introducing two new features: a consistent estimator that can detect when a change is happening in data with short-term dependence, and a consistent block-type long-run variance estimator. Numerical evidence is provided to back up our theoretical results.

This paper studies change-point testing for high-dimensional linear models, an important problem that is not well explored in the literature. Specifically, we propose a quadratic-form-based cumulative sum~(CUSUM) test to inspect the stability of the regression coefficients in a high-dimensional linear model. The proposed test is able to control the type-I error at any desired level and is theoretically sound for temporally dependent observations. We establish the asymptotic distribution of the proposed test under both the null and alternative hypotheses. Furthermore, we show that our test is asymptotically powerful against multiple-change-point alternative hypotheses and achieves the optimal detection boundary for a wide class of high-dimensional linear models. Extensive numerical experiments and a real data application in macroeconomics are conducted to demonstrate the promising performance and practical utility of the proposed test. In addition, some new consistency results of the Lasso~\citep{Tibshirani1996} are established under the change-point setting with the presence of temporal dependence, which may be of independent interest.

The Bradley-Terry-Luce (BTL) model is a classic and very popular statistical approach for eliciting a global ranking among a collection of items using pairwise comparison data. In applications in which the comparison outcomes are observed as a time series, it is often the case that data are non-stationary, in the sense that the true underlying ranking changes over time. In this paper we are concerned with localizing the change points in a high-dimensional BTL model with piece-wise constant parameters. We propose novel and practicable algorithms based on dynamic programming that can consistently estimate the unknown locations of the change points. We provide consistency rates for our methodology that depend explicitly on the model parameters, the temporal spacing between two consecutive change points and the magnitude of the change. We corroborate our findings with extensive numerical experiments and a real-life example., Comment: 37 pages, 4 figures, 7 tables

We study the problem of online network change point detection. In this setting, a collection of independent Bernoulli networks is collected sequentially, and the underlying distributions change when a change point occurs. The goal is to detect the change point as quickly as possible, if it exists, subject to a constraint on the number or probability of false alarms. In this paper, on the detection delay, we establish a minimax lower bound and two upper bounds based on NP-hard algorithms and polynomial-time algorithms, i.e., \[ \mbox{detection delay} \begin{cases} \gtrsim \log(1/\alpha) \frac{\max\{r^2/n, \, 1\}}{\kappa_0^2 n \rho},\\ \lesssim \log(\Delta/\alpha) \frac{\max\{r^2/n, \, \log(r)\}}{\kappa_0^2 n \rho}, & \mbox{with NP-hard algorithms},\\ \lesssim \log(\Delta/\alpha) \frac{r}{\kappa_0^2 n \rho}, & \mbox{with polynomial-time algorithms}, \end{cases} \] where $\kappa_0, n, \rho, r$ and $\alpha$ are the normalised jump size, network size, entrywise sparsity, rank sparsity and the overall Type-I error upper bound. All the model parameters are allowed to vary as $\Delta$, the location of the change point, diverges. The polynomial-time algorithms are novel procedures that we propose in this paper, designed for quick detection under two different forms of Type-I error control. The first is based on controlling the overall probability of a false alarm when there are no change points, and the second is based on specifying a lower bound on the expected time of the first false alarm. Extensive experiments show that, under different scenarios and the aforementioned forms of Type-I error control, our proposed approaches outperform state-of-the-art methods.

We study a functional linear regression model that deals with functional responses and allows for both functional covariates and high-dimensional vector covariates. The proposed model is flexible and nests several functional regression models in the literature as special cases. Based on the theory of reproducing kernel Hilbert spaces (RKHS), we propose a penalized least squares estimator that can accommodate functional variables observed on discrete sample points. Besides a conventional smoothness penalty, a group Lasso-type penalty is further imposed to induce sparsity in the high-dimensional vector predictors. We derive finite sample theoretical guarantees and show that the excess prediction risk of our estimator is minimax optimal. Furthermore, our analysis reveals an interesting phase transition phenomenon that the optimal excess risk is determined jointly by the smoothness and the sparsity of the functional regression coefficients. A novel efficient optimization algorithm based on iterative coordinate descent is devised to handle the smoothness and group penalties simultaneously. Simulation studies and real data applications illustrate the promising performance of the proposed approach compared to the state-of-the-art methods in the literature.

We investigate sequential change point estimation and detection in univariate nonparametric settings, where a stream of independent observations from sub-Gaussian distributions with a common variance factor and piecewise-constant but otherwise unknown means are collected. We develop a simple CUSUM-based methodology that provably control the probability of false alarms or the average run length while minimizing, in a minimax sense, the detection delay. We allow for all the model parameters to vary in order to capture a broad range of levels of statistical hardness for the problem at hand. We further show how our methodology is applicable to the case in which multiple change points are to be estimated sequentially.

Detecting when the underlying distribution changes for the observed time series is a fundamental problem arising in a broad spectrum of applications. In this paper, we study multiple change-point localization in the high-dimensional regression setting, which is particularly challenging as no direct observations of the parameter of interest is available. Specifically, we assume we observe $\{ x_t, y_t\}_{t=1}^n$ where $ \{ x_t\}_{t=1}^n $ are $p$-dimensional covariates, $\{y_t\}_{t=1}^n$ are the univariate responses satisfying $\mathbb{E}(y_t) = x_t^\top \beta_t^* \text{ for } 1\le t \le n $ and $\{\beta_t^*\}_{t=1}^n $ are the unobserved regression coefficients that change over time in a piecewise constant manner. We propose a novel projection-based algorithm, Variance Projected Wild Binary Segmentation~(VPWBS), which transforms the original (difficult) problem of change-point detection in $p$-dimensional regression to a simpler problem of change-point detection in mean of a one-dimensional time series. VPWBS is shown to achieve sharp localization rate $O_p(1/n)$ up to a log factor, a significant improvement from the best rate $O_p(1/\sqrt{n})$ known in the existing literature for multiple change-point localization in high-dimensional regression. Extensive numerical experiments are conducted to demonstrate the robust and favorable performance of VPWBS over two state-of-the-art algorithms, especially when the size of change in the regression coefficients $\{\beta_t^*\}_{t=1}^n $ is small., Comment: 44 pages

We study change point detection and localization for univariate data in fully nonparametric settings in which, at each time point, we acquire an i.i.d. sample from an unknown distribution. We quantify the magnitude of the distributional changes at the change points using the Kolmogorov--Smirnov distance. We allow all the relevant parameters -- the minimal spacing between two consecutive change points, the minimal magnitude of the changes in the Kolmogorov--Smirnov distance, and the number of sample points collected at each time point -- to change with the length of time series. We generalize the renowned binary segmentation (e.g. Scott and Knott, 1974) algorithm and its variant, the wild binary segmentation of Fryzlewicz (2014), both originally designed for univariate mean change point detection problems, to our nonparametric settings and exhibit rates of consistency for both of them. In particular, we prove that the procedure based on wild binary segmentation is nearly minimax rate-optimal. We further demonstrate a phase transition in the space of model parameters that separates parameter combinations for which consistent localization is possible from the ones for which this task is statistical unfeasible. Finally, we provide extensive numerical experiments to support our theory. R code is available at https://github.com/hernanmp/NWBS.

Autoregressive models capture stochastic processes in which past realizations determine the generative distribution of new data; they arise naturally in a variety of industrial, biomedical, and financial settings. A key challenge when working with such data is to determine when the underlying generative model has changed, as this can offer insights into distinct operating regimes of the underlying system. This paper describes a novel dynamic programming approach to localizing changes in high-dimensional autoregressive processes and associated error rates that improve upon the prior state of the art. When the model parameters are piecewise constant over time and the corresponding process is piecewise stable, the proposed dynamic programming algorithm consistently localizes change points even as the dimensionality, the sparsity of the coefficient matrices, the temporal spacing between two consecutive change points, and the magnitude of the difference of two consecutive coefficient matrices are allowed to vary with the sample size. Furthermore, the accuracy of initial, coarse change point localization estimates can be boosted via a computationally-efficient refinement algorithm that provably improves the localization error rate. Finally, a comprehensive simulation experiments and a real data analysis are provided to show the numerical superiority of our proposed methods., Comment: 53 pages; 4 figure

We study the problem of change point detection for covariance matrices in high dimensions. We assume that we observe a sequence {X_i}_{i=1,...,n} of independent and centered p-dimensional sub-Gaussian random vectors whose covariance matrices are piecewise constant. Our task is to recover with high accuracy the number and locations of the change points, which are assumed unknown. Our generic model setting allows for all the model parameters to change with n, including the dimension p, the minimal spacing between consecutive change points, the magnitude of smallest change size and the maximal Orlicz- 2 norm of the covariance matrices of the sample points. Without assuming any additional structural assumption, such as low rank matrices or having sparse principle components, we set up a general framework and a benchmark result for the covariance change point detection problem. We introduce two procedures, one based on the binary segmentation algorithm (e.g. Vostrikova, 1981) and the other on its extension known as wild binary segmentation of Fryzlewicz (2014), and demonstrate that, under suitable conditions, both procedures are able to consistently es- timate the number and locations of change points. Our second algorithm, called Wild Binary Segmentation through Independent Projection (WBSIP), is shown to be optimal in the sense of allowing for the minimax scaling in all the relevant parameters. Our minimax analysis reveals a phase transition effect based on the problem of change point localization. To the best of our knowledge, this type of results has not been established elsewhere in the high-dimensional change point detection literature., 44 pages

We study the problem of optimal estimation of the density cluster tree under various assumptions on the underlying density. Building up from the seminal work of Chaudhuri et al. [2014], we formulate a new notion of clustering consistency which is better suited to smooth densities, and derive minimax rates of consistency for cluster tree estimation for Holder smooth densities of arbitrary degree \alpha. We present a computationally efficient, rate optimal cluster tree estimator based on a straightforward extension of the popular density-based clustering algorithm DBSCAN by Ester et al. [1996]. The procedure relies on a kernel density estimator with an appropriate choice of the kernel and bandwidth to produce a sequence of nested random geometric graphs whose connected components form a hierarchy of clusters. The resulting optimal rates for cluster tree estimation depend on the degree of smoothness of the underlying density and, interestingly, match minimax rates for density estimation under the supremum norm. Our results complement and extend the analysis of the DBSCAN algorithm in Sriperumbudur and Steinwart [2012]. Finally, we consider level set estimation and cluster consistency for densities with jump discontinuities, where the sizes of the jumps and the distance among clusters are allowed to vanish as the sample size increases. We demonstrate that our DBSCAN-based algorithm remains minimax rate optimal in this setting as well., Comment: 55 pages, 5 figures