Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences

By Borja Balle, Gilles Barthe, Marco Gaboardi. 2018

492 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “Beyond privacy ampliﬁcation by shuﬄing (Erlingsson et al., 2019; Balle et al., 2019b; Feldman et al., 2020) (based on the shuﬄing primitive mentioned above), we can mention ampliﬁcation by subsampling (Balle et al., 2018) and ampliﬁcation by iteration (Feldman et al., 2018).”
Privacy Amplification via Random Check-Ins (2020, methodology): “The desired bound is then obtained by using the overlapping mixtures technique [5] to show that B is log(1 + p0qi(e0 − 1))-DP with respect to changes on d1, and heterogeneous advanced composition [24] to compute the final ε of composing the B adaptively.”
Federated Learning and Differential Privacy: Software tools analysis, the Sherpa.ai FL framework and methodological guidelines for preserving data privacy (2020, background): “That is, if an ( (cid:101) , δ )-differentially private mechanism is used to query random subsample from a database with n records, then an improved ( (cid:101) (cid:48) , δ (cid:48) ) parameters can be provided according to the type of random subsample [23].”
The Privacy Blanket of the Shuffle Model (2019, methodology): “On the one hand, the randomizer may need to output y ∈ [0, 1] on input x ∈ [0, 1] such that |x− y| is small, to promote accuracy.”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “For the case of ( (cid:15), δ ) -DP, Balle et al. (2018) provide a uniﬁed account of privacy ampliﬁcation techniques for diﬀerent types of subsampling and dataset neighboring relations.”
Federated Model Distillation with Noise-Free Differential Privacy (2020, methodology): “We remark that sampling can individually serve as a privacy amplification method to tighten the privacy budget of a differentially private algorithm [Balle et al., 2018], which is in sharp contrast with the inherent privacy guarantee of sampling given in this paper.”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “This lack of clarity is especially concerning because of recent formal results—known colloquially as “privacy amplification by shuffling” [3], [13], [14], [19]—which have fundamentally changed privacy/utility tradeoffs and forced a reconsideration of previous approaches, like those described above.”
AN EMPIRICAL STUDY (2022, unknown): “The random sampling of SGD is implicitly used for privacy amplification [3] in DP-SGD [2].”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, unknown): “Almost all of these inheritances are immediate and we present them in the full version of the paper.”
Poission Subsampled Rényi Differential Privacy (2019, methodology): “The privacy amplification lemma was derived in (Kasiviswanathan et al., 2011; Beimel et al., 2013; Li et al., 2012), where all three authors adopted what Balle et al. (2018) calls Poisson subsampling: Definition 3 (PoissonSample).”
Large-Scale Differentially Private BERT (2021, methodology): “Now, in order for each step be ( (cid:15) 0 , δ 0 ) -DP, we may apply the ampliﬁcation-by-subsampling theorem (Balle et al., 2018) with sampling probability p = q/n .”
Private-kNN: Practical Differential Privacy for Computer Vision (2020, background): “The result of this style is also known as “subsampling lemma” or “secrecy of the samples” in the literature [2].”
Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning (2021, background): “Since then, many works [13, 2, 54, 41, 31, 3] improved the analysis of the Moments Accountant analysis to get better theoretical privacy bounds.”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “…with probability q, leading to variable-sized minibatches) is commonly analyzed using the add-or-remove notion of adjacency, while uniform subsampling (of fixed sized batches independently on each round) is analyzed with the replace-one notion of adjacency (Wang et al., 2019b; Balle et al., 2018).”