|Borja Balle||Amazon Research Cambridge|
|Gilles Barthe||IMDEA Software Institute|
|Marco Gaboardi||Univeristy at Buffalo|
Differential privacy comes equipped with multiple analytical tools for thedesign of private data analyses.
Differential privacy comes equipped with multiple analytical tools for thedesign of private data analyses. One important tool is the so-called "privacyamplification by subsampling" principle, which ensures that a differentiallyprivate mechanism run on a random subsample of a population provides higherprivacy guarantees than when run on the entire population. Several instancesof this principle have been studied for different random subsampling methods,each with an ad-hoc analysis. In this paper we present a general method thatrecovers and improves prior analyses, yields lower bounds and derives newinstances of privacy amplification by subsampling. Our method leverages acharacterization of differential privacy as a divergence which emerged in theprogram verification community. Furthermore, it introduces new tools,including advanced joint convexity and privacy profiles, which might be ofindependent interest.