Locally Private Parametric Methods for Change-Point Detection

arXiv:2602.13619 · stat.ML, cs.IT, cs.LG, math.IT, stat.ME · Submitted 2026-02-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Locally Private Parametric Methods for Change-Point Detection".

Jane: The gist: The authors study parametric change-point detection under local differential privacy,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we’re looking at this paper titled "Locally Private Parametric Methods for Change-Point Detection." Basically, the main goal here is figuring out how to detect shifts in data sequences, like when something changes in a time series, while keeping that data private using local differential privacy.

Jane: That makes sense. The authors are looking at parametric change-point detection under local differential privacy and they're trying to give us better ways to do it than what's currently out there for the non-private case.

Lu: They tackle this in two main parts, first deriving improved finite-sample accuracy guarantees for a change-point detection algorithm using martingale methods in the non-private setting. Then, they propose two locally differentially private algorithms based on randomized response and binary mechanisms to analyze their performance theoretically.

Meng: So it’s not just about doing the detection privately; it’s about quantifying exactly how much privacy hurts your accuracy, which is a crucial thing for real applications where data sensitivity matters.

Lalam: I think the paper claims they establish finite-sample minimax lower bounds in both the non-private and locally private settings, showing that localization accuracy is fundamentally limited by the Chernoff information between those pre- and post-change distributions.

Tom: That sounds pretty fundamental, Jane; they're saying there’s a hard limit on how accurate we can get based on the difference between the two data states.

Jane: And then they use that to guide their design of these private algorithms, proposing mechanisms that try to maximize the Chernoff information between those induced output distributions in low and high privacy regimes.

Lu: They also tackle a structural result for strong data processing inequalities, which is pretty interesting because they prove that the coefficients for Renyi divergences and Jeffreys–Renyi divergences are actually achieved by binary input distributions.

Meng: Wait, they’re saying we only need to worry about distributions supported on at most two atoms when calculating these divergence coefficients? That would simplify things a lot in practice.

Lalam: Exactly; they show that computing the SDPI coefficient can be restricted to binary input distributions, and for a q-ary symmetric channel, the coefficient for Renyi divergence of order infinity is v minus u max

u, v: .

Tom: So what this means practically is that we don't need to analyze super complex data distributions if we can restrict our thinking to something with just two possible outcomes.

Jane: It also gives them a way to characterize the cost of privacy through these strong data processing inequalities, which links the theoretical bounds directly to how much privacy degrades performance relative to a non-private benchmark.

Lu: In the private setting, they show that Algorithm two based on randomized response outperforms Algorithm three based on binary mechanisms in the high-privacy regime where epsilon is small.

Meng: So for someone trying to keep their data super safe, using those binary mechanisms gives them a better result than just using randomized response when epsilon is tiny.

Paper summary: Lalam: And conversely, the converse holds in the low-privacy regime where epsilon is large. This suggests that the choice of privacy mechanism matters depending on how much privacy you need to guarantee.

Tom: The paper shows that imposing an epsilon local differential privacy constraint actually attenuates the exponential error rate by a factor of approximately tanh squared of epsilon over two relative to the non-private exponent.

Jane: That's a concrete way they quantify the statistical cost of adding that privacy layer, showing how much performance you lose based on your chosen level of privacy.

Lu: The empirical error exponents for Algorithm three scale approximately as tanh to the fourth power of epsilon over two times the order infinity Jeffreys–Renyi divergence between pre- and post-change distributions <ref:2602.13619#pg3,pre- and post-change distributions>.

Meng: So if we want a certain accuracy, we can calculate how much privacy we have to give up by looking at that tanh expression.

Lalam: They validate all this theoretical work through Monte Carlo simulations on synthetic data, which confirms these scaling behaviors in the real world context they modeled.

Tom: The paper "Locally Private Parametric Methods for Change-Point Detection" shows us how to get better accuracy guarantees in private change-point detection by using randomized response and binary mechanisms, while also giving a mathematical framework to measure the cost of that privacy.

Jane: The authors are giving us tools to understand how much performance we sacrifice when we try to keep our data private from local adversaries.

Lu: They prove that the statistical limits are set by the Chernoff information between the distributions and that these bounds hold even for general alphabets, which is pretty broad.

Meng: From an engineering standpoint, knowing exactly how privacy impacts the error exponent helps us design systems where we can trade off accuracy for security in a predictable way.

Lalam: And they also provide novel characterizations of strong data processing inequality coefficients for Renyi divergences and Jeffreys–Renyi divergences of order infinity, showing that these are achieved by binary input distributions.

Tom: So, to wrap up on this paper "Locally Private Parametric Methods for Change-Point Detection," the core idea is using these new mechanisms and bounds to understand the trade-off between privacy constraints and change-point detection accuracy.

Jane: It really highlights how the level of local differential privacy you choose directly impacts your achievable performance, quantified by those tanh terms in their error exponents.

Lu: The structural result about binary input distributions simplifying the calculation of those divergence coefficients is a neat mathematical finding that connects data structure to privacy analysis.

Meng: For practical deployment, it means we can estimate the security cost before we even start running a detection model, which is pretty useful for system design.

Lalam: So, this work gives us a more complete picture of the statistical limitations when applying local differential privacy to detecting changes in data sequences.

Conclusion: Tom: So we’ve been looking at this paper, "Locally Private Parametric Methods for Change-Point Detection." It’s about taking change-point detection—finding when something shifts in a data stream—and doing it while keeping that data private using local differential privacy.

Jane: Yeah, and what they really focus on is giving us concrete ways to do that privately. They aren't just throwing privacy constraints at a problem; they’re building actual algorithms based on randomized response and binary mechanisms.

Lu: The real insight here is how the authors use these tools to set bounds. They show that localization accuracy is fundamentally limited by the Chernoff information between those two data states, no matter what kind of alphabet you're using.

Meng: That means even with privacy, there’s a hard statistical limit dictated by how different the two data distributions really are. It’s not just about adding noise; it’s about understanding the inherent difficulty of spotting a change.

Lalam: And they characterize how that privacy budget actually eats into your accuracy through these strong data processing inequalities, showing that the error exponent gets reduced by a factor related to epsilon squared.

Tom: So what does this mean for us right now? It tells us exactly what you can expect in terms of performance versus security when you try to find those critical shifts in data.

Jane: It gives engineers a roadmap for designing private systems, showing them the trade-off curve between how much privacy they need and how accurate their detection can actually be.

Lu: And that structural result about binary input distributions for the divergence coefficients is pretty neat—it simplifies the math needed to calculate those limits significantly.

Meng: For me, it’s useful because it grounds these abstract bounds in something more practical. It means we can start estimating the security cost before we even build the whole detection model.

Lalam: And for culture, this work helps us build better trust in AI systems by giving us a mathematical way to quantify exactly what privacy constraints actually mean for system reliability.

Tom: Right, so it boils down to understanding that every privacy choice has a measurable statistical price tag on your detection performance. Next up, we’re looking at how these new algorithms perform when you actually run them on real data sets.

School of Computer and Communication Sciences, Ecole Polytechnique Fédérale de Lausanne (EPFL)

stat.ML, cs.IT, cs.LG, math.IT, stat.ME

Submitted: 2026-02-14

Updated: 2026-10-09

Comments: 60 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist: The authors study parametric change-point detection under local differential privacy, proposing two algorithms based on randomized response and binary mechanisms and deriving performance

Key concepts

Chernoff Information
This measures the statistical distinguishability between two probability distributions, specifically the pre-change and post-change distributions. It is a fundamental quantity that dictates how quickly an estimator can converge to the correct answer when comparing these two states.
Strong Data Processing Inequality (SDPI) Coefficients
These coefficients relate how much information is lost when transforming data distributions, particularly concerning Renyi and Jeffreys–Renyi divergences. The paper shows these coefficients are easiest to compute when dealing with input distributions that only have at most two distinct symbols.
Local Differential Privacy (LDP)
LDP ensures that the output of an algorithm reveals little information about any single individual's data point. In this context, it means adding noise or using mechanisms like randomized response to ensure the change-point detection process does not leak sensitive information about the observations.
Cost of Privacy
This refers to the statistical penalty incurred when applying a privacy constraint, such as LDP. The analysis shows that for this change-point detection task, this cost attenuates the error exponent by a factor of approximately tanh^2(epsilon/2), meaning privacy limits how accurately the change point can be found.

Terminology

Summary

The gist: The authors study parametric change-point detection under local differential privacy, proposing two algorithms based on randomized response and binary mechanisms and deriving performance bounds using strong data processing inequalities.

Non-Private Change-Point Detection

The non-private setting involves deriving improved finite-sample accuracy guarantees for a change-point detection algorithm based on the generalized log-likelihood ratio test via martingale methods. The analysis establishes two accuracy bounds (Theorem 3.1), one decaying exponentially at a rate determined by the ratio of the KL divergence to the order-∞ Jeffreys–Renyi divergence between pre- and post-change distributions, and another decaying exponentially at a rate determined by the Chernoff information. The bound B is characterized by the Chernoff information, which holds for general (including continuous) alphabets.

Characterization of SDPI coefficients

The authors present novel characterizations of strong data processing inequality (SDPI) coefficients for Renyi divergences of any order ρ ∈ [1,∞] and Jeffreys–Renyi divergences of order ρ = ∞. They show that the SDPI coefficients are achieved by input distributions supported on at most two atoms, implying that computing the SDPI coefficient can be restricted to binary input distributions. For a q-ary symmetric channel, the SDPI coefficient for Renyi divergence of order infinity is η∞(W) = v − u max[u, v]. Similarly, for Jeffreys–Renyi divergence of order ∞, the coefficient is ηJ∞(W) = v − u v + u.

LDP-based CPD algorithms

In the privacy-preserving setting, two change-point detection algorithms are proposed based on randomized response and binary mechanisms. Using the characterization of SDPI coefficients, finite-sample accuracy bounds are derived for both private CPD algorithms. The analysis shows that the algorithm based on binary mechanisms outperforms the algorithm based on randomized response in the high-privacy (small ε) regime, while the converse holds in the low-privacy (large ε) regime.

Cost of privacy

The effect of imposing an ε-LDP constraint enters the theoretical guarantees through the contraction of the effective separation between pre- and post-change distributions. In Algorithms 2 and 3, the exponents in error bounds involve multiplicative factors of the form tanh 2(ε/2). The empirical error-exponents for Algorithm 3 scale approximately as our theoretically computed cost of tanh 4(ε/2) · tanh 2(ε/2) · (D(P0, P1)) = tanh 4(ε/2) · (D(P0, P1)). Consequently, the private error exponent is attenuated by a factor on the order of tanh 2(ε/2) in the privacy parameter ε, relative to the corresponding non-private exponent.

Experimental Results

The empirical error exponents for Algorithm 3 scale approximately as tanh 4(ε/2) · (D(P0, P1)). This characterization via our upper bound correctly captures the limiting regimes: as ε → 0, tanh 2(ε/2) → 0 and the exponent vanishes, yielding a trivial (near-constant) error bound; as ε → ∞, tanh 2(ε/2) → 1 and the exponent approaches its non-private counterpart.

Conclusion

The authors study parametric offline change-point detection in the non-Bayesian framework and propose two locally private algorithms based on randomized response and binary mechanisms. Leveraging SDPI coefficients for Jeffreys–Renyi divergences, they establish performance bounds for both algorithms and characterize the cost of privacy. Their analysis shows that the two mechanisms exhibit complementary behavior across privacy regimes, and that the ε-LDP constraint reduces the exponential error rate by a factor of approximately tanh 2(ε/2). Finally, they validate their theoretical findings via Monte Carlo simulations on synthetic data.

How it works

The non-private CPD estimator in Algorithm 1 is based on the Generalized Log-likelihood Ratio Test (GLRT). The sensitivity s of the GLRT statistic w.r.t P0 and P1 is given by s:= max x∈X log P1(x)/P0(x) - min x∈X log P1(x)/P0(x) = D∞(P1∥P0) + D∞(P0∥P1) = DJ∞(P0, P1). The finite-sample accuracy bound in Theorem 3.1 is given by β ≤ 2 min (i X∗i=1 exp −2i−1αC 2/s squared; exp (−αIch(P0, P1))).

LDP-based CPD algorithms

Algorithm 5.6 provides an upper bound on the error probability of Algorithm 2, which is ε− locally differentially private as well as (α, βr)−accurate. The bound in Theorem 5.6 can be further upper bounded to have a closed form expression as follows βr ≤ 2 min (tr(1 − tM r) / 1 − tr; exp (−αIch(Q0, Q1))). The analysis shows that the algorithm based on binary mechanisms outperforms the algorithm based on randomized response in the high-privacy regime (small ε), while the converse holds in the low-privacy (large ε) regime.

Cost of privacy

The cost of privacy is quantified by comparing empirical error exponents for Algorithm 2 and Algorithm 3 with our theoretical generic privacy cost, for a fixed α = 50. We observe that the empirical error-exponents for Alg. 2 and Alg. 3 scale approximately as our theoretically computed cost of tanh 4(ε/2) · tanh 2(ε/2) · (D(P0, P1)) = tanh 4(ε/2) · (D(P0, P1)).

Comparison of Empirical Performances of Algorithm 2 and Algorithm 3

Figure 15 compares the empirical error probabilities as functions of privacy parameter ε, for truncated geometric distributions TGeom(p, m) with truncation parameter m = 10. The empirical results show that Algorithm 2 and Algorithm 3 exhibit similar performance over binary alphabets.

Cost of privacy

The cost of privacy is quantified by comparing empirical error exponents for Algorithm 2 and Algorithm 3 with our theoretical generic privacy cost, for a fixed α = 50. The empirical error-exponents for Alg. 2 and Alg. 3 scale approximately as tanh 4(ε/2) · tanh 2(ε/2) · (D(P0, P1)). The private error exponent is attenuated by a factor on the order of tanh 2(ε/2) in the privacy parameter ε, relative to the corresponding non-private exponent.

Cost of privacy

The cost of privacy is quantified by comparing empirical error exponents for Algorithm 3 with our theoretical generic privacy cost, for a fixed α = 50. The empirical error-exponents for Alg. 3 scale approximately as tanh 4(ε/2) · tanh 2(ε/2) · (D(P0, P1)).

Improvements for AI systems

  1. Identification of Distributional Shifts in Health Data: The improved system can detect disease outbreaks by tracking hospital admissions and identifying statistically significant changes in incidence, utilizing a change-point detection algorithm based on the generalized log-likelihood ratio test (GLRT) for offline data analysis.

  2. Privacy-Preserving Change-Point Detection with Algorithmic Selection: The system can implement two distinct locally differentially private algorithms—the randomized response mechanism and the binary mechanisms—and automatically select the mechanism that maximizes Chernoff information, as indicated by Theorem 5.3 and Corollary 5.4.

  3. Quantification of Privacy-Utility Trade-off: The system can explicitly quantify the statistical cost of local differential privacy, showing how privacy degrades performance relative to a non-private benchmark by measuring the empirical error exponent ratio, which is characterized as approximately tanh2(ε/2) in the common regime.

  4. Optimized Quantization for Binary Data Processing: For data requiring binary processing, the system can dynamically select a quantization parameter τ that maximizes the Chernoff information between the Bernoulli distributions (Qτ0, Qτ1) induced by the binary mechanism after privatization, as described in Algorithm 3 and Remark 5.9.

Abstract

We study parametric change-point detection under local differential privacy, focusing on the offline localization of a single change point in a sequence of independent observations. In the non-private setting, we derive improved finite-sample accuracy guarantees for a generalized likelihood-ratio estimator using martingale methods. We establish finite-sample minimax lower bounds in both the non-private and locally private settings, showing that localization accuracy is fundamentally limited by the Chernoff information between the pre- and post-change distributions. Guided by this, we design locally private CPD algorithms based on aggregated randomized response and binary mechanisms, which maximize the Chernoff information between the induced output distributions in low- and high-privacy regimes, respectively, and derive their finite-sample guarantees. Together, our upper and lower bounds quantify the statistical cost of privacy in change-point localization. As part of our analysis, we also show that strong data processing inequality coefficients of Rényi divergence and Jeffreys--Rényi divergence of order infinity can be computed by restricting to pairs of input distributions with a common support of at most two symbols. We corroborate our results through empirical evaluation on synthetic data.

Related papers