,
11 tweets,
3 min read
Read on Twitter
We wrote a paper proposing a new relaxation of differential privacy that has lots of nice properties: arxiv.org/abs/1905.02383 It's 85 pages long, so here is the TL;DR. Suppose S is a dataset with your data, and S' is the dataset with your data removed. 1/
Differential privacy can be viewed as promising that any hypothesis test aiming to distinguish whether I used S vs. S' in my computation that has false positive rate alpha must have a true positive rate of at most e^eps*alpha+delta. Cool - its easy to interpret this guarantee! 2/
This characterization is exact: its equivalent to the usual definition of DP. But DP is mis-parameterized in that when we compose mechanisms, there is no way to describe the resulting tradeoff between Type I and type II errors with any parameters eps,delta anymore. 3/
This is fundamentally the reason why composition theorems for DP are not tight. Even "optimal" composition (which is #P hard) is only providing a bound on the correct tradeoff between Type I and Type II error. (The tightest bound parameterized by eps,delta, but still loose) 4/
So: We propose describing privacy guarantees with a function f instead of 2 parameters. The function describes the optimal tradeoff between Type I and Type II error. This is expressive enough to exactly capture composition, and admits a simple calculus for composition. 5/
It turns out this way of describing a privacy guarantee is "dual" to describing it with an infinite collection of (eps,delta)-DP guarantees. You can switch back and forth via the convex conjugate of the function f. This is useful for a couple of reasons. Most notably, 6/
It provides a way to import known results from the DP literature into this new framework. This is how we get "privacy amplification by sub-sampling" for this new family of definitions --- something that has proven challenging for other proposed relaxations of DP. 7/
Isn't keeping track of functions complex? Yes, but there is a "central limit theorem". In the limit under composition, no matter what your functions f looked like, the privacy guarantee converges to the tradeoff function for testing two standard Gaussians with shifted means. 8/
This family of functions has only one parameter (the gap in the means), and has a simple additive composition rule. We call it "Gaussian Differential Privacy". The CLT means that it is the -only- hypothesis testing based definition of privacy tightly closed under composition. 9/
It also provides an analytic tool. Too hard to reason about the composition of many functions? Compute the Gaussian-DP parameter using our central limit theorem instead. Convergence is fast: after 10 compositions, its hard to distinguish the CLT bound from the true bound. 10/
I think its pretty neat. I can say that, because all credit for this work goes to Jinshuo Dong. If you are at the Simons workshop today, come and ask him questions about it. He's speaking at 11:30. 11/11
