Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guarantees than when run on the entire population. Several instances of this principle have been studied for different random subsampling methods, each with an ad-hoc analysis. In this paper we present a general method that recovers and improves prior analyses, yields lower bounds and derives new instances of privacy amplification by subsampling. Our method leverages a characterization of differential privacy as a divergence which emerged in the program verification community. Furthermore, it introduces new tools, including advanced joint convexity and privacy profiles, which might be of independent interest.
This paper derives differential privacy guarantees for algorithms that combines subsampling and differentially private mechanisms. It first presents some general tools, and then applies it to different subsampling methods. Analyzing the privacy amplification of subsampling is a very important and interesting problem in differentially private algorithm design. And this paper provides results on different sampling methods and algorithms with different privacy guarantees. More comparison with previous work would make the result more solid, and the presentation might be improved a bit for better readability.  More detailed comments: - It is important to mention related work which proves privacy bound of privacy amplification with sampling in more detail. For example, [1] provides a bound for Gaussian mechanism with sampling. How does the result compare? It might be good to illustrate the comparison with figures and values in some real scenarios. - The presentation in Section 3 might be more clear with subsections for divergences and privacy profiles. - I think Section 4 is an important (if not the most important) section of the paper. So giving it a more informative name may help emphasize its importance and the significance of the paper.    Small typo: - Line 11: there are two "introduces" - Line 114: is the "increasing" supposed to be "decreasing"? Otherwise this couldn't be compatible with limit equal to 0.