Comparison of Poisson-Gamma and Laplace Mechanisms for

Differential Privacy

Harrison Quick (Drexel University)
Table of Contents

Motivating Use-Case: CDC WONDER

Generating Differentially Private Synthetic Data

Illustrative Example: Cancer Mortality in Pennsylvania

Summary
Table of Contents

Motivating Use-Case: CDC WONDER

Generating Differentially Private Synthetic Data

Illustrative Example: Cancer Mortality in Pennsylvania

Summary
CDC WONDER
CDC WONDER

County-level heart disease-related death counts for ages 35–44 in 2016 from all races

and all genders

All counts less than 10 are suppressed in public-use datasets
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Racial disparities

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Racial disparities

I Differences by sex

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Racial disparities

I Differences by sex

I Differences by age

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Racial disparities

I Differences by sex

I Differences by age

I Differences by cause-of-death

I Privacy

Is there a way that CDC can address these issues?
CDC WONDER

While CDC WONDER offers a wealth of data and does implement privacy protections,

there is still room for improvement:

I Utility: Suppression of small counts affects users’ ability to assess...

I Urban/Rural disparities

I Racial disparities

I Differences by sex

I Differences by age

I Differences by cause-of-death

I Privacy

I Targeted attacks by clever intruders can overcome data suppression to uncover the

true counts

Is there a way that CDC can address these issues?
Table of Contents

Motivating Use-Case: CDC WONDER

Generating Differentially Private Synthetic Data

Illustrative Example: Cancer Mortality in Pennsylvania

Summary
Synthetic Data

One option to address the issue of data suppression would be to release synthetic data:

e.g., if

I y = (y1, . . . , yI)

T

denotes a restricted-use dataset of I observations,

I p (y | φ) is an appropriate statistical model for y with parameters φ, and

I p (φ | ψ) is a prior distribution for φ given hyperparameters, ψ,

then we can generate a synthetic dataset, z = (z1, . . . , zI)

T

, from the posterior

predictive distribution,

p (z | y, ψ) = Zp (z | φ) p (φ | y, ψ) dφ.

That is, we can sample φ

∗

from p (φ | y, ψ) and then sample z from p (z | φ

∗

).

I Natural next question: How do we know if synthetic data generated from

p (z | y, ψ) are sufficiently protective?
Differential Privacy (Dwork, 2006)

The standard typically used for demonstrating formal privacy guarantees is the concept

of differential privacy (Dwork, 2006).

In this context, p (z | y, ψ) is -differentially private if for any similar1 dataset, x,









log p (z | y, ψ)

p (z | x, ψ)









≤ . (1)

While ψ can be viewed as a vector of model parameters, in practice the elements of ψ

are merely specified to satisfy -differential privacy.

1

kx − yk = 2 and P

i

xi =

P

i

yi — i.e., there exists i and i

0

such that xi = yi − 1 and xi

0 = yi0 + 1

with all other values equal
What is Differential Privacy? Simple (Conventional) Example

Suppose we want to release the proportion of

triangles in this dataset without disclosing any

individual shape.

I Worst case scenario: Intruder knows all

but one shape

I Releasing the true value (8/14)

compromises the remaining shape

I Let’s add noise to the proportion such that

8 + noise

14

≈

7 + noise

14

where the amount of noise depends on the

level of protection desired (measured by )

I e.g., noise ∼ Lap (0, 1/)
Laplace Mechanism

In theory, the Laplace mechanism is pretty straightforward:

zi = yi + ei, where ei ∼ Lap (0, 1/)

but because the Laplace mechanism can produce negative values, some post processing

is required to produce sensible values.

I Suppose we desire synthetic values zi ≥ 0, for i = 1, . . . , I such that P

i

zi = z·,

then we can let

z

∗

i = dyi + ei e

+, where ei ∼ Lap (0, 1/),

zi = z

∗

i × P

z·

i

z

∗

i

I Note: This approach will produce non-integer values, but that feels less awkward

than negative values...
Laplace Mechanism with Hierarchical Structure

Now suppose our data are indexed by multiple factors (e.g., age, race, county),

denoted yijk . While we could simply let zijk be defined by

z

∗

ijk = dyijk + eijk e

+, where eijk ∼ Lap (0, 1/),

zijk = z

∗

ijk ×

P

ijk yijk

P

ijk z

∗

ijk

,

we may instead try to preserve utility at certain aggregate levels; e.g.,

zi·· = z

∗

i·· × P

z···

i

z

∗

i··

, where z

∗

i·· = dyi·· + ei··e

+ and ei·· ∼ Lap (0, 1/1)

zij· = z

∗

ij· × P

zi··

j

z

∗

ij·

, where z

∗

ij· = dyij· + eij·e

+ and eij· ∼ Lap (0, 1/2)

zijk = z

∗

ijk × P

zij·

k

z

∗

ijk

, where z

∗

ijk = dyijk + eijk e

+ and eijk ∼ Lap (0, 1/3)

such that 1 + 2 + 3 =  and where z··· = y··· =

P

ijk yijk .
A Working Hypothesis...

The hypothesis underlying my work in data privacy is that synthetic data generated

from the true data generating process will outperform a noisy version of the true data.

Thus, my strategy is to specify a model that (a) is statistically appropriate and (b) can

be proven to satisfy differential privacy, and then hope the posterior predictive

distribution can approximate the true data generating process.

I In the next few slides, I’ll discuss two simple model specifications — the

multinomial-Dirichlet model and the Poisson-gamma model — that have been

proven to satisfy differential privacy.

I Along the way, I will discuss the appropriateness of these models for synthesizing

public health data — e.g., county-level death counts.
Multinomial-Dirichlet model (Machanavajjhala et al., 2008)

Let y be a vector of sensitive count data of length I ≥ 2 with P

i

yi = y· and assume

y | θ ∼ Mult (y·, θ) and θ ∼ Dir (α).

To generate a synthetic data vector, z, with a given P

i

zi = z· = y·:

1. Sample θ

∗

from its posterior, θ | y ∼ Dir (y + α)

2. Sample z from the posterior predictive distribution, z ∼ Mult (z·, θ

∗

)

It can (but won’t) be shown that if

min αi ≥ z·/ [exp () − 1] ,

the multinomial-Dirichlet synthesizer, p (z | y, α), will satisfy -differential privacy.

I If our Dir (α) prior is informative enough, it can sufficiently mask the data...

I ... but it will do so by allocating events uniformly, which is bad.

I e.g., if  is small, the model will try to assign the same number of deaths to Small

Town, PA as it would to Philadelphia.
Poisson-Gamma model (Quick, 2021)

Motivated by the field of disease mapping — where death data are typically modeled

as being Poisson distributed — Quick (2021) proposed assuming

yi| λi ∼ Pois (niλi) and λi ∼ Gamma (ai, bi)

which implies λi| yi ∼ Gamma (yi + ai, ni + bi). Now recall that if the yi are

(conditionally) independent Poisson random variables, then

y |λ,

X

i

yi = y· ∼ Mult y·,

(

P

niλi

j

njλj

)!

Thus, we can generate synthetic data by:

1. Sampling λ

∗

i

from Gamma (yi + ai, ni + bi) for i = 1, . . . , I

2. Sampling z ∼ Mult z·,

n

niλ

∗

i

/

P

j

njλ

∗

j

o

But under what conditions will this satisfy -differential privacy?
Poisson-Gamma model — -differential privacy

It can (but won’t) be shown that the Poisson-gamma synthesizer, denoted

p (z | y, a, b), will satisfy -differential privacy if

ai ≥

z·

e

/νi − 1

(2)

where νi ∈ [1, 2] denotes what amounts to a penalty term associated with the

additional information gained from using the Poisson-gamma model compared to the

multinomial-Dirichlet model.

I It would take too much time/space to write out the expression for νi

, but it’s a

function of the group-specific population sizes and prior event rates.

I If the group-specific population sizes and prior event rates are equal, then νi = 1

for all groups, thus making the M-D and P-G models mathematically equivalent.
Drawback of the Poisson-Gamma model of Quick (2021)

Unlike the multinomial-Dirichlet model, the Poisson-gamma model behaves fairly well

when  is small.

I i.e., the model will allocate events based on the population sizes, ni

, and the prior

expected event rates, λi0 = ai/bi, thus if these values were chosen “wisely”, we

won’t get terrible synthetic data like Small Town, PA ≈ Philadelphia

Unfortunately, another problem with the multinomial-Dirichlet model that is shared by

the Poisson-gamma model of Quick (2021) is that when the total number of events,

y·, is large, very informative priors are required to satisfy even moderate values of .

I While it is unlikely that Small Town, PA would be assigned as many deaths as

Philadelphia, our privacy protections are designed to guard against this possibility,

and that’s where the issues arise.

As a result, the synthetic data typically just reflect the prior information.
Prior Predictive Truncated Poisson-Gamma model (Quick, 2022)

To combat this, Quick (2022) proposed using the prior predictive distribution to

truncate the synthetic data to a “reasonable” range of values.

0 20 40 60 80 100

1.0 1.5 2.0 2.5

Number of Synthetic Events

Differential Privacy Ratio

Standard

PP Trun.

Bounds

Group 1

Group 2 Example on the left has E [y | a, b] = (15, 85)T

and  = 1

I Standard approach: Risk increases slowly up to e

1 = 2.71 at z1 = 100.

I Truncated approach: Risk increases quickly up to e

1 = 2.71 at z1 = 30.

The speed of the risk increase is driven by how not informative the prior distribution is

I Plot on the right is from the cancer example I will talk about momentarily...
Table of Contents

Motivating Use-Case: CDC WONDER

Generating Differentially Private Synthetic Data

Illustrative Example: Cancer Mortality in Pennsylvania

Summary
Cancer-related Deaths in Pennsylvania Counties in 1980

Attribute Levels

County i = 1, . . . , 67 Counties in Pennsylvania

Cancer Type

c = 1, . . . , 9 Forms of Cancer

Cancers of the lip, oral cavity, and pharynx (ICD-9: 140–149);

Cancers of the digestive organs and peritoneum (ICD-9: 150–159);

Cancers of the respiratory and intrathoracic organs (ICD-9: 160–165)

Cancers of the breast (ICD-9: 174–175);

Cancers of the genital organs (ICD-9: 179–187);

Cancers of the urinary organs (ICD-9: 188–189);

Cancers of all other and unspecified sites (ICD-9: 170–173, 190–199);

Leukemia (ICD-9: 204–208);

and all other cancers of the lymphatic and hematopoietic tissues (ICD-9: 200–203)

Age

a = 1, . . . , 13 Levels

Ages under 1; Ages 1–4; Ages 5–9; Ages 10–14; Ages 15–19; Ages 20–24; Ages 25–34;

Ages 35–44; Ages 45–54; Ages 55–64; Ages 65–74; Ages 75–84; and Ages 85 and older

Race r = 1, . . . , 3 Levels (Black, White, and Other)

Sex s = 1, 2 Levels (Male and Female)

In total, there were y· =

P

icars yicars = 26,116 cancer-related deaths in PA in 1980

belonging to these 67 × 13 × 9 × 3 × 2 = 47,034 strata.
Cancer-related Deaths in Pennsylvania Counties in 1980

Attribute Levels

County i = 1, . . . , 67 Counties in Pennsylvania

Cancer Type

c = 1, . . . , 9 Forms of Cancer

Cancers of the lip, oral cavity, and pharynx (ICD-9: 140–149);

Cancers of the digestive organs and peritoneum (ICD-9: 150–159);

Cancers of the respiratory and intrathoracic organs (ICD-9: 160–165)

Cancers of the breast (ICD-9: 174–175);

Cancers of the genital organs (ICD-9: 179–187);

Cancers of the urinary organs (ICD-9: 188–189);

Cancers of all other and unspecified sites (ICD-9: 170–173, 190–199);

Leukemia (ICD-9: 204–208);

and all other cancers of the lymphatic and hematopoietic tissues (ICD-9: 200–203)

Age

a = 1, . . . , 13 Levels

Ages under 1; Ages 1–4; Ages 5–9; Ages 10–14; Ages 15–19; Ages 20–24; Ages 25–34;

Ages 35–44; Ages 45–54; Ages 55–64; Ages 65–74; Ages 75–84; and Ages 85 and older

Race r = 1, . . . , 3 Levels (Black, White, and Other)

Sex s = 1, 2 Levels (Male and Female)

In total, there were y· =

P

icars yicars = 26,116 cancer-related deaths in PA in 1980

belonging to these 67 × 13 × 9 × 3 × 2 = 47,034 strata.

I Over 42,000 of the death counts are zero
How Good is our Prior Information?

Years of Age

Deaths per 100,000

0 20 40 60 80

0 0.1 1 10 1000

Lip

Digestive

Lung

Other/Unspec.

Breast

Genital

Urinary

Other Lymph.

Leukemia

US Average

PA Average

Figure 1: Cause-specific death rates at the national level and for the state of Pennsylvania.

National-level rates are used as prior information for estimating the proper allocation of deaths

at the state and county level.
What do the Poisson-Gamma Synthetic Data Look Like?

(a) Group with small y, E (y | a, b) (b) Group with large y, E (y | a, b)

Figure 2: Posterior predictive distribution for various levels of . In Panel (a), the prior

predictive expected value is E [y | a, b] = 1.15 and the true death count is y = 0. In Panel (b),

the prior predictive expected value is E [y | a, b] = 211 and the true death count is y = 237.

I As  → 0, the synthetic values shift away from y toward E [y | a, b].
Hierarchical Strategy for Laplace mechanism

To do our comparison, we will consider:

I No hierarchy

I One-level hierarchy

I Add noise to the [County], [Age], [Cause], [Race], or [Sex] specific totals

I Most of the privacy budget allocated to top level of hierarchy

I I plan(ned) to explore different privacy budget allocations, but I haven’t yet :/

I Selected two-level hierarchies

I Selected three-level hierarchies

I Selected four-level hierarchies

I Multilevel hierarchies selected for each inferential question (you’ll see what I mean)

Note: All designs preserve the state-level total number of deaths (i.e., it’s invariant).
What do the Laplace-Sanitized Values Look Like?

(a) y = 0, Various  (b)  = 2, Various y

Figure 3: Sampling distribution of the Laplace-sanitized values (with no hierarchical structure).

Panel (a) shows the distribution of values when is y = 0 for various levels of , while Panel (b)

shows the distribution of values for  = 2 for y ∈ [0, 10].

I As  → 0, the bias for E [z | y = 0] increases

I Because of the disproportionate number of zeros in our dataset, all other values of

E [z | y] are also biased
Age-Adjusted Cancer Death Rates — Poisson-Gamma

(a) True Age-Adjusted Rates (b) Synthetic Age-Adjusted Rates

Death Rate

(per 100,000)

Below 193

193 − 200

200 − 207

207 − 214

214 − 221

Over 221

Figure 4: Degradation in utility for the age-adjusted rates as  decreases.

I For large , geographic disparities in the data are largely preserved

I As  → 0, the prior — which does not account for geographic disparities —

becomes more influential and the rates all converge toward the statewide average
Urban/Rural Disparities in Cancer Death Rates

0 1 2 3 4

0.7 0.9 1.1

Privacy Budget (ε)

Urban/Rural Disparity

Truth

Prior

Poisson−Gamma

Laplace

(a) “Best” Case Scenario (b) Other Scenarios

Figure 5: Estimated urban/rural disparities. Values based on the true data (dashed lines) and

the prior information (dotted lines) are provided for reference, while the shaded bounds

represent the variability of the synthetic data.

I Poisson-gamma approach generally provides estimates between truth and the prior

I Laplace performs best when county-level totals are targeted, otherwise... :/
Black/White Disparities in Cancer Death Rates Among Males

0 1 2 3 4

0.8 1.2 1.6

Privacy Budget (ε)

Black/White Disparity

Truth

Prior

Poisson−Gamma

Laplace

(a) “Best” Case Scenario (b) Other Scenarios

Figure 6: Estimated black/white disparities. Values based on the true data (dashed lines) and

the prior information (dotted lines) are provided for reference, while the shaded bounds

represent the variability of the synthetic data.

I Poisson-gamma approach generally provides estimates between truth and the prior

I Laplace performs decently when race+age totals are targeted, otherwise it’s mixed or bad
Gender Disparities in Breast Cancer Death Rates

0 1 2 3 4

0 200 500

Privacy Budget (ε)

Gender Disparity

Truth

Prior

Poisson−Gamma

Laplace

(a) “Best” Case Scenario (b) Other Scenarios

Figure 7: Estimated female/male disparity in breast cancer death rates. Values based on the

true data (dashed lines) and the prior information (dotted lines) are provided for reference,

while the shaded bounds represent the variability of the synthetic data.

I Poisson-gamma approach generally provides estimates between truth and the prior

I Laplace performs decently when cause+sex+age totals are targeted, otherwise it’s BAD
Table of Contents

Motivating Use-Case: CDC WONDER

Generating Differentially Private Synthetic Data

Illustrative Example: Cancer Mortality in Pennsylvania

Summary
Summary

Based on this work, I claim:

I Using additive noise / “output perturbation” approaches to satisfy differential

privacy — while convenient — will be inferior to sampling from the true data

generating process

I While hierarchical designs can help preserve inference on certain quantities (e.g.,

urban/rural disparities), it quickly devolves into a game of whack-a-mole as

improving inference on one quantity will likely erode inference on many others.

I Samples from a posterior predictive distribution that aims to approximate the true

data generating process can still perform well

I Good prior information can keep your synthetic values in the right ballpark

I Minimizing the informativeness of the priors allows the data to dictate what happens