Characterizing the sample complexity of private learners

By Amos Beimel, Kobbi Nissim, Uri Stemmer. 2013

82 citations recorded by the source corpus.

In 2008, Kasiviswanathan el al. defined private learning as a combination of PAC learning and differential privacy [16]. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. gave a generic construction of private learners for (finite) concept classes, with sample complexity logarithmic in the size of the concept class. This sample complexity is higher than what is needed for non-private learners, hence leaving open the possibility that the sample complexity of private learning may be sometimes significantly higher than that of non-private learning. We give a combinatorial characterization of the sample size sufficient and necessary to privately learn a class of concepts. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure RepDim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies RepDim(C) = O(m), and that there exists a private learning algorithm with sample complexity m = O(RepDim(C)). We further demonstrate that a similar characterization holds for the database size needed for privately computing a large class of optimization problems and also for the well studied problem of private data release.

Subfields: Artificial Intelligence, Statistical Learning Theory, 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 Statistical Learning Theory

In Privacy & Security

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Speciﬁcally, we use lower bounds for ε -di ﬀ erential private learning of the threshold functions in the cura-tor model [11, 30]; these lower bounds do not hold for ( ε,δ )-di ﬀ erential private learning of the threshold functions [12, 17].”
The structure of optimal private tests for simple hypotheses (2018, background): “There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [11, 43, 48, 57, 58] and PAC and agnostic learning [10, 39, 46].”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “The ﬁrst privacy ampliﬁcation lemma appeared in (Kasiviswanathan et al., 2011; Beimel et al., 2013), with many subsequent improvements in diﬀerent settings.”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, methodology): “This setting has been used in [Beimel et al., 2013, Bassily et al., 2014, Wang et al., 2016] with non-tight bounds.”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “There have also been attempts to explicitly and precisely determine the sample complexity of even simpler query families than k-way conjunctions, such as point functions and interval functions [2, 3, 4].”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “An alternative private learner for this class was presented in [4].”
Simultaneous Private Learning of Multiple Concepts (2015, methodology): “It is however known that the sample complexity of such learners can be significantly lower than that of pure-differentially private learners and yet higher than the VC dimension of C (for proper learning) [4, 18, 10].”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “A key difference of our work from Kasiviswanathan et al. (2011); Chaudhuri & Hsu (2011); Beimel et al. (2013a) is that we consider a more general class of learning problems and provide a proper treatment in a statistical learning framework.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “There have also been attempts to explicitly and precisely determine the sample complexity of even simpler query families than k-way conjunctions, such as point functions and threshold functions [5, 6, 7, 13].”
The Large Margin Mechanism for Differentially Private Maximization (2014, background): “The subsequent work of [4] introduces the notion of representation dimension, and shows how it relates to differentially private learning in the discrete and finite case, and [3] provides improved convergence bounds with approximate differential privacy that exploit the structure of some specific hy”
The Algorithmic Foundations of Differential Privacy (2014, background): “For more refined analysis of the sample complexity of private learning, see [3, 4, 12, 19].”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “Their subsequent paper [87] proposed a probabilistic representation of C to improve the sample complexity.”
Differentially Private Release and Learning of Threshold Functions (2015, background): “[3] exhibited an ε-differentially private improper learner for POINTN with sample complexity O(1).”
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).”
The Complexity of Differential Privacy (2017, background): “[8], Feldman and Xiao [50] showed that the sample complexity of learning C with pure differential privacy is related to the one-way communication complexity maximized over all joint distributions on C× {0, 1}d.”
Bounds on the sample complexity for private learning and private data release (2010, background): “A randomized algorithm A is - differentially private if for all neighboring databases D, D′, and for all sets S of outputs, Pr[A(D) ∈ S] ≤ exp( ) · Pr[A(D′) ∈ S].”
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 [25, 4, 10, 5, 6].”