Adversarially Robust Change Point Detection
Authors: Mengchu Li
Yi Yu
Venue: NeurIPS 2021 Poster (2021)
Keywords: change point detection
robust statistics

Abstract: Change point detection is becoming increasingly popular in many application areas. On one hand, most of the theoretically-justified methods are investigated in an ideal setting without model violations, or merely robust against identical heavy-tailed noise distribution across time and/or against isolate outliers; on the other hand, we are aware that there have been exponentially growing attacks from adversaries, who may pose systematic contamination on data to purposely create spurious change points or disguise true change points. In light of the timely need for a change point detection method that is robust against adversaries, we start with, arguably, the simplest univariate mean change point detection problem. The adversarial attacks are formulated through the Huber $\varepsilon$-contamination framework, which in particular allows the contamination distributions to be different at each time point. In this paper, we demonstrate a phase transition phenomenon in change point detection. This detection boundary is a function of the contamination proportion~$\varepsilon$ and is the first time shown in the literature. In addition, we derive the minimax-rate optimal localisation error rate, quantifying the cost of accuracy in terms of the contamination proportion. We propose a computationally feasible method, matching the minimax lower bound under certain conditions, saving for logarithmic factors. Extensive numerical experiments are conducted with comparisons to robust change point detection methods in the existing literature.  

Adversarially Robust Change Point Detection
Mengehu Li Department of Statisties University of Warwick mengchu.. li @wwrwwwwckk...ooo.... ac ac.uk uk
Yi Yu
Department of Statistics University of Warwick yi. yu.yu. 2wwarwwwwwwccccc ac
Abstract
Change point detection is becoming increasingly popular in many application areas. On one hand, most of the theoreticalll-justfeee methods are investigated in an ideal setting without model violations, merely robust against identical heavy-tailed noise distribution across time and/or against isolate outliers; on the other hand, we are aware that there have been exponentially growing attacks from adversaries, who may pose systematic contamination on data to purposely create spurious change points or disguise true change points. In light of the timely need of a change point detection method that is robust against adversaries, we start with, arguably. the simplest univariate mean change point detection problem. The adversarial attacks are formulated through the Huber E-contamination framework, which in particular allows the contamination distributions be different at each time point. In this paper, we demonstrate phase transition phenomenon in change point detection. This detection boundary is a function of the contamination proportion and is the first time shown in the literature. In addition, we derive the minimax-rate optimal localisation error rate, quantifying the cost of accuracy in terms of the contamination proportion. We propose computationaall--easiii method, matching the minimax lower bound under certain conditions, saving for logarithmic factors. Extensive numerical experiments are conducted with comparisons to existing robust change point detection methods.
Introduction
Change point detection is attracting tremendous attention due to the demand from various application
areas, including bioinformatics [e.g. 1, 2], climatology [c.g. 3, 4] and finance [c.g. 5, 6]. among many change point analysis have been studied based on different data types [e.g. 7, 8, 9, 10, 11, 12]. The majority of the methods are studied in model- specific way, in the sense that the noise distributions are -ub-Gaussian/sub- Exponential and the between change points data are independent and identically distributed. The few robust change point detection results [e.g. 13, 14, 15] are designed against isolated outliers and/or heavy-tailed noise.
others. In the last few decades, a vast body of methods and theory
In recent years, we aware of the risk of adversary attacks in emerging application areas, ranging from image classification [16], object detection [17], to natural language processing [18] and beyond. In this paper, we consider change point analysis setting possibly attacked by adversaries. As teaser, we consider a concrete climate data set from [19] containing the daily average PM2.5 index data in Beijing from 15-Apr-2017 15-Feb-2021. The original and adversarially contaminated data (with a spurious change point created on 17-Jan-2020) are shown in Figure 1, where the orange points in the right panel denote the adversarially chosen contamination points. As we will see more details in Sections 4.2 and E.3, applying the BIWEIGHT(3) method [15] to the original data set leads to two change point estimators, while only the spurious change point is detected in the presence of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

contamination. In contrast, our proposed method aARC is less affected by the adversarial attack and detects the same two change points with and without the presence of the contamination.
Daily average PM2.5 Beijing 2017/4/15 2021/2/15
Daily average Beljing from 2017/4/15 2021/2/15 (corrpted))
Algorithm aARC
BIWEIGHT(3) Point type Advarsarial
Original
Figure Adversarial attacks on a PM2.5 index data set. Red and blue lines indicate the change points estimators of aARC and BIWEIGHT(3); lines in the left panel are jittered to be visible.
From this example, we see that the presence of adversarial contamination can significantly affect the performance of even the state-of-the- art robust change point detection algorithm and lead to detecting spurious change points, while missing out the ones that can be discovered without contamination. In general, three effects of the adversarial attacks are of interest: (i) hiding change points; (fi) creating spurious change points; and (iii) increasing the localisation error rate.
To armour the change point detection procedure against potential adversarial attacks, in this paper, we establish and investigate a univariate mean change point detection framework, under a dynamic extension of the Huber e-contamination model (1). Our contributions in this paper are threefold.
To the best of our knowledge, this the first paper formalising the change point detection framework with the dynamic Huber e-contamination model (2). To be specific, the contamination distributions are allowed to be distinct every time point. Most if not all of the robust change point detection papers, despite that they have shown their methods are robust against outliers and/or heavy-tail noise, the theoretical framework they study are still within the i.i.d. territory. This has handicapped the existing work to study the adversary attacks, where adversaries may design specific contamination based on their knowledge of the underlying models.
In Section 2, we propose a signal-to-noise ratio quantity k/o and show that in the regime k/o S v max (s, log(n)) LJ, algorithm is guaranteed to estimate the change points consistently in the sense of (3); and we show in Section 3 that in the regime n//o 2 Vmax (E, log(n)/L) and L > (o), our proposed algorithm can localise change points consistently with properly chosen tuning parameters. The localisation error rate can also be nearly minimax optimal, off by logarithmic factor, for certain range of model parameters. The detection boundary matches that in the standard change point literature (i.e. e = 0) and that in the robust statistics literature (i.e. λ 0). Compared to the standard literature in the univariate mean change point detection [20, 21], our results can quantify the cost the contamination terms of e, and shed light on both the cost of robustness and designs of adversarial attacks.
The Adversarially Robust Change point detection algorithm (ARC) that we propose in Algorithm 1 is combination of [22] and simple scanning idea. Prasad et al. [22] showed that their robust univariate mean estimator (RUME) can provide optimal estimation without the presence of change points. The scanning idea has been widely used with numerous variants, but none of which is studied an adversarial setting. our paper, we exploit the potential of these two areas and investigate both the theoretical and numerical performances of ARC. In addition, we also propose variant of ARC, namely automatic ARC (aARC), which adapts to the contamination proportion e.
1.1 Related literature
Without the concern of robustness, the theoretical framework of univariate mean change point analysis problem is well established [e.g. 21, 20), with a host of algorithms available to practitioners, including penalised least square methods [c.g. 9] and CUSUM- based methods [e.g. 23], among many others.

---

When the robustness comes into play, a line of attack has been deployed recently. Fearnhead and Rigaill [15] considered a penalised M-estimation procedure, which designed particularly against outliers with large variances. Yu and Chen [24] studied a testing problem, utilising a U U-statistic-type test statistics and showing that robust against i.i.d. heavy-tailed noise distributions. Hušková [25] and Hušková [13] adapted Huber's s theory on robust statistics to study regression change point detection problem. There has also been work on the online version of the robust change point detection problem [e.g. 26].
In the robust statistics literature, without the presence of change points, the heavy-tailed model and the Huber e-contamination model are the two in the spotlight. A fundamental problem therein is to estimate the mean of the underlying distribution or the decontaminated distribution accurately. Efficient and optimal algorithms have been developed for both models separately [e.g. 27, 28]. Some work tackles the two models simultaneously. For instance, Prasad et al. [22] exploited the connection between these two models and developed a conputationally--finnn -efficiient univariate mean estimator that optimal under both models. Hopkins et al. [29] and Diakonikolas al. [30] considered filter-type algorithm, which was developed under the high-dimensional contamination model, and showed that it achieves optimal error guarantees under the heavy-tailed model as well. It is worth noting that the theoretical results derived in this paper is not straightforward adaptation of the existing literature due to the presence of potentially multiple change points.
1.2 Problem setup
We kick off the formalisation of the problem with the Huber e-contamination model [31]
F. (1 F) ell,
(I)
where F' and Il are the distributions of interest and arbitrary contamination, respectively, and measures the strength of contamination. This model is widely used in the robust statistics literature, but usually if not always, it is assumed that F is sub-Gaussian has some form of symmetry, and the data are i.i.d. from F. [e.g. 32, 33, 22]. In our model assumption below, we relax both restrictions by considering F' to be potentially heavy-tailed and allowing H vary across time, which we refer to as the dynamic Huber E- E-contamination model, and which prompts it to model the three types of adversarial attack we mentioned previously, as well as a wide range of less adversarial attacks studied already in the literature.
Assumption 1. Lei (Y:)== E TR be a sequence of random variables with distributions
F) + H;H;, i (1,...,,,,
(2)
where Fi's are distributions with means f. 's and variances upper bounded by o² < co, H; ''s are the distributions of arbitrary contamination and e; 's are the proportions of contamination upper bounded by s E 1/2). Let {Ne K+1 )== C [0, n)] be strictly increasing integer sequence with No = 0, M]+11 = n, satisfying that ft+1 + fú, if and only if t E {nk] f== Further assume that F = ... F for k- O....,K. Let the minimal spacing L and jump size is be K
K minn(n+++ (M++1 } and min K5 = min Im -mul k=1
K
min k=0
k=1
With Assumption 1, our goal can be formalised detecting any change on Jt's, provided that K > O. in the presence of adversarial noise H 's In some applications, adversaries may have access to the generating process (2), and in particular have control over H, 's. As a consequence, adversaries may be able to design attacks creating spurious change points or cancelling out the change point patterns in Fs's. We are the first attempt in discussing the robust change point detection, allowing for such form of structural attacks.
We aim to obtain consistent change point estimators (ri lm such that with high probability it holds that
K = K and n n'd ([m) (7) + 0.
(3)
where dh (-::) is the two-sided Hausdorff distance (see Definition A.I in the supplementary material).
In the case when x. = 0, i.e. there is no change point on the signal fi.....ff. regardless of the situations of H, 's, we would like to have
P(K- 0) + 1.
3

---

To highlight that Fi's are the distributions of interest, in Assumption 1, we restrict the power of an adversary by assuming E < 1/2. It is apparent that when 2 1/2, detecting the change points in Pi's may be impossible regardless of any other model parameters.
2 Phase Transition and Minimax Lower bounds
Without contamination, well established that, if TV & Vlog(n), then the minimax sense, no algorithm is guaranteed to produce consistent estimators; if Lo Z v Vlog(n), then the optimal localisation rate is of order o²x -2 [e.g. 21, 20J. In this section, we are to present the counterparts of such results in the model described in Assumption 1. In detail, Lemma shows that
k/o S V /max (og
(4)
then no consistent estimator exists. In particular, by considering the two regimes inherited in (4), we can identify two sources of difficulties in detecting change points in an adversarial setting.
Small E regime. When E S log(n)/L, LL, condition (4) is reduced to ko Vlog(n)/L, which is essentially the boundary without the presence of contamination (cf. Section 2 in [21]). An interesting
interpretation of the result is that quantifies how much contamination will affect the fundamental difficulty of the problem and this threshold is of order log(n)) L.. Similar phenomena have been observed in the robust mean estimation [e.g. 34] and testing (e.g. 35] problems.
Large E regime. When e 2 log(n))L, condition (4) is reduced to k/O S VE. The term oVe is essentially the minimal asymptotic bias that any estimator of the means fi's must suffer under the Huber e-contamination model (1) with finite variance o² [36, 22]. Here, we assert that if the jump size k is no larger than the asymptotic bias ovE, then no consistent estimator exists. Referring the three attack strategies we mentioned in Section 1, this is the situation where the signal of change point can be completely hidden by contamination.
Lemma 1.
Let (Yi) satisfy Assumption 1. Suppose that = i - -, ....., Let Pm L., denote the corresponding joint distribution. Consider the class of distributions
P == {PH,L,o, x22 Lo -2 < max {8s/(1 - -2s), log(n), 4eL}, L. S [n/4]]
For all n E N large enough, it holds that inf sup Ep(du(() n n(P)) 2 n/8, where the infinum is
9 PεP
over all possible measurable functions of the data and (PP) is the set of true change points of P E P.
Note that in many interesting scenarios, log(n) 8=/(1 2z), which is equivalent to < log(n)/(2log(()) + 8). Therefore, for simplicity, in the following, we only consider the condi- tion k/O K max Ve, Vlog(n)/L), under which, algorithm is ensured to output consistent estimator. As we will show later in Theorem 1, ARC can produce consistent estimation under nearly optimal conditions.
Our second task is to demonstrate the optimal localisation error, under a higher signal-to-noise ratio condition. To be specific, we consider
min {ie2 Lo (1 2x) log - [.] Sn=
(5)
with { being arbitrarily diverging sequence. Noting that ++ (1 - 2x) log x)/x} is a decreasing function on (0, 0.5), to see how (5) complements (4), we consider the following two regimes.
Small E regime. 1 < (1-2s) log ((1 ((-==) =)/E}, then (5) 2 2 Sn. which complements the small regime implied by (4), and under which, as implicd by Lemma 2, the lower bound on the localisation rate is of order o² -2 This is the same rate without the presence of contamination and this again quantifies the cost of contamination, that is to say, if is small enough, one can hope for localisation error as if there is no contamination.
Large regime. If -=-o-2 2 (1 2x) log (11-((11)) =)/=). then (5) is (1 2s) log ((1 E)/E} L 2 Sn- This complements the large regime implied by (4). The corresponding lower bound, as implied by Lemma 2, will diverge if & tends to 1/2 at an arbitrary rate. If & is bounded away from 1/2, then regardless of the strength of x, the lower bound of constant order, which is in fact trivial due the discrete nature of the change points.

---

Lemma 2. Let {Yit--1 satisfy Assumption I with only one change point and let P L.,.,,z denote the corresponding joint distribution. Suppose that E, E, I....,n. distribution
n. Consider the class of
p= (P = min (N (1)
22) log ((1 e)/e} L) 2 L, <n/3),
where {Gn} is any arbitrarily diverging sequence. Then for all E N large enough, it holds that {2 log(log(11 =)/E)}}
inf sup Epfda (7, m( 2 max (1-
4 PEP
where the infimum is over all possible measurable functions of the data and n) (P) is the set of true change points of P E P.
2.1 The cost the contamination
To quantify the cost of the contamination, we compare the results derived above with their counterparts when no contamination presents.
The difficulty of the problem. Intuitively speaking, the existence of contamination H, 's increases the difficulty level of detecting the change points in F,'s, 's, and the larger the proportion is the more difficult the problem becomes. Lemma I details this cost. When the contamination proportion is small enough fit in the small е regime, no matter how dramatic each contamination distribution H; is, we are facing problem with the same difficulty level as if contamination does not exist. When the contamination proportion is large enough, the difficulty is dominated by the difficulty of one-sample robust mean estimation problem, no matter how large the minimal spacing is.
This is indeed interesting, if not surprising, that the difficulty of this robust change point detection problem has a phase transition between the difficulties of change point without contamination and robust estimation without change points.
The accuracy of the localisation. The localisation error will be affected in the presence of adversarial contamination especially when is large relative to x/o as evidenced by Lemma 2. Nevertheless, in terms of order, we should aim to achieve the same localisation accuracy as no contamination exists.
3 The Adversarially Robust Change Point Detection Algorithm
In this section, we propose the adversarially robust change point detection method (ARC), which borrows the strength from robust estimation and standard change point analysis areas.
3.1 Methodology
ARC is a very intuitive algorithm but can achieve nearly optimal results in certain regimes as discussed in Section 3.3. We scan through the whole time course using the statistic D,,(), which is the absolute difference between two RUME estimators [22]. The RUME is proposed in the context of one sample robust mean estimation problem based on the idea of shorth estimators [37, 36] and is shown to be simultaneously optimal under both the heavy tailed and Huber e-contamination model (1). For completeness, detail the RUME in Algorithm B. in the supplementary material. Note that the sample splitting procedure in the RUME helps to avoid statistical dependency during the theoretical analysis but may increase the variance of the estimator.
The sean statistic D-(-) a robust variant of the renowned CUSUM statistie [7], except for two differences. First, instead of just using the sample average, with the robustness in mind, robust mean estimator RUME deployed. Second, the CUSUM statistic takes the difference between two normalised sample means, which be of two heavily unbalanced samples. However, due to contamination, it is difficult to track the performance robust mean estimator based on arbitrary sample sizes. Similar concern also arises in the robust clustering problem where each sub-population needs to be represented sufficiently to derive theoretical guarantees [e.g. 38). Despite the ubiquity of such scan statistics in the change point literature, arguably, the most closely-related one would be [39], where E is set to be zero and F, 's are assumed to be sub-Gaussian.
With (Dx())} in hand, we first focus on all the 4h-local maximisers an idea seen in [39] when tackling uncontaminated change point detection problems - defined below. All 4h-local maximisers then thresholded by À 0 to avoid overestimating the number of change points.
5

---

Algorithm Adversarially robust change point detection (ARC)
Input: [Yij=1
R. A, h O.
B + 0.C 0:
for j E {2h, 2h +l..... 2h} do
(a) + RUME (M))
RUME
See [22] or Algorithm B.1 b See Definition I
j is 4/-local maximiser of Dr (i) then - B BU()
end if end for
for I B do
if (t), > X then C Cu
end end for Output: C.
Definition 1. For any h 2 0 and x E R. the interval (x: - h, h) is called the h-neighbourhooo of I. We call an h-local maximiser of function f(-), if f(x) 2 faz), ), for any x' E (x h, + h).
A probably unsatisfactory feature of using the RUME is that the proportion of contamination is required as an input. Unfortunately, this seems to be the bottleneck observed in the majority of optimal robust procedures, including M Meestimators [e.g. 31], truncated means [40], and more recently developed nigh-dimensional robust procedures [e.g. 36, 28]. Recently, Chen et al. [35] proposed cournament-based procedure for one sample robust mean estimation in the Huber e-contamination model (1) that is adaptive in and it has been used for tuming parameter selection in [33]. We also investigate the empirical performance of our algorithm when using this procedure select & in Section 4. In terms of theory, applying the tournament procedure [35] requires the knowledge of the density function of F, 's and the i.i.d, assumption, which are more restrictive than our framework. Another key tuning parameter in ARC is the window width h, the theoretical guidance of which is discussed in Sections 3.2 and 3.3, and the practical guidance can be found in Section
Lastly, we note that the computational complexity of ARC is of order Onn log(h)), where the term h log(h) is from ranking the data to find the shortest interval involved in RUME. Even though the worst complexity is O(n log(n)), it is still more efficient than the existing methods such as the penalised biweight loss approach with computational complexity O(n²) (cf. Corollary 2 in [15]).
3.2 Theoretical guarantees
Theorem Let (Yi)== be an independent sequence satisfying Assumption with K > Let (ix J be the output of Algorithm 1.
Assume that (i) there exists a sufficiently large absolute constant Cx such that k/O > Ox / S.ymaxle, /mxx(e, log(n)/hh) (ii) there exists an absolute constant C" > such that 2 C'ee log(n)/h C' Cooo(n)/h < 1/2, where s' = max (e, C' (og(n)/h;; (ii) the window width satisfies that h L/8; and (iv) the threshold satisfies that X = CLOVE'.
We then have that there exists an absolute constunt e > 0 such that
{ K
K and
max
7K mel S 2h
2 2
Theorem shows that under certain conditions, we have consistent estimation on the number of fi's change points with h =(n), in the presence of adversarial attacks. The localisation error rate essentially the window width and the required hignal-to-noiss ratio condition is also function of the window width A similar result is obtained in [39] with h x without contamination. Even though we allow h O(L) in Theorem 1, this is still somewhat unsatisfactory, but we would like to point out that requiring some knowledge of T. is widely observed phenomenon in the change point analysis literature, even when the contamination is absent. For example, in the wild binary segmentation

---

algorithm [e.g. 23, 21], random intervals are deployed to localise change points. However, the ideal theoretical performances rely heavily on knowing that the length of these random intervals are the same order of the minimal spacing I. [41].
Given the conditions, conduct sanity check the feasibility of choosing window width h implying consistency. Based on Proposition D. in the supplementary material, we see that the conditions (i)-(iv) in Theorem hold if
max {10, 4C302/n²) log(n), C(s) log(n),
E S 0.1, 0.1 < < 1/4 {1, x² x²((()))))
h
where (0) 1/(1/2-111) 20(1 20)). The lower bounds on h in both cases are of order o(n)) This means that there exist regimes of h such that n max Mi m7c - 0, which implies the consistency.
Theorem 1 provides the guarantees of ARC when there exists at least one change point, i.c. K > O. When K 0, i.e. there is no change point of fi's Algorithm is still consistent in the following sense.
Corollary 1. Let {Y:)i=1 be an independent sequence satisfying Assumption 1 with k = 0. Let {Fis k== (fic) be the output of Algorithm Assume that there exists absolute constant C' > such that 2 + +22C'e log(n)/h + C' log(n))h < 1/2, where e' = max (E, C' log(n)) and the thresholding tuning parameter satisfies that = CxaVe'. We then have that there exists an absolute constant e >> 0 such that P KK- 0} 2 -
3.3 Optimality of the ARC algorithm
Recalling the fundamental limits of the adversarially robust change point detection problem, in view of Theorem 1, ARC can be nearly optimal in terms of both the signal-to-noise ratio condition and the localisation rate in certain regimes, with a properly chosen width depending on the model parameters. This is indeed restrictive, but generally speaking, robust learning problems suffer from the same restriction. For instance, as we mentioned before, in robust mean estimation problems under the Huber E-contamination model, the value should be known in order to achieve optimal results in most algorithms and it is impossible to estimate E when the contamination distribution not specified [35]. Padilla et al. [42] studied the nonparametric change point detection problems, which also a type of robust change point detection problem, and the optimality results thereof rely on the kernel bandwidth to be the same order the minimal signal strength. In line with our discussions in Section 2, we consider the following two cases.
Small regime. If S log(n)/L L, then with the choice that h x L, the conditions in Theorem 1 be- come KV LVL Z v /log(n), which by comparing with the small regime in (4) shows that ARC con- sistent under the minimal signal-to-noise condition. In this regime, ARC also enjoys the nearly-optimal localisation rate, provided that the minimal segment length satisfies L max {o² /K² 11 log(n).
Large regime. Consider two cases in this regime. If log(n)/T. S < 0.1, then with the choice h x log(n)/s, the conditions in Theorem reduce to K ス ovV and L Z log(n)/s, which the minimal signal-to-noise condition required by comparing to the large regime in (4). In this regime, ARC achieves nearly-optima localisation rate of log(n)/= if E is of constant order. If 0.1 < 8 < 1/4 min (1, x² (())²)). then with the choice / x w(E) log(n), conditions in Theorem 1 reduce to 6 2 AvE and L 2 w(e) log(n), which is the minimal signal-to- -to-soise condition since is of constant order. In this regime, ARC achieves nearly-optimal localisation rate of w(s) log(n).
4 Numerical Results
We consider the following competitors to ARC: PELT, the Pruned Exact Linear Time method [9]; BIWEIGHT, the penalised cost approach based on biweight loss [15]; ___UUUM, recursive application of a Wald-type testing procedure [43, 15] that is shown to be consistent for single change point detection in robust regression context; and R_ =_USTAT, U-statistic-type robust bootstrap change point test [24], the theory of which is developed for testing change points but not localisation. PELT serves non-robust baseline. As for the other competitors, their theoretical guarantees, if exist,
7

---

are established against identical heavy-tail contamination at each time point, but not against the potentially, systematic adversarial attacks.
For BIWEIGHT, we adopt its default setting denoted as BIWFIGHT(2) and a stronger penalty setring BIWEIGHT(5). For R_ CUSUMM, we combine it with the wild binary segmentation [23], with 500 random intervals and BIC-type threshold as in [15]. For R RSUTT,,, we choose the kernel ((z, y) sign(x - y). the bootstrap sample size 100 and the initial block size 250.
For ARC, the choice of should depend on the applications. In general, we recommend h = (n) where 10 C' 30. As for simulation purpose, fix h 170 and X max{0.60, 80s) In the simulations, we vary L which serves the purpose of examining the sensitivity of h' ''s choice. More sensitivity results can be found in Section E.2.2 in the supplementary material. Note that the true value of a is used as the input for all algorithms in simulation. For real data, due to the suspected short segment length, we consider a range of smaller h and adapt À accordingly estimation error incurred. Different tuning parameter choices for the competitors are also considered. The standard deviations are estimated via the median absolute deviation of the data. For the choice of é, we use the true ε as the input in simulations, and a data-driven automated method based on the tournament procedure considered in [35], which views the uncontaminated distributions as Gaussian. We call ARC with automaticcall-choseee and aaRC inherited from the RUME procedure, we run the algorithms over 1000 times on the real data sets and report the mode. See Section E in the supplementary material for further details.
account for the larger
as automated ARC (aARC). Due to the variability of ARC
4.1 Simulations
Recall that the goal is to detect the changes in the means of Ft's with the attacks in the form of H; "s. We design two settings mimicking two types of adversarial attacks: (i) creating spurious change points and (ii) hiding change points. Less adversarial settings where the contamination does not rely on the knowledge of change point locations are considered in Section E.2.3 in the supplementary material. Throughout, let n 5000 and 6(-) be the Dirac measure.
(i) Creating spurious change points. Let Y; ~ W), + c5(-3), i E (G 1 1)M + 1. I,..., (j- - 1/2) and Y; ~ (1 -1- (V),)) + +3()), E {G 1/2) + +1...,,MM,, {1..... }} and M = n/A. An illustration the left panel in Figure There is no change point on Ft's, but 2A- 1 changes on [[Y] are created through the contamination distributions H; 's.
E
(ii) Hiding change points. Let Y; (1 (0, 1) + e (s/ (2)),, i ((i 1)M 1, ..... Uj
M) and Y; idd (1 (K, 1) + εō (M(1 1/(2)))) i E {(i - 1/2) + , M). j E {l..... A and M = n/A. A. An illustration the right panel in Figure 2, which shows that the change points in Ff's are all offset, in terms of [Y;))'s, 's, by the contamination.
Figure 2: The left panel: an illustration of attack setting (i) with E = 0.1, A = 5 and o = 1. The right panel: an illustration of attack setting (ii) with E 0.2, realisations of Gaussian distributions and the orange dots are from the contamination distributions.
and x = 1.5. Black dots are
Note that each scenario in (i) is specified by the tuple fc, o and we consider 19 different combinations. The measurement is R K, with = O. Each scenario in (ii) is specified by the tuple (s, A, and we consider 12 different combinations. The measurements are A KK| and n - (7). m)) Detailed results can be found in Section E.2 in the supplementary material. Some representative settings are depicted in Figure 3.
Overall, if the adversarial attacks are creating spurious change points scenario, when the strength of adversarial attack is strong, e.g. when E is large and when A and small, ARC and AARC
8

---

outperform other competitors by detecting fewer spurious change points. If the adversarial attacks are hiding change points, when E large and the signal к is small, the adversarial noise can fool the competitors such that they consistently output incorrect estimated numbers of change points, while ARC and aARC maintain a reasonable performance across all settings.
In terms of localisation errors, in general, we under-perform with respect to the competitors when they can correctly detect the change points, which can be seen as the cost of accuracy when preserving robustness. The observed variability of our results is mainly due to the sample splitting step in the RUME procedure and can be improved with larger sample size. Moreover, we notice that aaRC performs competitively comparing with ARC with the true value as an input.
Mean error on K ()
Mean enor on (i)
Mean localisation error in (i)
ARC BIWEIGHT(2) BIWEIGH(5))
C_CUSUM RLUSTAT
Figure 3: Representative simulation results. From left to right: | K| in setting (i) with {E, A, a} =
{0.1, 2, 1}; j K| in setting (i) with {e, A, o} = {0.2, 2, 1}; IK K] in setting (ii) with {s, A, x} = {0.1, 2, 0.66); J K| in setting (ii) with {e. A, x] {0.2, 2, 1.2); dæ in setting (ii)
with {E, A, k] = {0.1, 2, 0.66]; and dæ in setting (ii) with {s, A, k} = {0.2, 2, 1.2].
4.2 Real data analysis
We consider three real data sets in this subsection: the well-log data set that has been extensively studied in the existing literature and two PM2.5 index data sets that additions the literature. Section E.3 in the supplementary material contains additional details on the evaluation method and choices of tuning parameters.
The well-log data set [e.g. 44, 15, 45, 46) contains 4049 measurements of nuclear magnetic response during the drilling of well. We depict the data set and the outputs of aaRC in Figure 4. With few isolated observations, the majority seem to behave well. This falls into the regime of the existing robust change point detection methods. As result, all competitors considered output very similar results which are omitted in Figure 4.
Consider PM2.5 index data sets [19]: the Beijing PM2.5 index from 15-Apr-2017 15-Feb- 2021 considered in Section and London PM2.5 index from 1-Ja to 17-Mar-2024
In the Beijing data set, BIWEIGHT(3), R_ CUSUM and aARC all detect two change points based on original data set as shown in the left panel of Figure 1. We then randomly sample 100 points uniformly from the first 1000 data points and change their value to 3/ where is the median absolute deviation of the original data set. Similarly, we sample 50 points from the remaining data and change their value 0.50. After this perturbation, only aARC still detects the previous two points and is robust against the spurious one, while the competitors both wrongly miss the previous ones while picking up the spurious one.
The London data set, compared to the well-log data set, contains way more 'outliers' terms of the model (2) - which can be viewed as either that the distributions of interest F,'s are heavy-tailed while & is small or F,'s are belaved while e is large. The result of aARC similar to that of R R_CUSUM, as they treat the data as if the underlying e is large. The ARC with input more frequently detects one additional point in the first quarter the data compared to aaRC, which is similar to the result obtained by BIWEIGHT(5), as they treat the data as if the underlying is small.
0.01

---

Wall-log data set
Daily average PM2 Beijing (corupled)
Daily average PM2.5 in London
Algorithm
aARC
ARC
BIWEIGHT(S)
R_ Point type
Adversorial Original
Figure 4: Real data analysis. From left to right: The well-log, Beijing PM2.5 index and London
PM2.5 index data sets. Lines jittered in the middle and right panels for visualisation purposes.
Conclusion
In this paper, we analysed the change point detection problem under a dynamic extension of the Huber e-contamination model by allowing the contamination distributions to be different at each point. Under our framework, the adversary can deploy certain attacking strategies that are of interest for the change point detection problem but cannot be modelled within the existing literature. A computationally-efficeenn algorithm ARC that combines the ideas in robust statisties and change point detection literature is shown to be nearly-optimal in terms of both the signal-to-noise ratio condition and the localisation rate when the minimal spacing is small or when is of constant order. The optimality results developed in this paper are first time shown in the literature, but are still somewhat restrictive. In order to achieve optimality in the whole parameter space, novel robust estimation and testing techniques necessary and are
agenda.
We note that our framework, even if of constant order, the optimal localisation error is of the same order compared to the situation when no contamination exists. This is in contrast to the strong contamination model [e.g. 47], where a cluster of outliers are allowed be created by the adversary, which would unavoidably have larger impact on the localisation error rate. For example, placing en contaminated points adjacent to a change point would incur localisation error of en which lead to inconsistent localisation in the sense of (3), Our future plan includes both considering different contamination models and extending the methodology to more challenging data types.
We conjecture that using optimal and efficient robust estimators for high dimensional data or other complex data types combining with the scanning window idea could lead similar results in Theorem and Corollary 1. This is left to our future work.
Supplementary material
The supplementary material contains all the technical details.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: DMS-EPSRC EP/VO13432/1.
10

---

References
[1] Adam Olshen, ES Venkatraman, Robert Lucito, and Michael Wigler. Cireular binary seg- mentation for the analysis of array-based DNA copy number data. Biostatistics, 5(4):557-572. 2004.
[2] Andreas Futschik, Thomas Hotz, Axel Munk, and Hannes Sieling. Multiscale DNA partitioning: statistical evidence for segments. Bioinformatics, 30(16))2255-2266) 2014.
[3] Jaxk Reeves, Jien Chen, Xiaolan L Wang. Robert Lund, and Qi Qi Lu. A review and comparison of changepoint detection techniques for climate data. Journal of applied meteorology and climatology, 46(6):00--115, 2007.
[4] Colin Gallagher, Robert Lund, and Michael Robbins. Changepoint detection in climate time series with long-term trends. Journal of Climate, 26(14):4994 5006, 2013.
[5] Andrey Pepelyshev and Aleksey S Polunchenko. Real-time financial surveillance via quickest change-point detection methods. arXiv preprint arXiv:1509.0157. 2015.
[6] L'luboš Pástor and Robert F Stambaugh. The equity premium and structural breaks. The Journal of Finance, 36(4):1207-123) 2001.
[7] Ewan S Page. Continuous inspection schemes. Biometrika, (1(112):100-111 1954.
[8] Alexander Aue, Siegfried Hörmann, Lajos Horváth, and Matthew Reimherr. Break detection in the covariance structure of multivariate time series models. The Annals of Statistics, 37(6B): 4046-4087, 2009.
[9] Rebecca Killick, Paul Fearnhead, and Idris A Eckley. Optimal detection of changepoints with linear computational cost. Journal of the American Statistical Association, 107(500):1590-15)) 2012.
[10] Tengyao Wang and Richard J Samworth. High dimensional change point estimation via sparse projection. Journal of the Royal Statistical Society: Series (Statistical Methodology). 80(1): 57-83, 2018
[11] Daren Wang, Yi Yu, and Alessandro Rinaldo. Optimal change point detection and localization in sparse dynamic networks. arXiv preprint 10X.v:800.0066/0 2018.
[12] Daren Wang, Yu, Alessandro Rinaldo, al. Optimal covariance change point localization in high dimensions. Bernoulli, (71))55445575, 2021.
[13] Marie Hušková. Recursive m-tests for the change-point problem. In Economic Structural Change, pages 13-33. Springer, 1991.
[14] Alexander Fisch, Idris Eckley, and Paul Fearnhead.. linear time method for the detection of point and collective anomalies. arXiv preprint (106:01800009944 2018.
[15] Paul Fearnhead and Guillem Rigaill. Changepoint detection in the presence of outliers. Journal of the American Statistical Association, 1196525): 2019
[16] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world, 2017.
[17] Dawn Song. Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Florian Tramer, Atul Prakash, and Tadayoshi Kohno. Physical adversarial examples for object detectors. In 12th (USENIX) Workshop on Offensive Techhologiess ({ (WOOT)) 18), 2018.
[18] Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. arXiv preprint
2017.
[19] Air Quality Historical Data Platform, 2018. URL hattp:://aggicc.og//dtttaaaaeaee register/.
[20] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud-Boured Optimal change-point detection and localization. arXiv preprint arXiv:2010.111 11470, 2020.
11

---

[21] Daren Wang, Yi Yu, and Alessandro Rinaldo. Univariate mean change point detection: Penal- ization, cusum and optimality. Electronic Journal of Statistics, 14(1):1917-1911 2020.
[22] Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar, A unified approach to robust mean estimation, arXiv preprint v/Xiv:107.000927, 2019.
[23] Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42(6):2243 228122222,,,,,, 2014.
[24] Mengjia Yu and Xiaohui Chen. A robust bootstrap change point test for high-dimensional location parameter. arXiv preprint arXiv:1904.033: 033772 2019.
[25] Marie Hušková. Robust change point analysis. In Robusiness and Complex Data Structures, pages 171-190. Springer, 2013.
[26] Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas. Doubly robust bayesian inference for non-stationary streaming data with 3-divergences. arXiv preprint arXiv: 1806.0226, 2018.
[27] Gábor Lugosi and Shahar Mendelson. Sub-gam gaussian estimators of the mean of random vector. Annals of Statistics, 47(2):783-794, 2019.
[28] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference Machine Learning, pages 999- 190- PMLR, 2017.
[29] Samuel B Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. arXiv preprint 200.:20007.18399, 2020.
[30] Ilias Diakonikolas, Daniel M Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. arXiv preprint orXiv:2007.15616 2020.
[31] Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 492-518. Springer, 1992.
[32] Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel. Robust statistics: the approach based on influence functions, volume 196. John Wiley & Sons, 2011.
[33] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv:/802.06485, 2018
[34] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber's contamination model. The Annals of Statistics, 46(5): Oct 2018
[35] Mengjie Chen, Chao Gao, and Zhao Ren. A general decision theory for Huber's s-contamnaionnnnonnnnooonn model. Electronic Journal of Statistics, 10(2):355233744, 2016.
[36] Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2016.
[37] David F Andrews and Frank R Hampel. Robust estimates of location. Princeton University Press, 2015.
[38] JA Cuesta-Albertos, C Matrán, and A Mayo-Iscar. Robust estimation in the normal mixture model based on robust clustering. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 70(4):779-80) 2008
[39] Yue S Niu and Heping Zhang. The screening and ranking algorithm to detect DNA copy number variations. The Annals of Applied Statistics, 6(3): 2012.
[40] Jerry Li. Lecture notes robustness in machine learning, October 2019.
[41] Yi Yu. A review on minimax rates change point detection and localisation, arXiv preprint axXiv:2011.01857, 2020.
12

---

[42] Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonpara- metric multivariate change point detection and localization. arXiv preprint vrXiv:1910.13289, 2019.
[43] Marie Hušková and Pranab K Sen. Nonparametric tests for shift and change in regression at an unknown time point. In Statistical analysis and forecasting of economic structural change, pages 71-85. Springer, 1989.
[44] Jeremias Knoblauch, 2018. URL https: https://gi http://gtttt..t/////.
turing-institutte
[45] Gerrit JJ van den Burg and Christopher KI Williams. An evaluation of change point detection algorithms. arXiv preprint arXiv:2003.06222 2020.
[46] Shintaro Fukushima, Atsushi Nitanda, and Kenji Yamanishi, Online robust and adaptive learning from data streams. arXiv preprint 2rXiv:2007.12/6// 2020.
[47] Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprint 1226: 2020.
13


Reviews:
[{"review_id": "uzSLrtaYNYy", "reviewer": "Reviewer_J2f5", "summary": "The paper addresses the problem of change point detection for univariate time series in the presence of adversarial attack through the introduction of data perturbations. A novel method is introduced for this problem based on a robust variant of the CUSUM statistic that uses robust mean estimators. The proposed method is supported by theoretical guarantees of the consistency of change point estimation in the presence of adversarial attacks according to the level of contamination.", "questions": "", "limitations": "", "rating": 8, "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: The problem of change point detection in the presence of adversarial attack has received little attention, and the proposed approach is an extension of traditional approaches, but with solid theoretical guarantees of robustness. The paper provides an interesting and relevant new branch of research in the field of adversarial machine learning.\n\nQuality: The paper provides detailed theoretical analysis of the properties of the proposed algorithm, as well as systematic evaluation of its performance on both synthetic and real-life datasets under a variety of adversarial attacks. The baselines used for evaluation include traditional change point detectors as well as more recent robust estimators.\n\nClarity: The paper is clearly structured and very well written. The evaluation methodology is described in sufficient detail. While the graphical presentation of the results on the real-life time series was interesting, it would help if this was accompanied by a more quantitative summary of the detection rate, false positive rate and localisation error for each method. I couldn’t see this in the supplementary material.\n\nSignificance: The paper has considerable practical significance in terms of addressing the robustness of change point detection, which has practical use in a wide range of application domains, such as fault detection and cyber security. The paper also provides a detailed theoretical framework from which to provide guarantees of the robustness of estimation using the proposed method.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors highlight that their robust change point estimation technique is computationally feasible. It would have been good to see some form of brief complexity analysis to quantify this point.\n\nA quantitative summary of the accuracy results on the real-life data sets would be useful.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "XMNxkf2_vLl", "reviewer": "Reviewer_6R4u", "summary": "This paper presents a method that aims for *robust* detection change points in a time series in the presence of noise, against the following adversarial attacks: (i) hiding true change points; (ii) creating spurious change points; and (iii) increasing the localisation error rate.  The key approach is to formulating the change point detection framework with the dynamic Huber epsilon-contamination model, such that the method can be robust against outliers and/or heavy-tail noise, as well as handling data that not out of the i.i.d. territory (e.g., temporally changing).\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": "Strengths:\n\nThe paper is well-written and well-organized, without obvious typos.\n\nThe topic is fundamental and useful for machine learning.\n\nAllowing non-iid data distribution in change-point detection is the key contribution.\n\n=======================================================\n\nMajor concerns:\n\n(1) Section 1.1 should discuss why the proposed method is not a straightforward adaptation of the existing Huber epsilon-contamination model.\n\n(2) The last paragraph in Section 3.1 claims that \"the computational complexity of ARC is ... still more efficient than the existing methods\"  There should be an experiment on time performance to show actual \"timing\" statistics as compared with the existing methods for different data set size.\n\n(3) Section 4.1 gives some guidance on how to set h but h depends on C, which ranges 10 to 40. Are the results sensitive to h?  Also for real data, the paper suggests to use a range of smaller h.  Why smaller h for real data?  Also, how small is small?  If we use different values for h on the same data, how will the change point vary?  There should be an experiment of the sensitivity of the results to h.\n\n(4) Missing several related references:\n[R1] Selective review of offline change point detection methods, Signal Processing 2020\n[R2] Doubly Robust Bayesian Inference for Non-Stationary Streaming Data with ß-Divergences, NIPS 2018\n[R3] QuantTree: Histograms for change detection in multivariate data streams, ICML 2018\n[R4] Differentially Private Change-Point Detection, NIPS 2018\n[R5] M-Statistic for Kernel Change-Point Detection, NIPS 2015\n[R6] Kernel Change-point Analysis, NIPS 2008\n\n(5) Why not include recent methods such as [R2] (see above) as competitors for comparison in Section 4?\n\n(6) From Tables 1 & 2 shown in supp., the proposed ARC and aARC do not always obtain the lowest mean error as compared with others. It is not obvious (from the results in supp.) that the proposed ARC and aARC are better than others in terms of mean error.  Also, the cases {0.1, 2, 1} and {0.2, 2, 1} (etc.) are not found in Supp.  I suppose the performance results in supp. should be more comprehensive and a superset of the cases reported in the main paper.\n\n(7) [44] demonstrates the use of many different datasets to evaluate various change point detection methods.  Why not use the datasets mentioned in [44]?\n\n=======================================================\n\nOther issues:\n\nYou may use a heatmap visualization to tabulate all the results here.\n\nLine 101: should f be\n\nLine 103: please double check the subscripts here.\n\nLine 109: better to mention \"in the supplementary material\" after Definition A.1.\n\nLine 226: widow -> window\n\nLine 227: please add a note on the meaning of the math symbol between h and L here\n\nBetween line 236 and 237: what if epsilon is 0.1?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not explicitly list down the limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "Nil.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "TRPpKIZ2KOK", "reviewer": "Reviewer_pALD", "summary": "The paper addresses the problem of change point detection under Huber contamination model. The work gives tight bounds on the minimax error as well as a simple, efficient algorithm for achieving it. ", "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": "Significance\n----\nChange point detection is a fundamental question in statistics, with applications to various areas. The paper tackles an important problem of designing robust algorithm for it. \n\nOriginality\n-----\nThe paper combines known techniques in robust estimation (RUME) and change point detection (CUSUM). I believe this combination, though natural, has not appeared in the literature. On the other hand, the paper does not introduce new (algorithmic) techniques.\n\nQuality\n----\nThe theoretical claims are correct.  The paper appears to be a full result, as the theorems settle the question almost completely. However, it has a few limitations, as I will point out later. \n\n\nClarity\n----\nThe paper is generally well-written. It's probably hard to do within the space limit, but a reader may like to see more intuition explaining the theorems and the algorithm.\n\n\n\nOther minor points on writing\n---\n\nLine 51: “paper” -> “papers”\n\nLine 93: redundant reference to [32]\n\nLine 102: it’s hard to parse the notation $F_{\\eta_{k}+1}=\\ldots=F_{\\eta_{k+1}}$. Maybe expand the ellipsis a little bit.\n\nLine 3 of Algorithm 1: it's better to write \"for $j \\in \\{ 2h, 2h+1, … , n-2h \\}$\". I made an incorrect interpretation of the ellipsis for my first reading.\n\nLine 194: \"the closest related\" -> \"most closely related\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations\n---\n1. As is pointed out in Sec 5, it would be nice to extend the model assumption to adaptive adversary (that is, the adversary can examine the data and arbitrarily modify it), recently studied in robust estimation literature. I am confused why the author(s) claims that \"the optimal localisation error is of the same order compared to the situation when no contamination exists\", as the Lemma 2 clearly factors $\\epsilon$ into the error bound. As far as we know, the difference between the Huber contamination and adaptive  adversary is not significant in mean estimation—the optimal error rate is the same, and the same set of algorithms (e.g., filter or convex programming) work for both.\n\n2. The paper fails to extend the model or algorithm to high dimensions. Such generalizations may be within reach. High-dimensional analog of robust mean estimation algorithms exist, and some of them, such as median-of-means, achieve strong sub-gaussian tail guarantees, similar to RUME. (I understand that a sub-gaussian tail is needed here, so just being robust is not enough.) The simple scanning idea of this paper also works for, say, $\\ell_2$ norm.\n\n3. It is unclear why the author(s) has to appeal RUME for robust mean estimation. There are simpler choices, such as median-of-means and trimmed means, that achieve same guarantees in the univariate setting. Note that RUME is not computationally efficient in high dimensions.  This prevents extending the results here.\n\n\n4. Assumption 1 states that $\\epsilon$ can be taken all the way to $1/2$, and Theorem 1 inherits this assumption. However, line 236 requires $\\epsilon <1/10$. The authors should make clear what the breakdown point is. It would be great if the algorithm achieves the optimal breakdown point of $1/2$. \n\nSocietal Impact\n---\nSince it is mostly theoretical, I believe the work will not make potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives an adversarially robust way to perform change point detection in univariate time series analysis. Adversarial robustness in this context has not been considered before, and this paper provides a new algorithm as well as empirical evidence.
Decision: Accept (Poster)