Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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).
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:
- 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?
- 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.
- 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
- Has the transition phase phenomenon been also verified empirically? 
- 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?
- 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?

Minor comments:
- Figures and Algorithms on top/bottom of pages ease the reading
- l. 43: In general, three
- l. 186: of *the* estimator
- l. 226: wi*n*dow
- l. 227: without contamination

Overall, 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.

[1] "Sub-gaussian mean estimators" Devroye et al. 2016

[2] "Loss minimization and parameter estimation with heavy tails" Hsu and Sabato 2016

[3] "Robust classification via MOM minimization" Lecué et al.2020

[4] "Generalization Bounds in the Presence of Outliers: a Median-of-Means Study" Laforgue et al. 2021

**Post-rebuttal edit**

I 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Major comments:
1. 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.
2. 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?
3. 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.
4. 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.

Minor comments:
1. On line 43, "In generally" --> "In general".
2. 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$?
3. In Algorithm 1, "$j$ is a local maximizer" of what? $D_h(j)$?
limitations_and_societal_impact: See comments above for suggestions.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 
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. 

In 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. 

Another 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. 

General comments and questions:
•	What 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. 
•	What was a motivation for Hyber $\epsilon$ - contamination model?
•	In line 136, the authors claim the lower bound for $log(n)$. Where it comes from? Please, put some explanations or references. 

In general, the text of paper should be improved:
•	Lines and contaminated points are not visible in Figure 1;
•	Line 64. "[22] showed that their … "whom? 
•	It will be better not to start sentences with the reference, e.g. lines 74, 76, 77
•	Line 134. $d_H$ defined only in Appendix. 
•	Why there are URLs in the references? 

limitations_and_societal_impact: -
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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,

Quality: 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.

Clarity: The paper is very well-written and easy to understand.

Significance: 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.
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_title: null

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)