A Short Tutorial on Differential Privacy
Borja Balle
Amazon Research Cambridge

The Alan Turing Institute — January 26, 2018

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Anonymization Fiascos

Disturbing Headlines and Paper Titles§ “A Face Is Exposed for AOL Searcher No. 4417749” [Barbaro & Zeller ’06]
§ “Robust De-anonymization of Large Datasets (How to Break Anonymity of the Netflix

Prize Dataset)” [Narayanan & Shmatikov ’08]
§ “Matching Known Patients to Health Records in Washington State Data” [Sweeney ’13]
§ “Harvard Professor Re-Identifies Anonymous Volunteers In DNA Study” [Sweeney et al. ’13]
§ ... and many others

In general, removing identifiers and applying anonymization heuristics is not always enough!

Why is Anonymization Hard?

§ High-dimensional/high-resolution data is essentially unique:officeLondondepartment
ITdate joined
Apr 2015

salary£###d.o.b.
May 1985

nationality
Portuguese

genderFemale§ Lower dimension and lower resolution is more private, but less useful:

officeUK

department
ITdate joined2015

salary£###d.o.b.
1980-1985

nationality—

genderFemaleWhy is Anonymization Hard?

§ High-dimensional/high-resolution data is essentially unique:officeLondondepartment
ITdate joined
Apr 2015

salary£###d.o.b.
May 1985

nationality
Portuguese

genderFemale§ Lower dimension and lower resolution is more private, but less useful:

officeUK

department
ITdate joined2015

salary£###d.o.b.
1980-1985

nationality—

genderFemaleManaging Expectations

Unreasonable Privacy Expectations§ Privacy for free? No, privatizing requires removing information (ñ accuracy loss)§ Absolute privacy? No, your neighbour’s habits are correlated with your habits

Reasonable Privacy Expectations§ Quantitative: offer a knob to tune accuracy vs. privacy loss
§ Plausible deniability: your presence in a database cannot be ascertained§ Prevent targeted attacks: limit information leaked even in the presence of side knowledge

The Promise of Differential Privacy
Quote from [Dwork and Roth, 2014]:
Differential privacy describes a promise, made by a data holder, or curator, to a data
subject: “You will not be affected, adversely or otherwise, by allowing your data to
be used in any study or analysis, no matter what other studies, data sets, orinformation sources, are available.”
Quotes from the 2017 Gödel Prize citation awarded to Dwork, McSherry, Nissim and Smith:Differential privacy was carefully constructed to avoid numerous and subtle pitfalls
that other attempts at defining privacy have faced.
The intellectual impact of differential privacy has been broad, with influence on thethinking about privacy being noticeable in a huge range of disciplines, ranging fromtraditional areas of computer science (databases, machine learning, networking,security) to economics and game theory, false discovery control, official statistics andeconometrics, information theory, genomics and, recently, law and policy.

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Differential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDifferential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with σ-algebra of measurable events)§ Privacy parameter ε ě 0

Differential Privacy [Dwork et al., 2006, Dwork, 2006]
A randomized mechanism M : X Ñ Y is ε-differentially private if for all neighbouring inputsx » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E sIntuitions behind the definition:§ The neighbouring relation » captures what is protected§ The probability bounds capture how much protection we getDP before DP: Randomized Response
The Randomized Response Mechanism [Warner, 1965]§ n individuals answer a survey with one binary question§ The truthful answer for individual i is xi P t0, 1u§ Each individual answers truthfully (yi “ xi ) with probability e ε {p1 ` e ε q and falsely(yi “ x̄i ) with probability 1{p1 ` e ε q§ Let’s denote the mechanism by py1 , . . . , yn q “ RRε px1 , . . . , xn q

Intuition: Provides plausible deniability for each individual’s answer
Claim: RRε is ε-DP (free-range organic proof on the whiteboard)
Utility: Averaging the (unbiased) answers ỹi from RRε satisfies w.h.p.
ˇ
ˇ
˙
ˆ
n
n
ˇ1 ÿ
1 ÿ ˇˇ
1ˇ?
xi ´
ỹi ˇ ď Oˇˇnn i“1 ˇε ni“1DP before DP: Randomized Response
The Randomized Response Mechanism [Warner, 1965]§ n individuals answer a survey with one binary question§ The truthful answer for individual i is xi P t0, 1u§ Each individual answers truthfully (yi “ xi ) with probability e ε {p1 ` e ε q and falsely(yi “ x̄i ) with probability 1{p1 ` e ε q§ Let’s denote the mechanism by py1 , . . . , yn q “ RRε px1 , . . . , xn q

Intuition: Provides plausible deniability for each individual’s answer
Claim: RRε is ε-DP (free-range organic proof on the whiteboard)
Utility: Averaging the (unbiased) answers ỹi from RRε satisfies w.h.p.
ˇ
ˇ
˙
ˆ
n
n
ˇ1 ÿ
1 ÿ ˇˇ
1ˇ?
xi ´
ỹi ˇ ď Oˇˇnn i“1 ˇε ni“1DP before DP: Randomized Response
The Randomized Response Mechanism [Warner, 1965]§ n individuals answer a survey with one binary question§ The truthful answer for individual i is xi P t0, 1u§ Each individual answers truthfully (yi “ xi ) with probability e ε {p1 ` e ε q and falsely(yi “ x̄i ) with probability 1{p1 ` e ε q§ Let’s denote the mechanism by py1 , . . . , yn q “ RRε px1 , . . . , xn q

Intuition: Provides plausible deniability for each individual’s answer
Claim: RRε is ε-DP (free-range organic proof on the whiteboard)
Utility: Averaging the (unbiased) answers ỹi from RRε satisfies w.h.p.
ˇ
ˇ
˙
ˆ
n
n
ˇ1 ÿ
1 ÿ ˇˇ
1ˇ?
xi ´
ỹi ˇ ď Oˇˇnn i“1 ˇε ni“1DP before DP: Randomized Response
The Randomized Response Mechanism [Warner, 1965]§ n individuals answer a survey with one binary question§ The truthful answer for individual i is xi P t0, 1u§ Each individual answers truthfully (yi “ xi ) with probability e ε {p1 ` e ε q and falsely(yi “ x̄i ) with probability 1{p1 ` e ε q§ Let’s denote the mechanism by py1 , . . . , yn q “ RRε px1 , . . . , xn q

Intuition: Provides plausible deniability for each individual’s answer
Claim: RRε is ε-DP (free-range organic proof on the whiteboard)
Utility: Averaging the (unbiased) answers ỹi from RRε satisfies w.h.p.
ˇ
ˇ
˙
ˆ
n
n
ˇ1 ÿ
1 ÿ ˇˇ
1ˇ?
xi ´
ỹi ˇ ď Oˇˇnn i“1 ˇε ni“1The Laplace Mechanism (for computing the mean)
Private Mean Computation§ A curator holds one bit xi P t0, 1u for each of n individuals§ The curator proceeds byř
1. Computing the mean µ “ n1 ni“1 xi ,1
2. Sampling noise Z „ Lapp εnq, and
3. Revealing the noisy mean µ̃ “ µ ` Z§ Let’s denote the mechanism by µ̃ “ MLap px1 , . . . , xn q

Claim: MLap is ε-DP (free-range organic proof on the whiteboard)
Utility: The answer returned by the mechanism satisfies w.h.p.
ˆ|µ ´ µ̃| ď O

1
εn

˙

The Laplace Mechanism (for computing the mean)
Private Mean Computation§ A curator holds one bit xi P t0, 1u for each of n individuals§ The curator proceeds byř
1. Computing the mean µ “ n1 ni“1 xi ,1
2. Sampling noise Z „ Lapp εnq, and
3. Revealing the noisy mean µ̃ “ µ ` Z§ Let’s denote the mechanism by µ̃ “ MLap px1 , . . . , xn q

Claim: MLap is ε-DP (free-range organic proof on the whiteboard)
Utility: The answer returned by the mechanism satisfies w.h.p.
ˆ|µ ´ µ̃| ď O

1
εn

˙

The Laplace Mechanism (for computing the mean)
Private Mean Computation§ A curator holds one bit xi P t0, 1u for each of n individuals§ The curator proceeds byř
1. Computing the mean µ “ n1 ni“1 xi ,1
2. Sampling noise Z „ Lapp εnq, and
3. Revealing the noisy mean µ̃ “ µ ` Z§ Let’s denote the mechanism by µ̃ “ MLap px1 , . . . , xn q

Claim: MLap is ε-DP (free-range organic proof on the whiteboard)
Utility: The answer returned by the mechanism satisfies w.h.p.
ˆ|µ ´ µ̃| ď O

1
εn

˙

Approximate Differential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with sigma-algebra of measurable events)§ Privacy parameters ε ě 0, δ P r0, 1s

Approximate Differential Privacy
A randomized mechanism M : X Ñ Y is pε, δq-differentially private if for all neighbouring
inputs x » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E s ` δInterpretation§ δ accounts for “bad events” that might result in high privacy losses§ Mechanism Mpx1 , . . . , xn q “ xUnifprnsq is p0, 1{nq-DP (ñ should take δ ! 1{n)Approximate Differential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with sigma-algebra of measurable events)§ Privacy parameters ε ě 0, δ P r0, 1s

Approximate Differential Privacy
A randomized mechanism M : X Ñ Y is pε, δq-differentially private if for all neighbouring
inputs x » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E s ` δInterpretation§ δ accounts for “bad events” that might result in high privacy losses§ Mechanism Mpx1 , . . . , xn q “ xUnifprnsq is p0, 1{nq-DP (ñ should take δ ! 1{n)Approximate Differential Privacy
Ingredients§ Input space X (with symmetric neighbouring relation »)§ Output space Y (with sigma-algebra of measurable events)§ Privacy parameters ε ě 0, δ P r0, 1s

Approximate Differential Privacy
A randomized mechanism M : X Ñ Y is pε, δq-differentially private if for all neighbouring
inputs x » x 1 and for all sets of outputs E Ď Y we have
PrMpxq P E s ď e ε PrMpx 1 q P E s ` δInterpretation§ δ accounts for “bad events” that might result in high privacy losses§ Mechanism Mpx1 , . . . , xn q “ xUnifprnsq is p0, 1{nq-DP (ñ should take δ ! 1{n)Output Perturbation Mechanisms
The Laplace mechanism is an example of a more general class of mechanisms
Global Sensitivity: for any function f : X Ñ Rd define ∆p “ supx»x 1 }f pxq ´ f px 1 q}p
Output Perturbation (with Laplace and Gaussian noise)§ A curator holds one vector xi P Rd for each of n individuals§ The curator computes a function f px1 , . . . , xn q of the data,∆2§ samples noise Z „ Lapp ∆1 qd or Z „ Np0, σ2 qd with σ “ε§ reveals the noisy value f px1 , . . . , xn q ` Z?

C logp1{δq, andε§ Let’s denote the mechanisms Mf ,Lap and Mf ,N respectively§ Note the mechanism of the previous slide is Mf ,Lap for f px1 , . . . , xn q “ 1nClaim: Mf ,Lap is ε-DP and Mf ,N is pε, δq-DPřn

i“1 xiOutput Perturbation Mechanisms
The Laplace mechanism is an example of a more general class of mechanisms
Global Sensitivity: for any function f : X Ñ Rd define ∆p “ supx»x 1 }f pxq ´ f px 1 q}p
Output Perturbation (with Laplace and Gaussian noise)§ A curator holds one vector xi P Rd for each of n individuals§ The curator computes a function f px1 , . . . , xn q of the data,∆2§ samples noise Z „ Lapp ∆1 qd or Z „ Np0, σ2 qd with σ “ε§ reveals the noisy value f px1 , . . . , xn q ` Z?

C logp1{δq, andε§ Let’s denote the mechanisms Mf ,Lap and Mf ,N respectively§ Note the mechanism of the previous slide is Mf ,Lap for f px1 , . . . , xn q “ 1nClaim: Mf ,Lap is ε-DP and Mf ,N is pε, δq-DPřn

i“1 xiOutput Perturbation Mechanisms
The Laplace mechanism is an example of a more general class of mechanisms
Global Sensitivity: for any function f : X Ñ Rd define ∆p “ supx»x 1 }f pxq ´ f px 1 q}p
Output Perturbation (with Laplace and Gaussian noise)§ A curator holds one vector xi P Rd for each of n individuals§ The curator computes a function f px1 , . . . , xn q of the data,∆2§ samples noise Z „ Lapp ∆1 qd or Z „ Np0, σ2 qd with σ “ε§ reveals the noisy value f px1 , . . . , xn q ` Z?

C logp1{δq, andε§ Let’s denote the mechanisms Mf ,Lap and Mf ,N respectively§ Note the mechanism of the previous slide is Mf ,Lap for f px1 , . . . , xn q “ 1nClaim: Mf ,Lap is ε-DP and Mf ,N is pε, δq-DPřn

i“1 xiFundamental Properties§ Robustness to post-processing: M is pε, δq-DP, then F ˝ M is pε, δq-DP§ Composition: if Mj , j “ 1, . . . , k, are pεj , δj q-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qq ispř

j εj ,

řj δj q-DP. In the homogeneous case this yields pkε, kδq-DP§ Advanced composition: if Mj , j “ 1, . . . , k, are pε, δq-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qqais pε k logp1{δ 1 q ` εpe ε ´ 1qk, kδ ` δ 1 q-DP for any δ 1 ą 0§ Group privacy: if M is pε, δq-DP with respect to x » x 1 , then M is ptε, te tε δq withrespect to x »t x 1 (ie. t changes)
xi§ Protects against side knowledge: if attacker has prior P xi
prior and computes Pposterior after
xi
xi
observing Mp~x q from ε-DP mechanism, then distpPprior , Pposterior q “ Opεq

Fundamental Properties§ Robustness to post-processing: M is pε, δq-DP, then F ˝ M is pε, δq-DP§ Composition: if Mj , j “ 1, . . . , k, are pεj , δj q-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qq ispř

j εj ,

řj δj q-DP. In the homogeneous case this yields pkε, kδq-DP§ Advanced composition: if Mj , j “ 1, . . . , k, are pε, δq-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qqais pε k logp1{δ 1 q ` εpe ε ´ 1qk, kδ ` δ 1 q-DP for any δ 1 ą 0§ Group privacy: if M is pε, δq-DP with respect to x » x 1 , then M is ptε, te tε δq withrespect to x »t x 1 (ie. t changes)
xi§ Protects against side knowledge: if attacker has prior P xi
prior and computes Pposterior after
xi
xi
observing Mp~x q from ε-DP mechanism, then distpPprior , Pposterior q “ Opεq

Fundamental Properties§ Robustness to post-processing: M is pε, δq-DP, then F ˝ M is pε, δq-DP§ Composition: if Mj , j “ 1, . . . , k, are pεj , δj q-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qq ispř

j εj ,

řj δj q-DP. In the homogeneous case this yields pkε, kδq-DP§ Advanced composition: if Mj , j “ 1, . . . , k, are pε, δq-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qqais pε k logp1{δ 1 q ` εpe ε ´ 1qk, kδ ` δ 1 q-DP for any δ 1 ą 0§ Group privacy: if M is pε, δq-DP with respect to x » x 1 , then M is ptε, te tε δq withrespect to x »t x 1 (ie. t changes)
xi§ Protects against side knowledge: if attacker has prior P xi
prior and computes Pposterior after
xi
xi
observing Mp~x q from ε-DP mechanism, then distpPprior , Pposterior q “ Opεq

Fundamental Properties§ Robustness to post-processing: M is pε, δq-DP, then F ˝ M is pε, δq-DP§ Composition: if Mj , j “ 1, . . . , k, are pεj , δj q-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qq ispř

j εj ,

řj δj q-DP. In the homogeneous case this yields pkε, kδq-DP§ Advanced composition: if Mj , j “ 1, . . . , k, are pε, δq-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qqais pε k logp1{δ 1 q ` εpe ε ´ 1qk, kδ ` δ 1 q-DP for any δ 1 ą 0§ Group privacy: if M is pε, δq-DP with respect to x » x 1 , then M is ptε, te tε δq withrespect to x »t x 1 (ie. t changes)
xi§ Protects against side knowledge: if attacker has prior P xi
prior and computes Pposterior after
xi
xi
observing Mp~x q from ε-DP mechanism, then distpPprior , Pposterior q “ Opεq

Fundamental Properties§ Robustness to post-processing: M is pε, δq-DP, then F ˝ M is pε, δq-DP§ Composition: if Mj , j “ 1, . . . , k, are pεj , δj q-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qq ispř

j εj ,

řj δj q-DP. In the homogeneous case this yields pkε, kδq-DP§ Advanced composition: if Mj , j “ 1, . . . , k, are pε, δq-DP, then ~x ÞÑ pM1 p~x q, . . . , Mk p~x qqais pε k logp1{δ 1 q ` εpe ε ´ 1qk, kδ ` δ 1 q-DP for any δ 1 ą 0§ Group privacy: if M is pε, δq-DP with respect to x » x 1 , then M is ptε, te tε δq withrespect to x »t x 1 (ie. t changes)
xi§ Protects against side knowledge: if attacker has prior P xi
prior and computes Pposterior after
xi
xi
observing Mp~x q from ε-DP mechanism, then distpPprior , Pposterior q “ Opεq

The Exponential Mechanism
The Laplace and Gaussian mechanisms are examples of a more general class of mechanisms
Densities of output perturbation mechanisms˙ˆ´ε}y ´ f pxq}1
pMf ,Lap pxq py q 9 exp∆1

ˆ
pMf ,N pxq py q 9 exp´ε2 }y ´ f pxq}22
C ∆22 logp1{δq˙Exponential Mechanism§ Prior distribution over outputs with density π§ Scoring function q : X ˆ Y Ñ Rě0 provides scores for each output y w.r.t. input x§ The exponential mechanism Mπ,q pxq outputs a sample from the distribution with density

pπ,q py q 9 πpy q exp p´βqpx, y qq

The Exponential Mechanism
The Laplace and Gaussian mechanisms are examples of a more general class of mechanisms
Densities of output perturbation mechanisms˙ˆ´ε}y ´ f pxq}1
pMf ,Lap pxq py q 9 exp∆1

ˆ
pMf ,N pxq py q 9 exp´ε2 }y ´ f pxq}22
C ∆22 logp1{δq˙Exponential Mechanism§ Prior distribution over outputs with density π§ Scoring function q : X ˆ Y Ñ Rě0 provides scores for each output y w.r.t. input x§ The exponential mechanism Mπ,q pxq outputs a sample from the distribution with density

pπ,q py q 9 πpy q exp p´βqpx, y qq

The Exponential Mechanism
The Laplace and Gaussian mechanisms are examples of a more general class of mechanisms
Densities of output perturbation mechanisms˙ˆ´ε}y ´ f pxq}1
pMf ,Lap pxq py q 9 exp∆1

ˆ
pMf ,N pxq py q 9 exp´ε2 }y ´ f pxq}22
C ∆22 logp1{δq˙Exponential Mechanism§ Prior distribution over outputs with density π§ Scoring function q : X ˆ Y Ñ Rě0 provides scores for each output y w.r.t. input x§ The exponential mechanism Mπ,q pxq outputs a sample from the distribution with density

pπ,q py q 9 πpy q exp p´βqpx, y qq

Calibrating The Exponential Mechanism
Properties of the Scoring Function§ Sensitivity: supx»x 1 supy |qpx, y q ´ qpx 1 , y q| ď ∆§ Lipschitz: supx»x 1 |pqpx, y q ´ qpx 1 , y qq ´ pqpx, y 1 q ´ qpx 1 , y 1 qq| ď L}y ´ y 1 }Properties of the Prior§ Strong log-concavity: πpy q “ e ´W py q for some κ-strongly convex W

Privacy Guarantees for the Exponential Mechanism
Assumptions
q bounded sensitivity
q Lipschitz + convex
π strongly log-concave

O

ˆ
O

`βε ˘

∆
˙
?
ε
κ
?
L logp1{δqPrivacypε, 0q

Reference[McSherry and Talwar, 2007]pε, δq[Minami et al., 2016]

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Differentially Private Empirical Risk Minimization
Setup: A curator has features and labels ~z “ ppx1 , y1 q, . . . , pxn , yn qq about n individuals andwants to train a model by minimizing over θ P Θn

Lp~z , θq “Rpθq1ÿ`pxi , yi , θq `n i“1nExamples: logistic regression, SVM, linear regression, DNN, etc.
Private ERM Algorithms§ Output Perturbation: add some noise Z to θ̂ “ argminθPΘ Lp~
z , θq§ Objective Perturbation: reveal the optimum of Lp~
z , θq ` xθ, Z y for some noise Z§ Gradient Perturbation: optimize Lp~
z , θq using mini-batch SGD with noisy gradientsDifferentially Private Empirical Risk Minimization
Setup: A curator has features and labels ~z “ ppx1 , y1 q, . . . , pxn , yn qq about n individuals andwants to train a model by minimizing over θ P Θn

Lp~z , θq “Rpθq1ÿ`pxi , yi , θq `n i“1nExamples: logistic regression, SVM, linear regression, DNN, etc.
Private ERM Algorithms§ Output Perturbation: add some noise Z to θ̂ “ argminθPΘ Lp~
z , θq§ Objective Perturbation: reveal the optimum of Lp~
z , θq ` xθ, Z y for some noise Z§ Gradient Perturbation: optimize Lp~
z , θq using mini-batch SGD with noisy gradients

DP-ERM: Method Comparison

Perturb

Optimization

Privacy

ObjectiveExactpε, δqOutputExactpε, δqOutputSGD

εOutputSGD

εAssumptions
linear model
convexity
linear model
convexity
linear model
convexity
linear modelstrong convexity

Gradient

SGDpε, δqconvexity

Gradient

SGDpε, δqstrong convexity

See also [Talwar et al., 2014, Abadi et al., 2016]

Excess Risk
´
¯
1
Õ ε?
n
´
¯
1
O ε?
n
´
¯
d
O ε?
n
`d˘
O´ εn
? ¯
Õ εnd`˘Õ ε2dn2

Reference[Jain and Thakurta, 2014][Jain and Thakurta, 2014][Wu et al., 2016][Wu et al., 2016][Bassily et al., 2014][Bassily et al., 2014]

Private Bayesian Learning
One-Posterior Sample (OPS) Mechanism [Wang et al., 2015]§ Curator has a prior Pprior pθq and a model Pmodel pxi |θq§ Given a dataset ~x the curators computes the posterior Pposterior pθ|~x q, and§ reveals a sample θ̂ „ Pposterior pθ|~xq

Claim: If the model satisfies supx,x 1 ,θ | log Pmodel px|θq ´ log Pmodel px 1 |θq| ď ε{2 then OPS isε-DP
See also: [Wang et al., 2015, Foulds et al., 2016, Minami et al., 2016] for DP with approximate
inference, [Park et al., 2016] for DP with variational Bayes, and [Zhang et al., 2016] for Bayesian
network mechanisms

Private Bayesian Learning
One-Posterior Sample (OPS) Mechanism [Wang et al., 2015]§ Curator has a prior Pprior pθq and a model Pmodel pxi |θq§ Given a dataset ~x the curators computes the posterior Pposterior pθ|~x q, and§ reveals a sample θ̂ „ Pposterior pθ|~xq

Claim: If the model satisfies supx,x 1 ,θ | log Pmodel px|θq ´ log Pmodel px 1 |θq| ď ε{2 then OPS isε-DP
See also: [Wang et al., 2015, Foulds et al., 2016, Minami et al., 2016] for DP with approximate
inference, [Park et al., 2016] for DP with variational Bayes, and [Zhang et al., 2016] for Bayesian
network mechanisms

Private Bayesian Learning
One-Posterior Sample (OPS) Mechanism [Wang et al., 2015]§ Curator has a prior Pprior pθq and a model Pmodel pxi |θq§ Given a dataset ~x the curators computes the posterior Pposterior pθ|~x q, and§ reveals a sample θ̂ „ Pposterior pθ|~xq

Claim: If the model satisfies supx,x 1 ,θ | log Pmodel px|θq ´ log Pmodel px 1 |θq| ď ε{2 then OPS isε-DP
See also: [Wang et al., 2015, Foulds et al., 2016, Minami et al., 2016] for DP with approximate
inference, [Park et al., 2016] for DP with variational Bayes, and [Zhang et al., 2016] for Bayesian
network mechanisms

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Privacy Losses
Let M : X Ñ Y be a randomized mechanism with density function pMpxq py q
Privacy Loss (function)ˆLM,x,x 1 py q “ logpMpxq py q
pMpx 1 q py q˙Privacy Loss (random variable)
LM,x,x 1 “ LM,x,x 1 pMpxqq
Lemma (Sufficient Condition)
A mechanism M : X Ñ Y is pε, δq-DP if for any x » x 1 we have PrLM,x,x 1 ě εs ď δPrivacy Losses
Let M : X Ñ Y be a randomized mechanism with density function pMpxq py q
Privacy Loss (function)ˆLM,x,x 1 py q “ logpMpxq py q
pMpx 1 q py q˙Privacy Loss (random variable)
LM,x,x 1 “ LM,x,x 1 pMpxqq
Lemma (Sufficient Condition)
A mechanism M : X Ñ Y is pε, δq-DP if for any x » x 1 we have PrLM,x,x 1 ě εs ď δPrivacy Losses
Let M : X Ñ Y be a randomized mechanism with density function pMpxq py q
Privacy Loss (function)ˆLM,x,x 1 py q “ logpMpxq py q
pMpx 1 q py q˙Privacy Loss (random variable)
LM,x,x 1 “ LM,x,x 1 pMpxqq
Lemma (Sufficient Condition)
A mechanism M : X Ñ Y is pε, δq-DP if for any x » x 1 we have PrLM,x,x 1 ě εs ď δPrivacy Losses
Let M : X Ñ Y be a randomized mechanism with density function pMpxq py q
Privacy Loss (function)ˆLM,x,x 1 py q “ logpMpxq py q
pMpx 1 q py q˙Privacy Loss (random variable)
LM,x,x 1 “ LM,x,x 1 pMpxqq
Lemma (Sufficient Condition)
A mechanism M : X Ñ Y is pε, δq-DP if for any x » x 1 we have PrLM,x,x 1 ě εs ď δAnalysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:}y ´ f px 1 q}22 ´ }y ´ f pxq}22}f pxq ´ f px 1 q}22 xy ´ f pxq, f pxq ´ f px 1 qy
“
`
2σ2
2σˆ2
σ2
˙
1
2
1
2
1
}f pxq ´ f px q}2 }f pxq ´ f px 1 q}22
}f pxq ´ f px q}2 xZ , f pxq ´ f px qy
LM,x,x 1 “
`
„N
,
2σ2
σ2
2σ2
σ2

LM,x,x 1 py q “

3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:Analysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:}y ´ f px 1 q}22 ´ }y ´ f pxq}22}f pxq ´ f px 1 q}22 xy ´ f pxq, f pxq ´ f px 1 qy
“
`
2σ2
2σˆ2
σ2
˙
1
2
1
2
1
}f pxq ´ f px q}2 }f pxq ´ f px 1 q}22
}f pxq ´ f px q}2 xZ , f pxq ´ f px qy
LM,x,x 1 “
`
„N
,
2σ2
σ2
2σ2
σ2

LM,x,x 1 py q “

3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:Analysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:}y ´ f px 1 q}22 ´ }y ´ f pxq}22}f pxq ´ f px 1 q}22 xy ´ f pxq, f pxq ´ f px 1 qy
“
`
2σ2
2σˆ2
σ2
˙
1
2
1
2
1
}f pxq ´ f px q}2 }f pxq ´ f px 1 q}22
}f pxq ´ f px q}2 xZ , f pxq ´ f px qy
LM,x,x 1 “
`
„N
,
2σ2
σ2
2σ2
σ2
LM,x,x 1 py q “

3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:Analysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:ˆ˙}f pxq ´ f px 1 q}22 }f pxq ´ f px 1 q}22,
“ Npη, 2ηq
LM,x,x 1 „ N
2σ2σ2
3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:¯2´aa
ε ` C1 logp1{δq ´ C1 logp1{δq ďηď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:η“}f pxq ´ f px 1 q}22
ε2 }f pxq ´ f px 1 q}22
ε2
“
ď
2σ2
C2 logp1{δq2∆22 C logp1{δqAnalysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:ˆ˙}f pxq ´ f px 1 q}22 }f pxq ´ f px 1 q}22,
“ Npη, 2ηq
LM,x,x 1 „ N
2σ2σ2
3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:η“}f pxq ´ f px 1 q}22
ε2 }f pxq ´ f px 1 q}22
ε2
“
ď
2σ2
C2 logp1{δq2∆22 C logp1{δqAnalysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:ˆ˙}f pxq ´ f px 1 q}22 }f pxq ´ f px 1 q}22,
“ Npη, 2ηq
LM,x,x 1 „ N
2σ2σ2
3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:η“}f pxq ´ f px 1 q}22
ε2 }f pxq ´ f px 1 q}22
ε2
“
ď
2σ2
C2 logp1{δq2∆22 C logp1{δqAnalysis of the Gaussian Mechanisma
1. Setup: Mpxq “ f pxq ` Z with Z „ Np0, σ2 I q with σ “ ∆ε2 C logp1{δq (for ε ď 1)
2. Compute the distribution of the privacy loss random variable:ˆ˙}f pxq ´ f px 1 q}22 }f pxq ´ f px 1 q}22,
“ Npη, 2ηq
LM,x,x 1 „ N
2σ2σ2
3. Use a concentration bound for Gaussian random variables. With probability ě 1 ´ δ:aNpη, 2ηq ď η ` C0 η logp1{δq ď ε
4. Assuming ε ď 1, a bit of algebra shows PrLM,x,x 1 ě εs ď δ if:
´a
¯2
a
ηď
ε ` C1 logp1{δq ´ C1 logp1{δq ď

ε2C2 logp1{δq5. Substitute the definition of σ2 and verify the condition is satisfied:η“}f pxq ´ f px 1 q}22
ε2 }f pxq ´ f px 1 q}22
ε2
“
ď
2σ2
C2 logp1{δq2∆22 C logp1{δqDifferential Privacy as a Concentration Property§ Let M : X Ñ Y be a randomized mechanism with privacy loss r.v. LM,x,x 1§ Define the cumulant generating function of M as ϕM,x,x 1 psq “ log Ere sLM,x,x 1 s

Name
Concentrated DPpµ, τq-CDP
Zero-Concentrated DPpξ, ρq-zCDP
Rényi DPpα ` 1, βq-RDP

Definitionx » x 1, s ą 0
2 2
ϕM,x,x 1 psq ď sµ ` s 2τx » x 1, s ą 0
ϕM,x,x 1 psq ď spξ ` ρq ` s 2 ρx » x1
ϕM,x,x 1 pαq ď αβ

Reference[Dwork and Rothblum, 2016][Bun and Steinke, 2016][Mironov, 2017]§ Gaussian: For L „ Npη, 2ηq the c.g.f. is ϕpsq “ sη ` s 2 η, i.e. p0, ηq-zCDP§ Markov: If Ds ą 0 such that supx»x 1 ϕM,x,x 1 psq ` logp1{δq ď sε, then M is pε, δq-DP§ Moment accountant: Let ϕi psq be c.g.f. for mechanism Mi . The mechanism
řMpxq “ pM1 pxq, . . . , Mk pxqq has c.g.f. ϕM psq “ ki“1 ϕi psq [Abadi et al., 2016]

Differential Privacy as a Concentration Property§ Let M : X Ñ Y be a randomized mechanism with privacy loss r.v. LM,x,x 1§ Define the cumulant generating function of M as ϕM,x,x 1 psq “ log Ere sLM,x,x 1 s

Name
Concentrated DPpµ, τq-CDP
Zero-Concentrated DPpξ, ρq-zCDP
Rényi DPpα ` 1, βq-RDP

Definitionx » x 1, s ą 0
2 2
ϕM,x,x 1 psq ď sµ ` s 2τx » x 1, s ą 0
ϕM,x,x 1 psq ď spξ ` ρq ` s 2 ρx » x1
ϕM,x,x 1 pαq ď αβ

Reference[Dwork and Rothblum, 2016][Bun and Steinke, 2016][Mironov, 2017]§ Gaussian: For L „ Npη, 2ηq the c.g.f. is ϕpsq “ sη ` s 2 η, i.e. p0, ηq-zCDP§ Markov: If Ds ą 0 such that supx»x 1 ϕM,x,x 1 psq ` logp1{δq ď sε, then M is pε, δq-DP§ Moment accountant: Let ϕi psq be c.g.f. for mechanism Mi . The mechanism
řMpxq “ pM1 pxq, . . . , Mk pxqq has c.g.f. ϕM psq “ ki“1 ϕi psq [Abadi et al., 2016]

Differential Privacy as a Concentration Property§ Let M : X Ñ Y be a randomized mechanism with privacy loss r.v. LM,x,x 1§ Define the cumulant generating function of M as ϕM,x,x 1 psq “ log Ere sLM,x,x 1 s

Name
Concentrated DPpµ, τq-CDP
Zero-Concentrated DPpξ, ρq-zCDP
Rényi DPpα ` 1, βq-RDP

Definitionx » x 1, s ą 0
2 2
ϕM,x,x 1 psq ď sµ ` s 2τx » x 1, s ą 0
ϕM,x,x 1 psq ď spξ ` ρq ` s 2 ρx » x1
ϕM,x,x 1 pαq ď αβ

Reference[Dwork and Rothblum, 2016][Bun and Steinke, 2016][Mironov, 2017]§ Gaussian: For L „ Npη, 2ηq the c.g.f. is ϕpsq “ sη ` s 2 η, i.e. p0, ηq-zCDP§ Markov: If Ds ą 0 such that supx»x 1 ϕM,x,x 1 psq ` logp1{δq ď sε, then M is pε, δq-DP§ Moment accountant: Let ϕi psq be c.g.f. for mechanism Mi . The mechanism
řMpxq “ pM1 pxq, . . . , Mk pxqq has c.g.f. ϕM psq “ ki“1 ϕi psq [Abadi et al., 2016]

Differential Privacy as a Concentration Property§ Let M : X Ñ Y be a randomized mechanism with privacy loss r.v. LM,x,x 1§ Define the cumulant generating function of M as ϕM,x,x 1 psq “ log Ere sLM,x,x 1 s

Name
Concentrated DPpµ, τq-CDP
Zero-Concentrated DPpξ, ρq-zCDP
Rényi DPpα ` 1, βq-RDP

Definitionx » x 1, s ą 0
2 2
ϕM,x,x 1 psq ď sµ ` s 2τx » x 1, s ą 0
ϕM,x,x 1 psq ď spξ ` ρq ` s 2 ρx » x1
ϕM,x,x 1 pαq ď αβ

Reference[Dwork and Rothblum, 2016][Bun and Steinke, 2016][Mironov, 2017]§ Gaussian: For L „ Npη, 2ηq the c.g.f. is ϕpsq “ sη ` s 2 η, i.e. p0, ηq-zCDP§ Markov: If Ds ą 0 such that supx»x 1 ϕM,x,x 1 psq ` logp1{δq ď sε, then M is pε, δq-DP§ Moment accountant: Let ϕi psq be c.g.f. for mechanism Mi . The mechanism
řMpxq “ pM1 pxq, . . . , Mk pxqq has c.g.f. ϕM psq “ ki“1 ϕi psq [Abadi et al., 2016]

Differential Privacy as a Concentration Property§ Let M : X Ñ Y be a randomized mechanism with privacy loss r.v. LM,x,x 1§ Define the cumulant generating function of M as ϕM,x,x 1 psq “ log Ere sLM,x,x 1 s

Name
Concentrated DPpµ, τq-CDP
Zero-Concentrated DPpξ, ρq-zCDP
Rényi DPpα ` 1, βq-RDP

Definitionx » x 1, s ą 0
2 2
ϕM,x,x 1 psq ď sµ ` s 2τx » x 1, s ą 0
ϕM,x,x 1 psq ď spξ ` ρq ` s 2 ρx » x1
ϕM,x,x 1 pαq ď αβ

Reference[Dwork and Rothblum, 2016][Bun and Steinke, 2016][Mironov, 2017]§ Gaussian: For L „ Npη, 2ηq the c.g.f. is ϕpsq “ sη ` s 2 η, i.e. p0, ηq-zCDP§ Markov: If Ds ą 0 such that supx»x 1 ϕM,x,x 1 psq ` logp1{δq ď sε, then M is pε, δq-DP§ Moment accountant: Let ϕi psq be c.g.f. for mechanism Mi . The mechanism
řMpxq “ pM1 pxq, . . . , Mk pxqq has c.g.f. ϕM psq “ ki“1 ϕi psq [Abadi et al., 2016]

Differential Privacy Without a Trusted Curator
Issues with the Trusted Curator Assumption§ Single point of failure: a DP curator might have other security vulnerabilities§ Conflicting incentives: valuable the data provides incentives for the curator to misbehave§ Requires agreement: a large number of individuals need to agree on who to trust

Randomized response: recall in py1 , . . . , yn q “ RRε px1 , . . . , xn q each yi depends only on xi
Multi-Party and Local Differential Privacy§ Dataset x distributed among m parties, party i owns ~xi§ Analyst initiates randomized protocol Π : X Ñ Y that interacts with the parties§ All the outputs produced by party i during Πpxq determine a mechanism Mi p~xi q§ Π is multi-party pε, δq-DP if each Mi is pε, δq-DP§ When each ~xi has size one we talk about local DP?

§ Utility loss: the difference between Op1{nq (Laplace) and Op1{of local DP

nq (RR) is characteristicDifferential Privacy Without a Trusted Curator
Issues with the Trusted Curator Assumption§ Single point of failure: a DP curator might have other security vulnerabilities§ Conflicting incentives: valuable the data provides incentives for the curator to misbehave§ Requires agreement: a large number of individuals need to agree on who to trust

Randomized response: recall in py1 , . . . , yn q “ RRε px1 , . . . , xn q each yi depends only on xi
Multi-Party and Local Differential Privacy§ Dataset x distributed among m parties, party i owns ~xi§ Analyst initiates randomized protocol Π : X Ñ Y that interacts with the parties§ All the outputs produced by party i during Πpxq determine a mechanism Mi p~xi q§ Π is multi-party pε, δq-DP if each Mi is pε, δq-DP§ When each ~xi has size one we talk about local DP?

§ Utility loss: the difference between Op1{nq (Laplace) and Op1{of local DP

nq (RR) is characteristicDifferential Privacy Without a Trusted Curator
Issues with the Trusted Curator Assumption§ Single point of failure: a DP curator might have other security vulnerabilities§ Conflicting incentives: valuable the data provides incentives for the curator to misbehave§ Requires agreement: a large number of individuals need to agree on who to trust

Randomized response: recall in py1 , . . . , yn q “ RRε px1 , . . . , xn q each yi depends only on xi
Multi-Party and Local Differential Privacy§ Dataset x distributed among m parties, party i owns ~xi§ Analyst initiates randomized protocol Π : X Ñ Y that interacts with the parties§ All the outputs produced by party i during Πpxq determine a mechanism Mi p~xi q§ Π is multi-party pε, δq-DP if each Mi is pε, δq-DP§ When each ~xi has size one we talk about local DP?

§ Utility loss: the difference between Op1{nq (Laplace) and Op1{of local DP

nq (RR) is characteristic

Outline

1. We Need Mathematics to Study Privacy? Seriously?
2. Differential Privacy: Definition, Properties and Basic Mechanisms
3. Differentially Private Machine Learning: ERM and Bayesian Learning
4. Variations on Differential Privacy: Concentrated DP and Local DP
5. Final Remarks

Beyond This Tutorial...
Additional Results§ More basic mechanisms: sparse vector technique and other selection mechanisms, private

data structures§ General theorems: everything is randomized response, lower bounds on utility,

computational hardness, optimal mechanisms, connections to generalization§ Database perspective: answering multiple queries on the same data, adaptive vs.

non-adaptive queries§ When global sensitivity is atypical: smoothed sensitivity, randomized DP§ Other privacy definitions: location privacy, pan DP, pufferfish privacy

Suggested Readings§ “The Algorithmic Foundations of Differential Privacy” [Dwork and Roth, 2014]§ “The Complexity of Differential Privacy” [Vadhan, 2017]

Some Open Research Directions
Bounds vs. Algorithms§ Few privacy analysis are tight: randomized response, Laplace mechanism, ε-DP

exponential mechanism§ Most complex mechanisms add too much noise (constants in bounds matter!)§ Alternative: calibrate noise using “exact” numerical computations instead of bounds§ Challenges: concentration bounds vs. exact densities, compositions, sub-sampling andother mixtures, approximate sampling
Correctness and Attacks§ Given a mechanism, it is not possible to test empirically if it is DP§ We can only resort to mathematical proofs to establish correctness (can be automated?)§ But we should have sanity-check to tools to break DP of candidate implementations§ Challenge: from pseudo-code to implementation things can go wrong (floating-point ‰ R)

Conclusion§ Differential privacy provides a formal notion of privacy satisfying many desirable

properties
Precise quantification of the privacy-utility trade-off
Robustness against powerful adversaries (eg. in the presence of side knowledge)§ Applicable to a wide range of data analysis problems§§§ Mature research field with a rich toolbox of mechanism design strategies§ Natural starting point for application-specific privacy guarantees§ Several real-world deployments and open source tools

Google Chrome’s RAPPORApple’s iOS 10§ U.S. Census Bureau§ GUPT, Microsoft’s PINQ, Uber’s FLEX§§

References I
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016).
Deep learning with differential privacy.
In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages
308–318. ACM.
Bassily, R., Smith, A. D., and Thakurta, A. (2014).
Private empirical risk minimization: Efficient algorithms and tight error bounds.
In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA,
USA, October 18-21, 2014, pages 464–473.
Bun, M. and Steinke, T. (2016).
Concentrated differential privacy: Simplifications, extensions, and lower bounds.
In Theory of Cryptography Conference, pages 635–658. Springer.
Dwork, C. (2006).
Differential privacy.
In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July
10-14, 2006, Proceedings, Part II, pages 1–12.

References II
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. (2006).
Calibrating noise to sensitivity in private data analysis.
In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA,
March 4-7, 2006, Proceedings, pages 265–284.
Dwork, C. and Roth, A. (2014).
The algorithmic foundations of differential privacy.
Foundations and Trends R in Theoretical Computer Science, 9(3–4):211–407.
Dwork, C. and Rothblum, G. N. (2016).
Concentrated differential privacy.
arXiv preprint arXiv:1603.01887.
Foulds, J. R., Geumlek, J., Welling, M., and Chaudhuri, K. (2016).
On the theory and practice of privacy-preserving bayesian data analysis.
In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI 2016, June
25-29, 2016, New York City, NY, USA.

References III
Jain, P. and Thakurta, A. G. (2014).
(near) dimension independent risk bounds for differentially private learning.
In International Conference on Machine Learning, pages 476–484.
McSherry, F. and Talwar, K. (2007).
Mechanism design via differential privacy.
In Foundations of Computer Science, 2007. FOCS’07. 48th Annual IEEE Symposium on, pages 94–103.
IEEE.
Minami, K., Arai, H., Sato, I., and Nakagawa, H. (2016).
Differential privacy without sensitivity.
In Advances in Neural Information Processing Systems, pages 956–964.
Mironov, I. (2017).
Renyi differential privacy.
arXiv preprint arXiv:1702.07476.

References IV
Park, M., Foulds, J. R., Chaudhuri, K., and Welling, M. (2016).
Variational bayes in private settings (VIPS).
CoRR, abs/1611.00340.
Talwar, K., Thakurta, A., and Zhang, L. (2014).
Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry.
CoRR, abs/1411.5417.
Vadhan, S. P. (2017).
The complexity of differential privacy.
In Tutorials on the Foundations of Cryptography., pages 347–450.
Wang, Y., Fienberg, S. E., and Smola, A. J. (2015).
Privacy for free: Posterior sampling and stochastic gradient monte carlo.
In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11
July 2015, pages 2493–2502.

References V

Warner, S. L. (1965).
Randomized response: A survey technique for eliminating evasive answer bias.
Journal of the American Statistical Association, 60(309):63–69.
Wu, X., Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J. F. (2016).
Differentially private stochastic gradient descent for in-rdbms analytics.
CoRR, abs/1606.04722.
Zhang, Z., Rubinstein, B. I. P., and Dimitrakakis, C. (2016).
On the differential privacy of bayesian inference.
In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix,
Arizona, USA., pages 2365–2371.

A Short Tutorial on Differential Privacy
Borja Balle
Amazon Research Cambridge

The Alan Turing Institute — January 26, 2018