{'fraction_non_alphanumeric': 0.04741525423728814, 'fraction_numerical': 0.011779661016949152, 'mean_word_length': 4.279865771812081, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Practical Privacy For Expectation Maximization

Expectation maximization (EM) is an iterative algorithm that computes maximum likelihood and maximum a posteriori estimates for models with unobserved variables. While widely used, the iterative nature of EM presents challenges for privacy-preserving estimation. Multiple iterations are required to obtain accurate parameter estimates, yet each iteration increases the amount of noise that must be added to achieve a reasonable degree of privacy. We propose a practical algorithm that overcomes this challenge and outputs EM parameter estimates that are both accurate and private. Our algorithm focuses on the frequent use case of models whose joint distribution over observed and unobserved variables remains in the exponential family. For these models, the EM parameters are functions of moments of the data. Our algorithm leverages this to preserve privacy by perturbing the moments, for which the amount of additive noise scales naturally with the data. In addition, our algorithm uses a relaxed notion of the differential privacy (DP) gold standard, called concentrated differential privacy (CDP). Rather than focusing on single-query loss, CDP provides high probability bounds for cumulative privacy loss, which is well suited for iterative algorithms. For mixture models, we show that our method requires a significantly smaller privacy budget for the same estimation accuracy compared to both DP and its (epsilon, delta)-DP relaxation. Our general approach of moment perturbation equipped with CDP can be readily extended to many iterative machine learning algorithms, which opens up various exciting future directions.


Introduction
Many devices such as household appliances, phones, drones, watches, cars, and so on, are increasingly equipped with sensors and connected in networks that collect, store and analyze data at an unprecedented scale. However, there are significant concerns that all this data in the hands of a few corporations and/or governments can lead to abuse. Hence there is a need for new machine learning tools to analyze the data but at the same time guarantee the privacy of every individual. Much progress has been made recently in developing privacy preserving algorithms [1]. In particular, differential privacy is emerging as the dominant notion of algorithmic privacy.
In this paper we will analyze the popular EM algorithm and derive privacy preserving variants for it. Expectation maximization iteratively estimates the parameters of models with unobserved variables. EM alternates inferring the unobserved variables given parameter values (the E-step) and optimizing the parameters given the inferred variables (the M-step) [2]. This iterative algorithm is widely used to solve statistical problems in many areas of science including bioinformatics [3], neuroscience [4], and computer vision [5]. We will apply our new privacy preserving EM algorithm to a mixture of Gaussians density estimation model. Having access to a private density estimator is particularly valuable because it provides a means to anonymize the data in a principled way (i.e. with strict privacy guarantees), by simply sampling a dataset from the model and replacing the original data with this sampled data.
When using privacy-sensitive data, iterative algorithms like EM need to handle a privacy-utility trade-off. The number of iterations required to guarantee accurate estimates causes high cumulative privacy loss. To compensate for the loss, one needs to add a significantly high level of noise to the parameters of interest. For example, recent work on the k-means algorithm, a variant of EM algorithm for mixture of Gaussians, requires adding noise to the parameters where the noise standard deviation is on the order of input dimension times the number of iterations [6]. To avoid adding so much noise, more recent work proposes generating a synopsis of a dataset first, then applying a standard k-means clustering algorithm on the synopsis [7]. Their synopsis generation method consists of putting rectangular bounding boxes in the data space and counting how many data points are in each box. However, this method mainly works well for a clustering task and for low dimensional data.
In this paper, we propose to resolve the privacy-utility trade-off by using moment perturbation. This is applicable for models where the complete-data likelihood is in the exponential family (even though the marginal over unobserved variables may not be). In such cases, the EM parameters are functions of moments of latent and observed variables, which we perturb for privacy. Since the amount of noise for perturbing the moments scales with the number of datapoints, our algorithm yields asymptotically efficient private EM parameters even when is non-zero. Besides, thanks to the 1 N factor, under the mixture of Gaussians model, the noise standard deviation in our method is smaller than that in other methods [6]. The difference in the amount of additive noise will be more significant when N gets larger. Moment perturbation for differentially private estimators isn't a new concept (See [8]). However, unlike existing methods, we do not require subsampling of the data. Furthermore, our algorithm uses a relaxed version of differential privacy called concentrated differential privacy (CDP) [9]. CDP has two major advantages over DP. First, (µ, τ )-CDP offers a bounded expected privacy loss, while in ( , δ)-DP the privacy loss is infinite with probability δ (in other words, the mechanism fails w.p. δ). Second, CDP requires adding much less noise for the same expected privacy guarantee compared to the ( , δ)-DP relaxation. As we will analyze in Sec 5, for J iterations, the noise standard deviation is roughly on the order of 2J log(1/δ 1 )/ in ( , δ)-DP relaxation 1 , where the failure probability is δ = Jδ + δ 1 . To obtain meaningful privacy guarantees, δ is set to be tiny, which yields quite a large noise standard deviation. In CDP, the noise standard deviation is on the order of J/2 , which effectively lowers the amount of additive noise.
We start by overviewing privacy and the general EM algorithm in Sec 2. In Sec 3, we introduce a general DP EM framework. We then derive the DP EM algorithm for mixture of Gaussians in Sec 4, which we will use for illustrating the effectiveness of our algorithm in Sec 6. In Sec 5, we construct the concentrated differential privacy formulation for EM.

Background
In this section, we provide background information on the definitions of algorithmic privacy that we use, as well as the general formulation of the EM algorithm.
Differential privacy and concentrated differential privacy. Differential privacy (DP) is a formal definition of the privacy properties of data analysis algorithms [1]. A randomized algorithm M(X) is said to be ( , δ)differentially private if P r(M(X) ∈ S) ≤ exp( )P r(M(X ) ∈ S) + δ for all measurable subsets S of the range of M and for all datasets X, X differing by a single entry. If δ = 0, the algorithm is said to be -differentially private. Intuitively, the definition states that the output probabilities must not change very much when a single individual's data is modified, thereby limiting the amount of information that the algorithm reveals about any one individual.
Concentrated differential privacy (CDP) is a recently proposed relaxation of differential privacy which aims to make privacy-preserving iterative algorithms more practical than for DP while still providing strong privacy guarantees. The CDP framework treats the privacy loss of an outcome, as a random variable. An algorithm is (µ, τ )-CDP if this privacy loss has mean µ, and after subtracting µ the resulting random variable l is subgaussian with standard deviation τ , i.e. ∀λ ∈ R : E[e λl ] ≤ exp(λ 2 τ 2 /2). While -DP guarantees bounded privacy loss, and ( , δ)-DP ensures bounded privacy loss with probability 1 − δ, (µ, τ )-CDP requires the privacy loss to be near µ w.h.p.
The general EM algorithm.
Instead, one can lower-bound L(θ) using the posterior distribution over latent variables q(Z) [10], where the lower bound is often called free energy [11], F(q, θ) = log p(X, Z|θ) q(Z) + H(q), where H(q) is the entropy of q(Z). EM alternates between: (1) the E-step: optimizing F wrt distribution over unobserved variables holding parameters fixed and (2) the M-step: maximizing F wrt parameters holding the latent distribution fixed where the second equality holds since H(q) does not directly depend on θ. To understand what EM does, one can rewrite the free energy in terms of the log-likelihood and the KL divergence terms, During the E-step, we set q (j) (Z) = p(Z|X, θ j−1 ), which makes the second term zero and the free energy equals the likelihood. Then, in the M-step, we get the maximum likelihood estimate (MLE). For the maximum a posteriori (MAP) estimate, we add the log prior for the parameters log p(θ) to the right hand side of eq (6) and optimize for θ.

The general differentially private EM algorithm
EM is widely used for models whose joint distribution over observed and unobserved variables has exponential family form: p(X, Z) = h(X, Z) exp(θ T (X, Z))/A(θ) while the marginal p(X) does not. In this case, the free energy can be rewritten as where So, in the E-step, all we need to compute is the expected sufficient statistics under q, i.e., T (X, Z) q(Z) . Then, in M-step, we compute partial derivatives wrt each parameter, Although it is not straightforward to derive a closed-form expression for each parameter update due to the dependence on other parameters in A(θ), it is easy to see that each parameter update depends on each expected sufficient statistics, i.e., moments, denoted by . So, to output privatized parameters, all we need is to perturb the moments to compensate any single data point's change. The sensitivity of expected sufficient statistics is given by where the last line is due to the triangle inequality. The expectation over z can be rewritten as an inner product, and using Hölder's inequality we obtain To further bound this quantity, we assume that the unobserved variables are discrete 2 , so that q(z) is bounded between 0 and 1. We also assume that datasets are pre-processed such that the L 2 norm of any x i is less than 1. In such a case, any x i and z i stay within a unit ball. Under these two assumptions, now the sensitivity is given by Using this sensitivity, we add noise to each moment and the perturbed moments are mapped by a model-specific deterministic function g to the vector of privatized parameters, given asθ * = g({M l } l=1,··· ,L ), whereM l=1,··· ,L are perturbed moments. Using this general framework, we derive the differentially private EM algorithm for mixture of Gaussians in the following.

Mixture of Gaussians
We consider the mixture of Gaussians (MoG) model as an example to derive the differentially private EM algorithm. For K Gaussians and N data points X : . Introducing a binary vector of length K for each data point, z i ∈ R K , to represent the membership to which Gaussian each datapoint belongs, e.g., z i,k ∈ {0, 1} and K k=1 z i,k = 1, the distribution over each z i is given by The joint distribution over observed and unobserved variables which is in exponential family is given by log p(X, Z|π, µ, . In E-step, we compute the responsibilities by δ z i,k =k q(Z) given the parameters from the previous iteration θ prev and in M-step, we update the parameters θ by eq (8) For the maximum a posteriori estimate, we impose the Dirichlet prior on π ∼ Dir(α) and Normal-inverse-Wishart In this paper we follow conventional ways to set hyperparameters, e.g. setting α = [2, 2, · · · , 2], κ 0 = 1, ν 0 = d + 2, S 0 = diag(0.1, · · · 0.1), rather than optimizing them [12].
Before moving to the next section, we would like to motivate why it is important to construct a privacy preserving algorithm for MoG. In Fig. 1, we show that if one runs the conventional EM algorithm for the given dataset, an individual's information can be easily revealed by just looking at the EM parameters, while the noised-up parameters obtained by the method, which will be described next, protect private information effectively 3 .

DPEM for MoG
Under MoG, we plug in the responsibilities given in eq (11) to the parameter update expressions given in eq (12). We then perturb each of these by taking into account one datapoint's worst-case difference between two neighboring datasets. We use to denote a privacy budget allocated for each type of parameter perturbation.
-DP mixing coefficients. For two datasets D,D ∈ N |χ| with a single data point difference, the maximum difference in π occurs when the data point x j is assigned to the k-th Gaussian with γ j,k = 1 and the altered data pointx j is assigned to another, e.g., the k -th Gaussian, withγ j,k = 1. Hence, we get the following sensitivity: ∆π M LE = max xj ,xj K k=1 1 N |γ j,k −γ j,k | ≤ 2/N, since 0 ≤ γ j,k ≤ 1 and K k=1 γ j,k = 1. We add noise to compensate the maximum difference 4 3 We first pre-processed the data by scaling down the magnitude with the maximum L2 norm of the data points, and then added noise to each parameter following the derivations in Sec 4. For visualisation, we map the results back to the original latitude/longtitude space. For π M AP k , we do not need any additional sensitivity analysis, since the MAP estimate is a deterministic mapping of the MLE.
-DP mean parameters. Using the noised-upÑ k obtained from the noised-up mixing coefficients, i.e., N k = Nπ k , the maximum difference in mean parameters due to one datapoint's difference is given by where A k := N i=1,i =j γ i,k x i , and the L 1 term is bounded due to eq (10) and ( , δ )-DP mean parameters. In order to use the Gaussian mechanism, we can straightforwardly derive the L 2 -sensitivity from the L 1 sensitivity of µ M LE : ∆ 2 µ M LE = 2/Ñ k .
-DP variance parameters. To make the sensitivity analysis easier, we plug in the noised-up mean parameters obtained from the previous section to µ M LE k , and the noised-up version ofÑ k to σ 2 . Now, we perturb the first term, using Gamma noise as below in order to obtain non-negative -DP variances:σ To set β, we look at the probability ratio given two neighboring datasets D andD: 5 The MAP estimate only differs from the MLE in the denominator: µ M AP k = 1 N k +κ 0 i γ i,k x i . We simply replaceÑ k with N k + κ 0 in eq (15) in the MAP estimation case.
where B k := N i=1,i =j γ i,k x i x i , and the last line is due to eq (10). Hence, β = dÑ k .
-DP covariance parameters. For full covariances, we follow the symmetric noise (SN) algorithm [13], which provides strong privacy guarantees and significantly higher utility than other methods (e.g., [14,15,16]) as illustrated in [13] when perturbing positive definite matrices. We first draw Gaussian random variables and construct a matrix Z k := [z 1 , · · · , z d+1 ] ∈ R d×(d+1) , which we add to perturb each of the covariance matrices asΣ The perturbed covarianceΣ M LE k are made -differentially private by setting λ to meet this privacy budget. We follow the proof of [13] to set λ using the fact that the matrix Z k Z k is a sample from a Wishart distribution with covariance λI d and d + 1 degrees of freedom. See Appendix for full derivation, where we set λ = 1/(2 Ñ k ). We provide the derivation for -DP MAP estimates of covariances in the Appendix.
In summary, we perturb the mixing coefficients by the Laplace mechanism ( -DP); mean parameters either by using the Laplace mechanism ( -DP) or using the Gaussian mechanism (( , δ )-DP); and the variance or covariance parameters by Gamma or Wishart noise ( -DP).

Concentrated differential privacy for EM
To construct a CDP formulation for EM, we use two key theorems from [9]. Their Theorem 3.5 states that any -DP algorithm is ( (exp( ) − 1)/2, )-CDP, which means that each pure-perturbation introduced in Sec 4 produces ( (exp( ) − 1)/2, )-CDP parameters. For simplicity, we rewrite 6 (exp( ) − 1)/2 ≈ 2 /2. Also, their Theorem 3.4 states that after J(2K + 1)-composition 7 , we obtain ((2K + 1)J 2 /2, (2K + 1)J )-CDP parameters. All we need is to set such that the expected cumulative privacy loss meets the privacy budget . For example, when we perturb all the parameters with -DP mechanisms, which equal ( 2 /2, )-CDP, we set = 2 J(2K+1) . When we use the Gaussian mechanism for mean perturbation, on the other hand, this introduces ( , δ )-DP parameters. In this case, we use Theorem 3.2 in [9], which states that the Gaussian mechanism with noise magnitude σ is (τ 2 /2, τ )-CDP, where τ = ∆ 2 µ k /σ. We further express τ as a function of : . Combined with -DP covariance and mixing coefficient perturbations, we set = 2 J(K/c 2 +K+1) . Notice that using the Gaussian mechanism for mean perturbation, a larger value of is assigned to each parameter perturbation compared to using the Laplace mechanism for mean perturbation. Algorithm 1 summarizes our algorithm.

Illustration
Synthetic data We first used synthetic data to illustrate how much improvement we gain by formulating the private EM algorithm under the CDP composition as opposed to the advanced ( , δ)-DP composition. We Test log-likelihood per data point as a function of number of training data points. Using the concentrated DP formulation (in red) enables us to add significantly less noise in each parameter perturbation, resulting in more accurate estimates with less data, compared to using the conventional DP formulation (in gray). Non-private EM is in black (top). We included N = 256,000 to make sure all of these estimates converge to those by the non-private version of EM with sufficiently many data points. B. Visualization of estimates under different privacy formulations using N = 8,000 training data points. Due to the high level of additive noise to the parameters, the ( , δ)-DP EM algorithm yields poor estimates (Left) even with N = 8,000. On the other hand, with the same amount of training data points, the CDP EM yields far better estimates (Middle) although the variance estimates are larger than those obtained by the non-private version of EM (Right). generated data from three isotropic Gaussians, where each Gaussian lies in 2D space. We generated 100 training datasets with varying N . For each training set, we also generated a test set in the amount of 10% of training data points, which we used to compute the test likelihood given the trained parameters. Since EM is well-known for being sensitive to parameter initialization, for each training set, we ran EM and (C)DP-EM 8 with 20 different initial values of parameters. We then calculated the interquantile range (25 − 75%) of the test likelihoods per training set, and computed the average of the interquantile range across 100 training sets. We report the test likelihood per data point by dividing the average by the number of test points in Fig. 2A. We set = 0.9 in this experiment. For ( , δ)-DP, we set δ = 0.01.
Real dataset I : Gowalla dataset. We first used the Gowalla dataset 9 to compare the clustering performance of our method (in "k-means mode") to a differentially private k-means clustering algorithm, DPLloyd [6]. As summarized in [7], the DPLloyd adds Laplace noise to the number of data points assigned to each cluster as well as to the sum of each coordinate of the data points assigned to each cluster. Due to the conventional composition theorem for DP, their noise distribution follows Lap((d + 1)J/ ) for J iterations. We also tested two variants of our algorithm, in which we perturb the mean by the Laplace mechanism (CDPlap), and by the Gaussian mechanism (CDPgau). In both algorithms, we set such that each algorithm satisfies ( , √ 2 )-CDP. In CDPgau, we set δ = 0.001. As shown in Fig. 3, even with a very small value of , our methods achieve significantly smaller NICV than DPLloyd.
Real dataset II: Lifescience dataset. We tested our method on Life science data from the UCI repository [17]. The dataset contains 26,733 records where each of them consists of 10 principal components for a chemistry or biology experiment (d = 10). Following other approaches (e.g., [18]), we set k = 3. We divided the dataset into 10 different pairs of training (90%)and test sets (10%), and show the average log test likelihood per data point across the 10 independent trials. In this experiment, we tried our CDP-EM algorithms with full covariances, as well as the EM algorithm with ( , δ) relaxation. 2 )-CDP, we used the Gaussian mechanism to perturb the mean, in which we set δ = 0.001. For ( , δ)-DP, we set δ = 0.01 generously to the baseline. Using the concentrated DP formulation (in blue) results in more accurate estimates with less data, compared to the ( , δ) relaxation.

Discussion
We developed a practical algorithm that outputs accurate and privatized EM parameters based on moment perturbation under the CDP formulation, which effectively decreases the amount of additive noise for the same expected privacy guarantee compared to the ( , δ)-DP relaxation. The private EM algorithm for the mixture of Gaussians model we discussed in this paper is clearly only one example of a much broader class of models to which our private EM framework applies. Our positive empirical results with EM strongly suggest that these ideas are likely to be beneficial for privatizing many other iterative machine learning algorithms. In future work we plan to apply this general framework to other inference methods which fits in our broader vision that practical privacy preserving machine learning algorithms will have an increasingly relevant role to play in our field.

A.1 L-1 sensitivity of MLE
We plug in the noised-up version ofÑ k fromÑ k =π k N in the definition of mean where the last line is due to Hence, the sensitivity of MLE is given by (21)

A.2 L-2 sensitivity of MLE
The only difference from L-1 sensitivity is rather than considering |x i | 1 , we consider |x i | 2 . Due to the assumption that |x i | 2 ≤ 1, the L-2 sensitivity of MLE is given by A.3 L-1 sensitivity of MAP estimate The MAP estimate only differs the MLE in the denominator: µ map So we replaceÑ k with N k + κ 0 in section A.1 and obtain the following sensitivity which simplifies to eq (21), when κ 0 = 0.

A.4 L-2 sensitivity of MAP estimate
Similar to the L-2 sensitivity for MLE, the L-2 sensitivity of MAP estimate is given by which simplifies to eq (22), when κ 0 = 0. . Hence, the probability ratio is given by where we plug in the noised-up mean parameters to µ k andÑ k , which makes the difference in trace is simply One-datapoint difference affects only two Gaussians' covariances. Hence, the difference in trace is given by where B k := N i=1,i =j γ(z i,k )x i x i . We look at the two terms in eq (25) since 0 ≤ x j x j ≤ 1. Therefore, the probability ratio is bounded by

B.2 Sensitivity of MAP estimate
We again use the symmetric noise (SN) algorithm [13] to perturb the MAP estimate of covariance matrix, where the difference in trace tr(Σ map k − Σ map k ) is given by (with plugging in the noised-up version ofÑ k to N k in the definition of covariance) sum(diag(S 0 )) N k + c where c := ν 0 + d + 2. We have the following upper bound: With the maximum of Tr(Σ map k − Σ map k ) is given in eq (29), to ensure DP, we set λ to λ = 1 2 (Ñ k + c) .
If we perturb parameters with -DP mechanisms, the resulting failure probability δ equals δ 1 . However, if we use the , δ -DP mechanism like the Gaussian mechanism for mean estimates, the failure probability δ = (Jδ + δ 1 ).