Privacy Amplification By Subsampling: Tight Analyses Via Couplings And Divergences

Authors:
Borja Balle Amazon Research Cambridge
Gilles Barthe IMDEA Software Institute
Marco Gaboardi Univeristy at Buffalo

Introduction:

Differential privacy comes equipped with multiple analytical tools for thedesign of private data analyses.

Abstract:

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.

You may want to know: