How can change-point detection be performed under local differential privacy?

Localizing one change point without a trusted curator

The paper studies offline parametric change-point detection: a batch of n independent observations starts out drawn from a known distribution P0, switches at some unknown index k* to another known distribution P1, and an analyst must estimate where that switch happened. "Offline" means the whole batch is available at once, and "parametric" means both distributions are fully specified in advance. The true change point is treated as a fixed unknown, with no prior placed on it.

The twist is local differential privacy (LDP). Instead of sending raw values to a trusted curator, each data owner randomizes their own observation through an ε-LDP mechanism before sharing it. The analyst then sees only the noisy outputs and the induced distributions Q0 and Q1, and must still recover the change point. The privacy parameter ε controls the trade-off: smaller ε means stronger privacy and noisier outputs.

Accuracy is measured by (α, β)-accuracy: the worst-case probability, over all possible true change points, that the estimate is off by more than a tolerance α must stay below β. This is a different question from detection delay in online monitoring, and the paper's guarantees should be read in those terms — a fixed batch, one change, and an error probability at a chosen tolerance.

Chernoff information sets the localization limit

The central quantity is the Chernoff information I_ch(P0, P1), which measures how distinguishable two distributions are by their best exponential trade-off between false alarms and misses. The paper proves finite-sample minimax lower bounds showing that, even in the non-private case, no estimator — randomized or not, including one allowed to declare no change — can localize more accurately than an exponent governed by I_ch.

The lower bound is built by generalizing Le Cam's two-point method to multiple candidate hypotheses and then refining the exponent with exponential tilting. A residual term captures fluctuations of the log-likelihood ratio around its mean under the tilted distribution. In the private setting, the same style of bound holds for every ε-LDP mechanism, with the Chernoff information now taken between the induced output distributions Q0 and Q1.

This is the conceptual pivot of the paper: privacy does not merely add noise, it contracts the distinguishability of the two regimes, and that contraction is what limits localization. The authors formalize the contraction using strong data processing inequality (SDPI) coefficients for Rényi and Jeffreys–Rényi divergences of order infinity, and show these coefficients can be computed by restricting attention to input pairs whose common support has at most two symbols.

The likelihood-ratio estimator is near-optimal without privacy

The estimator the paper analyzes scans every candidate index k and computes the log-likelihood ratio of the observations from k onward, then reports the index maximizing that ratio. This is the offline analogue of the classical CUSUM approach. Using martingale arguments, the authors derive a finite-sample accuracy bound for this generalized likelihood-ratio test (GLRT) in terms of I_ch, and show it improves substantially on earlier guarantees for the same estimator.

Comparing the upper and lower bounds, the GLRT is asymptotically optimal up to a factor of two in the leading localization-error exponent. That factor of two is a specific, stated gap — not an claim of exact optimality. The authors also give an alternative guarantee expressed through the minimum Kullback–Leibler divergence and the sensitivity of the log-likelihood ratio, which makes the comparison with prior work direct and links the analysis to the privacy contraction results.

Two mechanisms split the low- and high-privacy regimes

Guided by the induced Chernoff information, the paper designs two LDP mechanisms. Aggregated randomized response (ARR) groups observations by equal likelihood ratios and applies randomized response within groups; the resulting ARR-CPD algorithm maximizes the induced Chernoff information among ε-LDP mechanisms for sufficiently large ε, that is, in the low-privacy regime. A binary mechanism (BM), which maps each observation to one of two symbols, does the same for sufficiently small ε, the high-privacy regime.

The finite-sample guarantees reproduce this ordering. The BM-CPD bound is smaller at high privacy and the ARR-CPD bound is smaller at low privacy. The paper is careful about what this means: the comparison concerns upper bounds, and the sufficient ranges for ordering those bounds need not coincide with the regimes where each mechanism is Chernoff-optimal. The authors explicitly note that these comparisons do not by themselves establish an ordering of the actual localization errors.

Privacy costs a factor of order tanh⁻²(ε/2)

Combining the upper and lower bounds yields a two-sided statement about the exponent cost of privacy, defined as the ratio of the non-private to the private minimax localization-error exponent. The ratio is bounded between max(1, 1/(2c²)) and 4 I_ch(P0,P1) / (c² d²_TV(P0,P1)), where c = tanh(ε/2) and d_TV is the total-variation distance between P0 and P1.

Consequently, for fixed distributions the cost is Θ(tanh⁻²(ε/2)) uniformly over ε > 0, and Θ(ε⁻²) as ε → 0. In plain terms, tightening privacy from a moderate level toward zero degrades the achievable error exponent quadratically in ε. The bound also shows the cost depends on how far apart the two distributions are: distributions with small total-variation distance pay a larger multiplicative penalty.

Synthetic experiments track the bounds and the crossover

The empirical evaluation uses synthetic data with n = 2000 observations and a true change point at index 1000, with truncated Poisson distributions as the main setting and additional Bernoulli, binomial, truncated geometric, and Gaussian cases in the appendices. Each error probability is estimated from 10,000 Monte Carlo repetitions, giving a standard error of at most 0.005 — small relative to the plotted trends.

The plots compare empirical error probabilities against the theoretical lower and upper bounds as the tolerance α varies, and against the privacy parameter ε at fixed α = 5. The empirical curves follow the bounds, and the crossover appears as predicted: ARR-CPD performs better at low privacy while BM-CPD performs better at high privacy. A separate plot traces the exponent cost of privacy against ε, with the shaded region marking the range permitted by the two-sided bound.

These are simulations on synthetic distributions, not deployments on real data streams. They corroborate the theory and illustrate the regime split, but they do not test the algorithms against model misspecification, unknown distributional parameters, or multiple change points — all of which lie outside the paper's stated setting.

Where the guarantee applies and where it stops

The results hold for offline localization of exactly one change point in a sequence of independent observations, with both pre- and post-change distributions known and fully specified. The lower bounds hold uniformly over ε-LDP mechanisms that may vary across observations and over all estimators, which is what makes the privacy cost statement strong. The analysis also assumes the data contain exactly one true change point in the candidate set.

The practical reading is a regime choice rather than a single recommended algorithm. If the privacy budget is generous, ARR-CPD is the mechanism whose induced Chernoff information is maximal in that regime; if the budget is tight, BM-CPD takes over. The threshold is not a universal constant — the paper's ordering conditions depend on the number of groups r and on ε, and the sufficient ranges for ordering the upper bounds need not match the Chernoff-optimality regimes. For a fixed pair of distributions, the most decision-relevant number remains the tanh⁻²(ε/2) scaling: it tells you how much localization accuracy you are trading away as ε shrinks, before any algorithm choice is made.

Sources used in this answer