We develop a novel, general and computationally efficient framework, called Divide and Conquer Dynamic Programming (DCDP), for localizing change points in time series data with high-dimensional features. DCDP deploys a class of greedy algorithms that are applicable to a broad variety of high-dimensional statistical models and can enjoy almost linear computational complexity. We investigate the performance of DCDP in three commonly studied change point settings in high dimensions: the mean model, the Gaussian graphical model, and the linear regression model. In all three cases, we derive non-asymptotic bounds for the accuracy of the DCDP change point estimators. We demonstrate that the DCDP procedures consistently estimate the change points with sharp, and in some cases, optimal rates while incurring significantly smaller computational costs than the best available algorithms. Our findings are supported by extensive numerical experiments on both synthetic and real data.

Time series data are ubiquitous in complex network systems, where each component of the system is treated as a vertex and has sequentially collected autocorrelated observations for condition monitoring. In many cases, components transit between different states, such as “normal,” “degrading,” “failure,” etc., and under different states their distributions vary, resulting in the mixture marginal distribution of each vertex's time series data. Moreover, states of different components influence each other through the system's network topology, i.e., the state of a component itself and its neighbors jointly affect its data distribution. For efficient condition monitoring, it is important to capture the state evolution of all vertices as a whole over time. However, the state-switching may be unobservable, which complicates the modeling. Hence, this article proposes a hidden Markov model for networked time series data with mixture marginal distributions. The Markov transition rule for latent states captures the state-switching behavior and the AR model reveals the temporal dependence of vertices. The states of different vertices further influence each other through the network topology structure. The Baum–Welch algorithm is used to estimate the parameters of the proposed model, allowing for state inference and data fitting. Extensive numerical studies as well as real case studies demonstrate the effectiveness and applicability of the proposed model.

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.

We propose a time-varying generalization of the Bradley-Terry model that allows for nonparametric modeling of dynamic global rankings of distinct teams. We develop a novel estimator that relies on kernel smoothing to pre-process the pairwise comparisons over time and is applicable in sparse settings where the Bradley-Terry may not be fit. We obtain necessary and sufficient conditions for the existence and uniqueness of our estimator. We also derive time-varying oracle bounds for both the estimation error and the excess risk in the model-agnostic setting where the Bradley-Terry model is not necessarily the true data generating process. We thoroughly test the practical effectiveness of our model using both simulated and real world data and suggest an efficient data-driven approach for bandwidth tuning.