  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. We find that not only do these
sampling schemes often fail to amplify privacy, they can actually result in
privacy degradation. We analyze the privacy implications of the pervasive
cluster sampling and stratified sampling paradigms, as well as provide some
insight into the study of more general sampling designs.
