Locally private online change point detection
Year: 2022

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 (Xt, Yt), where Xt is a d-dimensional feature vector and Yt is a response variable. Our primary aim is to detect changes in the regression function mt(x) = E(Yt|Xt = 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 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.

heading: 1 Introduction
text: Online change point detection has been an active statistical research area for decades, originated from the demand of a reliable quality control mechanism under time and resources constraints [e.g. 34]. In recent years, due to the advance of technology, the applications of online change point detection are well beyond quality control and include climatology, speech recognition, imaging processing, among many others. While collecting the data as they are generated, one wishes to detect the underlying distributional changes as soon as the changes occur.
As the ability of collecting and storing data improves exponentially, protecting users’ privacy has become one of the central concerns of data science. In practice, many of the systems that we monitor contain sensitive information. For instance, change point algorithms are used in cyber security to detect attacks, with the ultimate aim often being to protect private information [24, 30, 1]. Other common application areas include public health [21, 17] and finance [18], in which many of the data involved are highly personal. Given the prevalence of such problems, we address two questions in this paper:
• whether we can detect changes without the need for direct access to the sensitive raw data; • and what the cost of protecting privacy is in terms of the detection delay and accuracy. Traditional anonymisation of data has been shown to be an outdated method of privacy protection, particularly in multivariate settings [28, 26]. Even when direct identifiers such as names and locations are removed, data sets often contain enough information for researchers to identify individual subjects, and hence there is a need to quantify and control the release of privileged information. Formal privacy constraints provide us with a rigorous framework in which we may tackle such problems and explore the fundamental limits of private methods. Constraints of this type have been imposed in analyses
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
carried out by Apple [31, 29], Google [16] and Microsoft [10], and provides organisations with a way of demonstrating the General Data Protection Regulation compliance [7].
The most popular privacy constraint is that of differential privacy [14], which assumes the existence of a third party who can be trusted to handle all the raw data. In situations where this assumption cannot be made, which are the focus in our work, we strengthen this constraint and require our algorithms to satisfy local differential privacy [e.g. 20, 12], which, in particular, insists that the raw data are not accessed by anyone except its original holder. Solutions to a wide range of statistical problems have been given, and much underlying theory has been developed [e.g. 35, 12, 13, 27, 3, 15, 19].
In this paper, we are concerned with a multivariate nonparametric regression online change point detection problem, with privatised data. To be specific, we assume that the original data are {(Xi, Yi)}i∈N∗ ⊂ Rd × R, where the regression functions
mi(x) = E(Yi|Xi = x), x ∈ Rd, i ∈ N∗, (1)
satisfy that mi+1 6= mi if and only if i = ∆ ∈ N∗. The goal is to find a stopping time t̂, which minimises the detection delay (t̂−∆)+, while controlling the false alarm probability P(t̂ < ∆). With the concern of maintaining privacy, we do not directly have access to the original data {(Xi, Yi)}i∈N∗ , but a privatised version. Specifically, the original data are transmitted through an α-locally differentially private (α-LDP) channel for some fixed α > 0. The privatised data are denoted by {(Wi, Zi)}i∈N∗ ⊂ Rd × R. In our upper bounds we restrict attention to non-interactive mechanisms [see e.g. 12], and so a privacy mechanism is given by a sequence {Qi}i∈N∗ of conditional distributions, with the interpretation that (Wi, Zi)|(Xi, Yi) = (xi, yi) ∼ Qi(·|(xi, yi)). For {Qi}i∈N∗ to satisfy the α-LDP constraint we require that
sup i∈N∗ sup A sup (x,y),(x′,y′)∈Rd×R Qi(A|(x, y)) Qi(A|(x′, y′)) ≤ eα. (2)
In our lower bounds, however, we allow mechanisms to be sequentially interactive [e.g. 12], so that a privacy mechanism is given by {Qi}i∈N∗ , with the interpretation that
(Wi, Zi)|{(Xi, Yi,Wi−1, Zi−1, . . . ,W1, Z1) = (xi, yi, wi−1, zi−1, . . . , w1, z1) ∼ Qi(·|(xi, yi, wi−1, zi−1, . . . , w1, z1)).
Here the α-LDP constraint requires that
sup i∈N∗ sup A sup (x,y),(x′,y′)∈Rd×R sup w1,z1,...,wi−1,zi−1 Qi(A|(x, y, wi−1, zi−1, . . . , w1, z1)) Qi(A|(x′, y′, wi−1, zi−1, . . . , w1, z1)) ≤ eα.
Since our upper and lower bounds match, up to a logarithmic factor, we may conclude that simpler non-interactive procedures result in optimal performance for this problem.
We will assume throughout that α ≤ 1, though this can be relaxed to α ≤ C for any C > 0. This restricts attention to the strongest constraints, and is often the regime of primary interest [e.g. 12].

heading: 1.1 Summary of contributions and related literature
text: To the best of our knowledge, this is the first work on a few fronts.
Firstly, this is the first paper to consider change point detection under local privacy constraints. Previous work has focused on the central model of differential privacy, where there exists a third party trusted to have access to all of the data. [9] use established tools from the central model of differential privacy to detect changes in both the offline and online settings. The pre- and post-change distributions are assumed to be known, and a private version of the likelihood ratio statistic is analysed. Further development of these ideas, in particular the extension to detection of multiple changes in the online setting, is given in [39]. [6] give differentially private tests of simple hypotheses, shown to be optimal up to constants, which are then applied to the change point detection problem with known pre- and post-change distributions. In a setting in which the distributions are unknown, [8] develop private versions of the Mann–Whitney test to detect a change in location. The problem has also been studied under different notions of central privacy [23].
Secondly, this is the first paper to study the fundamental limits in multivariate nonparametric regression change point detection problems. We have derived the minimax rate of the detection delay,
allowing the jump size ‖m∆ − m∆+1‖∞, the variance of the additive noise σ2 and the privacy constraint α to vary with the location of the change point ∆. There has been a vast body of literature discussing the detection boundary and optimal estimation in the offline change point analysis [e.g. 33, 36]. Their counterparts in online change point analysis are relatively scarce and existing work includes univariate mean change [e.g. 37] and dynamic networks [e.g. 38]. On a separate note, multivariate nonparametric regression estimation, under privacy constraints, is studied in [4], and classification is studied in [2]
In addition, we have also provided the analysis and results based on the univariate mean online change point detection problem, with privatised data. This is, arguably, the simplest privatised, online change point detection problem. The analysis and results we shown in this paper enrich statisticians’ toolboxes and serve as a benchmark for more complex problems.

heading: 2 Methodology
text: In this section, we describe our private change point detection algorithm, which takes the privatised data as input. The whole algorithm consists of two key ingredients: (1) the privacy mechanism and (2) the change point detection method.
The privacy mechanism. Throughout this paper, a binned estimator is the core of the analysis. Recall that the raw data at time point i include a d-dimensional feature vector Xi, which we assume is supported within some bounded set X ⊂ Rd, and a univariate response variable Yi. We denote {Ah,j}j=1,...,Nh as a set of cubes of volume hd, such that {X ∩Ah,j}j=1,...,Nh is a partition of X , and write xh,j for the centre of Ah,j . The data point (Xi, Yi) is then randomised by taking
Wi,j = 1{Xi∈Ah,j} + 4α −1 i,j and Zi,j = [Yi]M−M1{Xi∈Ah,j} + 4Mα −1ζi,j ,
where { i,j , ζi,j} are independent and identically distributed standard Laplace random variables, and where [Y ]M−M = min(M,max(Y,−M)) with M > 0 a truncation parameter. It is shown in Proposition 1 in [4] [see also 2] that this non-interactive mechanism is an α-LDP channel. We emphasise that privacy is guaranteed without any assumptions on the distribution of (X,Y ).
The change point detection method. Given data {(Wi,j , Zi,j)}, as for online change point detection, we propose Algorithm 1, with the CUSUM estimator defined in Definition 1 and the nonparametric estimators involved defined in Definition 2.
Algorithm 1 Online change point detection via CUSUM statistics INPUT: {(Wu,j , Zu,j)}u,j=1,2,... ⊂ Rd × R, {bs,t, 1 ≤ s < t <∞, . . .} ⊂ R. t← 1, FLAG← 0; while FLAG = 0 do
t← t+ 1; FLAG = 1− ∏t−1 s=1 1 { D̂s,t ≤ bs,t } ;
end while OUTPUT: t.
Definition 1. Given a sequence {(Wt,j , Zt,j)} and a pair of integers 1 ≤ s < t, we define the CUSUM statistic
D̂s,t = Nh
max j=1
√ s(t− s)/t ∣∣m̂1:s(xh,j)− m̂(s+1):t(xh,j)∣∣ , where m̂·:·(·) is defined in Definition 2. Definition 2. Given a sequence {(Wt,j , Zt,j)} and a pair of integers 1 ≤ s < t, with h > 0 being our bandwidth parameter, we define the regression function estimator as
m̂s:t(x) = ν̂s:t(Ah,j)
µ̂s:t(Ah,j) 1{µ̂s:t(Ah,j)≥ log(t−s+2)t−s+1 }, if x ∈ Ah,j ,
where ν̂s:t(Ah,j) = (t− s+ 1)−1 ∑ s≤i≤t Zi,j and µ̂s:t(Ah,j) = (t− s+ 1)−1 ∑ s≤i≤t Wi,j .
Algorithm 1 is a standard online change point detection procedure. Whenever a new data point stamped at t is collected, one checks if a change point has occurred by checking if any of (D̂s,t)s=1,...,t−1 have exceeded pre-specified thresholds. Apparently, both the storage and computation costs of this procedure are high. As pointed out in [37], without knowing the pre- and/or post-change point distributions, there is no existing algorithm which can have a constant computational cost O(1) when a new data point is collected. Of course, one can also be smarter: instead of scanning through s ∈ {1, . . . , t− 1}, one can just scan through a dyadic grid as described in [38].
The CUSUM statistic D̂s,t, defined in Definition 1, is a normalised difference between two estimated functions, before and after time point s, evaluated at each cell in the partition. It is used to examine, given all the data up to t, if s is a possible change point. It can be viewed as a sample version of the quantity
t−1 max s=1
√ s(t− s)
t
∥∥∥∥∥s−1 s∑ i=1 mi − (t− s)−1 t∑ i=s+1 mi ∥∥∥∥∥ ∞ ,
where ‖ · ‖∞ is the sup-norm of a function. In [25], a similar CUSUM was proposed in studying the nonparametric density change point detection problem. In our setting, we are interested in change points in the regression functions. The construction of estimators is detailed in Definition 2. This estimator has previously studied in the one sample estimation scenario in [4], where it was shown to be a universally strongly consistent estimator of the true regression function.

heading: 3 Theory
text: In this section, we present our core results. All the assumptions are collected in Section 3.1. The theoretical guarantees of Algorithm 1 are presented in Section 3.2, which also includes a minimax lower bound result showing our proposed method is optimal, off by at most a logarithmic factor. To quantify the cost of maintaining α-LDP, we also provide a benchmark result of the same data generating mechanism but without privacy in Section 3.3.

heading: 3.1 Assumptions
text: Assumption 1 (Setup). Assume that {(Xi, Yi)}i∈N∗ is a sequence of independent random objects, taking values in X × R, such that {Xi}i∈N∗ are independent each with distribution µ on X . We assume that there exists an absolute constant cmin > 0 such that µ(Ah,j) ≥ cminhd for all Ah,j in the partition of X . Assume that the regression functions mi(·), given by (1), are well defined for µ-almost all x and i ∈ N∗, such that there exists an absolute constant CLip > 0 with
sup i∈N∗ |mi(x1)−mi(x2)| ≤ CLip‖x1 − x2‖, ∀x1, x2 ∈ X .
We also assume that there exists σ > 0 such that for all λ ∈ R we have
sup i∈N∗ sup x∈Rd
E ( eλ{Yi−mi(x)} ∣∣∣ Xi = x) ≤ eλ2σ22 and that supi∈N∗ supx∈Rd |mi(x)| ≤M0 for some M0 > 0.
Assumption 1 is the main model assumption. It is a general feature of the local differential privacy constraint that it is not possible to work with unbounded parameter spaces [see e.g. 11, Appendix G]. Thus, we assume that the feature vectors are supported in a bounded set X , and we moreover assume that the regression functions mi are bounded, though these bounds are allowed to vary with the pre-change sample size ∆. In addition, we also assume that the regression functions are Lipschitz with a constant CLip. The Lipschitz condition can be easily relaxed to other type of continuity conditions, e.g. Hölder continuity. We assume the additive noise is sub-Gaussian with parameter σ, which is allowed to vary with the pre-change sample size. Assumption 1 is required to ensure that our algorithm controls the false alarm probability correctly and to ensure its optimality. Assumption 2 (No change point). Assume that m1 = m2 = · · · . Assumption 3 (One change point). Assume that there exists a positive integer ∆ ≥ 1 such that
m1 = · · · = m∆ 6= m∆+1 = m∆+2 = · · · . In addition, let κ = ‖m∆ −m∆+1‖∞.
Assumption 4 (Signal-to-noise ratio). There exists a sufficiently large absolute constant CSNR > 0 such that κ2h2dα2∆/max{σ2, M20 } ≥ CSNR log { ∆/(cminh 2dγ) } ,
where γ ∈ (0, 1) is the desired bound on false alarm probability and h is the bin-width used in constructing the estimators.
Assumptions 2, 3 and 4 describe different scenarios and aspects of the change point assumptions. Assumption 2 is a formal assumption describing when there is no change point and Assumption 3 depicts the scenario when there is one change point. Recall that in Definition 1 we proposed the CUSUM statistic which is a sample version of a normalised sup-norm difference between two functions. This is to be consistent with κ, the characterisation of the jump, introduced in Assumption 3.
Assumption 4 is the signal-to-noise ratio condition, and is required when we study the optimality of our algorithm to detect changes. Recall that κ is the jump size, σ is the fluctuation size, M0 is the upper bound of the mean function mi, α is the privacy constraint and ∆ is the size of the pre-change point sample size. Assumption 4 requires that κ2h2dα2∆ min{M−20 , σ−2} is larger than a logarithmic factor. This in fact allows κ, σ, M0 and α to vary as ∆ diverges. It may appear to be unnatural to involve tuning parameters in the signal-to-noise ratio condition. We remark that the involvement of h in Assumption 4 is to provide more flexibility in the tuning parameter selection. We will elaborate this point in Section 3.2.

heading: 3.2 Optimal online change point detection with privatised data
text: Theorem 1 below is the main result, which shows that for any γ ∈ (0, 1), with properly chosen tuning parameters, with probability at least of 1 − γ, Algorithm 1 does not have false alarms and has a detection delay upper bounded by in (12).
Theorem 1. Consider the settings described in Assumption 1. Let γ ∈ (0, 1) and t̂ be the stopping time returned by Algorithm 1 with inputs {(Wtj , Ztj)}t,j=1,2,... and {bs,t}t=2,3,...;s=1,...,t, where
bs,t=  2 √ s(t−s) t { 2(M −M0)e− (M−M0) 2 2σ2 + CLip √ dh } + M cminhdα √ log ( 72t3 γcminhd ) , if s(t−s)t c 2 minh 2dα2 ≥ 64 log ( 72t3 γcminhd ) ;
∞, otherwise. (3)
Assume that the truncation parameter satisfies M ≥M1 = M0 + σ √ 2 log(2 + σ/h) + log log(2 + σ/h) (4)
and the bandwidth satisfies h ≤ Cκ, where C > 0 is an absolute constant. If Assumption 2 holds, then
P∞ { t̂ <∞ } < γ. (5)
Under Assumption 3, we have P∆ { t̂ ≤ ∆ } < γ, (6)
for any ∆ ≥ 1. If Assumptions 3 and 4 both hold, then
P∆ { ∆ < t̂ ≤ ∆ + } ≥ 1− γ, where = Cε M2
κ2h2dα2 log
( ∆
h2dcminγ
) (7)
and Cε > 0 depends only on d.
To better understand Theorem 1, we first inspect the sources of the error in the procedure. The estimators of the regression functions mi are defined in Definition 2, which is a binned estimator averaging over cubes of volume hd. This is a typical nonparametric estimator, which brings in both bias and variance. On top of this, due to the constraints of privacy, we truncate the responses by M in
the privacy channel. The truncation level M should be an upper bound on M1 – a large-probability upper bound on the response, consisting of the upper bound on the regression function and the additive noise – so that the truncation bias is no larger than the bias due to smoothing. On the other hand, larger values of M result in larger variance, due to the need to add more noise in the privacy mechanism. If M < M1 then the change point may be undetectable, as the bias could be larger than the signal. The same phenomenon occurs in nonparametric testing and change point detection problems, that the smoothing parameter should not be too large to mask the signal.
Algorithm 1 declares the existence of a change point t, if there exists an integer pair (s, t) such that D̂s,t > bs,t. The threshold sequence is detailed in (3). It is separated into two cases: (i) when s(t− s)/t is large enough for both m̂1:s and m̂(s+1):t to be estimated accurately, and (ii) otherwise. In view of the sources of errors, we can see that in case (i), with probability at least 1 − γ, the threshold bs,t is set to be the sum of an upper bound of all sources of errors. In case (ii), the threshold is set to be infinity, so that we never declare a change.
When there is no change point, or when there is a change point but t ≤ ∆, the thresholds, with probability at least 1 − γ, are upper bounds on the estimators. When there is a change point and t > ∆, due to Assumption 4, one can always let s = ∆ such that there are enough samples to provide a good estimator of m∆, the pre-change regression function. If t−∆ is not large enough such that case (i) holds, then we cannot provide a good estimator of m∆+1. Once enough data are collected after the change point, Algorithm 1 is able to tell the difference and declare a change point, with delay upper bounded by in (12). Note that the conditions of case (i) will be satisfied before time ∆ + .
We require the bandwidth h ≤ Cκ to ensure that the binning will not smooth out the jump, and this condition is necessary. In practice, the bin-width can be chosen in a data-driven way [e.g. 38]. In view of Assumption 4, the smaller h is, the larger κ2α2∆/max{σ2,M20 } needs to be. In the best case that h κ, Assumption 4 and in (12) read as
κ2+2dα2∆
max{σ2, M20 } & log
( ∆
cminκ2dγ
) and = Cε M2
κ2+2dα2 log
( ∆
κ2dcminγ
) . (8)
We remark that the detection delay in (12) is of order
M 2 κ2h2dα2 log(∆/(h2dγ)) (M −M0) 2 +M20 + σ 2 κ2h2dα2 log(∆/(h2dγ)),
which again reflects all three sources of errors. Now the question is whether this rate can be improved. To answer the question, we consider a simplified scenario, where we assume that M0 ≤ σ. Theorem 2 (Lower bound). Denote by Pκ,σ,∆ the class of distributions satisfying Assumptions 1 and 3, and assume M0 ≤ σ. Given α > 0 let Qα be the collection of all sequentially interactive αlocally differentially private mechanisms. Given γ > 0 consider the class of change point estimators
D(γ) = { T : T is a stopping time wrt. the natural filtration and satisfies P∞(T <∞) ≤ γ } .
Then for sufficiently small γ, it holds that
inf Q∈Qα inf t̂∈D(γ) sup P∈Pκ,σ,∆
2κ2+2dσ−2α2EP { (t̂−∆)+ } ≥ log(1/γ).
Theorem 2 studies the private minimax rate of the detection delay in the framework proposed in [12]. Compared with standard minimax theory, new tools are required in order to deal with an arbitrary privacy mechanism in Qα. We use Lemma 1 in [12, Supplementary material], which provides a uniform bound on the log-likelihood ratio of two distributions seen through a private channel. To the best of our knowledge, this is the first time that these tools have been applied to change point problems. Although, in our upper bounds, we only had to consider non-interactive mechanisms, this lower bound also applies to general sequentially interactive mechanisms. In particular, this shows that the use of interactive mechanisms is unnecessary in our problem.
Since in the minimax sense the lower bound is taken to be the infimum over all possible estimators, to make the results comparable in Assumption 4 and Theorem 1, we let h κ and compare Theorem 2 with (8). Theorem 2 shows that the lower bound on the detection delay is of order σ2/(κ2+2dα2) log(1/γ), which compared to (8) is off by a logarithmic factor and therefore shows that Algorithm 1 is nearly minimax rate optimal.
We now provide a sketch of the proof of Theorem 2, focusing on the non-interactive case for simplicity. The proof is conducted on an online change point detection framework used in [22] and [37], based on a change of measure argument. The LDP ingredient used in this proof is devised by [12].
To be specific, we first construct a pair of distributions based on Lipschitz regression functions f1 and f2 on some ball B(0, rX ), where rX = O(1), f1 ≡ 0 and f2(x) = (κ− ‖x‖)1{x∈B(0,κ)}. Note that, when κ is small, the regression functions only differ in a small region, and thus this is a difficult change to detect. Given f1 and f2, the two distributions of (X,Y ) are denoted P1 and P2, where X has the same marginal distribution under both while Y |X = x ∼ Unif[fk(x)− σ, fk(x) + σ] under Pk for k = 1, 2. Letting Q be any α-LDP non-interactive privacy mechanism, write Pnκ,σ,ν for the joint distribution of the first n privatised data points when (Xi, Yi) ∼ P1 for i ≤ ν and (Xi, Yi) ∼ P2 for i > ν. By controlling the size of the log-likelihood ratio Zν,n = log(dPnκ,σ,ν/dP n κ,σ,∞) we show that any algorithm that has probability of false alarm bounded by γ will require at least σ2 log(1/γ)/(κ2+2dα2) observations after the change point to reliably detect the change from P1 to P2 at time ν.
As each observation is independent, we may decompose Zν,n = ∑n i=ν+1 Zi. A straightforward calculation shows that dTV(P1, P2) . κd+1/σ, and then ideas from [12] are applied to see that |Zi| . ακd+1/σ and EZi . α2κ2d+2/σ2 for any α-LDP privacy mechanism. We use the Azuma– Hoeffding inequality to extend this to show that
Pκ,σ,ν {
max 1≤t≤σ 2 log(1/γ)
κ2+2dα2
Zν,ν+t ≥ 3
4 log(1/γ) ∣∣∣∣W1, . . . ,Wν} ≤ γ a.s. Using the change of measure argument [e.g. 22, 37], the above bound leads us to complete the proof.

heading: 3.3 Optimal online change point detection with non-private data
text: As a benchmark, we provide the non-private counterpart of Theorem 1 and 2 in this subsection. For completeness, we also detail the counterparts of Definitions 1, 2 and Algorithm 1 in Definitions 3, 4 and Algorithm 2, respectively. We will conclude this subsection with comparisons of results in the private and non-private cases, quantifying the cost of maintaining privacy. Definition 3. Given a sequence {(Xt, Yt)}t∈N∗ and a pair of integers 1 ≤ s < t, we define the CUSUM statistic
D̃s,t = t
max i=1
√ s(t− s)/t ∣∣m̃1:s(Xi)− m̃(s+1):t(Xi)∣∣ , where m̃·:·(·) is defined in Definition 4. Definition 4. Given a sequence {(Xt, Yt)}t∈N∗ , a pair of integers 1 ≤ s < t and a tuning parameter h > 0, we define the regression function estimator as
m̃s:t(x) = νs:t(Ah,j)
µs:t(Ah,j) , if x ∈ Ah,j ,
where νs:t(Ah,j) = (t−s+1)−1 ∑ s≤i≤t Yi1{Xi∈Ah,j} and µs:t(Ah,j) = (t−s+1) −1 ∑ s≤i≤t 1{Xi∈Ah,j}.
Algorithm 2 Online change point detection via CUSUM statistics INPUT: {(Xu, Yu)}u=1,2,... ⊂ Rp × R, {b̃u,t, t = 2, 3, . . . ;u = 1, . . . , t} ⊂ R. t← 1; FLAG← 0; while FLAG = 0 do
t← t+ 1; FLAG = 1− ∏t−1 s=1 1 { D̃s,t ≤ b̃s,t } ;
end while OUTPUT: t.
Assumption 5 (Non-private signal-to-noise ratio). There exists a sufficiently large absolute constant CSNR > 0 such that
κ2hd∆σ−2 ≥ CSNR log(∆/(γhd)).
The following two theorems are the non-private version counterparts of Theorems 1 and 2. Theorem 4 shows that the detection delay rate we obtain in Theorem 3 is optimal off by a logarithmic factor.
Theorem 3. Consider the settings described in Assumption 1. Let γ ∈ (0, 1) and t̃ be the stopping time returned by Algorithm 2 with inputs {(Xt, Yt)}t=1,2,... and {b̃s,t}t=2,3,...;s=1,...,t, where
b̃s,t = 2
√ s(t− s)
t CLip √ dh+ 4σ√ cminhd
√ 5 log(t) + log(32/γ) (9)
Assume that the bandwidth satisfies h ≤ Cκ. If Assumption 2 holds, then
P∞ { t̃ <∞ } < γ. (10)
Under Assumption 3 we have P∆ { t̃ ≤ ∆ } < γ, (11)
for any ∆ ≥ 1. If Assumptions 3 and 5 both hold, then P∆ { ∆ < t̃ ≤ ∆ + } ≥ 1− γ − (cminhd)−1 exp(−∆cminhd), (12)
where
= Cε σ2
κ2hd log(∆/γ),
with Cε > 0 depending only on d. Theorem 4. Denote by Pκ,σ,∆ the class of distributions satisfying Assumptions 1 and 3 For any γ ∈ (0, 1), consider the class of change point estimators
D(γ) = { T : T is a stopping time wrt. the natural filtration and satisfies P∞(T <∞) ≤ γ } .
Then for any sufficiently small γ, it holds that
inf t̂∈D(γ) sup P∈Pκ,σ,∆
2κ2+dσ−2EP { (t̂−∆)+ } ≥ log(1/γ).
We are now ready to quantify the cost of maintaining the privacy in the multivariate nonparametric regression online change point detection scenario.
• As we have pointed out, in order to maintain the privacy, we require X to be a bounded set, the regression function to be upper bounded by M0 and an extra tuning parameter M is introduced in truncation. All these are not needed in the non-private case.
• A more prominent difference roots in the detection delay rate. In the non-private case, the denominator is κ2+d, which roots in the optimal nonparametric estimation [e.g. 32]. In the private case, the corresponding rate is κ2+2d. This is in line with the literature in local differential privacy, where the curse of dimensionality is typically worse in nonparametric and high-dimensional problems than in their non-private counterparts [12, 2, 5, 3].
• Another difference is in terms of the privacy parameter α, which only shows up in the private case. Recalling that we restrict ourselves to the most interesting regime α ∈ (0, 1], the effect of α is twofold: (1) Comparing Assumptions 4 and 5, we see that the private case requires a larger signal by a factor of α−2; and (2) comparing the detection delay rates in Theorem 1 and 3, we see that the rate in the private case is also inflated by a factor of α−2.

heading: 4 Numerical study
text: In this section we present the results of a numerical study of our locally private method’s performance. We consider raw data (X1, Y1), . . . , (Xn, Yn) with n = 10000,∆ = 5000, Xi ∼ Unif[0, 1] and Yi ∼ Unif[mi(x)− 1/2,mi(x) + 1/2], where
m∆ ≡ 0 and m∆+1(x) = (1/2) min(1,max(5− 10x,−1)).
To speed up computation, we modify Algorithm 1 so that D̂s,t is only calculated and compared to its threshold when t ∈ {n/100, 2n/100, . . . , n}. We privatise the data using α in the range
1 2 3 4 5 6
0. 0
0. 2
0. 4
0. 6
0. 8
1. 0
α
fla gg
ed
Figure 1: Proportion of trials with a change flagged 1 2 3 4 5 6
15 00
25 00
35 00
45 00
α
av de
la y
Figure 2: Average detection delay given a flag
{1, 1.5, 2, . . . , 6}. For each value of α, we assume that we have a privatised sample of size n from the pre-change distribution, here Unif[0, 1]×Unif[−1/2, 1/2]. The choices M = 1 and h = 0.2 are used to privatise the data and calculate the test statistics. We permute this sample B = 1000 times to choose our thresholds, as follows: for a range of values of C we run the modified Algorithm 1 on each permutation of the privatised data with the choice
bs,t=  C hα √ log ( t γh ) if s(t−s)t h 2α2 ≥ C2 log ( t γh ) ;
∞, otherwise
and we choose the minimal value of C for which the overall false alarm probability is bounded above by γ = 0.1. With the thresholds chosen we ran the experiment over 1000 repetitions, and results are presented in Figures 1 and 2. The false detection probability was bounded by γ for all values of α. Full details of the implementation and simulation study can be found in the code available online.

heading: 5 Conclusions
text: We studied a multivariate, nonparametric regression, online, privatised change point detection problem. The method we proposed is shown to be minimax optimal in terms of its detection delay, with a theory-guided tuning parameter. As a benchmark result, we have also provided its counterpart for non-private data. The comparisons enable us to understand the cost of maintaining privacy.
In addition to the main results in the paper, in Appendix A we investigate an online univariate mean change point detection problem with privatised data. It includes a minimax lower bound on the detection delay and a polynomial-time algorithm which provides a matching upper bound, saving for a logarithmic factor. The framework we set up in Appendix A serves as a blueprint to study private online change detection with more complex data types.
Comparing the results in Appendix A to those in the non-private setting [e.g. 37] and comparing these differences with those we examined at the end of Section 3.3, one can see that we pay different costs for privacy in different data types. This leads to our future work, studying private change point detection in high-dimensional, functional or other nonparametric data, and understanding the tradeoff between accuracy and privacy in these more challenging situations.
Regarding the setup we have in this paper, it can be easily adjusted to allow for multiple change points. This is because, with large probability, our algorithm will not declare false alarms and will correctly detect a change point with a delay being a small fraction of ∆. Therefore, provided that two consecutive change points are at least ∆ apart, refreshing the algorithm whenever a change point is declared can enable us to detect multiple change points accurately.
Another interesting but challenge future work direction is to allow temporal dependence, say weakly dependent time series. It is not even clear how to define valid privacy mechanisms in this setting: if the time points were strongly dependent then our mechanisms would give more information as time progressed. In fact, this is even an open problem without the presence of change points. We would also need to adjust the concentration inequalities we are currently using to those which are suitable for weakly dependent data.
Supplementary material
The supplementary material contains all the technical details and code of this paper.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: DMS-EPSRC EP/V013432/1.

heading: A A privatised univariate mean online change point detection
text: This is a self-contained section and the notation used in this section is independent from the notation in the rest of the paper. We start by considering a simple Laplace privacy mechanism and CUSUM statistics. Assumption 6. Assume the privatised data are {Z1, Z2, . . .} satisfying Zi = Xi + i/α, where (i) {X1, X2, . . .} is the original data and is a sequence of independent random variables with unknown means E(Xi) = fi, i = 1, 2, . . . and such that supi=1,2,... ‖Xi‖ψ2 ≤ σ; (ii) { 1, 2, . . .} is a sequence of independent and identically distributed standard Laplace random variables, i.e. each t has density z 7→ exp(−|z|)/2 on R; and (iii) α > 0 is a pre-specified value.
Note that when Xi takes values in an interval of length one [a, a+ 1] then the privacy mechanism given by Zi is α-LDP. This can be generalised to intervals of any fixed length by increasing the scale of the Laplace noise appropriately. To extend to unbounded variables we may truncate as in our main methodology in Section 2. Assumption 7. Assume that there exists a positive integer ∆ ≥ 1 such that f1 = · · · = f∆ 6= f∆+1 = f∆+2 = · · · . Let κ = |f∆ − f∆+1|. Assumption 8. There exists a sufficiently large absolute constant CSNR > 0 such that ∆κ2(σ2 + 4α−2)−1 ≥ CSNR log(∆/γ).
We consider the CUSUM statistics D̂s,t = |{(t−s/(ts)}1/2 ∑s l=1 Zl−[s/{t(t−s)}]1/2 ∑t l=s+1 Zl| and run Algorithm 1.
Theorem 5. Consider the settings described in Assumption 6. Let γ ∈ (0, 1) and t̂ be the stopping time returned by Algorithm 1 with inputs {Zt}t=1,2,... and {bt}t=2,3,..., where
bt = 2 3/2 √ σ2 + 4α−2 log1/2(t/γ). (13)
If ∆ =∞, then P∞ { t̂ <∞ } < γ. (14) Under Assumption 7, we have P∆ { t̂ ≤ ∆ } < γ, (15)
for any ∆ ≥ 1. If Assumptions 7 and 8 both hold, then P∆ { ∆ < t̂ ≤ ∆ + Cd (σ2 + 4α−2) log(∆/γ)
κ2
} ≥ 1− γ, (16)
where Cd > 0 depends only on d and satisfies Cd < CSNR. Theorem 6. Denote Pκ,σ,∆ be the class of distributions satisfying Assumptions 6 and 7 supported on an interval of fixed finite length. Denote Qα be the collection of all sequentially interactive α-locally differentially private mechanisms, α > 0. Consider the class of change point estimators
D(γ) = { T : T is a stopping time with respect to the natural filtration
and satisfies P∞(T <∞) ≤ γ } .
Then for small enough γ, and for κ, σ > 0 with κ < 2σ and κ+ 2σ < 1, it holds that
inf Q∈Qα inf t̂∈D(γ) sup P∈Pκ,σ,∆
EP { (t̂−∆)+ } ≥ cσ 2α−2 log(1/γ)
κ2 ,
where c > 0 is an absolute constant.

Review summaries:
The paper analyzes the online change point detection problem subject to local DP.  They claim to be the first to study this problem, which seems like a natural problem to solve, although the central DP setting has been studied before, as they point out.  The contributions of this work are not limited to privacy considerations by also giving minimax rate of detection delay.  

This paper aims to detect the change in the regression function for multivariate sequential data, under the constraint of local differential privacy. Theoretical analysis on the information-theoretic lower bound to the detection delay is proved. And the detection statistic used in this paper is proved to be near-optimal since it matches the lower bound.

The paper studies change point detection for regression under the constraint of local differential privacy (LDP). Its main contribution is a non-interactive (in the sense that all randomizers are chosen ahead of time) algorithm and upper bound on the error of the identified change point, with a sequentially interactive lower bound matching up to logarithmic factors in the failure probability. The paper also provides a non-private benchmark, which is apparently also original.

This paper studies the change point detection problems in the multivariate nonparametric regression under the constraint of local differential privacy. Specifically, the goal is to detect changes in the regression function as soon as the change occurs. To achieve LDP, the proposed method first uses a locally private mechanism to transform the data point (x,y) to another random pair and then uses a classical change point detection algorithm with newly defined CUSUM statistics to detect the change. Theoretical false alarm probability analysis and the minimax detection delay properties are given. To quantify the cost of privacy, the paper also provides the optimal rate in the non-private setting.