Controlling Privacy Loss in Survey Sampling

Mark Bun (Boston University), Jörg Drechsler (IAB), 

Marco Gaboardi (Boston University), Audra McMillan (Apple), 

Jayshree Sarathy (Harvard University)

Outline

Background

Cluster sampling

Stratified sampling

General findings

Differential Privacy

Definition:

Mechanism  is -differentially private if for all datasets differing on one record, and for all sets ,

where the probabilities are (only) taken over the randomness in .

Framework

Framework

’ ?

Privacy amplification by subsampling

For simple random sampling with replacement, simple random sampling without replacement, and Poisson sampling

where  is the privacy loss parameter used by ,  is the sampling rate, and  is resulting privacy loss guarantee

Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith (2008)

... 

Balle, Barthe, and Gaboardi (2018)

Related Work

Poisson sampling: Kasiviswanathan et al. 2008, Beimel et al. 2010

Simple random sampling with replacement: Bun et al. 2015

Simple random sampling without replacement: Beimel et al. 2010, Bassily et al. 2014, Wang et al. 2016

Unified analysis through probabilistic couplings: Balle et al. 2018

Using amplification results in practice

Using amplification in practice 

Dataset S contains records, want to compute -DP proportion of employed individuals with 

Add Laplace noise with scale 1/300 

But, if S is a secret, simple random sample from a population P of individuals

Laplace noise with scale 1/300 will yield 

To get , add noise with scale only 1/3000

Intuition: Secrecy of sample -> more privacy -> less noise needed

This work

Q: Can we extend these results to more complex sampling designs? 

Privacy amplification not guaranteed for more complex sampling designs 

Examples from cluster and stratified sampling

Insight into more general sampling designs

Cluster sampling

P

...

Cluster sampling

Negligible amplification if size of clusters is large!

Intuition:

Large clusters -> less secrecy of sample

Privacy of records within cluster may not protect privacy of chosen clusters

Multi-stage cluster sampling

P

...

Stratified sampling

P

...

Stratified differential privacy

Suppose there are  strata. Let  denote stratum in question and  denote an individual datapoint.

Definition: 

A mechanism satisfies -stratified differential privacy if for all datasets P and datapoints  andare indistinguishable.

Allows for different values of  for each stratum.

Protects datapoint and stratum it belongs to.

Stratified sampling, proportional allocation

Constant sampling rate within each stratum

Deterministic rounding (ie. take ceiling of ) can leak information about the dataset

Example: Neighboring datasets , 

Always sample 1 records from  and 2 records from 

No privacy amplification: !

How can we fix this?

Stratified sampling, proportional allocation

Constant sampling rate within each stratum

Randomized rounding 

Let 

With probability sample 

Example: Neighboring datasets , 

Always sample 1 records from sample 1 or 2 records from 

Regain privacy amplification: !

Randomized data-independent sampling rate

Let  be a distribution over sample sizes.

Draw  and sample  records from  without replacement.

	Then,  / 

where  for all .

To get amplification,  must be concentrated away from ! 

Randomized data-dependent sampling rate

Let  denote the data-dependent function that returns the sample size.

Eg. Neyman allocation:

Let  denote a randomized approximation of 

To get privacy amplification,  needs to have large variance

Challenge for budgeting in practice: may need to sample many more records than planned

Proportional vs. Neyman allocation

What is optimal in the non-private setting may not be optimal in the private setting

Proportional allocation can perform better than Neyman allocation in high privacy regimes

Discussion question: what practical settings to test this finding?

Conclusion

Intuitively, sampling can increase the privacy amplification

But, privacy amplification not guaranteed for complex sampling designs

Amplification can be negligible even when only a small fraction of the population is included in the final sample

If sampling design is data-dependent, privacy degradation can occur -- the sample design itself can reveal sensitive information

Thank you!

Results

Positive results

Stratified sampling + proportional allocation with randomized rounding 

Negative results

Cluster sampling 

Stratified sampling + proportional allocation with deterministic rounding

Data-dependent sampling schemes

Neyman allocation

# image1.png

# image2.png

# image3.png

# image4.png

# image5.png

# image6.png

# image7.png

# image8.png

# image9.png

# image10.png

# image11.png

# image12.png

# image17.png

# image13.png

# image14.png

# image15.png

# image16.png

# image18.png

# image19.png

# image20.png

# image21.png

# image22.png

# image23.png

# image24.png

# image25.emf

# image26.png

# image27.png

# image28.png