Profile picture
, 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: 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
Missing some Tweet in this thread?
You can try to force a refresh.

Like this thread? Get email updates or save it to PDF!

Subscribe to Aaron Roth
Profile picture

Get real-time email alerts when new unrolls are available from this author!

This content may be removed anytime!

Twitter may remove this content at anytime, convert it as a PDF, save and print for later use!

Try unrolling a thread yourself!

how to unroll video

1) Follow Thread Reader App on Twitter so you can easily mention us!

2) Go to a Twitter thread (series of Tweets by the same owner) and mention us with a keyword "unroll" @threadreaderapp unroll

You can practice here first or read more on our help page!

Follow Us on Twitter!

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just three indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3.00/month or $30.00/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!