Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> The probably approximately correct learning model Occam's razor the Vapnik-Chervonenkis dimension weak and strong learning learning in the presence of noise inherent unpredictability reducibility in PAC learning learning finite automata by experimentation appendix - some tools for probabilistic analysis. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much larger in size than the database itself. Specifically, we give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class. ::: We also show that it is not possible to privately release even simple classes of queries (such as intervals and their generalizations) over continuous domains. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, given a slight relaxation of the utility guarantee. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension. ::: Finally, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask, What concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (nonprivate) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private probabilistically approximately correct learner for the class of parity functions. This result dispels the similarity between learning with noise and private learning (both must be robust to small changes in inputs), since parity is thought to be very hard to learn given random classification noise. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Therefore, for local private learning algorithms, the similarity to learning with noise is stronger: local learning is equivalent to SQ learning, and SQ algorithms include most known noise-tolerant learning algorithms. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms. Because of the equivalence to SQ learning, this result also separates adaptive and nonadaptive SQ learning. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> Learning is a task that generalizes many of the analyses that are applied to collections of data, and in particular, collections of sensitive individual information. Hence, it is natural to ask what can be learned while preserving individual privacy. [Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith; FOCS 2008] initiated such a discussion. They formalized the notion of private learning, as a combination of PAC learning and differential privacy, and investigated what concept classes can be learned privately. Somewhat surprisingly, they showed that, ignoring time complexity, every PAC learning task could be performed privately with polynomially many samples, and in many natural cases this could even be done in polynomial time. ::: ::: While these results seem to equate non-private and private learning, there is still a significant gap: the sample complexity of (non-private) PAC learning is crisply characterized in terms of the VC-dimension of the concept class, whereas this relationship is lost in the constructions of private learners, which exhibit, generally, a higher sample complexity. ::: ::: Looking into this gap, we examine several private learning tasks and give tight bounds on their sample complexity. In particular, we show strong separations between sample complexities of proper and improper private learners (such separation does not exist for non-private learners), and between sample complexities of efficient and inefficient proper private learners. Our results show that VC-dimension is not the right measure for characterizing the sample complexity of proper private learning. ::: ::: We also examine the task of private data release (as initiated by [Blum, Ligett, and Roth; STOC 2008]), and give new lower bounds on the sample complexity. Our results show that the logarithmic dependence on size of the instance space is essential for private data release. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> This work studies the problem of privacy-preserving classication { namely, learning a classier from sensitive data while preserving the privacy of individuals in the training set. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> 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. <s> BIB006 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> A private learner is an algorithm that given a sample of labeled individual examples outputs a generalizing hypothesis while preserving the privacy of each individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic construction of private learners, in which the sample complexity is (generally) higher than what is needed for non-private learners. This gap in the sample complexity was then further studied in several followup papers, showing that (at least in some cases) this gap is unavoidable. Moreover, those papers considered ways to overcome the gap, by relaxing either the privacy or the learning guarantees of the learner. ::: ::: We suggest an alternative approach, inspired by the (non-private) models of semi-supervised learning and active-learning, where the focus is on the sample complexity of labeled examples whereas unlabeled examples are of a significantly lower cost. We consider private semi-supervised learners that operate on a random sample, where only a (hopefully small) portion of this sample is labeled. The learners have no control over which of the sample elements are labeled. Our main result is that the labeled sample complexity of private learners is characterized by the VC dimension. ::: ::: We present two generic constructions of private semi-supervised learners. The first construction is of learners where the labeled sample complexity is proportional to the VC dimension of the concept class, however, the unlabeled sample complexity of the algorithm is as big as the representation length of domain elements. Our second construction presents a new technique for decreasing the labeled sample complexity of a given private learner, while roughly maintaining its unlabeled sample complexity. In addition, we show that in some settings the labeled sample complexity does not depend on the privacy parameters of the learner. <s> BIB007 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Sample Complexity in Private Learning <s> We show a new lower bound on the sample complexity of (e,δ)-differentially private algorithms that accurately answer statistical queries on high-dimensional databases. The novelty of our bound is that it depends optimally on the parameter δ, which loosely corresponds to the probability that the algorithm fails to be private, and is the first to smoothly interpolate between approximate differential privacy (δ >0) and pure differential privacy (δ= 0). ::: ::: Specifically, we consider a database D ∈{±1}n×d and its one-way marginals, which are the d queries of the form “What fraction of individual records have the i-th bit set to +1?” We show that in order to answer all of these queries to within error ±α (on average) while satisfying (e,δ)-differential privacy for some function δ such that δ≥2−o(n) and δ≤1/n1+Ω(1), it is necessary that ::: ::: \[n≥Ω (\frac{√dlog(1/δ)}{αe}).\] ::: ::: This bound is optimal up to constant factors. This lower bound implies similar new bounds for problems like private empirical risk minimization and private PCA. To prove our lower bound, we build on the connection between fingerprinting codes and lower bounds in differential privacy (Bun, Ullman, and Vadhan, STOC’14). ::: ::: In addition to our lower bound, we give new purely and approximately differentially private algorithms for answering arbitrary statistical queries that improve on the sample complexity of the standard Laplace and Gaussian mechanisms for achieving worst-case accuracy guarantees by a logarithmic factor. <s> BIB008
The second problem: how many samples are needed in bounded accuracy? is associated with sample complexity analysis. Sample complexity interprets the distance utility measurement in another way to show how many samples are needed to at least achieve a particular accuracy a. Probably approximately correct (PAC) learning BIB001 helps to measure the sample complexity of learning algorithms. Based on this theory, Blum et al. BIB002 and Kasiviswanathan et al. BIB003 proved that every finite concept class can be learned privately using a generic construction with a sample complexity of OðVCðCÞlog jX jÞ (we omit the other parameters). This is a higher sample complexity than a non-private learner who only needs a constant number of samples. Improving sample complexity is an essential issue, and its study can be categorized into the following three groups: relaxing the privacy requirement, relaxing the hypothesis, and semisupervised learning. Relaxing privacy requirement. Relaxing the privacy requirement is an effective way to close the gap of sample complexity. Beimel et al.  showed that when relaxing -differential privacy to (; d)-differential privacy, sample complexity can be significantly decreased. Their follow-up paper decreases sample complexity to Oðlog ð ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ffi ðd Á 1=dÞ p ÞÞ BIB008 . Another way to relax privacy requirements is to preserve the privacy of sample labels, rather than all sample attributes. Chaudhuri et al. BIB005 assumed that with the exception of labels, the attributes of the samples are insensitive. Label privacy aims to decrease the dimension of sensitivity information. This may provide enough protection in scenarios where the content of the underlying samples is publicly known except for their labels. In other scenarios, however, these attributes may be highly sensitive, and Chaudhuri et al.'s relaxation may not be applicable in these cases. Relaxing hypothesis. This gap can also be closed by relaxing the requirement of the hypothesis. If the output hypothesis is selected from the learning concept H C, the learning process is defined as a proper learning. Otherwise, it is called an improper learning. For proper learning, the sample complexity is approximately VðdÞ. If choosing improper learning, the sample complexity can be further decreased. Beimel et al. BIB004 confirmed that when selecting a hypothesis that is not in C, the sample complexity can be decreased to the constant. Their subsequent paper BIB006 proposed a probabilistic representation of C to improve the sample complexity. They considered a list of hypothesis collections fH 1 ; :::; H m g rather than just one collection of H to represent C. The authors assumed that, when sampling H i from the hypothesis list, there will be h 2 H close to c in high probability. The sample complexity can be reduced to Oðmaxðln jH i jÞÞ. This improvement in sample complexity comes at the cost of an increased workload on evaluation, however. The learner will have to exponentially evaluate many points that are far from the concept set C. In general, for a private learner, if H ¼ C, the sample complexity is OðdÞ and the time for evaluation is constant. If H 6 ¼ C, there is constant sample complexity but OðexpðdÞÞ time for evaluation. Semi-supervised learning. Semi-supervised learning is a useful method for reducing the complexity of labeled samples. Beimel et al. BIB007 proposed a private learner by introducing semi-supervised learning to active learnings. The method starts with an unlabeled dataset to create a synthetic dataset for a class C. This synthetic dataset is then used to choose a subset of the hypotheses with a size of 2 OðVCðCÞÞ . In the last step the authors apply OðVCðCÞÞ labeled examples to choose the target synthetic dataset according to the hypotheses set. In this process, the sample complexity of the labeled samples is Oð Þ. Comparing the sample complexity of labeled and unlabeled samples, this private learner uses a constant number of labeled samples and OðdÞ unlabeled samples. Discussion. Table 15 compares the different methods in terms of their sample complexity. To make the results clear, we use a VC dimension representation and omit the other parameters such as a, b and .