arxiv: 2604.13274 · v1 · submitted 2026-04-14 · 🧮 math.ST · cs.CR· stat.TH

Sequential Change Detection for Multiple Data Streams with Differential Privacy

Lixing Zhang , Liyan Xie , Ruizhi Zhang This is my paper

Pith reviewed 2026-05-10 13:24 UTC · model grok-4.3

classification 🧮 math.ST cs.CRstat.TH

keywords differential privacychange point detectionCUSUMmultiple streamssequential detectionLaplace mechanismaverage run lengthdetection delay

0 comments

The pith

DP-SUM-CUSUM detects synchronized changes in multiple streams while satisfying sequential ε-differential privacy and bounding false-alarm and detection-delay performance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a differentially private procedure for sequential change-point detection across several independent data streams that sums the CUSUM statistics from each stream and adds Laplace noise scaled to meet a given privacy level ε. The authors prove that this construction satisfies sequential differential privacy and derive explicit bounds on the average run length until a false alarm and on the worst-case average delay until a true change is detected, making the privacy-efficiency tradeoff concrete. A truncation step extends the method to cases where log-likelihood ratios can be arbitrarily large. This matters for applications such as monitoring IoT devices or networks where both rapid detection and data privacy are required.

Core claim

DP-SUM-CUSUM is a detection procedure based on the summation of per-stream CUSUM statistics with calibrated Laplace noise injection. It satisfies sequential ε-differential privacy. Bounds are derived on the average run length to false alarm and the worst-case average detection delay, explicitly characterizing the privacy--efficiency tradeoff. A truncation-based extension handles distributional shifts with unbounded log-likelihood ratios.

What carries the argument

DP-SUM-CUSUM, the summation of per-stream CUSUM statistics with calibrated Laplace noise injection

Load-bearing premise

The multiple data streams are independent, experience a synchronized change at an unknown time in an unknown subset, and have bounded log-likelihood ratios.

What would settle it

An experiment that measures the actual average detection delay for a specific distribution and ε value and checks whether it exceeds the paper's derived upper bound.

Figures

Figures reproduced from arXiv: 2604.13274 by Lixing Zhang, Liyan Xie, Ruizhi Zhang.

read the original abstract

Sequential change-point detection seeks to rapidly identify distributional changes in streaming data while controlling false alarms. Existing multi-stream detection methods typically rely on non-private access to raw observations or intermediate statistics, limiting their usage in privacy-sensitive settings. We study sequential change-point detection for multiple data streams under differential privacy constraints. We consider multiple independent streams undergoing a synchronized change at an unknown time and in an unknown subset of streams, and propose DP-SUM-CUSUM, a differentially private detection procedure based on the summation of per-stream CUSUM statistics with calibrated Laplace noise injection. We show that DP-SUM-CUSUM satisfies sequential $\varepsilon$-differential privacy and derive bounds on the average run length to false alarm and the worst-case average detection delay, explicitly characterizing the privacy--efficiency tradeoff. A truncation-based extension is also presented to handle distributional shifts with unbounded log-likelihood ratios. Simulations and experiments on an Internet of Things (IoT) botnet dataset validate the proposed approach.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper adds Laplace noise to the summed per-stream CUSUMs to get sequential ε-DP while keeping the standard drift analysis intact for synchronized multi-stream changes.

read the letter

The core contribution is a direct DP version of the SUM-CUSUM detector. They inject calibrated Laplace noise into the sum of individual CUSUM statistics at each step, prove that the whole procedure meets sequential ε-differential privacy via the Laplace mechanism, and then adjust the usual ARL and worst-case delay bounds to account for the added zero-mean noise. The truncation extension for unbounded log-likelihood ratios is handled separately and does not change the main argument. That construction is clean and the performance tradeoff is stated explicitly, which is useful for applications where you cannot release raw statistics.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces DP-SUM-CUSUM, a differentially private procedure for sequential change-point detection across multiple independent data streams that experience a synchronized distributional change at an unknown time in an unknown subset of streams. Per-stream CUSUM statistics are summed and perturbed by Laplace noise scaled to the bounded sensitivity of the sum, yielding sequential ε-differential privacy. Closed-form or explicit bounds are derived on the average run length to false alarm and the worst-case average detection delay, explicitly quantifying the privacy-efficiency tradeoff. A separate truncation extension is provided to accommodate unbounded log-likelihood ratios. The theoretical results are illustrated with simulations and experiments on an IoT botnet dataset.

Significance. If the derivations hold, the paper supplies the first explicit privacy-preserving multi-stream CUSUM with provable ARL and delay bounds, directly characterizing the cost of privacy via the noise scale. The summation construction elegantly sidesteps the need to identify the unknown changing subset while preserving the sign of the post-change drift. The combination of a clean Laplace-mechanism argument, adjusted drift analysis, and empirical validation on real data makes the contribution self-contained and practically relevant for privacy-sensitive streaming applications.

minor comments (3)

[Abstract] Abstract: the phrase 'explicitly characterizing the privacy--efficiency tradeoff' would be strengthened by a one-sentence indication of whether the ARL and delay bounds are closed-form expressions in ε or asymptotic statements.
[§5] §5 (Performance Bounds): the adjustment of the standard CUSUM drift analysis for zero-mean Laplace noise is central; a short remark comparing the resulting bound constants with the non-private case would clarify the precise efficiency loss.
[Simulations] Simulation section: the IoT botnet experiments should report the specific values of ε, the per-stream log-likelihood ratio bounds, and the truncation threshold used, to allow exact reproduction of the reported ARL and delay curves.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper constructs DP-SUM-CUSUM by summing per-stream CUSUM statistics and adding Laplace noise scaled to the bounded sensitivity of this sum at each step. Sequential ε-DP follows directly from the standard Laplace mechanism for sensitivity-bounded adaptive queries. The ARL-to-false-alarm and worst-case detection-delay bounds are obtained by extending the classical CUSUM drift analysis to account for the added zero-mean Laplace noise (which increases variance but leaves the sign of the post-change drift unchanged under the synchronized-change model). This is a direct probabilistic adjustment using standard tools, not a reduction to fitted parameters, self-referential definitions, or load-bearing self-citations. The truncation extension is presented separately for the unbounded-LLR case and does not affect the main claims. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only: the procedure relies on standard properties of CUSUM statistics and the Laplace mechanism for differential privacy; no new entities are postulated and no parameters appear to be fitted to data.

axioms (2)

domain assumption Streams are independent and experience a synchronized change in an unknown subset at an unknown time.
Stated in the problem setup of the abstract.
standard math The Laplace mechanism provides ε-differential privacy when noise scale is calibrated to the sensitivity of the summed CUSUM statistic.
Invoked to establish the privacy guarantee.

pith-pipeline@v0.9.0 · 5465 in / 1488 out tokens · 55532 ms · 2026-05-10T13:24:31.792692+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

46 extracted references · 1 canonical work pages

[1]

H. V . Poor and O. Hadjiliadis,Quickest Detection. Cambridge University Press, 2008

2008
[2]

Siegmund,Sequential Analysis: Tests and Confidence Intervals

D. Siegmund,Sequential Analysis: Tests and Confidence Intervals. Springer-Verlag, New York, 1985

1985
[3]

Tartakovsky, I

A. Tartakovsky, I. Nikiforov, and M. Basseville,Sequential analysis: Hypothesis testing and changepoint detection. CRC press, 2014

2014
[4]

Sequential analysis: Some classical problems and new challenges,

T. L. Lai, “Sequential analysis: Some classical problems and new challenges,”Statistica Sinica, vol. 11, no. 2, pp. 303–351, 2001

2001
[5]

Sequential (quickest) change detection: Classical results and new directions,

L. Xie, S. Zou, Y . Xie, and V . V . Veeravalli, “Sequential (quickest) change detection: Classical results and new directions,”IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 2, pp. 494–514, 2021

2021
[6]

Balageas, C.-P

D. Balageas, C.-P. Fritzen, and A. Güemes,Structural Health Monitor- ing. John Wiley & Sons, 2010, vol. 90

2010
[7]

The science of fake news,

D. M. Lazer, M. A. Baum, Y . Benkler, A. J. Berinsky, K. M. Greenhill, F. Menczer, M. J. Metzger, B. Nyhan, G. Pennycook, and D. Rothschild, “The science of fake news,”Science, vol. 359, no. 6380, pp. 1094–1096, 2018

2018
[8]

Detecting changes in dynamic events over networks,

S. Li, Y . Xie, M. Farajtabar, A. Verma, and L. Song, “Detecting changes in dynamic events over networks,”IEEE Transactions on Signal and Information Processing over Networks, vol. 3, no. 2, pp. 346–359, 2017

2017
[9]

Nearly optimal change-point detection with an application to cybersecurity,

A. S. Polunchenko, A. G. Tartakovsky, and N. Mukhopadhyay, “Nearly optimal change-point detection with an application to cybersecurity,” Sequential Analysis, vol. 31, no. 3, pp. 409–435, 2012

2012
[10]

Sequential multi-sensor change-point detec- tion,

Y . Xie and D. Siegmund, “Sequential multi-sensor change-point detec- tion,”Annals of Statistics, vol. 41, no. 2, pp. 670–692, 2013

2013
[11]

Large-scale multi-stream quickest change de- tection via shrinkage post-change estimation,

Y . Wang and Y . Mei, “Large-scale multi-stream quickest change de- tection via shrinkage post-change estimation,”IEEE Transactions on Information Theory, vol. 61, no. 12, pp. 6926–6938, 2015

2015
[12]

Scalable sum-shrinkage schemes for distributed monitoring large-scale data streams,

K. Liu, R. Zhang, and Y . Mei, “Scalable sum-shrinkage schemes for distributed monitoring large-scale data streams,”Statistica Sinica, vol. 29, no. 1, pp. 1–22, 2019

2019
[13]

Spectral CUSUM for online network structure change detection,

M. Zhang, L. Xie, and Y . Xie, “Spectral CUSUM for online network structure change detection,”IEEE Transactions on Information Theory, vol. 69, no. 7, pp. 4691–4707, 2023

2023
[14]

High-dimensional, multiscale online changepoint detection,

Y . Chen, T. Wang, and R. J. Samworth, “High-dimensional, multiscale online changepoint detection,”Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, no. 1, pp. 234–266, 2022

2022
[15]

The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy,

T. T. Cai, Y . Wang, and L. Zhang, “The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy,”Annals of Statistics, vol. 49, no. 5, pp. 2825–2850, 2021

2021
[16]

Calibrating noise to sensitivity in private data analysis,

C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of cryptography conference. Springer, 2006, pp. 265–284

2006
[17]

Efficient scalable schemes for monitoring a large number of data streams,

Y . Mei, “Efficient scalable schemes for monitoring a large number of data streams,”Biometrika, vol. 97, no. 2, pp. 419–433, 04 2010

2010
[18]

An efficient online monitoring method for high-dimensional data streams,

C. Zou, Z. Wang, X. Zi, and W. Jiang, “An efficient online monitoring method for high-dimensional data streams,”Technometrics, vol. 57, no. 3, pp. 374–387, 2015

2015
[19]

Second-order asymptotic optimality in multisensor sequential change detection,

G. Fellouris and G. Sokolov, “Second-order asymptotic optimality in multisensor sequential change detection,”IEEE Transactions on Infor- mation Theory, vol. 62, no. 6, pp. 3662–3675, 2016

2016
[20]

Optimal sequential detection in multi-stream data,

H. P. Chan, “Optimal sequential detection in multi-stream data,”Annals of Statistics, vol. 45, no. 6, pp. 2736–2763, 2017

2017
[21]

Asymptotic statistical properties of communication-efficient quickest detection schemes in sensor networks,

R. Zhang and Y . Mei, “Asymptotic statistical properties of communication-efficient quickest detection schemes in sensor networks,” Sequential Analysis, vol. 37, pp. 375–396, 2018

2018
[22]

High-dimensional change-point detec- tion under sparse alternatives,

F. Enikeeva and Z. Harchaoui, “High-dimensional change-point detec- tion under sparse alternatives,”Annals of Statistics, vol. 47, no. 4, pp. 2051 – 2079, 2019

2051
[23]

Sketching for sequential change-point detection,

Y . Cao, A. Thompson, M. Wang, and Y . Xie, “Sketching for sequential change-point detection,”EURASIP Journal on Advances in Signal Processing, vol. 2019, no. 1, pp. 1–22, 2019

2019
[24]

Robust change detection for large-scale data streams,

R. Zhang, Y . Mei, and J. Shi, “Robust change detection for large-scale data streams,”Sequential Analysis, vol. 41, no. 1, pp. 1–19, 2022

2022
[25]

An adaptive approach for online monitoring of large-scale data streams,

S. Cao and R. Zhang, “An adaptive approach for online monitoring of large-scale data streams,”IISE Transactions, vol. 57, no. 2, pp. 119–130, 2025

2025
[26]

Subspace change-point detection: A new model and solution,

Y . Jiao, Y . Chen, and Y . Gu, “Subspace change-point detection: A new model and solution,”IEEE Journal of Selected Topics in Signal Processing, vol. 12, no. 6, pp. 1224–1239, 2018

2018
[27]

Multivariate statistical process control using LASSO,

C. Zou and P. Qiu, “Multivariate statistical process control using LASSO,”Journal of the American Statistical Association, vol. 104, no. 488, pp. 1586–1596, 2009

2009
[28]

Real-time monitoring of high- dimensional functional data streams via spatio-temporal smooth sparse decomposition,

H. Yan, K. Paynabar, and J. Shi, “Real-time monitoring of high- dimensional functional data streams via spatio-temporal smooth sparse decomposition,”Technometrics, vol. 60, no. 2, pp. 181–197, 2018

2018
[29]

Sequential change-point detection in high-dimensional Gaussian graphical models,

H. Keshavarz, G. Michailidis, and Y . Atchadé, “Sequential change-point detection in high-dimensional Gaussian graphical models,”Journal of Machine Learning Research, vol. 21, no. 1, pp. 3125–3181, 2020

2020
[30]

Big data? statistical process control can help!

P. Qiu, “Big data? statistical process control can help!”The American Statistician, vol. 74, no. 4, pp. 329–344, 2020

2020
[31]

Change detection in noisy dynamic networks: a spectral embedding approach,

I. U. Hewapathirana, D. Lee, E. Moltchanova, and J. McLeod, “Change detection in noisy dynamic networks: a spectral embedding approach,” Social Network Analysis and Mining, vol. 10, pp. 1–22, 2020

2020
[32]

Sequential subspace change point detection,

L. Xie, Y . Xie, and G. V . Moustakides, “Sequential subspace change point detection,”Sequential Analysis, vol. 39, no. 3, pp. 307–335, 2020

2020
[33]

Quickest detection of the change of community via stochastic block models,

F. Sha and R. Zhang, “Quickest detection of the change of community via stochastic block models,” in2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 1903–1908

2022
[34]

Monitoring network changes in social media,

C. Y .-H. Chen, Y . Okhrin, and T. Wang, “Monitoring network changes in social media,”Journal of Business & Economic Statistics, pp. 1–16, 2022

2022
[35]

Sequential change point detection in high dimensional time series,

J. Gösmann, C. Stoehr, J. Heiny, and H. Dette, “Sequential change point detection in high dimensional time series,”Electronic Journal of Statistics, vol. 16, no. 1, pp. 3608–3671, 2022

2022
[36]

Differen- tially private change-point detection,

R. Cummings, S. Krehbiel, Y . Mei, R. Tuo, and W. Zhang, “Differen- tially private change-point detection,”Advances in Neural Information Processing Systems (NeurIPS), vol. 31, 2018

2018
[37]

Privately detecting changes in unknown distributions,

R. Cummings, S. Krehbiel, Y . Lut, and W. Zhang, “Privately detecting changes in unknown distributions,” inProceedings of the International Conference on Machine Learning (ICML). PMLR, 2020, pp. 2227– 2237

2020
[38]

Differentially private online community detection for censored block models: Algorithms and fundamental limits,

M. Seif, L. Xie, A. J. Goldsmith, and H. V . Poor, “Differentially private online community detection for censored block models: Algorithms and fundamental limits,”IEEE Transactions on Information Forensics and Security, vol. 20, pp. 8312–8326, 2025

2025
[39]

Locally private online change point detection,

T. Berrett and Y . Yu, “Locally private online change point detection,” Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 3425–3437, 2021

2021
[40]

Sequential change detection with local differential privacy,

L. Zhang, X. Liu, R. Zhang, and L. Xie, “Sequential change detection with local differential privacy,”Entropy, vol. 28, no. 4, 2026

2026
[41]

Locally pri- vate parametric methods for change-point detection,

A. K. Yadav, C. Cadir, Y . Shkel, and M. Gastpar, “Locally pri- vate parametric methods for change-point detection,”arXiv preprint arXiv:2602.13619, 2026

work page arXiv 2026
[42]

Online privacy- preserving data-driven network anomaly detection,

M. N. Kurt, Y . Yılmaz, X. Wang, and P. J. Mosterman, “Online privacy- preserving data-driven network anomaly detection,”IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, pp. 982–998, 2022

2022
[43]

Sequential change detection with differential privacy,

L. Xie and R. Zhang, “Sequential change detection with differential privacy,”IEEE Transactions on Information Theory, 2025, in press

2025
[44]

Procedures for reacting to a change in distribution,

G. Lorden, “Procedures for reacting to a change in distribution,”Annals of Mathematical Statistics, vol. 42, no. 6, pp. 1897–1908, 1971

1908
[45]

Continuous inspection schemes,

E. S. Page, “Continuous inspection schemes,”Biometrika, vol. 41, no. 1/2, pp. 100–115, 1954

1954
[46]

N-baiot—network-based detection of iot botnet attacks using deep autoencoders,

Y . Meidan, M. Bohadana, Y . Mathov, Y . Mirsky, A. Shabtai, D. Breiten- bacher, and Y . Elovici, “N-baiot—network-based detection of iot botnet attacks using deep autoencoders,”IEEE Pervasive Computing, vol. 17, no. 3, pp. 12–22, 2018

2018