The Structure of Optimal Private Tests for Simple Hypotheses
summary
Gives an instance-specific formula for the optimal sample size to privately distinguish two distributions: clamp each sample’s log‑likelihood ratio to ±epsilon (with a slight epsilon′ tweak), then either run the soft clamped likelihood (exponential mechanism) or the noisy clamped likelihood (add Laplace noise). Sample complexity is Θ(1 / [epsilon·tau + (1−tau)·Hellinger^2(P′,Q′)]), where tau (hockey‑stick divergence) is the clipped mass; lower bounds match via coupling, and there is a privacy‑for‑free phase when epsilon exceeds H^2/TV.
AI-written summary · about
chapters (22)
- 0:00Introduction
- 0:17Hypothesis testing review
- 1:47Simple hypothesis tests
- 2:40Differential privacy
- 3:53Related work
- 5:04Defining sample complexity
- 6:02Private testing goals
- 6:42Main contributions
- 7:33Non-private solutions
- 8:46Likelihood ratio tests
- 10:04Sample complexity results
- 11:59Limitations of simple formulas
- 13:08Proposed private tests
- 15:01Main theorem statement
- 17:15Sanity checks and comparisons
- 18:47Proof intuition
- 21:31Non-private test analysis
- 25:33Upper bound proof
- 28:36Characterizing test behavior
- 32:32Lower bound proof
- 37:25Conclusion
- 39:21Q&A and closing remarks
related talks
01h 03mStatistical Inference and Privacy, Part II
26mGeneralized Private Selection and Testing with High Confidence
01h 00mDifferential Privacy: Fundamentals to Forefront I
26mLocally Private Histograms in All Privacy Regimes
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
01h 07mStatistical Inference and Privacy, Part I
39mVirtual talk by Jonathan Ullman (Northeastern)
35mPrivacy amplification by random allocation