Sequential Change Detection with Differential Privacy
Liyan Xie, Ruizhi Zhang · 2025
Read Sequential Change Detection with Differential Privacy by Liyan Xie, Ruizhi Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02768.txt.
Introduction
Liyan Xie and Ruizhi Zhang present a 2025 statistics paper adding privacy to sequential change detection, the task of spotting a distribution shift as data streams in. The classic CUSUM procedure is optimal in a precise sense, but publishing its statistics can leak individual data points.
Their DP-CUSUM variant adds calibrated Laplace noise both to the running statistic and to its alarm threshold, giving per-sample differential privacy while keeping the simple recursive update. The authors derive closed-form bounds on false alarm run length and worst-case detection delay, spelling out the trade-off among privacy, false alarms, and speed. Under weak privacy demands, the method matches the classical procedure's first-order optimality. Simulations across privacy levels agree with the theory.
Catalog record
| CREATOR | Liyan Xie, Ruizhi Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-02768
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sequential Change Detection with Differential Privacy Liyan Xie, Ruizhi Zhang Abstract Sequential change detection is a fundamental problem in statistics and signal processing, with the CUSUM procedure widely used to achieve minimax detection delay under a prescribed false-alarm rate when pre- and post-change distributions are fully known. However, releasing CUSUM statistics and the corresponding stopping time directly can compromise individual data privacy. We therefore introduce a differentially private (DP) variant, called DP-CUSUM, that injects calibrated Laplace noise into both the vanilla CUSUM statistics and the detection threshold, preserving the recursive simplicity of the classical CUSUM statistics while ensuring per-sample differential privacy. We derive closed-form bounds on the average run length to false alarm and on the worst-case average detection delay, explicitly characterizing the trade-off among privacy level, false-alarm rate, and detection efficiency. Our theoretical results imply that under a weak privacy constraint, our proposed DP-CUSUM procedure achieves the same first-order asymptotic optimality as the classical, non-private CUSUM procedure. Numerical simulations are conducted to demonstrate the detection efficiency of our proposed DP-CUSUM under different privacy constraints, and the results are consistent with our theoretical findings. I Introduction Sequential change detection is a fundamental problem in statistics and signal processing, with applications across a wide range of practical domains. The canonical formulation considers a sequence of observations sampled independently, with an unknown changepoint at which the underlying distribution switches from one distribution to an alternative. The goal of sequential change detection is to detect the occurrence of the distributional change with a minimal delay while controlling the false alarm rate. This problem is of major importance in many applications, such as seismic event detection [ 1 ] , quality control [ 2 ] , dynamical systems [ 3 ] , healthcare [ 4 ] , social networks [ 5 ] , anomaly detection [ 6 ] , detection of attacks [ 7 ] , etc. However, in many of these applications, the data may contain sensitive personal information such as financial or medical records [ 8 ] , while traditional sequential detection procedures typically release the decision directly without appropriate privacy protection. Thus, procedures with good detection ability while preserving individual’s information are highly desirable. Since Dwork et al .’s pioneering work [ 9 ] , differential privacy has garnered much attention. A wide variety of differentially private procedures with theoretical efficiency guarantees have been developed for many statistical problems such as point estimation [ 8 , 10 ] and hypothesis testing [ 11 , 12 , 13 ] . Informally, the field of differential privacy provides a systematic tool for constructing private algorithms or procedures by adding designed random noise, such that the output has a similar distribution whether or not the data is present for each individual participant, thereby helping to protect the information of individuals in the dataset. In this article, we study the problem of differentially private sequential change detection when both pre-change and post-change distributions are known and specified. We first extend the classical notion of \epsilon -differential privacy [ 9 ] for fixed databases to sequential change detection tasks over potentially infinite data streams, where the sample size is not fixed. We then develop a differentially private (DP) variant of the CUSUM procedure, called DP-CUSUM , which satisfies the new \epsilon -DP constraint. Our proposed DP-CUSUM procedure involves computing the CUSUM statistics while adding an independent Laplace noise at each time step, as well as to the detection threshold. By doing this, we do not release the CUSUM statistics or the threshold directly during the detection procedure. Meanwhile, the DP-CUSUM retains the same computational efficiency as the classical CUSUM procedure, as its computational overhead is minimal when noise is added at each time step. Our main contributions can be summarized as follows. First, we introduce a new concept of \epsilon -DP for sequential detection procedures when the sample size is not fixed. Second, we construct DP-CUSUM procedure that satisfies the new \epsilon -DP constraint. Third, under the assumption that the log-likelihood ratio statistic is always bounded by a known constant, we prove a lower bound to the average run length (ARL) of DP-CUSUM which enables an analytical way of selecting the detection threshold, and an upper bound to Lorden’s worst-case detection delay (WADD) [ 14 ] , which thus proves its asymptotic optimality under weak privacy constraints. Fourth, we extend our results to scenarios with general unbounded log-likelihood ratios by relaxing to a slightly weaker differential-privacy definition with an added small constant \delta in the DP definition. Finally, we validate our theoretical findings through numerical simulations, illustrating how the choice of privacy parameter affects the delay-versus-false-alarm trade-off in practical settings. The remainder of this paper is organized as follows. Section II provides preliminaries about sequential change detection when both pre-change and post-change distributions are fully specified, and introduces the modified concept of \epsilon -DP for sequential detection procedures. Section III presents our proposed DP-CUSUM detection procedure and the theoretical analysis when the log-likelihood function is bounded. Section IV extends the method and theory to the general case with unbounded log-likelihood ratios. Finally, Section V presents simulation examples that demonstrate the performance of the proposed DP-CUSUM procedure under distributions with both bounded and unbounded log-likelihood ratios. All proofs are presented in the Appendix. I-A Related Work The study of sequential change detection can be traced back to the early work of Page [ 15 ] and has been studied extensively for several decades. Most works address the detection problem under the assumption of independent observations, particularly when new methods and theories are first introduced, but significant progress has also been made in extending these methods and theories to more complicated data models; see [ 16 , 17 , 18 , 19 , 20 , 21 , 22 ] for thorough reviews in this field. The first optimality result for sequential change detection appears in [ 23 ] , with a focus on detecting a change in the drift of a Brownian motion. It was studied under a Bayesian framework, where the changepoint was modeled as an independent, exponentially distributed random variable. In contrast, the non‑Bayesian (minimax) setting considers the changepoint to be deterministic but unknown. Under the minimax setting, the CUSUM procedure is arguably the most widely adopted change detection algorithm for the classical setup of detecting a change from a known distribution to a known alternative [ 15 ] . The CUSUM procedure was first proved to be asymptotically optimum in [ 14 ] when observations are i.i.d. before and after the change. Its exact optimality under the same data model was established in [ 24 ] . In addition to its strong optimality guarantees, the CUSUM statistic admits a recursive update, making it computationally efficient for sequential settings that require processing each new sample immediately. Although the problem of change detection when both pre-change and post-change distributions are known is fully studied in literature, these procedures do not consider the data privacy-preserving guarantees. First introduced by Dwork et al. [ 9 ] , differential privacy has garnered much attention. Many classical statistical procedures are tailored to satisfy the privacy guarantees [ 8 , 10 , 11 , 12 , 13 ] . In particular, in