Accuracy Gains from Privacy Amplification through

Sampling for Differential Privacy

Jingchen (Monika) Hu

Vassar College

Joint work with Jorg Drechsler and Hang J. Kim  ̈

FCSM 2021

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 1 / 12
Background

For simple random sample without replacement:

Population parameter: g(YN ); sample estimator: g(S(YN ))

Goal: achieve (, δ)-DP for g(YN )

Method 1: Add noise according to (, δ) to g(YN )

Method 2: Add noise according to (n, δn) to g(S(YN ))

Amplification effects: n > , δn > δ, therefore less noise to be

added (Li et al. (2012))

n = log(1 + N/n(e

 − 1))

δn = (N/n)δ

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 2 / 12
Population mean

−DP and add noise with Laplace Mechanism based on global

sensitivity

Method 1: Add noise according to  to g(YN )

Laplace Mechanism, global sensitivity ∆G = R/N

The variance of the privatized population parameter is

VN = Var(A( ̄yN )) = 2 

R

N 2

(1)

Method 2: Add noise according to n to g(S(YN ))

Laplace Mechanism, global sensitivity ∆G

n = R/n

The total variance of the privatized sample mean is

Vn = Var(A( ̄yn)) = 1 −

n

N

 S

2

N

n

+ 2 

R

nn

2

(2)

Difficult to get accuracy gains if the sensitivity strongly depends on

the sample size; also need to consider sampling variance

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 3 / 12
Population median

(, δ)−DP and add Laplace noise based on smooth sensitivity (Nissim

et al. (2007))

Method 1: Add noise according to (, δ) to g(YN )

Laplace noise, smooth sensitivity ∆S

,δ(YN )

Method 2: Add noise according to (n, δn) to g(S(YN ))

Laplace noise, smooth sensitivity ∆S

n,δn

(S(YN ))

Accuracy gains? No analytical solution...

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 4 / 12
Population median of a lognormal

N = 10, 001

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 5 / 12
Population median of a lognormal

log(MSE) of privatized sample medians (1000 repeated samples)

Accuracy gains for  ≤ 0.1 (too small to be used in practice)

No gains for  = 0.5 and  = 1 (and larger values)

Reason: no reduced sensitivity

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 6 / 12
Population median of a lognormal

Ratio of the smooth sensitivity of the sample over the smooth

sensitivity of the population

No reduced sensitivity and amplified values of (n, δn): no accuracy

gains

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 7 / 12
Population median of two scaled and shifted betas

N = 10, 001

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 8 / 12
Population median of two scaled and shifted betas

log(MSE) of privatized sample medians (1000 repeated samples)

Accuracy gains for all  values being considered

Reason: reduced sensitivity

Jingchen (Monika) Hu Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy 9 / 12
Population median of two scaled and shifted betas

Ratio of the smooth sensitivity of the sample over the smooth

sensitivity of the population

Reduced sensitivity and amplified values of (n, δn): accuracy gains

Jingchen (Monika) Hu

Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy

10 / 12
Summary and future work

No accuracy gains for population mean with global sensitivity and

−DP

For Lognormal(5, 0.5) with smooth sensitivity and (, δ)−DP,

accuracy gains with small 

For mixture of two scaled and shifted betas with smooth sensitivity

and (, δ)−DP, accuracy gains for a range of  values (as large as

 = 1)

Key: Whether the sensitivity can reduced in the sample; if not, no

accuracy gains to be expected; sampling variance also needs to

be considered

Future work: derive the optimal sampling rate from an accuracy

perspective, extend to other mechanisms and other statistics, etc.

Jingchen (Monika) Hu

Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy

11 / 12
Summary and future work

No accuracy gains for population mean with global sensitivity and

−DP

For Lognormal(5, 0.5) with smooth sensitivity and (, δ)−DP,

accuracy gains with small 

For mixture of two scaled and shifted betas with smooth sensitivity

and (, δ)−DP, accuracy gains for a range of  values (as large as

 = 1)

Key: Whether the sensitivity can reduced in the sample; if not, no

accuracy gains to be expected; sampling variance also needs to

be considered

Future work: derive the optimal sampling rate from an accuracy

perspective, extend to other mechanisms and other statistics, etc.

Jingchen (Monika) Hu

Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy

11 / 12
Summary and future work

No accuracy gains for population mean with global sensitivity and

−DP

For Lognormal(5, 0.5) with smooth sensitivity and (, δ)−DP,

accuracy gains with small 

For mixture of two scaled and shifted betas with smooth sensitivity

and (, δ)−DP, accuracy gains for a range of  values (as large as

 = 1)

Key: Whether the sensitivity can reduced in the sample; if not, no

accuracy gains to be expected; sampling variance also needs to

be considered

Future work: derive the optimal sampling rate from an accuracy

perspective, extend to other mechanisms and other statistics, etc.

Jingchen (Monika) Hu

Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy

11 / 12
References

Hu, J., Drechsler, J. and Kim, H. J., Accuracy gains from privacy

amplification through sampling for differential privacy. arXiv:

2103.09705.

Li, N., Qardaji, W., and Su, D. (2012), On sampling,

anonymization, and differential privacy or k-anonymization meets

differential privacy. In Proceedings of the 7th ACM Symposium on

Information, Computer, and Communications Society, 32-33.

Nissim, K., Raskhodnikova, S., and Smith, A. (2007), Smooth

sensitivity and sampling in private data analysis. In Proceedings

of the 39th Annual ACM Symposium on Theory of Computing, 75

- 83.

Jingchen (Monika) Hu

Accuracy Gains from Privacy Amplification through Sampling for Differential Privacy

12 / 12