Controlling Privacy Loss in Sampling Schemes: an Analysis of Stratified and Cluster Sampling

Understand

Sampling schemes are fundamental tools in statistics, survey design, and algorithm design.

• A fundamental result in differential privacy is that a differentially private mechanism run on a simple random sample of a population provides stronger privacy guarantees than the same algorithm run on the entire population.
• However, in practice, sampling designs are often more complex than the simple, data-independent sampling schemes that are addressed in prior work.
• In this work, we extend the study of privacy amplification results to more complex, data-dependent sampling schemes.