Locally private online change point detection

Abstract

We study online change point detection problems under the constraint of local differential privacy (LDP) where, in particular, the statistician does not have access to the raw data. As a concrete problem, we study a multivariate nonparametric regression problem. At each time point $t$, the raw data are assumed to be of the form $(X_t,Y_t)$, where $X_t$ is a $d$-dimensional feature vector and $Y_t$ is a response variable. Our primary aim is to detect changes in the regression function $m_t(x)=\mathbb{E}(Y_t|X_t=x)$ as soon as the change occurs. We provide algorithms which respect the LDP constraint, which control the false alarm probability, and which detect changes with a minimal (minimax rate-optimal) delay. To quantify the cost of privacy, we also present the optimal rate in the benchmark, non-private setting. These non-private results are also new to the literature and thus are interesting \emph{per se}. In addition, we study the univariate mean online change point detection problem, under privacy constraints. This serves as the blueprint of studying more complicated private change point detection problems.

References in corpus (11)

• Extremal Mechanisms for Local Differential Privacy
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Towards Formalizing the GDPR's Notion of Singling Out
• Detection and localization of change-points in high-dimensional network traffic data
• Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
• Local Differential Privacy for Evolving Data
• Differentially Private Change-Point Detection
• A review on minimax rates in change point detection and localisation
• Classification under local differential privacy
• Optimal network online change point localisation
• Privately detecting changes in unknown distributions