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)
(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 4
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)))))))
12222da2
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 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.
(z) - o, fx(x)) +o] under
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 a 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 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.02753. 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:/saarca..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": "loDOcve1OHe", "reviewer": "Reviewer_djMH", "summary": "Paper proposes an online change point detection method with local differential privacy", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "An online changepoint detection method is proposed that preserves privacy via the use of differential privacy. Paper is clearly written, but is theoretically dense (which, by no means is a negative), hence making  a fair review in time constrained fashion hard. My views are based on the superficial skimming of the proofs.\n\nThe main idea of the paper can be reduced to using a local differentially private chanel to privatize incoming data and then running an online change point detection on it. It is an interesting approach where the argument for non-interactive queries is made. I'm curious to what authors think about the use of other DP data encoding techniques for this approach (from a global perspective), such as if we have some prior data available, cant we train a generative model with DP and then use it subsequently for encoding incoming observations? This might lead to a different set of assumptions, but i think it is possible.\n\nAs the paper doesn't have any experiments, it makes it a bit hard to empirically  evaluate the efficacy of the proposed method. If space was the issue, I think the Section 3.3 can be moved into the supplementary material and some empirical results can really strengthen the paper.\n\n\nI have read authors' response.", "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": "2"}, "extra_text": {}}, {"review_id": "_BpLwPb3mT9", "reviewer": "Reviewer_ALYo", "summary": "This paper studies the online CPD problem under the constraint of LDP. In particular, they develop an algorithm to detect changes in the regression function between pairs (X, Y). ", "questions": "", "limitations": "", "rating": 7, "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 is a high quality paper with important contributions to the CPD research field. Let me summarize some comments:\n\n1. Significance: This paper makes significant contributions in \n\n(1) Proposing the new setting where they focus on online CPD in a more strict version of local privacy constraints. This is a realistic but currently under-research setting.\n\n(2) Deriving minimax rate for their setting. And the comparison of privacy bounds against nonprivacy bounds is very informative.\n\nThis work could point a future direction for many subsequent works.\n\n2. Clarity: This paper is very easy to read, even with a large number of maths notations and equations. Explanation of each theorem is clear and thorough.\n\n3. Quality: a very high quality paper.\n\n4. Minor point: this paper does not contain any experiment, even not on simulated dataset. It would be interesting to see the actual performance of the proposed algorithm. And even some toy examples which serves for confirming the conclusions in the theorems would be interesting and worthwhile to include (maybe in the appendix).", "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": "2 hours"}, "extra_text": {}}, {"review_id": "PUDK35Ug8Dw", "reviewer": "Reviewer_KJKZ", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "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": "—Originality— \nI’m not aware of previous work studying LDP solutions to change point detection for regression. If I’m following the paper’s presentation correctly, the given algorithm is really a LDP twist on existing methods for change point detection, although the dependence that LDP forces on additional parameters makes the analysis more challenging. \n\nI know there has been some work on tracking changing data over time with LDP (https://arxiv.org/abs/1802.07128, https://arxiv.org/abs/1811.12469). It’s not directly relevant since users in those papers draw new samples/have new data at each time step, but it’s relevant enough to be discussed — I was initially wondering how this paper differed from those.\n\n—Quality— \nI didn’t read the proofs, but the claims are believable, and all the material needed to verify the claims seems to be there. Nearly-matching upper and lower bounds are a nice, relatively complete story. \n\nI did want to see more discussion of the storage/runtime cost of the algorithm — if I understand correctly, N_h is exponential in the dimension d. This seems like a nontrivial obstacle to practicality. Am I missing some reason that this is not actually a problem?\n\n—Clarity— \nIn general, the writing in the submission is clear. I don’t have any concrete suggestions for improving the writing itself. I do think it’s weird that the paper includes a self-contained treatment of a different problem at the beginning of the supplement. I’m not sure what the point of that section is supposed to be.\n\n—Significance— \nI think significance is the trickiest question to review. On one hand, nearly-matching upper and lower bounds are a nice contribution, and I don’t think the algorithm and analysis are obvious (at least as somebody unfamiliar with change point detection as its own literature). \n\nHowever, the upper bound seems to rely *heavily* on auxiliary knowledge of the problem itself. For example, in Theorem 1, M_0, sigma, C_Lip, and kappa are all assumed to be known to the algorithm operator. This seems like a strong (and unrealistic) requirement. I understand this is probably the price of nearly matching upper and lower bounds, but it does curtail any claim the paper has to a practical solution (plus, the N_h issue mentioned above). Possible ways to mitigate this are some discussion of how flexible the utility is wrt exact knowledge of these quantities, or experiments (though that seems like too much to ask at this point). \n\nOverall, my take on the paper is that it provides a good amount of new info on LDP regression change point detection, but that little of this info is practical, or tells us much about LDP itself (there are already many problems where the optimal LDP algorithm is non-interactive, even against fully interactive algorithms). That makes it hard for me to recommend this paper for acceptance. I’ll try to keep an open mind in discussion, since this is kind of subjective, but I have trouble getting excited about papers that provide (what I see as) impractical solutions to new specific problems.\n\nI may also be undervaluing the non-DP result in this paper, since I really can’t assess its significance to the change point literature in general.\n\nUPDATE AFTER READING AUTHORS' RESPONSE: My overall impression is about the same. The assumptions on knowing many parameters are strong (the authors' claim that these can be obtained by \"data-driven\" methods seems odd in the context of local privacy -- you can get the problem parameters fine, but for some reason change point detection must be done privately?), and the result is a solution with limited practicality. Since I don't think it tells us anything new conceptually about differential privacy, and it doesn't give us tools that we might use in the real world, I suggest rejecting the current version of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some comments on limitations appear above. The paper rejects out of hand the notion that it might have negative societal impact. But to be fair, change point detection is a pretty abstract problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "DBubsg75R8p", "reviewer": "Reviewer_dv2E", "summary": "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. ", "questions": "", "limitations": "", "rating": 3, "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": "I have a main correctness concern on the false alarm constraint. It is well-known that any change point detection algorithms will stop sooner or later. See some classical papers in change point detection literature [Page 1954; Shiryaev 1963; Lorden 1971]. Intuitively, at each time, there's a small error probability, and it will accumulate over time. So the classical false alarm constraint is on the average run length: E(\\hat{t}|\\Delta=\\infty)\\ge \\gamma. It's not clear to me how you can get equations (5) and (10) that P_\\infty(t<\\infty)<\\gamma. And this false alarm probability also appears as the main constraint in Theorem 2 and 4. I would suggest the authors give more explanation on that.\n\nIt'd be helpful if the authors can elaborate more on Definition 1. I'm confused about why it is a CUSUM statistic. My understanding is CUSUM stands for cumulative sum, and it is usually based on likelihood ratio statistics. \n\nIt's also not clear how the signal-to-noise ratio is defined. Assumption 4 is hard to parse. \n\nAdditionally, I don't see any fundamental differences in detecting the change in data vs. detecting the change in the regression parameters. Some motivating examples or explanations would be helpful.\n\nFinally, I would suggest the authors add some experimental results to empirically demonstrate the usefulness of the proposed method.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some discussion of the limitation is given in the conclusion section. I don't see any negative societal impact of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the change point detection under the constraint of LDP. Specifically, at each time point t, a new user arrives with data of the form (X_t, Y_t), where X_t is a feature vector and Y_t is a response variable. 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 an existing change point detection algorithm to detect the change. The reviewers agree that while this is a solid paper, it just misses the bar for NeurIPS.
Decision: Accept (Poster)