Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the $\epsilon$-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Discovering frequent patterns from data is a popular exploratory technique in datamining. However, if the data are sensitive (e.g., patient health records, user behavior records) releasing information about significant patterns or trends carries significant risk to privacy. This paper shows how one can accurately discover and release the most significant patterns along with their frequencies in a data set containing sensitive information, while providing rigorous guarantees of privacy for the individuals whose information is stored there. We present two efficient algorithms for discovering the k most frequent patterns in a data set of sensitive records. Our algorithms satisfy differential privacy, a recently introduced definition that provides meaningful privacy guarantees in the presence of arbitrary external information. Differentially private algorithms require a degree of uncertainty in their output to preserve privacy. Our algorithms handle this by returning 'noisy' lists of patterns that are close to the actual list of k most frequent patterns in the data. We define a new notion of utility that quantifies the output accuracy of private top-k pattern mining algorithms. In typical data sets, our utility criterion implies low false positive and false negative rates in the reported lists. We prove that our methods meet the new utility criterion; we also demonstrate the performance of our algorithms through extensive experiments on the transaction data sets from the FIMI repository. While the paper focuses on frequent pattern mining, the techniques developed here are relevant whenever the data mining output is a list of elements ordered according to an appropriately 'robust' measure of interest. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Differential privacy is a recent notion of privacy tailored to privacy-preserving data analysis [11]. Up to this point, research on differentially private data analysis has focused on the setting of a trusted curator holding a large, static, data set; thus every computation is a "one-shot" object: there is no point in computing something twice, since the result will be unchanged, up to any randomness introduced for privacy. However, many applications of data analysis involve repeated computations, either because the entire goal is one of monitoring, e.g., of traffic conditions, search trends, or incidence of influenza, or because the goal is some kind of adaptive optimization, e.g., placement of data to minimize access costs. In these cases, the algorithm must permit continual observation of the system's state. We therefore initiate a study of differential privacy under continual observation. We identify the problem of maintaining a counter in a privacy preserving manner and show its wide applicability to many different problems. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> The discovery of frequent itemsets can serve valuable economic and research purposes. Releasing discovered frequent itemsets, however, presents privacy challenges. In this paper, we study the problem of how to perform frequent itemset mining on transaction databases while satisfying differential privacy. We propose an approach, called PrivBasis, which leverages a novel notion called basis sets. A θ-basis set has the property that any itemset with frequency higher than θ is a subset of some basis. We introduce algorithms for privately constructing a basis set and then using it to find the most frequent itemsets. Experiments show that our approach greatly outperforms the current state of the art. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> We consider differentially private frequent itemset mining. We begin by exploring the theoretical difficulty of simultaneously providing good utility and good privacy in this task. While our analysis proves that in general this is very difficult, it leaves a glimmer of hope in that our proof of difficulty relies on the existence of long transactions (that is, transactions containing many items). Accordingly, we investigate an approach that begins by truncating long transactions, trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy. Experimental results over standard benchmark databases show that truncating is indeed effective. Our algorithm solves the "classical" frequent itemset mining problem, in which the goal is to find all itemsets whose support exceeds a threshold. Related work has proposed differentially private algorithms for the top-k itemset mining problem ("find the k most frequent itemsets".) An experimental comparison with those algorithms show that our algorithm achieves better F-score unless k is small. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Differential privacy is a framework for privately releasing summaries of a database. Previous work has focused mainly on methods for which the output is a finite dimensional vector, or an element of some discrete set. We develop methods for releasing functions while preserving differential privacy. Specifically, we show that adding an appropriate Gaussian process to the function of interest yields differential privacy. When the functions lie in the same RKHS as the Gaussian process, then the correct noise level is established by measuring the"sensitivity"of the function in the RKHS norm. As examples we consider kernel density estimation, kernel support vector machines, and functions in reproducing kernel Hilbert spaces. <s> BIB006 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Discovering frequent graph patterns in a graph database offers valuable information in a variety of applications. However, if the graph dataset contains sensitive data of individuals such as mobile phone-call graphs and web-click graphs, releasing discovered frequent patterns may present a threat to the privacy of individuals. Differential privacy has recently emerged as the de facto standard for private data analysis due to its provable privacy guarantee. In this paper we propose the first differentially private algorithm for mining frequent graph patterns. We first show that previous techniques on differentially private discovery of frequent itemsets cannot apply in mining frequent graph patterns due to the inherent complexity of handling structural information in graphs. We then address this challenge by proposing a Markov Chain Monte Carlo (MCMC) sampling based algorithm. Unlike previous work on frequent itemset mining, our techniques do not rely on the output of a non-private mining algorithm. Instead, we observe that both frequent graph pattern mining and the guarantee of differential privacy can be unified into an MCMC sampling framework. In addition, we establish the privacy and utility guarantee of our algorithm and propose an efficient neighboring pattern counting technique as well. Experimental results show that the proposed algorithm is able to output frequent patterns with good precision. <s> BIB007 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. As mentioned in Chaudhuri et al. (2011), the problem seems to be intractable for general kernel functions in the standard learning model of releasing different private predictor. We study this problem in three simpler but practical settings. We first study an interactive model where the user sends its test points to a trusted learner (like search engines) and expects accurate but differentially private predictions. In the second model, the learner has access to a subset of the unlabeled test set using which it releases a predictor, which preserves privacy of the training data. (NIH, 2003) is an example of such publicly available test set. Our third model is similar to the traditional model, where learner is oblivious to the test set but the kernels are restricted to functions over vector spaces. For each of the models, we derive differentially private learning algorithms with provable "utility" or error bounds. 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). Finally, we provide experimental validation of our methods. <s> BIB008 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Frequent itemset mining is a core data mining task and has been studied extensively. Although by their nature, frequent itemsets are aggregates over many individuals and would not seem to pose a privacy threat, an attacker with strong background information can learn private individual information from frequent itemsets. This has lead to differentially private frequent itemset mining, which protects privacy by giving inexact answers. We give an approach that first identifies top-k frequent itemsets, then uses them to construct a compact, differentially private FP-tree. Once the noisy FP-tree is built, the (privatized) support of all frequent itemsets can be derived from it without access to the original data. Experimental results show that the proposed algorithm gives substantially better results than prior approaches, especially for high levels of privacy. <s> BIB009 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the loss function is Lipschitz bounded and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for $(\epsilon,0)$- and $(\epsilon,\delta)$-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median. <s> BIB010 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> In this paper, we study the problem of differentially private risk minimization where the goal is to provide differentially private algorithms that have small excess risk. In particular we address the following open problem: Is it possible to design computationally efficient differentially private risk minimizers with excess risk bounds that do not explicitly depend on dimensionality (p) and do not require structural assumptions like restricted strong convexity? ::: ::: In this paper, we answer the question in the affirmative for a variant of the well-known output and objective perturbation algorithms (Chaudhuri et al., 2011). In particular, we show that under certain assumptions, variants of both output and objective perturbation algorithms have no explicit dependence on p; the excess risk depends only on the L2-norm of the true risk minimizer and that of training points. ::: ::: Next, we present a novel privacy preserving algorithm for risk minimization over simplex in the generalized linear model, where the loss function is a doubly differentiable convex function. Assuming that the training points have bounded L∞-norm, our algorithm provides risk bound that has only logarithmic dependence on p. We also apply our technique to the online learning setting and obtain a regret bound with similar logarithmic dependence on p. In contrast, the existing differentially private online learning methods incur O(√p) dependence. <s> BIB011 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> A wide variety of fundamental data analyses in machine learning, such as linear and logistic regression, require minimizing a convex function defined by the data. Since the data may contain sensitive information about individuals, and these analyses can leak that sensitive information, it is important to be able to solve convex minimization in a privacy-preserving way. A series of recent results show how to accurately solve a single convex minimization problem in a differentially private manner. However, the same data is often analyzed repeatedly, and little is known about solving multiple convex minimization problems with differential privacy. For simpler data analyses, such as linear queries, there are remarkable differentially private algorithms such as the private multiplicative weights mechanism (Hardt and Rothblum, FOCS 2010) that accurately answer exponentially many distinct queries. In this work, we extend these results to the case of convex minimization and show how to give accurate and differentially private solutions to exponentially many convex minimization problems on a sensitive dataset. <s> BIB012 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Deep learning based on artificial neural networks is a very popular approach to modeling, classifying, and recognizing complex data such as images, speech, and text. The unprecedented accuracy of deep learning methods has turned them into the foundation of new AI-based services on the Internet. Commercial companies that collect user data on a large scale have been the main beneficiaries of this trend since the success of deep learning techniques is directly proportional to the amount of data available for training. Massive data collection required for deep learning presents obvious privacy issues. Users' personal, highly sensitive data such as photos and voice recordings is kept indefinitely by the companies that collect it. Users can neither delete it, nor restrict the purposes for which it is used. Furthermore, centrally kept data is subject to legal subpoenas and extra-judicial surveillance. Many data owners--for example, medical institutions that may want to apply deep learning methods to clinical records--are prevented by privacy and confidentiality concerns from sharing the data and thus benefitting from large-scale deep learning. In this paper, we design, implement, and evaluate a practical system that enables multiple parties to jointly learn an accurate neural-network model for a given objective without sharing their input datasets. We exploit the fact that the optimization algorithms used in modern deep learning, namely, those based on stochastic gradient descent, can be parallelized and executed asynchronously. Our system lets participants train independently on their own datasets and selectively share small subsets of their models' key parameters during training. This offers an attractive point in the utility/privacy tradeoff space: participants preserve the privacy of their respective data while still benefitting from other participants' models and thus boosting their learning accuracy beyond what is achievable solely on their own inputs. We demonstrate the accuracy of our privacy-preserving deep learning on benchmark datasets. <s> BIB013 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Dimensionality reduction is a popular approach for dealing with high dimensional data that leads to substantial computational savings. Random projections are a simple and effective method for universal dimensionality reduction with rigorous theoretical guarantees. In this paper, we theoretically study the problem of differentially private empirical risk minimization in the projected subspace (compressed domain). We ask: is it possible to design differentially private algorithms with small excess risk given access to only projected data? In this paper, we answer this question in affirmative, by showing that for the class of generalized linear functions, given only the projected data and the projection matrix, we can obtain excess risk bounds of O(w(C)2/3/n1/3) under e-differential privacy, and O(√w(C)/n) under (eδ)-differential privacy, where n is the sample size and w(C) is the Gaussian width of the parameter space C that we optimize over. A simple consequence of these results is that, for a large class of ERM problems, in the traditional setting (i.e., with access to the original data), under e-differential privacy, we improve the worst-case risk bounds of (Bassily et al., 2014). <s> BIB014 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Machine learning techniques based on neural networks are achieving remarkable results in a wide variety of domains. Often, the training of models requires large, representative datasets, which may be crowdsourced and contain sensitive information. The models should not expose private information in these datasets. Addressing this goal, we develop new algorithmic techniques for learning and a refined analysis of privacy costs within the framework of differential privacy. Our implementation and experiments demonstrate that we can train deep neural networks with non-convex objectives, under a modest privacy budget, and at a manageable cost in software complexity, training efficiency, and model quality. <s> BIB015 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> In recent years, deep learning has spread beyond both academia and industry with many exciting real-world applications. The development of deep learning has presented obvious privacy issues. However, there has been lack of scientific study about privacy preservation in deep learning. In this paper, we concentrate on the auto-encoder, a fundamental component in deep learning, and propose the deep private auto-encoder (dPA). Our main idea is to enforce e-differential privacy by perturbing the objective functions of the traditional deep auto-encoder, rather than its results. We apply the dPA to human behavior prediction in a health social network. Theoretical analysis and thorough experimental evaluations show that the dPA is highly effective and efficient, and it significantly outperforms existing solutions. <s> BIB016 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Private Learning in ERM <s> Data is continuously generated by modern data sources, and a recent challenge in machine learning has been to develop techniques that perform well in an incremental (streaming) setting. A variety of offline machine learning tasks are known to be feasible under differential privacy, where generic construction exist that, given a large enough input sample, perform tasks such as PAC learning, Empirical Risk Minimization (ERM), regression, etc. In this paper, we investigate the problem of private machine learning, where as common in practice, the data is not given at once, but rather arrives incrementally over time. We introduce the problems of private incremental ERM and private incremental regression where the general goal is to always maintain a good empirical risk minimizer for the history observed under differential privacy. Our first contribution is a generic transformation of private batch ERM mechanisms into private incremental ERM mechanisms, based on a simple idea of invoking the private batch ERM procedure at some regular time intervals. We take this construction as a baseline for comparison. We then provide two mechanisms for the private incremental regression problem. Our first mechanism is based on privately constructing a noisy incremental gradient function, which is then used in a modified projected gradient procedure at every timestep. This mechanism has an excess empirical risk of ≈√d where d the input and constraint set can be used to derive significantly better results for certain interesting regression problems. Our second mechanism which achieves this is based on the idea of projecting the data to a lower dimensional space using random projections, and then adding privacy noise in this low dimensional space. The mechanism overcomes the issues of adaptivity inherent with the use of random projections in online streams, and uses recent developments in high-dimensional estimation to achieve an excess empirical risk bound of ≈ T1/3 W2/3, where T is the length of the stream and W is the sum of the Gaussian widths of the input domain and the constraint set that we optimize over. <s> BIB017
The foundation of ERM. ERM is used to select an optimal model from a set of hypotheses by minimizing the expected loss over the collected samples  . Suppose h 2 H is a hypothesis and w is the output model. We define a loss function 'ðhðw; rÞ; yÞ to estimate the expected risk of the hypothesis. The goal of ERM is to identify a w that minimizes the empirical risk R n ðwÞ on training sample D. Eq. (8) shows the empirical risk minimization where the regularizer mðwÞ prevents over-fitting. BIB002 , BIB004 , BIB005 , BIB009 Easy to implement Merge strategy has high impact on the output. Some important patterns may be missed. Binary search in the candidate set. [66] The frequent itemsets can be quite accurate The search time can be decreased, but still inefficient. Sampling from candidate set BIB007 Highly efficient Some important patterns may be missed. Fig. 5 . Learning problem and process description. By choosing different loss functions, ERM can be implemented for certain learning tasks, such as linear regression BIB001 , in which the loss function is defined as maximum likelihood estimation (MLE); logistic regression  , in which the loss function is defined as logistic loss; and the kernel method BIB008 , BIB006 , in which the loss function is set to hinge loss. To make the ERM solution tractable, people assumed that 1) the loss function and regularizer are convex and 2) the loss function is L-Lipschitz. Under these two assumptions, Eq. (8) can be considered to be a d dimensional convex optimization problem. The utility of private ERM is measured by the difference between the real risk RðwÞ and the private Rð b wÞ, defined as a risk bound. A lower risk bound leads to a higher utility. Perturbation methods. When incorporating differential privacy into the current learning process, current works apply two methods via an ERM technique: output perturbation and objective operation. The output perturbation inserts noise into the output w; while the objective operation adds noise to the objective function prior to learning. Chaudhuri et al.  proposed output perturbation solutions on logistic regression. Fig. 6a shows that the b w is obtained by moving the original w on the horizontal axis. The sensitivity is 2 n , which is associated with the regularizer parameter . With analysis, Chaudhuri et al. argued that the learning performance of this private algorithm degrades with a decreasing of . Their subsequent paper, BIB001 , trains classifiers on disjoint subsets of the data with different parameters and uses an exponential mechanism to privately choose parameters. The objective perturbation adds noise to the loss function 'ðDÞ  , BIB001 , which is illustrated in Fig. 6b and shows that the calibration of noise is associated with the gradient of R n ðwÞ. Chaudhuri et al. conclude that objective perturbation outperforms output perturbation when the loss function is convex and doubly differentiable. This is because regularization already changes the objective to protect against over-fitting, and changing the objective will not significantly impact performance. This claim is confirmed in terms of a risk bound in the next section. Risk bound in different learning algorithms. Many machine learning algorithms can be implemented in privacy learning frameworks, including linear regression, online learning, deep learning, etc. With the exception of the learning process and the privacy budget, the risk bound is related to the dimension and the size of training samples. Bassily et al. BIB010 showed that the risk bound depends on Oð ffiffi ffi d p =nÞ under ð; dÞ-differential privacy and Oðd=nÞ under ðÞ-differential privacy. These results show that the larger the dimension and the size, the lower utility that ERM can achieve. Table 14 lists several typical learning algorithms and their risk bounds. Nearly all types of learning problems can be analyzed in terms of their risk bound. For example, most of the existing papers solve regression problems that have a single optimal objective. Ullman BIB012 considered the regression problem as a multiple objective optimization when the datasets are examined with different aims. Multiple convex minimization is considered as a set of queries that can be answered by a prevalent multiplicative weights method. Ullman implemented several single objective regression results in multiple objectives platform and their risk bounds are consistent with those original papers. Kasiviswanathan et al. BIB017 considered private incremental regression in terms of streaming data. They combined continual release BIB003  In addition, some papers consider private learning in a higher dimension dataset. Kifer et al.  gave the first results on private sparse regression with high dimensions. The authors designed the algorithm based on sub-sampling stability for support recovery using a LASSO estimator. Their following work  extended and improved the results with an algorithm based on a sample efficiency test of stability. Jain et al. BIB011 proposed an entropy regularized ERM using a sampling technique, This algorithm provides a risk bound that has a logarithmic dependence on d. Kasiviswanathan et al. BIB014 considered random projections in ERM frameworks. They provided a new private compress learning method with the risk bound related to the Gaussian width of the parameter space C in the random projection. One of the most promising directions is the deep learning. Recent research focus has been devoted to the design of deep learning mechanisms. Abadi et al. BIB015 applied objective perturbation in a deep learning algorithm by defining the loss function as the penalty for mismatching training data. As the loss function is non-convex, they adapted a mini-batch stochastic gradient descent algorithm to solve the problem. The noise is added to every step of the stochastic gradient descent. In another pilot work BIB013 , Shokri et al. designed a distributed deep learning model training system that enables multiple parties to jointly learn an accurate neural network. They implemented private stochastic gradient descent algorithms to achieve ð; dÞ-differential privacy within multiple parties. In the work of Phah et al. BIB016 , the authors perturbed the objective functions of the traditional deep auto-encoder and designed the deep private autoencoder algorithm by incorporating a Laplace mechanism. Discussion. Private learning applies ERM to estimate the hypothesis set to select an optimal output w. It uses the output perturbation and the objective perturbation to ensure that the output satisfies differential privacy. A series of works have proven that this private learning is tractable for certain learning tasks, such as linear regression, SVM, and deep learning, etc. Risk bounds are highly associated with the dimension of the dataset. Current research has decreased dependence on dimension to OðdÞ. Under certain assumptions, the dimension dependence could be further relaxed. 