Differentially Private Data Publishing and Analysis: A Survey <s> Local Differential Privacy <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> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Local Differential Privacy <s> Working under local differential privacy-a model of privacy in which data remains private even from the statistician or learner-we study the tradeoff between privacy guarantees and the utility of the resulting statistical estimators. We prove bounds on information-theoretic quantities, including mutual information and Kullback-Leibler divergence, that influence estimation rates as a function of the amount of privacy preserved. When combined with minimax techniques such as Le Cam's and Fano's methods, these inequalities allow for a precise characterization of statistical rates under local privacy constraints. In this paper, we provide a treatment of two canonical problem families: mean estimation in location family models and convex risk minimization. For these families, we provide lower and upper bounds for estimation of population quantities that match up to constant factors, giving privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds. <s> BIB002
The majority of work on differential privacy assumes that the curator is trustworthy; however, as more organizations have resorted to distributed systems for data acquisition, storage, and analysis, it has been noted that curators are less reliable in this distributed context. Recently, a Local Differential Privacy (LDP) model has been proposed to address the issue. Noise is added on the user side before submitting the results to an un-trusted data curator. The curator then conducts post-processing on them to obtain acceptable statistics, which can be further shared with the public. Here in the statistics types, which are available for the data curator to obtain would be limited to the population statistics and depend on both the design of the local perturbation mechanism and the postprocessing mechanism. The local privacy model was first formalized in BIB001 , and then a theoretic upper bound under the LDP model was provided by Duchi et al. BIB002 . Typically two main research questions have been investigated: 1) How to design acceptable LDP mechanisms for different original data types generated by distributed users? 2) How to design acceptable LDP mechanisms that can achieve different analysis targets such as value estimation, distribution estimation and more complex machine learning tasks? In the past few years, related LDP works have focused on three aspects: the existing data types in user nodes (original data type), the data types submitted to data curators by users (uploaded data type), and the targets to achieve by analyzing the uploaded data (post-process target). Table 16 gives an overview of these three data types.