Locally Private Parametric Methods for Change-Point Detection
Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar · 2026
Read Locally Private Parametric Methods for Change-Point Detection by Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar (2026) 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-2602-13619.txt.
Introduction
Finding when a data sequence changes is a core task, and privacy rules complicate it: local differential privacy means each observation is privatized before analysis. This paper studies offline pinpointing of a single change point among independent observations under that constraint. In the non-private setting, improved finite-sample accuracy bounds are derived for a generalized likelihood-ratio estimator using martingale methods.
Minimax lower bounds in both private and non-private settings show pinpointing accuracy is capped by Chernoff information between pre- and post-change distributions. Private algorithms based on pooled randomized response and binary tools push that information up in low- and high-privacy regimes. That measures the statistical cost of privacy, with tests on made-up data backing the theory. Anuj Kumar Yadav leads the work with three co-authors.
Catalog record
| CREATOR | Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 127 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-13619
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Locally Private Parametric Methods for Change-Point Detection Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar Abstract We study parametric change-point detection, where the goal is to identify distributional changes in time series, under local differential privacy. In the non-private setting, we derive improved finite-sample accuracy guarantees for a change-point detection algorithm based on the generalized log-likelihood ratio test, via martingale methods. In the private setting, we propose two locally differentially private algorithms based on randomized response and binary mechanisms, and analyze their theoretical performance. We derive bounds on detection accuracy and validate our results through empirical evaluation. Our results characterize the statistical cost of local differential privacy in change-point detection and show how privacy degrades performance relative to a non-private benchmark. As part of this analysis, we establish a structural result for strong data processing inequalities (SDPI), proving that SDPI coefficients for Rényi divergences and their symmetric variants (Jeffreys–Rényi divergences) are achieved by binary input distributions. These results on SDPI coefficients are also of independent interest, with applications to statistical estimation, data compression, and Markov chain mixing. 1 Introduction 1.1 Motivation Consider a scenario in which a city health office is responsible for the detection of disease outbreaks and the enforcement of appropriate public health measures. To accomplish this task, they rely on daily patient-admission records provided by a city-wide hospital network. The task is to detect an outbreak by tracking hospital admissions for designated symptoms and identifying statistically significant changes in incidence. This process of identifying distributional shifts in the underlying data is commonly referred to as Change-Point Detection (CPD). CPD has diverse applications in many areas including but not limited to health care ( 35 ) , finance ( 29 ) , climate and environmental systems ( 3 ) , monitoring in communication networks ( 17 ) and industrial fault detection ( 18 ) . In our example, the hospitals are required to share the relevant data with the city health office. However, the data may incorporate sensitive patient information. This motivates the use of privacy-preserving algorithms that enable data sharing with minimal loss in utility. Ideally, these algorithms provide formal guarantees under well-defined mathematical notions of privacy. Differential privacy (DP) is a widely adopted central notion of privacy. Standard DP assumes the presence of a trusted curator who has access to the raw data and applies a privacy-preserving algorithm before releasing the output. While this assumption is appropriate in some settings, it may be undesirable when the analyst responsible for producing or releasing the output cannot be completely trusted with sensitive data. Local differential privacy (LDP) strengthens the privacy guarantee by requiring each data owner to locally privatize their data prior to sharing, thereby protecting the data at the source and removing reliance on a trusted curator. Motivated by this stronger privacy model, we study change-point detection under LDP. 1.2 Related Work Change-point detection has been an important research problem in statistics going back to early works of ( 42 ) . Different algorithms ( 31 ; 38 ; 34 ) have been proposed in the literature to accurately estimate change-points under multiple frameworks. An early work introduced the cumulative sum (CUSUM) algorithm based on the generalized likelihood ratio test (GLRT) ( 31 ) . This algorithm has been employed in numerous studies within the non-Bayesian framework and has stood the test of time. The CUSUM algorithm was shown to be asymptotically optimal under Lorden’s criterion in ( 26 ) , while exact optimality was later established by ( 28 ) . Our approach is also inspired by the CUSUM algorithm. See ( 19 ; 41 ; 43 ) for more recent work on sequential CPD algorithms. Differential privacy is a well studied privacy notion ( 11 ; 12 ) . There is extensive work on differentially private estimation ( 50 ; 10 ; 48 ) , learning ( 1 ; 25 ) , and hypothesis testing ( 22 ; 6 ) . In this work, we are interested in a local variant of DP, namely local differential privacy (LDP) ( 2 ; 47 ) , to study change-point detection. Change-point detection under differential privacy was first studied in ( 9 ) (see also the extended work ( 49 ) ). The authors considered parametric CPD and employed the well known Laplace mechanism to design differentially private algorithms, deriving performance bounds. In the recent years, the problem of private change-point detection has attracted significant attention. In ( 23 ) , the authors used maximal leakage ( 21 ) as a privacy constraint to study CPD. ( 8 ) investigated differentially private CPD in the non-parametric setting, while ( 4 ) examined multivariate CPD under local differential privacy. This line of work was further extended to CPD over networks in ( 24 ) . ( 40 ) studied private community detection on graphs. More recently, a differentially private variant of the CUSUM algorithm was introduced in ( 44 ) . 1.3 Our Contributions We study parametric change-point detection in the offline setting under the non-Bayesian framework. We summarize our contributions below: • Non-private accuracy guarantees. We derive finite-sample performance bounds for an offline change point detection algorithm based on the generalized log-likelihood ratio test (GLRT). Using martingale concentration techniques, we establish two accuracy bounds (Theorem 3.1 ). The first bound shows that the error probability decays exponentially at a rate determined by the ratio of the KL divergence to the order- \infty Jeffreys–Rényi divergence between the pre- and post-change distributions. This exponent is the same as in the bound proved by ( 49 ) ; however our bound involves a tighter analysis and explicitly accounts for the size of dataset. The second bound decays exponentially at a rate determined by the Chernoff information. It holds for general (including continuous) alphabets. Both bounds significantly improve upon existing results in the literature. (Section 3 ) • Characterization of SDPI coefficients. We present novel characterizations of strong data processing inequality (SDPI) coefficients for Rényi divergences of any order \rho\in[1,\infty] and Jeffreys–Rényi divergences of order \rho=\infty . We show that the SDPI coefficients are achieved by input distributions supported on at most two atoms. This binary-support optimality implies that computing the SDPI coefficient can be restricted to binary input distributions, reducing the optimization from the full (|\mathcal{X}|-1) -dimensional simplex to a low-dimensional search over two-point mixtures. Leveraging this result, we explicitly characterize the SDPI coefficients for a class of symmetric channels. (Section 4 ) • LDP-based CPD algorithms. In the privacy-preserving setting, we propose two change-point detection algorithms based on randomized response and binary mechanisms. Using our characterization of SDPI coefficients, we derive finite-sample accuracy bounds for both private CPD algorithms. Our analysis shows that the algorithm based on binary mechanisms outperforms the algorithm based on randomized response in the high-privacy (small \varepsilon ) regime, while the converse holds in the low-privacy (large \varepsilon ) regime. (Section 5 ) • Empirical validation and cost of privacy. We run several Monte Carlo simulations on synthetic data to empirically validate our theoretical bounds in both non-private and private settings. Our results quantify the performance degradation of CPD algorithms under LDP. Specifically, the \varepsilon -LDP constraint reduces the exponential rate in the error probability