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.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
" 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 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 {K- 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² /K2 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 {( 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-gau 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-Isear. 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 120.::200..12/60, 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": "wRCDnexdAQM", "reviewer": "Reviewer_aT7R", "summary": "In this paper, the authors investigate the problem of univariate change point detection under adversarial noise, specifically a dynamic extension of Huber's $\\epsilon-$contamination model. The paper also extends the signal-to-noise ratio lower bounds in the non-adversarial setting to an $\\epsilon$ dependent bound in the new setting. Also, it provides the optimal localization error rate for the case when the signal-to-noise ratio is above the minimum threshold. Additionally, the authors propose an algorithm that can consistently detect the number of change points when the signal-to-noise ratio is higher than the proposed lower bound, assuming the minimal spacing is at least of the order of $\\log(n)$. The provided algorithm uses a mix of RUME and a scanning idea producing an almost optimal localization rate.", "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 paper considers a new and relevant setting to study the problem of adversarial univariate change point detection. It also provides novel $\\epsilon-$ dependent signal-to-noise ratio lower bounds for detection in this new setting,\n\nQuality: To the best of my knowledge, the submission seems theoretically sound, and the authors do an excellent job of discussing the implications of the theoretical results. The splitting of the problem into two regimes helps better understand the nature of the challenges faced in solving the problem.\n\nClarity: The paper is very well-written and easy to understand.\n\nSignificance: This paper investigates a very relevant problem and gives a great systematic theoretical approach to the problem. Apart from establishing some critical theoretical bounds for the problem, the paper also provides a practically useful algorithm to solve the problem in a near-optimal fashion.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not seem to have any negative societal impacts and I feel it adequately discusses the incomplete parts of the problem in the conclusion section.", "review_text": "", "extra_scores": {"ethical_concerns": "I did not find any ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "YM6IYUOUijF", "reviewer": "Reviewer_9vuk", "summary": "This paper studies the change point detection problem in the context of possibly adversarial contamination. Recall that previous literature on change point detection either neglected the robustness issues, or focused on heavy-tailed data only. Under a generalization of the Huber contamination model (Assumption 1) authors first derive lower bounds (Lemmas 1 and 2) which highlight an interesting transition phase between the impacts of the signal to noise ratio and the proportion of outliers. Next an algorithm is proposed, mixing standard change point detection method with a robust mean estimator (Algorithm 1). Consistency guarantees for Algorithm 1 are derived in Theorem 1. Finally, numerical experiments are presented, showing the robustness of the proposed method to adversarial contamination (Section 4).", "questions": "", "limitations": "", "rating": 7, "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": "I find the paper globally well written and interesting. The combination of change point detection and outlier robustness is quite natural, and the solution proposed is very sound. The phase transition phenomenon exhibited is interesting, and well discussed. The fact that no knowledge about $\\epsilon$ is required is of great practical interest. On the negative side:\n- l. 50-52: works on change point detection in the context of (time independent) adversarial contamination are evoked, but their results are not compared to Theorem 1 for instance. Furthermore, from the reading of Section 1.1, I kind of understood that this paper was the first one to focus on change point detection and robustness to outliers (independently of the dependence on $i$). Could the authors be a bit more precise on this point?\n- I would like to point out the following work [3], as the $O \\cup I$ framework developed therein seems very similar to Assumption 1. In particular, no i.i.d. assumption is made for the outliers.\n- In the same vein, I wanted to point out the Median-of-Means (MoM), a robust mean estimator, firstly shown to be robust to heavy-tailed data [1, 2], and now studied under adversarial contamination too [3, 4]. This could be of interest for the authors and future research\n- Has the transition phase phenomenon been also verified empirically? \n- The interpretation of Theorem 1 is made slightly difficult by the fact that most constants are not explicited. This is true in particular for the value of $c$, which controls the rate. Is there any analogous result for time independent contamination, that could serve as bechmark?\n- l. 240: I might have missed something, but $\\kappa = 0$ only means that the smallest gap is 0, not that there is no change point, no?\n\nMinor comments:\n- Figures and Algorithms on top/bottom of pages ease the reading\n- l. 43: In general, three\n- l. 186: of *the* estimator\n- l. 226: wi*n*dow\n- l. 227: without contamination\n\nOverall, I feel the paper develops a coherent story with an interesting solution, motivating my grade. However, I am not extremely familiar with the related works so I keep a 3 confidence and wait for discussion with other reviewers to refine my assessment.\n\n[1] \"Sub-gaussian mean estimators\" Devroye et al. 2016\n\n[2] \"Loss minimization and parameter estimation with heavy tails\" Hsu and Sabato 2016\n\n[3] \"Robust classification via MOM minimization\" Lecué et al.2020\n\n[4] \"Generalization Bounds in the Presence of Outliers: a Median-of-Means Study\" Laforgue et al. 2021\n\n**Post-rebuttal edit**\n\nI thank the authors for their response. I encourage them to incorporate some of the arguments raised (especially for points 1&5 and points 2&3) in the revision, as things were more clear with these explanations. In light of the other reviews (and the subsequent discussions with the authors) I keep my 7 score and am in favor of acceptance.", "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": "5"}, "extra_text": {}}, {"review_id": "NSu0oXBGdsl", "reviewer": "Reviewer_x4pj", "summary": "This paper studies the problem of univariate mean change detection in the presence of adversarial contaminations. The authors formalize the adversarial contamination via the dynamic Huber $\\epsilon$-contamination model and propose an algorithm to detect changes. They provide theoretical analysis of the estimation error and perform experiments comparing their method with existing ones.", "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": "The formalization of change point detection with the dynamic Huber $\\epsilon$-contamination model is new. The proposed algorithm is a combination of the robust mean estimation and scanning. The theoretical analysis is solid providing two interesting regimes of the detectability as well as near optimal localization error of the proposed algorithm. Experiment results demonstrate the ability of the proposed algorithm against adversarial contaminations. While the paper is mostly clear, I still have several questions/comments stated below.\n\nMajor comments:\n1. The motivation of considering adversarial contaminations in change point problems is not very convincing. I would like to see more explanation why this setting is interesting. In particular, it seems to me that this contamination is not very realistic -- the attacker needs to have access to the full data sequence, locate potential change points, and then design contaminations. In comparison, the adversarial examples in image classification can simply be obtained by adding Gaussian noise.\n2. I found Lemma 2 confusing. In particular, where does the condition (5) come from and why (5) is the complement of the regime in Lemma 1?\n3. Following my first comment, since adding specifically designed contaminations is hard, It is interesting see how the proposed method and others perform under less adversarial contaminations.\n4. Since $\\sigma$ and $\\epsilon$ are usually unknown in practice, it is expected to see experiments demonstrating how different the detected change points would be if we estimate these two quantities from data rather than input the true values.\n\nMinor comments:\n1. On line 43, \"In generally\" --> \"In general\".\n2. While the model allows for a different $\\epsilon$ at different time point, both Lemma 1 and Lemma 2 assumes $\\epsilon_i = \\epsilon$. Do they hold true if $\\epsilon_i \\le \\epsilon$?\n3. In Algorithm 1, \"$j$ is a local maximizer\" of what? $D_h(j)$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments above for suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "EtKqtcASJix", "reviewer": "Reviewer_k3Ng", "summary": "In the paper \"Adversarially Robust Change Point Detection\", the authors showed that localization rate depends on contamination proportion. In addition, they propose a method for change point detection resistant to such events as, e.g. spurious change points. ", "questions": "", "limitations": "", "rating": 4, "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": "In general, although the title and the article's body is full of change point detection and adversarial attacks, it seems both topics are not fully disclosed. We recommend the author concentrate on more interesting topics such as robustness. It helps to bring the work as the development of known methods, e.g. from \"Univariate mean change point detection: Penalization, cusum and optimality\", from a novel perspective. \n\nIn the current variant, the considered cases for adversarial attacks seems contradictory: on the one hand, creating spurious change point is a reasonable attack, but on the other hand, as there is interference in the data distribution by adding the change in it, so why we suspect that methods for change detections shouldn't signalize about this spurious point. \n\nAnother limitation is considered the univariate mean change point case. It's an extreme constraint, and we recommend considering multivariate data and changes in scale too. \n\nGeneral comments and questions:\n•\tWhat is a motivation for choosing baseline methods, e.g. BIWEIGHT? We recommend using methods from a review of the 2020 year \"An Evaluation of Change Point Detection Algorithms\" as a benchmark in addition to proposed in the paper. \n•\tWhat was a motivation for Hyber $\\epsilon$ - contamination model?\n•\tIn line 136, the authors claim the lower bound for $log(n)$. Where it comes from? Please, put some explanations or references. \n\nIn general, the text of paper should be improved:\n•\tLines and contaminated points are not visible in Figure 1;\n•\tLine 64. \"[22] showed that their … \"whom? \n•\tIt will be better not to start sentences with the reference, e.g. lines 74, 76, 77\n•\tLine 134. $d_H$ defined only in Appendix. \n•\tWhy there are URLs in the references? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission characterize a phase transition in a change-point univariate problem where a fraction of the time points
are contaminated by adversarially chosen distributions. The problem is clearly posed and the phase transition
had not been previously reported.
   
There is strong enthusiasm among most referees that the contributions are significant.
While some referees suggested interesting extensions to multivariate data and other forms of adversarial contamination,
the univariate phase transition under Huber's contamination model discovered in
the current submission is a sufficiently solid and complete contribution on its own.
Based on this, leaving these extensions for future work is reasonable and I recommend to accept the paper.

Decision: Accept (Poster)