Boosting and Differential Privacy

By Cynthia Dwork, Guy N. Rothblum, Salil P. Vadhan. 2010

1,092 citations recorded by the source corpus.

Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct improved {\em privacy-preserving synopses} of an input database. These are data structures that yield, for a given set $\Q$ of queries over an input database, reasonably accurate estimates of the responses to every query in~$\Q$, even when the number of queries is much larger than the number of rows in the database. Given a {\em base synopsis generator} that takes a distribution on $\Q$ and produces a ``weak'' synopsis that yields ``good'' answers for a majority of the weight in $\Q$, our {\em Boosting for Queries} algorithm obtains a synopsis that is good for all of~$\Q$. We ensure privacy for the rows of the database, but the boosting is performed on the {\em queries}. We also provide the first synopsis generators for arbitrary sets of arbitrary low-sensitivity queries, {\it i.e.}, queries whose answers do not vary much under the addition or deletion of a single row. In the execution of our algorithm certain tasks, each incurring some privacy loss, are performed many times. To analyze the cumulative privacy loss, we obtain an $O(\eps^2)$ bound on the {\em expected} privacy loss from a single $\eps$-\dfp{} mechanism. Combining this with evolution of confidence arguments from the literature, we get stronger bounds on the expected cumulative privacy loss due to multiple mechanisms, each of which provides $\eps$-differential privacy or one of its relaxations, and each of which operates on (potentially) different, adaptively chosen, databases.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “However, since privacy guarantees degrade as additional information is published about the same data [147, 148], these updates must be less frequent to still preserve both privacy and accuracy of the overall analysis.”
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, methodology): “A natural way to bound our approach’s privacy loss is to ﬁrst bound the privacy cost of each label queried by the student, and then use the strong composition theorem (Dwork et al., 2010) to derive the total cost of training the student.”
Privacy Amplification by Decentralization (2020, methodology): “By leveraging the fact that the view of each user u is restricted to the values taken by the token at each of its K visits to u , combined with advanced composition (Dwork et al., 2010b), we have the following result (see Appendix A for the proof).”
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].”
Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “) A small charge is necessary even if the answer is no, but, via advanced composition [29], this charge can be “prepaid” at the beginning and amortized over a large number of queries.”
Privacy-Preserving Tensor Factorization for Collaborative Health Data Analysis (2019, background): “The overall privacy guarantee of Algorithm 1 is analyzed under the zCDP definition which provides tighter privacy bound than strong composition theorem [10] for multiple folds Gaussian mechanism [4, 34].”
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].”
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (2018, positive): “Theorem 2 (Advanced composition [DRV10, DR14]) .”
Distributed Differential Privacy via Shuffling (2018, neutral): “3 (Composition [14, 15]).”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, methodology): “…by keeping track of the privacy loss over each iterative update of the model parameters using the strong composition theorem in diﬀerential privacy (Dwork et al., 2010), which gives roughly ( ˜ O ( √ k(cid:15) ) , ˜ O ( kδ )) -DP 7 for k iterations of an arbitrary ( (cid:15), δ ) -DP algorithm…”
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).”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “1] for the analysis) to repeatedly “peel off” the column of x with the approximately largest mean x , and applying the composition theorem for differential privacy [12], [42], [43].”
Rényi Differential Privacy (2017, background): “A tighter, advanced composition theorem [6], gives a choice of δ, from which one computes ′ so that the n-fold composition satisfies ( ′, δ)-differential privacy.”
The Composition Theorem for Differential Privacy (2013, methodology): “A routine argument shows that the composition of k queries, each of which is (ε, δ)differentially private, is at least (k , kδ)-differentially private (Dwork et al., 2006b;a; Dwork & Lei, 2009; Dwork et al., 2010).”