Locally private online change point detection
Authors: Thomas Berrett
Yi Yu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Locally private data
online change point detection
multivariate nonparametric regression

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.

Locally private online change point detection
Thomas Berrett
Yi Yu Department Statistics University of Warwick Coventry, CV47AL, U.K. yu. www.wwiwiwcckk. ac. .u
Department Statistics
University of Warwick
Coventry, CV4 7AL, U.K. tom. berrettewarwick ac. uk
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 concrete problem, we study multivariate nonparametric regression problem. At each time point L, the raw data are assumed to be of the form (X,, Yz), where X, is d-dimensional feature vector and Y, is response variable. Our primary aim is detect changes in the regression function ma(x) E{Y][X, 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 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. 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.
Introduction
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 the advance of technology, the applications of online change point detection well beyond quality control and include climatology, speech recognition, imaging processing, among many others. While collecting the data as they are generated, one wishes 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 data science. In practice, many of the systems that we monitor contain sensitive information. For instance, change point algorithms used in cyber security to detect attacks, with the ultimate aim often being to protect private information [24 30 I Other common application involved are highly personal. Given the prevalence of such problems, we address two questions in this paper:
include public health [21 [7] and finance [88, in which many of the data
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 outdated method of privacy protection, particularly in multivariate settings 28 26). Even when direct identifiers such as names and locations removed, data sets often contain enough information for researchers to identify individual subjects, and hence there is need to quantify and control the release of privileged information. Formal privacy constraints provide 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 (NcurIPS 2021).

---

carried out by Apple B1 29 Google [16] and Microsoft [TO], and provides organisations with way of demonstrating the General Data Protection Regulation compliance 77]
The most popular privacy constraint is that of differential privacy [14] which assumes the existence of 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
I5 19
In this paper, we are concerned with a multivariate nonparametric regression online change point detection problem, with privatised data. To be specific, assume that the original data are {(X,, Yi) C R.d x IR, where the regression functions
m²(1) E(Y|X; x), I EER, iEN,
satisfy that m4+1 A my if and only if - A E N". The goal is to find a stopping time 7, which minimises the detection delay (7 ( 4)+, while controlling the false alarm probability P( < A).
With the concern of maintaining privacy, we do not directly have access to the original data {(X,, J.) but a privatised version. Specifically, the original data are transmitted through an a-locally differentially private (a-LDP) channel for some fixed denoted by {WW, ]eeN C Rd x R. In our upper bounds we restrict attention to non-interactive mechanisms [see e.g. [12], and privacy mechanism is given by a sequence {QN) of condi- tional distributions, with the interpretation that (W, Z,)l Y.) = (2,, ~ Q2(-1(2,, y:)). For (er) to satisfy the a-LDP constraint require that
O. The privatised data
(i(A((r,,)) v)) iEN A (..)).(z' ER xR Q((A((x', 6
sup sup sup
In our lower bounds, however, we allow mechanisms to be sequentially interactive [e.g. 12] 2 so that privacy mechanism is given by {Qihie,, with the interpretation that
(W,, (XX,, Y, W,-1, ......... W1, Z1) = (Iz, U/. W4 1-1-122-11.... W1, 21 (- Vs. 04-1, 21-1. W1, 21)).
Here the a-LDP constraint requires that
QA(A((Z, U, 1;; W1, 21)
sup sup sup (x.3). wf XR
sup
(A( V' 1,-1, 2-11 U1 21))
EEN*
Since upper and lower bounds match, up logarithmic factor, 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]
1.1 Summary of contributions and related literature
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 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 private version of the likelihood ratio statistic is analysed. Further development of these ideas, in particular the extension to detection of multiple changes 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 setting in which the distributions private versions of the Mann-Whitney Whitney test to detect a change in location. The problem has also been studied under different notions of central privacy (23
unknown, [8] develop
Secondly, this is the first paper to study the fundamental limits in multivariate nonparametric re- gression change point detection problems. We have derived the minimax rate of the detection delay,

---

allowing the jump size Ilma - ma+1lloo. the variance of the additive noise o² and the privacy constraint a to vary with the location of the change point A. There has been a vast body of literature discussing the detection boundary and optimal estimation in the offline change point analysis [e.g.
33
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. (8). On separate note, multivariate nonparametric regression estimation, under privacy constraints, is studied in [4], and
[6]
classification is studied in 22]
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 this paper enrich statisticians' toolboxes and serve as a benchmark for more complex problems.
2 Methodology
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, binned estimator is the core of the analysis. Recall that the raw data time point include d-dimensional feature vector X,, which we assume is supported within some bounded set A' C Rd and univariate response variable Y, We denote (An.j)j=t,.... as a set of cubes of volume nd, such that {X n An.jjj=1....., a partition of X, and write T for the centre of An.j. The data point (X,, Y,) is then randomised by taking
Wi 1 (X.EA.,,) + aas and Zt. = [ + 4Ma GG,5
where {er,g, ) are independent and identically distributed standard Laplace random variables, and where [M] min(MM max(Y, -M)) with M > a truncation parameter. is shown in Proposition in [see also 2 that this non-interactive mechanism is an a-LDP channel. We emphasise that privacy guaranteed without any assumptions on the distribution of (X
The change point detection method. Given data {WW,, 2 as for online change point detection, we propose Algorithm []] with the CUSUM estimator defined in Definition T and the nonparametric estimators involved defined in Definition 2
Algorithm 1 Online change point detection via CUSUM statistics
INPUT: {(W.. j. Zu,) Juj=1,2... C Rd x R, (br 1 S <<< <t< ts .o....} C R. Ć 2-1 1, FLAG 0;
while FLAG = 0 do
t + 1; FLAG = II- 1 (Det < beaf:
end while OUTPUT: L.
Definition 1. Given a sequence {[Wr,, Ze,)} and pair of integers S < we define the CUSUM statistic
D.,
No max jm1
v s(1 - 8)/1 (m:s(())))))) - ((ot)))(tns))l
where (.).(-) is defined in Definition 2
Definition 2. Given sequence {WW.. Ze.s)} and pair of integers 1 S < t, with h being our bandwidth parameter, we define the regression function estimator as
Dsse(An Mon (Anis) (Aare(An
(x)(x)
if An.
Inc(t-e+3) (-e+1
where
(An = (t ++1 Σ Zio and Dsa(Ans) = -t-
Σ Wish
#SiSt
3

---

Algorithm 1 is standard online change point detection procedure. Whenever a new data point stamped at collected, one checks if a change point has occurred by checking if any of (Ds.t)e=.....t-1 have exceeded pre-specified thresholds. Apparently, both the storage and com- putation costs of this procedure 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 computa- tional cost ((1) when new data point is collected. Of course, can also be smarter: instead of scanning through 8 E {1...., 1}. one can just scan through dyadic grid as described in [38].
The CUSUM statistic D..I. defined in Definition is a normalised difference between two estimated functions, before and after time point s, evaluated each cell in the partition. is used to examine, given all the data up to i, if s is a possible change point. It can be viewed as a sample version of the quantity
st 8)
max
MIG (1
i=++1
where || /loe is the sup-norm of function. In (25 similar CUSUM 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 44, where was shown to be universally strongly consistent estimator of the true regression function.
3 Theory
In this section, we present our core results. All the assumptions are collected in Section 3.1 The theoretical guarantees of Algorithm [ are presented in Section 3.2 which also includes minimax lower bound result showing our proposed method is optimal, off by at most a logarithmic factor. To quantify the cost of maintaining a-LDP, also provide benchmark result of the same data generating mechanism but without privacy in Section 3.3
3.1 Assumptions
Assumption 1 (Setup). Assume that {(x,, Y.)eeen is a sequence of independent random objects, taking values X R. such that vete are independent each with distribution μ on X. We assume that there exists an absolute constant Cmin 0 such that p(Ar.s) 2 hn for all An in the partition of X. Assume that the regression functions m²(.), given by (L. are well defined for p-almost all and E N*, such that there exists an absolute constant CLip 0 with
sup (m;(11) m,(x2)) S CLipllæ1 - xall. 121, X.
VEN-
We also assume that there exists o > such that for all À E R we have
sup sup E MY: X; = x < 12 iEN #ER"
and that supien. supwER [m,(x)] < Assumption]
Mo for some Mo > O.
I is the main model assumption. It is general feature of the local differential privacy constraint that it is not possible work with unbounded parameter spaces [see e.g. [T] Appendix G]. Thus, we assume that the feature vectors are supported in a bounded set N', and we moreover assume that the regression functions m; are bounded, though these bounds are allowed to vary with the pre-change sample size A. 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 aab-Gaussian with parameter which is allowed to vary with the pre-change sample size. Assumption i required to ensure that our algorithm controls the false alarm probability correctly and to ensure its optimality.
Assumption (No change point). Assume that m1 = m2
Assumption 3 (One change point). Assume that there exists positive integer A 2 1 such that
mi
m. # ma+1 mA+2
In addition, let ||ma- ma+1lles

---

Assumption 4 (Signal-to-noies noise ratio). There exists sufficiently large absolute constant OSNR > 0 such that K A/ max Ma) N CSNR log { (A/(Cminh2 ?)
where 7 (0, is the desired bound on false alarm probability and h is the bin-width used in constructing the estimators.
Assumptions and describe different scenarios and aspects of the change point assumptions. Assumption formal assumption describing when there is change point and Assumption depicts the scenario when there one change point. Recall that in Definition | we proposed the CUSUM statistic which is sample version of normalised sup-norm difference between two functions. This is to consistent with K, the characterisation of the jump, introduced in Assumption
Assumption i the signal-to- 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, Mo the upper bound of the mean function mi, a is the privacy constraint and A is the size of the pre-change point sample size. Assumption 4 requires that x212d a logarithmic factor. This in fact allows K, a, Mo and a to vary as A 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
min M 2 3} is larger than
3.2 Optimal online change point detection with privatised data
Theorem below is the main result, which shows that for any E (0, 1), with properly chosen tuning parameters, with probability at least of - y, Algorithm does not have false alarms and has detection delay upper bounded by in (12).
Theorem 1. Consider the settings described in Assumption ! Lety E (0, and & be the stopping with inputs {(Wrj. Zzz) (ej)...=......... and (be,t 1t=,,, t.... where
time returned by Algorithm i
s(t 5) t
(M-MM)2 20
21
{2(M -Moe
if c((==)
2 122d22 64 log
7213 Teminht
M
7213
be,t
+ CLip Vdh)
+
log
Omin hd
7CCminh
oC,
otherwise.
(3)
Assume that the truncation parameter satisfies
M 2 M1 = MM + / 2og(2222222222 + a/h) + log log(2 + a o/h)
(4)
and the bandwidth satisfies h S Ck, where C > is an absolute constant. If Assumption 2 holds, then
Po [T < 20) <7.
(5)
Under Assumption 3 we have
FA f < A} 7
(6)
for any A 2 1. If Afsumpttssss and both hold, then
M
PA fA < A 2-+221100 where e= c=C,
log
h h22
and C. > 0 depends only on d.
To better understand Theorem 1 we first inspect the sources of error in the procedure. The estimators of the regression functions m, are defined in Definition 2 which is a binned estimator averaging over cubes of volume ad This is a typical nonparametric estimator, which brings both bias and variance. On top of this, due the constraints of privacy, truncate the responses by M in
5

---

the privacy channel. The truncation level M should be an upper bound on M1 harge-rrobabllig 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 ! declares the existence of change point t, if there exists an integer pair (s, such that De.. > b,.t. The threshold sequence is detailed in (3) It is separated into two cases: (i) when s(t s is large enough for both mis and (s+1)a 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 % the threshold ba. 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, when there is change point but / S A, the thresholds, with probability at least - 7, are upper bounds on the estimators. When there a change point and t >> A, due to Assumption 4 one can always let A such that there are enough samples to provide a good estimator of ma. the pre-change regression function. If - A is not large enough such that case (i) holds, then we cannot provide good estimator of ma+1. Once enough data are collected after the change point, Algorithm 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 A
We require the bandwidth S Ck 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 is, the larger 2²a²2 A/ max(o" MD} needs be. In the best case that h x K. Assumption
and in (12) read as
R 22+28 a22
A
M
log
and
Ce 2222d
log 22 1:20
(8)
max MR
1min
We remark that the detection delay in 12) is of order
M
(M M2)² + M3 + 02
n:2ndda2 log(A/(124)))
log(A/ (1)))))))
1222dda2
which again reflects all three sources of errors. Now the question is whether this rate can be improved. To answer the question, we consider simplified scenario, where we assume that Mo S a.
Theorem (Lower bound). Denote by Pr,o, A the class of distributions satisfying Assumptions 7 and 3 and assume Mo S Given > 0 let Qa be the collection of all sequentially interactive locally differentially private mechanisms. Given 7 > consider the class of change point estimators
D(7) = :TT T is stopping time wrt. the natural filtration and satisfies PP (T xc) S 5
Then for sufficiently small 7; it holds that
inf inf sup 2 ( log(1/))
(f-
QEQu. TeD()) PEP
Theorem studies the private minimax rate of the detection delay in the framework proposed in [2] 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 uniform bound on the likeliied 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 Assumption 4 and Theorem [ we x x and compare Theorem 2 with ( Theorem 2 shows that the Tower bound on the detection delay is of order
a² 22/(x22 2+20 20 o² log(1 (1/7), which compared to (8) is off by a logarithmic factor and therefore shows
that Algorithm is nearly minimax rate optimal.

---

We now provide a sketch of the proof of Theorem 2, focusing on the non non-interacee interactive case for simplicity.
The proof is conducted on an online change point detection framework used [22] and [37 based on change of measure argument. The L.PP ingredient used in this proof is devised by 12]
To be specific, we first construct pair of distributions based Lipschitz regression functions fi and f2 on some ball (0, rx), where xxx O(1), f1 = 0 and f2(x) (x || ((000)x))) Note that, when is small, the regression functions only differ in small region, and thus this is a difficult
change to detect. Given fi and f2. the two distributions of (X, Y) are denoted P1 and P2, where X has the same marginal distribution under both while YJX z Unif fx
(z) - o, fx(x)) +o] under
Pk for h = 2. Letting Q be any a-LDP non interactive privacy mechanism, write PR. FR.a.v for the joint distribution of the first privatised data points when (X,, Y2) ~ Pi for i S 1/ and (X Y.) P2 for i >> v. By controlling the size of the log-likelihood ratio Zy,n log(d n... / s.., we show that any algorithm that has probability of false alarm bounded by y will require at least o² (og(1//)/(n" (n=+2d a²) observations after the change point to reliably detect the change from P1 to P2 at time V.
As each observation is independent, we may decompose Zu,a Di=u+1 Zz A straightforward calculation shows that drv (P,, P2) S ndt1/a, and then ideas from [12 are applied to see that |Z,| 5 axx+1 /or and EZ, I x2222+2/222 /o² for any a-LDP privacy mechanism. We use the Azuma- Hoeffding inequality to extend this to show that
3
max (ng()/))
Zu 2 log(117))
W Wi.... W
S a.s.
ISS
22+20
Using the change of measure argument (e.g. 22 37
the above bound leads us to complete the proof.
3.3 Optimal online change point detection with non-private data
As benchmark, provide the non-private counterpart of Theorem I and 2 in this subsection. For completeness, we also detail the counterparts of Definitions 0 and Algorithm
[ in Definitions 3
and Algorithm? 2 respectively. We will conclude this subsection with comparisons of results in the private and non con-private cases, quantifying the cost of maintaining privacy.
Definition 3. Given a sequence {(Xr, YI) and a pair of integers S s we define the CUSUM statistic
Da, max aa(l 8)/0 (x. ( (x:)))((X)))
==1
where m...--) is defined in Definition
4
Definition 4. Given a sequence {(X,, YOHENN pair of integers 1 S 8 < and a tuning parameter
we define the regression function estimator as
mx)(x) Usz( Usi(An..) Msst(An.))
if E Andj
where
(ar(Ann)) = (1- (1-8+1)-1
Σ Yıl (X.EA))))) and Maz(And) = (1 (1-8+1)-1 $515
Σ
1(.EA
SSiS
Algorithm 2 Online change point detection via CUSUM statistics
INPUT: {(x,, ku),u=1,,... C. IR x IR, (bu,t. = : u 1..... t c t + 1; FLAG + 0;
while FLAG = 0 do
t t + 1; FLAG = I (D.. s b
end while OUTPUT: t.
Assumption 5 (Non-private signal-to-noise ratio). There exists sufficientll large absolute constant CSNR > such that
2² Ao 22 CsNR log( A (7)1
7

---

Another difference is terms the privacy parameter a, which only shows up in the private case. Recalling that restrict ourselves to the most interesting regime E (0, 1]. the effeet of is twofold: (1) Comparing Assumptions/ [5) we see that the private case requires a larger signal by that the rate The following two theorems are the non non-private version counterparts of Theorems TestoremsTaane and Theorem shows that the detection delay rate obtain in Theorem is optimal off by a logarithmic factor.
Theorem 3. Consider the settings described in Assumption Lery E (0, 1) and t be the stopping time returned by Algorithm 2 with inputs {(X,, Y.) and do.. where
s(t 5)
CLip CLip +
4
/5lg((t) + log((2/1))
(9)
Vinin
Assume that the bandwidth satisfies h S Ck. If Assumption hoold,, then
3o 17 <o> <9
(10)
Under Assumption 3 we have
PA PatisAs A} <n
(11)
for any A 2 1. Assumptions aadd both hold, then
PAfA< PafA<i<A+a
2 - (1mmnnn -1 exp( Acmin
(12)
where
6= Ce
log( A/7),
with Cg > 0 depending only on d.
Theorem 4. Denote by PK...A the class of distributions satisfying Assumptions 7 and 3 For any
7 (0, 1), consider the class of change point estimators
D(v)= {T: T is stopping time wrt. the natural filtration and satisfies P (T < <0) s
Then for any sufficiently small y, it holds that
inf sup TED(1) PEPR.O.A
2xd o - (f- log(1/7).
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 be upper bounded by Mg and an extra tuning parameter M is introduced in truncation. All these are not needed in the non-private case.
prominent difference roots in the detection delay rate. In the non-private case, the denominator is x2+d which roots in the optimal nonparametric estimation [e.g. [32]. In the private
[e.g.32)].
case, the corresponding rate is x2+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-prives non-private counterparts [12 3..
factor of 2; and (2) comparing the detection delay rates in Theorem 1 and in the private case also inflated by a factor of a -2
Numerical study
In this section present the results of numerical study of locally private method's performance.
We consider raw data (X,, (1),..., (Xn, Y,) with = 10000, A 5000, X; Unif[o, 1 and Y, Unif Unif[m, (2))) (z) 1/2, (x) + 1/2], where
mA = 0 and m=+1 (1/2) min max(5 10z, -1))
To speed up computation, we modify Algorithm so that Da. only calculated and compared to its threshold when E {n/100, 2n/100, ... n.. We privatise the data using in the range

---

4500
0.8
3500
2500
1500
5
Figure 1: Proportion of trials with change flagged
Figure 2: Average detection delay given flag
{1, 1... 6). For each value of a. we assume that we have a privatised sample of size n from the pre-change distribution, here Unif[0, 1] x Unif[-1/2. 1/2]. 1/2]. used to privatise the data and calculate the test statistics. We permute this sample 1000 times to choose our thresholds, as follows: for range of values of C' we run the modified Algorithm on each permutation of the privatised data with the choice
The choices M = and 0.2 are
C ha
V
log
7/
if 5(t h2--2 C2 log
7/
00;
otherwise
and we choose the minimal value of C' for which the overall false alarm probability is bounded above by 7 = 0.1. With the thresholds chosen we ran the experiment over 1000 repetitions, and results are bounded by y for all values of
presented in Figures [ [ The false detection probability Full details of the implementation and simulation study can be found in the code available online.
Conclusions
We studied 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 theory-guided tuning parameter. As a benchmark result, we have also provided counterpart for non-private data. The comparisons enable us to understand the cost of maintaining privacy.
In addition the main results in the paper, Appendix A we investigate online univariate mean change point detection problem with privatised data. It includes a minimax lower bound on the detection delay and polynomial-time algorithm which provides matching upper bound, saving for a logarithmic factor. The framework we set up in Appendix A serves 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 examined the end of Section 3.3] one that pay different costs for privacy different data types. This leads to our future work, studying private change point detection in high-dimensional, functional other nonparametric data, and understanding the tradcoff 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 change point with delay being small fraction of A. Therefore, provided that two consecutive change points are at least apart, refreshing the algorithm whenever a change point declared can enable us detect multiple change points accurately.
Another interesting but challenge future work direction dependent time series. It is not even clear how to define valid privacy mechanisms in this setting: the time points were strongly dependent then our mechanisms would give more information 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.
allow temporal dependence, say weakly

---

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/VO13432/1.
A A privatised univariate mean online change point detection
This is 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. Zz....} satisfying Z; X2 + es/a, where (i) (X1,X2....) the original data and is a sequence of independent random variables with unknown means Ix) Sú, = 1, 1.2.... and such that supi=1,2... | S a; (ū) (2........ is sequence of independent and identically distributed standard Laplace random variables, iee. each et has density + exp( <=s(-1=1)/2 on R; and (iii) a > i pre-specified value.
Note that when X; takes values in an interval of length one [a, + then the privacy mechanism given by Z; is a-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
Assumption 7. Assume that there exists a positive integer A N
1 such that fi = = ff +
fa+1 fa+2 ..... Let K = fa+l
Assumption 8. There exists a sufficiently large absolute constant CSNN > O such that (n² 4a 2 > CSNR (17))
We consider the CUSUM statistics D., |[(t-s/(ts)) Zi (=(ss(((t-s))1/// Ei Zil and run Algorithm [
Theorem 5. Consider the settings described in Assumption
6 Letr E (0. 1) and & be the stopping
time returned by Algorithm 7 with inputs [Ze) and (- 2.3.... where
by = 23/2 02 + 4a log (t/7))
(13)
If A oo, then
Po { [0) <9
(14)
Under Assumption
7
we have
PA ( < A} <
(15)
for any A 2 1. If Assumptions
and 8 both hold, then
PA A (a + 4a 2) log( A/7)
2 21-7
(16)
where Ca > O depends only on d and sutisfies Ca < CSNR.
Theorem 6. Denote Pr. be the class of distributions satisfying Assumptions 6 and supported on an interval of fixed finite length. Denote Qa be the collection of all sequentially interactive a-locally differentially private mechanisms, a > O. Consider the class of change point estimators
D(7) (T: T is stopping time with respect to the natural filtration and satisfies P Pxo xc)= 7).
Then for small enough 7, and for Ks a > O with K < 20 and k. + 20 < 1, it holds that Ep (t A)+ co²a -2 log((11))
inf inf sup QE TED()) PEPro.
R2
where e > O is an absolute constant.
10

---

References
[1] Ibrahim Ethem Bagci, Utz Roedig, Ivan Martinovic, Matthias Schulz, and Matthias Hollick. Using channel state information for tamper detection in the internet of things. In Proceedings of the 31st Annual Computer Security Applications Conference, pages 131-140, 2015.
[2] Thomas Berrett and Cristina Butucea. Classification under local differential privacy. Annales de I'ISU,, 63 80 ans de Denis Bosq, 2019.
[3] Thomas B Berrett and Cristina Butucea. Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms. Advances in Neural Information Processing Systems 34, 2020.
[4] Thomas B. Berrett, László Györfi, and Harro Walk. Strongly universally consistent nonpara- metric regression and classification with privatised data. Electron. Statist., 15()):243--2453, 2021.
[5] Cristina Butucea, Amandine Dubois, Martin Kroll, and Adrien Saumard. Local differential privacy: Elbow effect in optimal density estimation and adaptation besov ellipsoids. Bernoulli, 26(3):177-1764, 2020.
[6] Clément L Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman. The structure of optimal private tests for simple hypotheses. In Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, pages 310-321, 2019.
[7] Aloni Cohen and Kobbi Nissim. Towards formalizing the gdpr's notion of singling out. Pro- ceedings of the National Academy of Sciences, 1 117(15):344-8352, 2020.
[8] Rachel Cummings, Sara Krehbiel, Yuliia Lut, and Wanrong Zhang. Privately detecting changes in unknown distributions. In Proceedings of the 37th International Conference on Machine Learning, volume 1 119, pages 2227-2237, 2020.
[9] Rachel Cummings, Sara Krehbiel, Yajun Mei, Rui Tuo, and Wanrong Zhang. Differentially pri- vate poongee-ponttto detection. In Advances in Neural Information Processing Systems, volume 31, 2018.
[10] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances Neural Information Processing Systems, pages 3571-3580, 2017.
[11] John C Duchi, Michael I Jordan, and Martin Wainwright. Local privacy, data processing inequalities, and minimax rates. arXiv preprint 1rXiv:1302.3200: 2013.
[12] John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):122200) 2018.
[13] John Duchi and Feng Ruan. The right complexity measure in locally private estimation: is not the Fisher information. arXiv preprint arXiv:1806.
2018.
[14) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
[15] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468-2479, SIAM, 2019.
[16] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[17] Dario Gregori, Danila Azzolina, Corrado Lanera, Iarii Prosepe, Nicolas Destro, Giulia Loren- zoni, and Paola Berchialla. A first estimation of the impact public health actions against covid-19 in veneto (italy). J Epidemiol Community Health, (4(10)8858-864 2020.
11

---

[18] David J Hand and Gordon Blunt. Prospecting for gems in credit card data. IMA Journal of management Mathematics, 12(2):1332000 2001.
[19] Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner. Local differential privacy for evolving data. arXiv preprint arXiv: 1802.07128, 2018.
[20] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. In Advances in Neural Information Processing Systems, volume 27, pages 2879-2887, 2014.
[21] Taha A Kass-Hout, Zhiheng Xu, Paul McMurray, Soyoun Park, David L Buckeridge, John S Brownstein, Lyn Finelli, and Samuel I. Groseclose. Application of change point analysis to daily influenza-like illness emergency department visits. Journal of the American Medical Informatics Association, 196) 2012.
[22] Tze Leung Lai. Information bounds and quick detection of parameter changes in stochastic systems. IEFE Transactions on Information Theory, 44(7):2917-292) 1998.
[23] T. S. Lau and W. Peng Tay. Privacy-awand quickest change detection. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1999-6003 2020.
[24] Céline Lévy-Ledur and François Roueff. Detection and localization of change-points in high- dimensional network traffic data. Annals of Applied Statistics, 3(2):637-662, 2009.
[25] Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonpara- metric multivariate change point detection and localization. arXiv preprint arXiv: 1910. 13289, 2019.
[26] Lue Rocher, Julien M Hendrickx, and Ales-nlex De Montjoye. Estimating the success of re-identifications in incomplete datasets using generative models. Nature Communications, 10(1):1-9, 2019.
[27] Angelika Rohde and Lukas Steinberger. Geometrizing rates of convergence under local differ- ential privacy constraints. Annals of Statistics, 4865)2664622670, 2020.
[28] Latanya Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(05):557-570, 2002.
[29] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Pri- vacy loss in Apple's implementation of differential privacy on MacOS 10.12. arXiv preprint 1.Xx::1709.027533 2017.
[30] Alexander Tartakovsky. Rapid detection of attacks computer networks by quickest changepoint detection methods. In Data Analysis for Network Cyber-Securily, pages 33-70. World Scientific, 2014.
[31] Apple Differential Privacy Team. Learning with privacy at scale. http::://maahhhineeeeannaaa http:/saaraa..aaaaaggagiataaarrr
Accessed: 30-09-001.
[32] Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008
[33] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Leynaud-Boured Optimal change-point detection and localization. arXiv preprint arXiv:2010. 1470, 2020.
[34] W Allen Wallis. The statistical research group, 1942-1945. Journal of the American Statistical Association, 75(370))320-330, 1980.
[35] Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical risk minimization in non-interactive local differential privacy revisited. In Advances in Neural Information Processing Systems, pages 965-974, 2018
[36] Yi Yu. A review on minimax rates change point detection and localisation, arXiv preprint arXiv:2011.01857, 2020.
12

---

[37] Yi Yu, Oscar Hernan Madrid Padilla, Daren Wang, and Alessandro Rinaldo. A note on online change point detection. arXiv preprint Stt::2006.03288. 2020.
[38] Yi Yu, Oscar Hernan Madrid Padilla, Daren Wang, and Alessandro Rinaldo. Optimal network online change point localisation. arXiv preprini arXiv:2101.05477, 2021.
[39] Wanrong Zhang, Sara Krehbiel, Rui Tuo, Yajun Mei, and Rachel Cummings. Single and multiple change-point detection with differential privacy. Journal of Machine Learning Research, 22(29):1-36, 2021.
13


Reviews:
[{"review_id": "zsltkZpOf1", "reviewer": "Reviewer_gcFi", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper uses a cusum-like detection statistic to detect the change in the regression function for privatised data. In detail, we do not have direct access to the true data but only the data transmitted through a locally differentially private channel. Then the regression function is estimated and used to compute the detection statistic. The detection statistic is not new but this paper provides theoretical analysis on the detection delay of the proposed detection statistic and also a matching theoretic lower bound, by using the tools in the paper \"John C Duchi, Michael I Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation.\"\n\nThis paper is well-written and easy to follow. And the theoretical results are interesting contributions to the change detection community.\nA few detailed comments: It would be interesting to provide the explicit form or the order of the constant C_\\epsillon as it is closely related to the detection delay as shown in Theorems. Also, it would be interesting to provide some numerical examples for demonstration purposes.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "r8bnMWyORah", "reviewer": "Reviewer_FYQ4", "summary": "The paper studies online change point detection problems,  in particular multivariate nonparametric regression problems, under the LDP constraint. Change point detection problems are some of the well studied problems in statistics, and have been considered in the central model of DP.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this problem (without the LDP constraint), the algorithm is presented with raw data of the form (X_i, Y_i), i \\in [N], where X_i is multidimensional. It is assumed that regression functions remain the same until some \"change point\" t = \\Delta. The goal of the algorithm is to detect this time step \\Delta with the least delay, while making sure that probability that algorithm declares change point before the time step \\Delta (false alarm) is minimized.\nUnder the assumption that the data set lies in a bounded set, the proposed algorithm simply adds Laplace noise and sends the noisy data. Then, on the server side,  upon getting the noisy data at time t, the algorithm checks if a change point has occurred by checking some cumulative statistic has exceeded pre-specified thresholds. This seems like a natural adaptation of the online change point detection algorithms to the LDP setting.  Both mechanisms on the server side and client side seem fairly standard.\nThe paper analyses this algorithm to show that it has no false alarms, and has nearly optimal detection delay. The paper also presents optimal rates and lower bounds on the problem without LDP constraints and bounds on the price of privacy. Overall these results are satisfactory.\nWhile I support accepting this paper, I do feel that authors could have done a better job at explaining the ideas behinds their proofs, especially of the lowerbound, which seems to be the main contribution. It also helps if they highlight their innovations compared to the previous works. Finally, the authors state that study of  univariate version of this problem as one of their 3 main contributions, yet there is not much regarding this despite having an entire page left unused!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3"}, "extra_text": {}}, {"review_id": "c_qXfzXlYJH", "reviewer": "Reviewer_P1kk", "summary": "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.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe privacy mechanism is simply the Laplace mechanism and the sensitivity analysis is referred to in a previous work.  The online change point detection statistic has very high computation cost, as pointed out in previous work.  It would be helpful to express whether the assumptions in 3.1 are necessary for privacy, utility, or both.  Theorem 1 requires knowledge of the assumption parameters, in particular the clip M needs to be sufficiently large.  \n\nThe major contribution from this work, in my opinion, comes from the lower bound.  The privacy mechanism and the statistical method are all standard and the assumptions seem to help the utility analysis carry through.  However, it is interesting that with those same assumptions, there is a nearly matching lower bound.  I would have liked to have seen more explanation for the lower bound as that seems to me to be the main result.  Since there is almost a full page left that the authors could have used, they could have at least provided a proof sketch.  Furthermore, the locally private univariate mean change point detection problem was listed as a contribution but its entire discussion is left to the supplementary file.  Much of this should be brought to the main body.  \n\nMinor comments:\n- Cite this work for Apple’s local DP use: https://machinelearning.apple.com/research/learning-with-privacy-at-scale \n- Small nit,  given this is a DP paper, it would be better to use \\epsilon as the privacy parameter, rather than \\alpha and thus another variable for the random Laplace noise terms in line 99.  \n\n\n#################\nUpdate: I have read the author comments and will keep my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "The paper deals with rigorous privacy guarantees.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agree that the problem studied in the paper would be of interest NeurIPS community, and the innovation in the paper is interesting. Hence, we decided to accept the paper for a poster presentation. However, we hope that in the final version of the paper, authors address several important comments made by reviewers and improve the presentation substantially.
Decision: Accept (Poster)