Differentially Private Change-Point Detection
summary
Provides private algorithms for offline and online single and multiple change point detection that match nonprivate accuracy up to constants and add a privacy cost proportional to the KL separation over epsilon. Uses CUSUM log‑likelihood scores with Report Noisy Max (Laplace noise) for the offline MLE and a sliding‑window test with Above‑Noisy‑Threshold (sparse vector) online, then runs the offline estimator on the flagged window. Bounded sensitivity via truncated log‑likelihood clipping is effective and empirically robust to misspecified P0/P1, achieving alpha‑beta accuracy with explicit bounds and small constant overhead.
AI-written summary · about
chapters (12)
- 0:00Introduction to problem
- 2:38Workshop outline
- 3:55Offline case and algorithms
- 8:01Private algorithm design
- 12:36Accuracy analysis
- 17:03Handling unbounded ratios
- 22:16Comparison with related work
- 26:07Online change point detection
- 30:44Online algorithm analysis
- 37:14Multiple change points
- 38:54Challenges in multi-change
- 43:25Empirical results and future
related talks
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
01h 03mStatistical Inference and Privacy, Part II
47mPrivate targeting strategies
28mOnline Change Point Detection Using Spark Streaming
01h 07mStatistical Inference and Privacy, Part I
58mLarge-Scale Private Learning, Part III
26mGeneralized Private Selection and Testing with High Confidence
43mDifferential Privacy Meets Robust Statistics