Sample Complexity Bounds for Differentially Private Learning

By Kamalika Chaudhuri, Daniel J. Hsu. 2011

166 citations recorded by the source corpus.

This work studies the problem of privacy-preserving classification – namely, learning a classifier from sensitive data while preserving the privacy of individuals in the training set. In particular, the learning algorithm is required in this problem to guarantee differential privacy, a very strong notion of privacy that has gained significant attention in recent years. A natural question to ask is: what is the sample requirement of a learning algorithm that guarantees a certain level of privacy and accuracy? We address this question in the context of learning with infinite hypothesis classes when the data is drawn from a continuous distribution. We first show that even for very simple hypothesis classes, any algorithm that uses a finite number of examples and guarantees differential privacy must fail to return an accurate classifier for at least some unlabeled data distributions. This result is unlike the case with either finite hypothesis classes or discrete data domains, in which distribution-free private learning is possible, as previously shown by Kasiviswanathan et al. (2008). We then consider two approaches to differentially private learning that get around this lower bound. The first approach is to use prior knowledge about the unlabeled data distribution in the form of a reference distribution chosen independently of the sensitive data. Given such a reference , we provide an upper bound on the sample requirement that depends (among other things) on a measure of closeness between and the unlabeled data distribution. Our upper bound applies to the non-realizable as well as the realizable case. The second approach is to relax the privacy requirement, by requiring only label-privacy – namely, that the only labels (and not the unlabeled parts of the examples) be considered sensitive information. An upper bound on the sample requirement of learning with label privacy was shown by Chaudhuri et al. (2006); in this work, we show a lower bound.

How researchers see this paper

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

Citations in the corpus

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “A rich line of work seeks to characterize the optimal error of differentially private algorithms for learning and optimization Kasiviswanathan et al. [31], Beimel et al. [3], Chaudhuri and Hsu [9], Beimel et al. [4, 5].”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “[5] show lower bounds on the sample complexity of label-private learners for a class C in terms of its doubling dimension.”
Characterizing the sample complexity of private learners (2013, background): “Chaudhuri and Hsu [7] studied the sample complexity needed for private learning infinite concept classes when the data is drawn from a continuous distribution.”
Simultaneous Private Learning of Multiple Concepts (2015, background): “roper learners (where hcomes from an arbitrary hypothesis class H). The latter is characterized by the representation dimension of the concept class C, which is generally higher than the VC dimension [5,4,15,6,22]. By contrast, a sample complexity gap between proper and improper learners does not ex”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “Another way to define a class of distribution D is to assume the existence of a reference distribution that is close to any distribution of interest as in Chaudhuri and Hsu (2011).”
Bounds on the sample complexity for private learning and private data release (2010, background): “1Chaudhuri and Hsu (2011) prove that this is not true for continuous domains.”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, background): “For the β in (5) Algorithm MOD-SULQ is ( p, δ) differentially private.”
Differentially private model selection with penalized and constrained likelihood (2016, background): “…2014; Karwa et al., 2014; Solea, 2014; Dwork et al., 2015; Sheffet, 2015; Wang et al., 2015; Gaboardi et al., 2016) and statistical lower bounds (Chaudhuri and Hsu, 2011; Duchi et al., 2013); there is also a large literature on private probably approximately correct learning, which echoes the…”
Differentially Private Release and Learning of Threshold Functions (2015, unknown): “Chaudhuri and Hsu [10] showed a similar result for the class C of threshold functions, which also has VC dimension 1.”
(Near) Dimension Independent Risk Bounds for Differentially Private Learning (2014, methodology): “(2011), we can obtain dimension independent excess risk for the well-known output and objective perturbation algorithms (Chaudhuri et al., 2011) when applied to the maximum-margin based problems.”
Differentially Private Learning with Kernels (2013, methodology): “Moreover, we show that our methods can also be applied to the traditional model where they demonstrate better dimensionality dependence when compared to the methods of (Rubinstein et al., 2009; Chaudhuri et al., 2011).”
Differentially Private Online Learning (2011, unknown): “Also, note that our √ d sample complexity bound does not contradict the corresponding Ω(d) lower bound proved by Chaudhuri and Hsu (2011). Reason being, we use ( , δ)-differential privacy notion which is a less strict notion of privacy than the -differential privacy notion used by Chaudhuri and Hsu ”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “For example, United States Census Bureau (2022) used ε = 12.2 to release its demonstration data (privacy unit is a person), Facebook (2022) employed ε = 2 to quantify the mobility changes of Facebook users (user-day privacy unit), and Apple collected various data from end users running iOS or macOS ”
The Large Margin Mechanism for Differentially Private Maximization (2014, background): “For the case of infinite hypothesis classes and continuous data distributions, [10] shows that distribution-free private PAC learning is not generally possible, but distribution-dependent learning can be achieved under certain conditions.”
Loss factorization, weakly supervised learning and label noise robustness (2016, background): “Elements of this work appeared in an early version [Patrini et al., 2015], mostly interested in elucidating the connection between loss factorization and α -label diﬀerential privacy [Chaudhuri and Hsu, 2011].”