Statistically and Computationally Efficient Change Point Localization in Regression Settings
Statistically and Computationally Efficient Change Point Localization in Regression Settings
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Daren Wang;Kevin Lin;R. Willett
中科院分区：
文献类型：
--
作者：
Daren Wang;Kevin Lin;R. Willett
从观测到的时间序列中检测基础分布何时发生变化是在广泛的应用中出现的一个基本问题。当我们只观察高维随机变量的低维投影时，变点定位尤其具有挑战性。具体地说，我们假设我们观察到$x_t，y_t=1}^n$，其中$x_t=1}^n$是$p$维协变量，$y_t=1}^n$是满足$E(Y_T)=x_t^\top\beta_t^*\text{for all}1的单变量响应，且${\beta_t^*}_{t=1}^n$是未观察到的回归参数。首先提出了一种新的基于估计累积和统计量的二进制分割算法(BSE)，该算法通过直接估计$\beta_t^*_t=1}^n$的CUSUM统计量来计算变化点。我们证明了BSE可以一致地估计变化点的未知位置，获得了$O(\log(P)/n)$阶的误差界。就我们所知，这是一个显著的改进，因为最先进的方法仅显示在多个变化点设置中达到$O(\log(P)/\SQRTn)$量级的误差界。然而，疯牛病的计算代价可能很高。为了克服这一局限性，我们引入了另一种算法，称为基于套索估计器的二进制分割(BSLE)。结果表明，与BSE相比，BSLE能够以略差的定位错误率一致地定位变点，但计算效率要高得多。最后，我们利用从BSE获得的洞察力来开发一种新的“局部筛选”算法，该算法可以输入对变化点位置的粗略估计以及观测数据，并有效地改进该估计，从而使我们能够改进过去估计器的实际性能。我们还在模拟实验中验证了我们的理论发现。
Detecting when the underlying distribution changes from the observed time series is a fundamental problem arising in a broad spectrum of applications. Change point localization is particularly challenging when we only observe low-dimensional projections of high-dimensional random variables. 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 $E(y_t)=x_t^\top \beta_t^*\text{ for all }1\let\le n$ and that $\{\beta_t^*\}_{t=1}^n $ are the unobserved regression parameters that change over time in a piecewise constant manner. We first propose a novel algorithm called Binary Segmentation through Estimated CUSUM statistics (BSE), which computes the change points through direct estimates of the CUSUM statistics of $\{\beta_t^*\}_{t=1}^n $. We show that BSE can consistently estimate the unknown location of the change points, achieving error bounds of order $O (\log(p)/n) $. To the best of our knowledge, this is a significant improvement, as the state-of-the-art methods are only shown to achieve error bounds of order $O(\log(p)/\sqrt n)$ in the multiple change point setting. However, BSE can be computationally costly. To overcome this limitation, we introduce another algorithm called Binary Segmentation through Lasso Estimators (BSLE). We show that BSLE can consistently localize change points with a slightly worse localization error rate compared to BSE, but BSLE is much more computationally efficient. Finally, we leverage the insights gained from BSE to develop a novel "local screening" algorithm that can input a coarse estimate of change point locations together with the observed data and efficiently refine that estimate, allowing us to improve the practical performance of past estimators. We also justify our theoretical finding in simulated experiments.