📊 statistics

Locally Private Parametric Methods for Change-Point Detection

This paper investigates locally differentially private parametric change-point detection by deriving improved finite-sample guarantees for non-private algorithms, proposing and analyzing two private detection methods, and establishing a structural result showing that binary input distributions maximize Strong Data Processing Inequality coefficients for Rényi and Jeffreys-Rényi divergences.

Original authors: Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anuj Kumar Yadav, Cemre Cadir, Yanina Shkel, Michael Gastpar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a city health official trying to spot the moment a new virus starts spreading. You have a stream of daily hospital admission records. Most days, the numbers look normal (Distribution A). Suddenly, on a specific day, the numbers spike because an outbreak has begun (Distribution B). Your job is to pinpoint exactly when that switch happened. This is called Change-Point Detection.

However, there's a catch: the hospital records contain sensitive patient data. You can't just look at the raw names and medical histories; that would be a privacy nightmare. You need a way to analyze the data to find the outbreak without ever seeing the individual secrets. This is where Local Differential Privacy (LDP) comes in.

Here is a breakdown of what this paper does, using simple analogies.

1. The Problem: The "Noisy" Messenger

In a perfect world, you would get the raw data. But in the privacy world, every hospital sends you a "privatized" version of their data. Think of it like this:

The Hospital has a secret (e.g., "Patient X was admitted").
The Privacy Mechanism is a mischievous messenger who adds a little bit of "noise" or confusion before sending the message to you.
You receive the noisy message. You know it's probably about an admission, but you can't be 100% sure if it was that specific patient or just a random guess.

The paper asks: If the data is this noisy, can we still find the exact moment the outbreak started? And if so, how much does the noise slow us down?

2. The Non-Private Solution: The "Perfect Detective"

First, the authors looked at the problem without privacy. They used a classic statistical tool called the Generalized Log-Likelihood Ratio Test (GLRT).

Analogy: Imagine a detective walking through a timeline of events. They compare the "before" pattern to the "after" pattern. If the difference is big enough, they shout, "Found it!"
The Result: The authors proved mathematically that this detective is very efficient. They derived a new, sharper formula to predict exactly how likely the detective is to make a mistake. They found that the "speed" of detection depends on how different the "before" and "after" patterns are.

3. The Private Solution: The "Blurred Lens"

Now, they added the privacy filter (LDP). The data is now blurred.

The Challenge: The "messenger" (the privacy mechanism) distorts the signal. The detective now has to work with a blurry picture.
The Innovation: The authors didn't just guess; they invented two new strategies for the detective to use when the picture is blurry:
1. Randomized Response (The "Coin Flipper"): Imagine the hospital flips a coin. If it's heads, they tell the truth. If it's tails, they lie randomly. This protects privacy but adds noise.
2. Binary Mechanism (The "Sorter"): Imagine the hospital first sorts all patients into two big piles (e.g., "High Risk" vs. "Low Risk") and then flips a coin to decide what to report. This is smarter because it focuses the noise on the most important distinction.

4. The Secret Weapon: "Strong Data Processing Inequalities" (SDPI)

This is the most technical part, but here's the simple version:

The Concept: When you pass data through a noisy channel (like the privacy mechanism), information gets "lost" or "contracted." The paper asks: How much information is lost?
The Discovery: The authors proved a surprising mathematical rule: The worst-case information loss happens with the simplest possible data (just two options, like a coin flip).
Why it matters: Instead of trying to calculate the noise for every complex medical record, they realized they only needed to study simple "Yes/No" scenarios to understand the worst-case privacy cost. This made their math much cleaner and more powerful.

5. The Trade-Off: Privacy vs. Accuracy

The paper quantifies the "cost" of privacy.

The Finding: Privacy acts like a dimmer switch on your detective's flashlight.
- High Privacy (Strict rules, small $\epsilon$ ): The light is very dim. The detective moves slowly and makes more mistakes. The error rate drops very slowly.
- Low Privacy (Loose rules, large $\epsilon$ ): The light is brighter. The detective works almost as well as in the non-private world.
The Magic Number: They found that the "dimming" effect scales roughly with $\tanh^2(\epsilon/2)$ .
- Translation: If you want to keep privacy very high (small $\epsilon$ ), the accuracy drops by a factor of roughly $\epsilon^2$ . To get the same accuracy back, you might need four times as much data (or a much wider tolerance for error) just to compensate for the privacy filter.

6. The Verdict: Which Strategy Wins?

The authors tested both the "Coin Flipper" (Randomized Response) and the "Sorter" (Binary Mechanism).

In the "High Privacy" zone (Strict rules): The Binary Mechanism (The Sorter) wins. It's better at preserving the signal when the noise is heavy.
In the "Low Privacy" zone (Loose rules): The Randomized Response (The Coin Flipper) is actually slightly better or comparable.

Summary

This paper is like a manual for a detective who must solve a crime using only "blurred" evidence to protect the witnesses' identities.

They figured out exactly how much the blur slows down the investigation.
They proved that the worst-case blur happens with the simplest scenarios, making the math easier.
They showed that if you are very strict about privacy, you need a lot more data to get the same result.
They offered two different tools (algorithms) for the detective, showing that one is better when privacy is strict, and the other is fine when privacy is loose.

The Bottom Line: You can detect outbreaks and changes in data while protecting privacy, but you have to pay a "tax" in the form of needing more data or accepting a slightly wider margin of error. The paper tells you exactly how much that tax costs.

1. Problem Statement

The paper addresses the problem of Parametric Change-Point Detection (CPD) under the constraint of Local Differential Privacy (LDP).

Context: In a dataset $D = \{x_1, \dots, x_n\}$ , data points are initially drawn i.i.d. from a pre-change distribution $P_0$ . At an unknown time $k^*$ , the distribution shifts to a post-change distribution $P_1$ . The goal is to estimate $k^*$ .
Privacy Constraint: Unlike standard CPD where a trusted curator aggregates raw data, this setting assumes Local Differential Privacy (LDP). Each data owner must privatize their data point $x_i$ locally via a mechanism $W^\epsilon$ before sending it to the analyst. The analyst only observes the privatized dataset $\tilde{D}$ and the induced distributions $Q_0, Q_1$ .
Objective: To design algorithms that detect the change point with high accuracy while satisfying $\epsilon$ -LDP, and to theoretically characterize the "cost of privacy" on detection performance.

2. Methodology

A. Non-Private Baseline (GLRT)

The authors first establish improved finite-sample accuracy bounds for a non-private CPD algorithm based on the Generalized Log-Likelihood Ratio Test (GLRT) (inspired by the CUSUM algorithm).

Technique: They utilize martingale concentration inequalities (specifically Azuma-Hoeffding and Doob's maximal inequality) rather than standard Ottaviani's inequality used in prior work.
Result: They derive two distinct error probability bounds:
1. Bound A: Depends on the ratio of KL divergence to the order- $\infty$ Jeffreys-Rényi divergence.
2. Bound B: Depends on the Chernoff Information ( $I_{ch}$ ).
- Significance: These bounds are tighter than existing literature (e.g., Zhang et al., 2021) and hold for general alphabets (including continuous).

B. Strong Data Processing Inequalities (SDPI)

A core theoretical contribution is the characterization of SDPI coefficients for Rényi divergences and Jeffreys-Rényi divergences.

Key Structural Result: The authors prove that the SDPI coefficient for any order $\rho \in [1, \infty]$ (and specifically for Jeffreys-Rényi divergence of order $\infty$ ) is achieved by binary input distributions (distributions supported on at most two atoms).
Implication: This reduces the optimization problem from a high-dimensional simplex to a low-dimensional search over binary mixtures. They explicitly derive these coefficients for $q$ -ary symmetric channels.

C. Private Algorithms

Based on the SDPI analysis, the authors propose two LDP-based CPD algorithms:

Algorithm 2 (Randomized Response - RR): Directly privatizes the original alphabet using a $q$ -ary symmetric channel.
Algorithm 3 (Binary Mechanism - BM): First quantizes the data into two bins (based on a threshold $\tau$ $τ$ ) and then applies a binary randomized response mechanism.
- Optimization: The threshold $\tau$ is chosen to maximize the Chernoff information between the induced Bernoulli distributions.

3. Key Contributions

Improved Non-Private Bounds: Derivation of sharper finite-sample error bounds for GLRT-based CPD using martingale methods, valid for both discrete and continuous alphabets.
SDPI Characterization: Proof that SDPI coefficients for Rényi and Jeffreys-Rényi divergences are achieved by binary inputs. This allows for explicit calculation of privacy-induced information loss for symmetric channels.
LDP Algorithms & Analysis:
- Proposal of two specific LDP algorithms (RR and BM).
- Derivation of finite-sample accuracy bounds for both, linking performance directly to the SDPI coefficients derived in Section 4.
Privacy Cost Quantification:
- Identification of a regime-dependent optimal mechanism: Binary Mechanisms outperform Randomized Response in the high-privacy regime (small $\epsilon$ ), while Randomized Response is superior in the low-privacy regime (large $\epsilon$ ).
- Derivation of the asymptotic cost of privacy: The exponential decay rate of the error probability is attenuated by a factor of approximately $\tanh^2(\epsilon/2)$ .

4. Key Results

Error Bounds:
- For the private setting, the error probability $\beta$ decays exponentially. The rate is governed by the Chernoff information of the privatized distributions.
- The bounds explicitly show how the privacy parameter $\epsilon$ shrinks the effective separation between $P_0$ and $P_1$ .
Privacy Cost Scaling:
- The ratio of the private error exponent ( $\Lambda_p$ ) to the non-private error exponent ( $\Lambda_{np}$ ) scales as:
  $\frac{\Lambda_p}{\Lambda_{np}} \approx \tanh^2(\epsilon/2)$
- In the high-privacy regime ( $\epsilon \ll 1$ ), this scales as $\Theta(\epsilon^2)$ .
- Practical Implication: To maintain the same accuracy level under LDP, the tolerance level (allowable error margin $\alpha$ ) must be inflated by a factor of roughly $4/\epsilon^2$ .
Empirical Validation:
- Monte Carlo simulations on synthetic data (Bernoulli, Poisson, Geometric, Binomial) confirm the theoretical bounds.
- Experiments validate the crossover point where Binary Mechanisms outperform Randomized Response as $\epsilon$ decreases.

5. Significance

Theoretical Rigor: The paper bridges the gap between information theory (SDPI, Rényi divergences) and statistical detection (CPD), providing a rigorous framework for understanding how privacy constraints degrade detection performance.
Practical Guidance: It offers concrete guidelines for practitioners:
- Use Binary Mechanisms when privacy requirements are strict (small $\epsilon$ ).
- Use Randomized Response when privacy constraints are looser (large $\epsilon$ ).
- Expect a quadratic degradation in performance ( $\epsilon^2$ ) in high-privacy settings.
Independent Value: The results on SDPI coefficients for Rényi divergences are of independent interest for statistical estimation, data compression, and Markov chain mixing, extending beyond the specific application of change-point detection.

In summary, this work provides a comprehensive theoretical and empirical analysis of parametric change-point detection under local differential privacy, establishing fundamental limits on performance and identifying optimal mechanisms for different privacy regimes.