The Composition Theorem for Differential Privacy
By Peter Kairouz, Sewoong Oh, Pramod Viswanath. 2013
825 citations recorded by the source corpus.
Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of a data processing inequality along with its converse. Our result improves over the state of the art, and has immediate connections to several problems studied in the literature.
Subfields: Artificial Intelligence, Statistics and Probability, Privacy & Security, Information Theory
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
- Peter Kairouz
- Abhradeep Thakurta
- Florian Tramèr
- Percy Liang
- H. Brendan McMahan
- Nicholas Carlini
- Dawn Song
- Qiang Yang
In Statistics and Probability
- Yu-Xiang Wang
- Jonathan Ullman
- Abhradeep Thakurta
- Jayadev Acharya
- Peter Kairouz
- Ziteng Sun
- Borja Balle
- Salil P. Vadhan
In Privacy & Security
- Peter Kairouz
- Abhradeep Thakurta
- Borja Balle
- Jonathan Ullman
- Thomas Steinke
- Yu-Xiang Wang
- Kunal Talwar
- H. Brendan McMahan
In Information Theory
- Yu-Xiang Wang
- Borja Balle
- Ziteng Sun
- Albert Cheu
- Jonathan Ullman
- Ilya Mironov
- Peter Kairouz
- Adam D. Smith
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, methodology): “To track the overall privacy budget across rounds, advanced composition theorems [148, 221] or the analytical moments accountant method developed in [7, 297, 299, 405] can be used.”
- 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): “The composition of a sequence {M k } of ( i , δ i )- differentially private mechanisms under the Composition experiment with More advanced versions of Equation 14 that allow the composition of private mechanisms with diverse (cid:101) and δ values and provide tighter bounds can be found in [21].”
- Privacy in Deep Learning: A Survey (2020, background): “It has been shown that tighter privacy bound for composition can be reached, so that the privacy budget decreases sub-linearly [56, 57].”
- Generative Models for Effective ML on Private, Decentralized Datasets (2019, methodology): “using the strong composition theorem for DP (Mironov, 2017; Kairouz et al., 2017).”
- AdaCliP: Adaptive Clipping for Private SGD (2019, background): “For the Gaussian mechanism, [14] introduced moments accountant, which provides tighter privacy bounds compared to other composition theorems [33, 34, 35, 34, 36].”
- Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “We consider two baselines: the naïve composition that simply adds up ( (cid:15), δ ) and the strong composition is through the result of (Kairouz et al., 2015) with an optimal choice of per-round δ parameter computed for every k .”
- Differentially-Private "Draw and Discard" Machine Learning (2018, background): “le privacy parameter, but allow multiple collections from the same user over time. Formally, this corresponds to the privacy loss growing as the number of items submitted, as per composition theorems [14, 24]. 6.3.1 Feature-level Privacy. We offer feature-level local differential privacy and, theref”
- cpSGD: Communication-efficient and differentially-private distributed SGD (2018, background): “5 [19]) or moments accounting [2] can be used to relate the privacy guarantee of SGD to that of gradient mean estimate at each instance t.”
- Personalized and Private Peer-to-Peer Machine Learning (2017, background): “The composition of several DP mechanisms remains DP, albeit a graceful degradation in the parameters (see Dwork et al., 2010; Kairouz et al., 2015, for strong composition results).”
- Rényi Differential Privacy (2017, methodology): “[7] for an optimal bound on composition of homogeneous mechanisms and Murtagh and Vadhan [8] for hardness results and an approximation scheme for composition of mechanisms with heterogeneous privacy guarantees.”
- A Hybrid Approach to Privacy-Preserving Federated Learning (2018, methodology): “When an algorithm requires multiple additive noise mechanisms, the evaluation of the privacy guarantee follows from the basic composition theorem [14, 15] or from advanced composition theorems and their extensions [7, 17, 18, 23].”
- PacGAN: The Power of Two Samples in Generative Adversarial Networks (2017, methodology): “This was used to prove strong composition theorems in differential privacy [34] and to identify the optimal differentially-private mechanisms under local privacy [32] and multi-party communications [33].”