Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies online change point detection problems,  in particular multivariate nonparametric regression problems, under the LDP constraint. Change point detection problems are some of the well studied problems in statistics, and have been considered in the central model of DP.

main_review: In this problem (without the LDP constraint), the algorithm is presented with raw data of the form (X_i, Y_i), i \in [N], where X_i is multidimensional. It is assumed that regression functions remain the same until some "change point" t = \Delta. The goal of the algorithm is to detect this time step \Delta with the least delay, while making sure that probability that algorithm declares change point before the time step \Delta (false alarm) is minimized.
Under the assumption that the data set lies in a bounded set, the proposed algorithm simply adds Laplace noise and sends the noisy data. Then, on the server side,  upon getting the noisy data at time t, the algorithm checks if a change point has occurred by checking some cumulative statistic has exceeded pre-specified thresholds. This seems like a natural adaptation of the online change point detection algorithms to the LDP setting.  Both mechanisms on the server side and client side seem fairly standard.
The paper analyses this algorithm to show that it has no false alarms, and has nearly optimal detection delay. The paper also presents optimal rates and lower bounds on the problem without LDP constraints and bounds on the price of privacy. Overall these results are satisfactory.
While I support accepting this paper, I do feel that authors could have done a better job at explaining the ideas behinds their proofs, especially of the lowerbound, which seems to be the main contribution. It also helps if they highlight their innovations compared to the previous works. Finally, the authors state that study of  univariate version of this problem as one of their 3 main contributions, yet there is not much regarding this despite having an entire page left unused!
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyzes the online change point detection problem subject to local DP.  They claim to be the first to study this problem, which seems like a natural problem to solve, although the central DP setting has been studied before, as they point out.  The contributions of this work are not limited to privacy considerations by also giving minimax rate of detection delay.


main_review: 
The privacy mechanism is simply the Laplace mechanism and the sensitivity analysis is referred to in a previous work.  The online change point detection statistic has very high computation cost, as pointed out in previous work.  It would be helpful to express whether the assumptions in 3.1 are necessary for privacy, utility, or both.  Theorem 1 requires knowledge of the assumption parameters, in particular the clip M needs to be sufficiently large.  

The major contribution from this work, in my opinion, comes from the lower bound.  The privacy mechanism and the statistical method are all standard and the assumptions seem to help the utility analysis carry through.  However, it is interesting that with those same assumptions, there is a nearly matching lower bound.  I would have liked to have seen more explanation for the lower bound as that seems to me to be the main result.  Since there is almost a full page left that the authors could have used, they could have at least provided a proof sketch.  Furthermore, the locally private univariate mean change point detection problem was listed as a contribution but its entire discussion is left to the supplementary file.  Much of this should be brought to the main body.  

Minor comments:
- Cite this work for Apple’s local DP use: https://machinelearning.apple.com/research/learning-with-privacy-at-scale 
- Small nit,  given this is a DP paper, it would be better to use \epsilon as the privacy parameter, rather than \alpha and thus another variable for the random Laplace noise terms in line 99.  


#################
Update: I have read the author comments and will keep my score unchanged.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to detect the change in the regression function for multivariate sequential data, under the constraint of local differential privacy. Theoretical analysis on the information-theoretic lower bound to the detection delay is proved. And the detection statistic used in this paper is proved to be near-optimal since it matches the lower bound.
main_review: This paper uses a cusum-like detection statistic to detect the change in the regression function for privatised data. In detail, we do not have direct access to the true data but only the data transmitted through a locally differentially private channel. Then the regression function is estimated and used to compute the detection statistic. The detection statistic is not new but this paper provides theoretical analysis on the detection delay of the proposed detection statistic and also a matching theoretic lower bound, by using the tools in the paper "John C Duchi, Michael I Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation."

This paper is well-written and easy to follow. And the theoretical results are interesting contributions to the change detection community.
A few detailed comments: It would be interesting to provide the explicit form or the order of the constant C_\epsillon as it is closely related to the detection delay as shown in Theorems. Also, it would be interesting to provide some numerical examples for demonstration purposes.

limitations_and_societal_impact: Yes
review_title: null

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