Synthetic population generation for nested data

using differentially private posteriors

Hang J. Kim1 Terrance Savitsky2 Matt Williams3

Monika Hu4

1University of Cincinnati (hang.kim@uc.edu)

2Bureau of Labor Statistics (Savitsky.Terrance@bls.gov)

3RTI International (mrwilliams@rti.org)

4Vassar College (jihu@vassar.edu)

FCSM

Oct 25, 2023

1
Outline

1 Motivating Examples

2 Review of Differential Privacy

3 Extensions to Nested Privacy

2
Motivating Data Structures

I Data Set with Nested Entities

I Students >> Teachers (class)

I Employees >> Owners (business)

I Patients >> Doctors (hospitals)

I Entities in each level may have

disclosure concerns

I poor performance

I sensitive responses

I competitive advantage

I risk of regulatory intervention

3
Motivating Models I Variance Decomposition I Attribute % of variability to

group vs. individual factors yig = μg + i μg ∼ N(ν, τ 2) i ∼ N(0, σ2)

I PISA 2000: Science Scores (US) I Average Score (top) I Between Class Variation (mid) I Individual Variation (bottom) I Different estimation methods

(columns/colors)

b0 sig_a sig_e

Double Single Unweighted

450

460

470

480

490

500

35

45

55

65

75

72.5

75.0

77.5

80.0

82.5

Method

Parameter

4
Outline

1 Motivating Examples

2 Review of Differential Privacy

3 Extensions to Nested Privacy

5
Differential privacy (Dwork et al., 2006)

Let D ∈ R

n×k

be a database in input space D. Let M be a randomized mechanism

such that M() : R

n×k → O. Then M is -differentially private if

Pr[M(D) ∈ O]

Pr[M(D

0

) ∈ O]

≤ exp(),

for all possible outputs O = Range(M) under all possible pairs of neighboring

datasets D, D

0

∈ D

- An output statistic f on database D: f (D)

- Global sensitivity ∆ = supD,D

0∈D: δ(D,D0

)=1 | f (D) − f (D

0

) |

- Definition of neighborhood - difference of an individual. We will

focus on Leave One Out (LOO).

- Laplace Mechanism for additive noise, scaled to be proportional to

∆G / with −DP guarantee

6
DP or not DP?

Why DP?

I Guarantee is global over all databases and provable.

I DP is property of a probabilistic mechanism. Plausible deniability.

I No explicit assumptions about intruder behaviors or knowledge

I Additivity of privacy guarantee across releases based on worst case

sensitivity (not averaging). Same privacy ‘currency’ for very different

data uses (tables, model output, public use file creation, etc).

I Privacy parameter  is a finite resource that needs to be budgeted.

7
DP or not DP?

Why not DP?

I Worst case sensitivity often ∞. Mechanisms with  < ∞ can be

challenging to prove (or implement).

I In practice assumptions of bounded data space not correct (e.g.

value of sales for a company).

I Supremum (maximum) criteria often severely injures data utility.

I Privacy is not really a single dimension  and is context-specific.

8
The Exponential Mechanism

I Wasserman and Zhou (2010); Zhang et al. (2016); Snoke and

Slavkovic (2018) propose the Exponential Mechanism (EM) to

generate synthetic data with DP properties.

I The EM generates samples from

θˆ ∝ exp (u(x, θ)) π (θ | γ), (1)

where u(x, θ) is a utility function with bound ∆u, π(θ | γ) is the

“base” distribution to ensure a proper density function (Zhang

et al., 2016; McSherry and Talwar, 2007).

I A single sample θˆ

j has a DP guarantee of  ≤ 2∆u.

I Using a globally bounded u(x, θ) is difficult. Rejection and

Metropolis Hastings sampling do not scale well with the dimension

of θ.

9
The Posterior Mechanism and the Exponential Mechanism

I Consider the log-likelihood function as the utility function, i.e.

u(x, θ) = log (Qn

i=1 π (xi

| θ)) and the prior distribution π(θ | γ) is

the base measure.

I Posterior Mechanism is an instantiation of the Exponential

Mechanism

exp log Yn

i=1

π (xi| θ)

!! π (θ | γ) = Yn

i=1

π (xi| θ)

!

π (θ | γ)

I Sampling from a Posterior is well researched and supported!

10
Generalizing the (Exponential and) Posterior Mechanisms

I To reduce  < 2∆u, modify the utility function u(x, θ).

I Rescale it: u

∗

(x, θ) = 

2∆u

u(x, θ) if ∆u < ∞. (See McSherry and

Talwar, 2007, among many others).

I Scalar-weighted pseudo-likelihood (posterior)

exp 

 log (Qn

i=1 π (xi

| θ))

2∆ 

ξ (θ | γ) = Yn

i=1

π (xi| θ)



2∆ !

π (θ | γ)

11
Pseudo Posterior Mechanism

I Savitsky et al. (2019) utilize record-indexed weights, α ∈ (0, 1]n

I To downweight likelihood contributions with high disclosure risk

ξ

α (θ | x, γ) ∝

"Yn

i=1

π (xi| θ)

αi

#

π (θ | γ)

I αi ∝ 1/ supθ∈Θ | fθ (xi) |

I Allows surgical downweighting of high risk records

I αi

induces an anti-informative prior

I Ensures ∆α < ∞

I Expected to better preserve real data distribution for any target

privacy budget, 

12
Outline

1 Motivating Examples

2 Review of Differential Privacy

3 Extensions to Nested Privacy

13
Extending the Neighborhood

I Leave-one-group-out (LOGO) or delete-a-group (DAG)

I Neighbors D and D

0 differ by an entire group (school, hospital,

business)

I Global sensitivity ∆G = supD,D

0∈D: δ(D,D0

)=1G

| f (D) − f (D

0

) |

LOO Neighbors

Records 1 2 3 4 5 6 7 8

A

B

C

D

E

F

G

H

DAG Neighbors

Records 1 2 3 4

A

B

C

D

E

F

G

H

14
Extending to Latent Variables

I Hierarchical Model

[ygi|μg ] ∼ N(μg , σ2),

[μg |ν] ∼ N(ν, τ 2)

with data as response ygi and group indicator 1g and latent group

mean μg .

I The utility function is then (the log of) the integrated likelihood

uG (x, θ) = X

G

g=1

log Z Yng

i=1

f (ygi|μg , σ2)

!

f (μg |ν, τ 2) dμg

I We assess the LOO and DAG sensitivities of uG (x, θ) to measure

the individual and group level DP bounds .

15
Extending the Weighting Approach

Where should we insert the weights?

u

A

G (x, θ) = X

G

g=1

αg log Z Yng

i=1

f (ygi|μg , σ2)

!

f (μg |ν, τ 2) dμg

u

B

G (x, θ) = X

G

g=1

log Z

" Yng

i=1

f (ygi|μg , σ2)

!

f (μg |ν, τ 2)

#αg

dμg

u

C

G (x, θ) = X

G

g=1

log Z

" Yng

i=1

f (ygi|μg , σ2)

αgi!

f (μg |ν, τ 2)

#αg

dμg

Option (A) requires us to have analytic integration for estimation. (B)

and (C) allow for data augmentation approaches for estimation. (C)

allows for individual-level tuning.

16
Preliminary Simulation Results

I G = 100 groups with ng = 50 individuals

I pg , pgi ∈ [0, 1]: approximate risk measures based on DAG and LOO

I All down-weighting schemes reduce group level sensitivity (Delta)

I Additional (vector) down-weighting of groups αg after vector

down-weighting of individuals αgi - little gain in privacy or utility

17
Group Level Sensitivity

18
Challenges and Future Work

I Calculating the sensitivities for LOO and DAG require tractable

integrals. Numeric and other approximations might be possible.

I Data augmentation can still be used for parameter generation.

I Most of the gains in privacy seem to come from the individual

weights αgi with little additional gains from αg . We are

investigating this more.

I Group level privacy  are naturally larger than individual level. While

an acceptable individual level  might be in [0.1, 10] - its not clear

what the target  for groups should be [ng /10, 10ng ] = [5, 500]?

19
References I

Dwork, C., McSherry, F., Nissim, K. and Smith, A. (2006), Calibrating noise to sensitivity in

private data analysis, in ‘Proceedings of the Third Conference on Theory of

Cryptography’, TCC’06, Springer-Verlag, Berlin, Heidelberg, pp. 265–284.

URL: http://dx.doi.org/10.1007/1168187814

McSherry, M. and Talwar, K. (2007), Mechanism design via differential privacy, in

‘Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science’,

pp. 94–103.

Savitsky, T. D., Williams, M. R. and Hu, J. (2019), ‘Bayesian Pseudo Posterior Mechanism

under Differential Privacy’, arXiv e-prints p. arXiv:1909.11796.

Snoke, J. and Slavkovic, A. (2018), pMSE mechanism: Differentially private synthetic data

with maximal distributional similarity., in J. Domingo-Ferrer and F. Montes, eds, ‘Privacy

in Statistical Databases’, Vol. 11126 of Lecture Notes in Computer Science, Springer,

pp. 138–159.

Wasserman, L. and Zhou, S. (2010), ‘A statistical framework for differential privacy’,

Journal of the American Statistical Association 105, 375–389.

Zhang, Z., Rubinstein, B. I. P. and Dimitrakakis, C. (2016), On the differential privacy of

Bayesian inference, in ‘Proceedings of the 30th AAAI Conference on Artificial

Intelligence’, AAAI, pp. 2365–2371.

20