# The Discrete Gaussian Expectation Maximization (Gradient) Algorithm for Differential Privacy

Authors: Weisan Wu
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

In this paper, we give a modified gradient EM algorithm; it can protect the privacy of sensitive data by adding discrete Gaussian mechanism noise. Specifically, it makes the high-dimensional data easier to process mainly by scaling, truncating, noise multiplication, and smoothing steps on the data. Since the variance of discrete Gaussian is smaller than that of the continuous Gaussian, the difference privacy of data can be guaranteed more effectively by adding the noise of the discrete Gaussian mechanism. Finally, the standard gradient EM algorithm, clipped algorithm, and our algorithm (DG-EM) are compared with the GMM model. The experiments show that our algorithm can effectively protect high-dimensional sensitive data.


---

## Body

## 1. Introduction

Now, big data have spread to every field and organization in our society, generating large amounts of personal data every day, which people use and analyse to enable the rapid development of society and technology. However, it is expected that some personal private data will be protected from being hacked or made public when it is collected. Therefore, how to effectively protect the privacy of data, not to be attacked, and can be effectively used, has gradually been paid attention to. Dwork et al. [1] introduced the concept and basic theoretical framework of differential privacy, which can effectively protect users’ data privacy and has a strict and elegant mathematical theoretical framework and guarantees.Gradient EM algorithm is one of the most important statistical models, and Wang et al. [2] recently applied sensitive data for privacy protection. Before this, people used the original EM algorithm and gradient EM algorithm, and there is no statistical guarantee. Until Balakrishnan et al. [4] gave the statistical guarantee of EM algorithm, Wang et al. [3] gave the guarantee of gradient EM algorithm based on it and extended it to the data privacy protection theory. However, just like most scholars, Gaussian noise with continuous distribution is added to the data, while in practice, the data output queries are often discrete, such as the number of records in the database that meets certain conditions. For this reason, Canonne et al. [5] proposed to use a discrete Gaussian mechanism to add discrete Gaussian noise to the data and to ensure that it has the same excellent accuracy as adding continuous Gaussian noise.In this paper, we design a discretized Gaussian algorithm based on the gradient EM algorithm for differential privacy calculation based on [2]. Our algorithm has a good practical effect and can be extended to the general standard model. Meanwhile, the corresponding statistical guarantee of the algorithm is given in this paper. The structure of this paper is as follows: in the second part, we first introduce some theories of gradient EM algorithm, discrete Gaussian, and differential privacy, as well as some works related to this paper. In the third part, we introduce our model, namely, differential privacy discrete Gaussian EM (Gradient) algorithm (DG-EM), and the relevant statistical guarantee theorem. In the fourth part, we give the data simulation of the sensitivity, sample size, and dimension of the aggregated data, and the discussion of the model and future work are shown in the fifth part. Finally, we add the proof of some lemmas in the appendix.


## 2. Preliminaries

### 2.1. Gradient EM Algorithm

Assume thatX,Z is complete data, where X is an observing sample and called Z as a latent variable. They are generally unobservable because they are missing or have underlying data structures. We denote X and Z as the sample space for variables X,Z, respectively. Suppose that X,Z has a joint density function pθ0x,z; it belongs to some parameterized distribution family pθ0|θ0∈Ω. For convenience, the variable X has a margin density function πθx=∫Zpθx,zdz, and πθz|x=pθx,z/πθx is a Z′ s conditional density function which is under X=x. Suppose that the given observer samples are x1,…,xn from population X. The EM algorithm needs to maximize the log-likelihood function ℓnθ=logpθx,z. Through Jensen’s inequality, the lower bound of the log-likelihood function can be writen as follows:(1)1nℓnθ−ℓnθ′≥1n∑i=1n∫Zπθ′z|xilogpθxi,zdz−1n∑i=1n∫Zπθ′z|xilogpθ′xi,zdz,where(2)qiθ,θ′=∑i=1n∫Zπθ′z|xilogpθxi,zdz,(3)Qnθ,θ′=1n∑i=1nqiθ,θ′.The expectation ofQnθ,θ′ is denoted as(4)Qθ,θ′=Ex∼πθ′x∫Zπθ′z|xlogpθx,zdz.To maximize equation (3), the left term of the inequality can be sufficiently large by iteratively increasing the lower bound on the right term. The standard EM algorithm [6–9] estimates the function Qnθ,θt by E-step at each iteration, then the parameters are estimated in M-step to make the parameter values of this iteration maximize the function Qnθ,θt and denote the parameter as θt+1=maxθ∈ΩQnθ,θt. The gradient EM algorithm is usually used to achieve higher accuracy and faster global maximum if the function is differentiable at each iteration step. The gradient EM algorithm is usually stated as follows: when the function Qnθ,θt is differentiable at the t-th iteration, we can update the current parameter θt to θt+1 by the following steps:E-step: computeQnθ,θt,M-step: updateθt+1=θt+η∇Qnθt,θt,where η is a parameter which calls step size.


### 2.2. Discrete Gaussian

The study of discrete distributed forms of noise has received more attention this year. In the literature, people studied discrete Laplace distribution, discrete binomial distribution, and discrete Gaussian distribution and applied them to the field of cryptography.In this paper, the differential privacy model is studied based on Gaussian mechanism. The noise with normal distribution makes the model have many elegant mathematical properties. Although the discrete Laplace noise mechanism and the discrete Gaussian noise mechanism cannot be compared in the same model, since they are used in different privacy mechanisms, we are still willing to use the discrete Gaussian noise in order to obtain aesthetic mathematical conclusions [10–13].In this paper, we need to add noise to have discrete Gaussian distribution to specially treated sample. Firstly, we will give the definition of the discrete Gaussian distribution and some useful related theories.Definition 1.
Letμ,σ2∈ℝ,σ>0, if random variable X has probability mass function as follows:(5)PrX=x=exp−x−μ2/2σ2∑y∈ℤexp−y−μ2/2σ2,∀x∈ℤ.
On the integers support set, then we call it is a discrete Gaussian distribution with location parameterμ and scale parameter σ2 and denoted Nℤμ,σ2.


### 2.3. Some Basic Theories on Differential Privacy

In this part, we will give some basic theories on differential privacy [14, 15].Definition 2.
A randomized algorithmℳ:X⟶Y satisfies ϵ,δ-differential privacy (DP) if for all neighboring datasets ,D,D′⊂X, differing on a single entry. For all events S in the space Y, we have PrℳD∈S≤eϵPrℳD′∈S+δ. Moreover, we called its approximate differential privacy, if δ>0, and we called its pure or point-wise ϵ-differential privacy in the case of ϵ,0-differential privacy.
The concept of concentrated differential privacy given by Bun et al. [14] as follows:Definition 3.
A randomized algorithmℳ:X⟶Y satisfies ρ-concentrated differential privacy if for neighboring datasets D,D′⊂X, and for any α∈1,∞, we have DαℳDℳD′≤ρ, where DαPQ=1/α−1log∑yPy/QyαQy is the Renyi divergence of order α of the distribution form the distribution.
From these definitions, we have the conclusion that pure-DP can implyρ-CDP, and ρ-CDP can imply ρ+2ρlogδ−1,δ-DP, where δ is a positive constant.
In order to ensure the consistency of the parameters of our model, we need some basic definitions and assumptions based on [4].Definition 4.
(self-consistent). We called the functionQ⋅;θ∗ is self-consistent if θ∗=argmaxθ∈ΩQθ;θ∗.Definition 5.
(Lipschitz-gradient-2L,ℬ). We called the function Q⋅;⋅ is Lipschitz-gradient-2 L,ℬ, if we have the following inequality for parameter θ∗ and θ∈ℬ:(6)∇Qnθ;θ∗−∇Qnθ;θ2≤Lθ−θ∗2.Definition 6.
(μ-smooth). We call the function Q⋅;⋅ is μ-smooth, if for any parameters θ,θ′∈ℬ, we have the inequality(7)Qθ;θ′≥Qθ′;θ∗+θ−θ′T∇Qθ′;θ∗−μ2θ−θ′22.Definition 7.
(λ-strongly concave). We call the function Q⋅;θ∗ is λ-strongly concave, if for any parameters θ,θ′∈ℬ, we have the inequality(8)Qθ;θ′≤Qθ′;θ∗+θ−θ′T∇Qθ′;θ∗−λ2θ−θ′22.Assumption 1.
We assume that the functionQ⋅;⋅ is self-consistent, Lipschitz-gradient-2 L,ℬ, μ-smooth, and λ-strongly concave on some parameter sets ℬ.


## 2.1. Gradient EM Algorithm

Assume thatX,Z is complete data, where X is an observing sample and called Z as a latent variable. They are generally unobservable because they are missing or have underlying data structures. We denote X and Z as the sample space for variables X,Z, respectively. Suppose that X,Z has a joint density function pθ0x,z; it belongs to some parameterized distribution family pθ0|θ0∈Ω. For convenience, the variable X has a margin density function πθx=∫Zpθx,zdz, and πθz|x=pθx,z/πθx is a Z′ s conditional density function which is under X=x. Suppose that the given observer samples are x1,…,xn from population X. The EM algorithm needs to maximize the log-likelihood function ℓnθ=logpθx,z. Through Jensen’s inequality, the lower bound of the log-likelihood function can be writen as follows:(1)1nℓnθ−ℓnθ′≥1n∑i=1n∫Zπθ′z|xilogpθxi,zdz−1n∑i=1n∫Zπθ′z|xilogpθ′xi,zdz,where(2)qiθ,θ′=∑i=1n∫Zπθ′z|xilogpθxi,zdz,(3)Qnθ,θ′=1n∑i=1nqiθ,θ′.The expectation ofQnθ,θ′ is denoted as(4)Qθ,θ′=Ex∼πθ′x∫Zπθ′z|xlogpθx,zdz.To maximize equation (3), the left term of the inequality can be sufficiently large by iteratively increasing the lower bound on the right term. The standard EM algorithm [6–9] estimates the function Qnθ,θt by E-step at each iteration, then the parameters are estimated in M-step to make the parameter values of this iteration maximize the function Qnθ,θt and denote the parameter as θt+1=maxθ∈ΩQnθ,θt. The gradient EM algorithm is usually used to achieve higher accuracy and faster global maximum if the function is differentiable at each iteration step. The gradient EM algorithm is usually stated as follows: when the function Qnθ,θt is differentiable at the t-th iteration, we can update the current parameter θt to θt+1 by the following steps:E-step: computeQnθ,θt,M-step: updateθt+1=θt+η∇Qnθt,θt,where η is a parameter which calls step size.


## 2.2. Discrete Gaussian

The study of discrete distributed forms of noise has received more attention this year. In the literature, people studied discrete Laplace distribution, discrete binomial distribution, and discrete Gaussian distribution and applied them to the field of cryptography.In this paper, the differential privacy model is studied based on Gaussian mechanism. The noise with normal distribution makes the model have many elegant mathematical properties. Although the discrete Laplace noise mechanism and the discrete Gaussian noise mechanism cannot be compared in the same model, since they are used in different privacy mechanisms, we are still willing to use the discrete Gaussian noise in order to obtain aesthetic mathematical conclusions [10–13].In this paper, we need to add noise to have discrete Gaussian distribution to specially treated sample. Firstly, we will give the definition of the discrete Gaussian distribution and some useful related theories.Definition 1.
Letμ,σ2∈ℝ,σ>0, if random variable X has probability mass function as follows:(5)PrX=x=exp−x−μ2/2σ2∑y∈ℤexp−y−μ2/2σ2,∀x∈ℤ.
On the integers support set, then we call it is a discrete Gaussian distribution with location parameterμ and scale parameter σ2 and denoted Nℤμ,σ2.


## 2.3. Some Basic Theories on Differential Privacy

In this part, we will give some basic theories on differential privacy [14, 15].Definition 2.
A randomized algorithmℳ:X⟶Y satisfies ϵ,δ-differential privacy (DP) if for all neighboring datasets ,D,D′⊂X, differing on a single entry. For all events S in the space Y, we have PrℳD∈S≤eϵPrℳD′∈S+δ. Moreover, we called its approximate differential privacy, if δ>0, and we called its pure or point-wise ϵ-differential privacy in the case of ϵ,0-differential privacy.
The concept of concentrated differential privacy given by Bun et al. [14] as follows:Definition 3.
A randomized algorithmℳ:X⟶Y satisfies ρ-concentrated differential privacy if for neighboring datasets D,D′⊂X, and for any α∈1,∞, we have DαℳDℳD′≤ρ, where DαPQ=1/α−1log∑yPy/QyαQy is the Renyi divergence of order α of the distribution form the distribution.
From these definitions, we have the conclusion that pure-DP can implyρ-CDP, and ρ-CDP can imply ρ+2ρlogδ−1,δ-DP, where δ is a positive constant.
In order to ensure the consistency of the parameters of our model, we need some basic definitions and assumptions based on [4].Definition 4.
(self-consistent). We called the functionQ⋅;θ∗ is self-consistent if θ∗=argmaxθ∈ΩQθ;θ∗.Definition 5.
(Lipschitz-gradient-2L,ℬ). We called the function Q⋅;⋅ is Lipschitz-gradient-2 L,ℬ, if we have the following inequality for parameter θ∗ and θ∈ℬ:(6)∇Qnθ;θ∗−∇Qnθ;θ2≤Lθ−θ∗2.Definition 6.
(μ-smooth). We call the function Q⋅;⋅ is μ-smooth, if for any parameters θ,θ′∈ℬ, we have the inequality(7)Qθ;θ′≥Qθ′;θ∗+θ−θ′T∇Qθ′;θ∗−μ2θ−θ′22.Definition 7.
(λ-strongly concave). We call the function Q⋅;θ∗ is λ-strongly concave, if for any parameters θ,θ′∈ℬ, we have the inequality(8)Qθ;θ′≤Qθ′;θ∗+θ−θ′T∇Qθ′;θ∗−λ2θ−θ′22.Assumption 1.
We assume that the functionQ⋅;⋅ is self-consistent, Lipschitz-gradient-2 L,ℬ, μ-smooth, and λ-strongly concave on some parameter sets ℬ.


## 3. Differential Privacy Discrete Gaussian EM (Gradient) Model

We will mention that the EM algorithm based on [2] and use the discrete Gaussian noise mechanism of high-dimensional truncation algorithm, which satisfies the centralized differential privacy (CDP). Like Wang et al. [2], we have first considered one coordinate case that is 1-dimensional random variable x. Let x1,…,xn be i.i.d. sampled from x. We get the clipped estimator as follows:Step 1. For the sample xi, we take a soft truncation function hx which is defined by Catoni and Giulini [16],(9)hx=−223,x<−2x−x36,−2≤x≤2223,x>2.Then, we take some mild constantω and rescaled sample xi by dividing ω to get hxi/ω; through this approach, we can get the truncated mean as follows:(10)ωn∑i=1nhxiω≈EX.From the expression of the functionhx, we know hx is bounded by 22/3, so the sensitivity is 42/3.Step 2. Generate random noises o1,…,on from a common distribution o∼χ with Eo=0. For data xi, we get a new data xi1+oi though multiply the noise factor 1+oi, and we get term hxi1+oi/ω by scaling and truncation step. Finally, we get(11)x˜o=ωn∑i=1nhxi1+oiω.Multiplicative noise is an effective method to ensure the estimation effect of typical points and increase the estimation effect of outliers as much as possible. It was first proposed by Srivastava et al. [17], and the motivation of using Gaussian multiplicative noise comes from [18].Step 3. Finally, we take the expectation for the distributions with arrive multiplicative noise as follows:(12)x^=Ex˜o=ωn∑i=1n∫hxi1+oiωdχoi.Like Catoni and Giulini [16], taking χ∼N0,1/β, we take the distribution χ following the discrete Gaussian distribution as χ∼Nℤ0,1/β. Easily, for any given constant a,b>0, we also have(13)Eχha+bβo=a1−b22−a36+Ra,b,where Ra,b is a correction term Ra,b=T1+T2+T3+T4+T5. Signs T1−T5 are respectively denoted as(14)T1=223F−−F+,T2=−a−a36F−+F+,T3=b2π1−a22E−−E+,T4=ab22F−+F++12πV+E+−V−E−,T5=b362π2+V−2E−−2+V+2E+.Also, the notation is defined by(15)V−=2−ab,V+=a+2b,E−=exp−V−22,E+=exp−V+22,F−=Φ−V−,F+=Φ−V+.Unproved, we have the following estimation error Lemma1 which is like Lemma 5 in Holland [19], and we gave the proof of it in Appendix A.Lemma 1.
Letx1,…,xn be i.i.d. sampled form x∼μ. Assume Eμx2≤τ, and the upper bound has known. Given a number 0<γ<1, for β=2logγ−1 and ω=nτ/2logγ−1, we have(16)x^−Eμx≤Oτlogγ−1n,with probability at least 1−γ.
From the soft truncation function and the multiplicative noise algorithm, we know that the sensitivity of the processed observation samples is42s/3n. Next, we need to add discrete Gaussian noise to the observations and obtain that the query(17)ℳD=x^+Y,Y∼Nℤ0,σ2,σ2=Oω2logδ−1ϵ2n2,will be ϵ,δ-DP, which leads the following Lemma 3; we give the proof in Appendix B.Lemma 2.
Letϵ>0; let the function q:Xn⟶ℤ be an operator algorithm which is defined by Steps 1–3, satisfying qx−qx′≤Δ for any x,x′∈Xn; the query can be writen as randomized algorithm ℳ:Xn⟶ℤ by ℳD=qx+Y, where Y∼Nℤ0,σ2, then ℳ satisfies ϵ,δ-DP.
Furthermore, these results imply the following lemma.Lemma 3.
Under the assumptions in Assumption1, with probability at least 1−γ, the following holds:(18)ℳD−Ex≤OΔlogδ−1ϵ2.
After the estimation of the univariate private data, in thet-th iteration of Algorithm 1, we use the univariate estimation method for each coordinate of the gradient ∇Qnθt;θt and then get the estimation of the gradient ∇Qnθt;θt. Finally, step M is performed.
Algorithm 1: Differentially private DG-EM (gradient) algorithm.
Input:D=xi⊂ℝd,i=1,…,n, privacy parameter ϵ,δ,Q⋅;⋅ and qi⋅;⋅, initial parameter θInit∈ℬ and τ satisfy Assumption 1, the number of iterations T, step size η, and failure probability γ>0.(1)
Letϵ¯=2logδ−1+ϵ−2logδ−1,ω=nτ/2logd/γ,β=logd/γ,(2)
fort=1,…,Tdo(3)
For eachj∈d, calculate the robust gradient and add a discrete Gaussian noise, that is,gjt−1θt−1=ω/n∑i=1n∇jqiθt−1;θt−11−∇j2qiθt−1;θt−1/2ω2β−∇j3qiθt−1;θt−1/6ω2+ω/n∑i=1n∑nR∇jqiθt−1;θt−1/ω,∇jqiθt−1;θt−1/ωβ+Yjt−1whereYjt−1∼Nℤ0,σ2,σ2=8τdT/9βnϵ¯2.(4)
Let vector∇ˇQnθt−1∈ℝd denote ∇ˇQnθt−1=g1t−1θt−1,g2t−1θt−1,…,gdt−1θt−1.(5)
Updateθt=θt−1+η∇ˇQnθt−1.(6)
end forLemma 4.
For any0<ϵ<1, let Dαℳxℳx′≤ϖ; for any α∈1,∞,ϵ≥0, and x,x′∈Xn, Algorithm 1 satisfies ϵ,δ-DP for(19)δ=expα−1ϖ−ϵα−11−1αα,where Y∼Nℤ0,σ2.
For Algorithm1, the next theorem shows that the parameter estimation is consistent if the initial parameter θInit is close to the true parameter θ∗ enough. After some simple calculations, we conclude that in Lemma 2, the upper bound is Δ=nτ+ωop2/nωop1+1/4log3nτ/2ωop2+logγ−1−1, where ωop is the optimal numerical solution to the equation(20)2ω2+nEμx2=ω2log3nEμx22ω2γ−2.Lemma 5.
Letℬ=θ:θ−θ∗2≤R denote a parameter set with R=κθ∗22,κ∈0,1 which is a positive constant. Assume parameters L,ℬ,μ,λ,τ satisfying condition of 1−2λ−L/λ+μ∈0,1. If θInit−θ∗2≤R/2 and n is a large number such that(21)Ω˜1λ−L2d2Tτlogγ−1ϵ2R2≤n.
We havePrθt∈ℬ≥1−2Tγ for all t∈T. Furthermore, if we take T=Oλ+μ/λ−Llogn and η=2/λ+μ, we have(22)θT−θ∗2≤O˜Rλ+μλ−L3dlogδ−1logγ−1τnϵ2.Lemma 6.
Letθ∗/σ≥r, then there exists a constant C such that the properties of self-consistent Lipschitz-gradient-2L,ℬ,μ-smoothness, and λ-strongly concave hold for the function Q⋅;⋅ with L=exp−Cr,μ=λ=1,R=κθ∗2,κ=1/4,ℬ=θ:θ−θ∗≤R, where r is a enough large constant means that the minimum signal-to-noise ratio (SNR).Furthermore, we can get Theorems1 and 2. The proof of these theorems is very simple; we do not list the detailed proof procedure here. In fact, we only need to replace the upper bound on the variance of the discrete noise in [2] with a single coordinate with 3exp−1/2σ2.Theorem 1.
With the same condition as in Lemma4, for any θ∈ℬ, the j-th coordinate of ∇qθ;θ satisfies the following results:(23)Ey∇jqθ;θ2≤Oθ∗∞2+3exp−12σ2.Theorem 2.
With the same conditions in Lemma3, we assume that θInit−θ∗2≤θ∗22/8 in Algorithm 1, and n is a large enough number such that(24)Ω˜nθ∗∞2+3exp−1/2σ2+ωop2ωopϵ2θ∗22d21+14log3nτ2ωop2+logγ−1−1≤n.
If we takeT=Ologn and the ratio as η=O1, then for a failure probability γ, we have with probability at least 1−2Tγ(25)θT−θ∗2≤O˜θ∗2nθ∗∞2+3exp−1/2σ2+ωop2nϵ2ωopd1+14log3nτ2ωop2+logγ−1−1.
We note that Lemmas3–6 and Theorems 1 and 2 are easy to get through Lemmas 1 and 2. Due to limited space, we delete these proofs here, and readers can prove them by themselves. It is only necessary to pay attention to the upper bound of the ℓ2-norm between the iterative values of parameters and the truth values in the process of proof.


## 4. Experiments and Results

In this section, we will evaluate the performance of Algorithm1 on the GMM model based on these methods. We will study the statistical setting and theoretical behavior of this algorithm on synthetic data.


### 4.1. Baseline Methods

In this part, we will compare the two methods primarily. For convenience, we will refer to the gradient EM algorithm as EM, which will serve as a nonprivate baseline method. The other is the clipped differential private EM algorithm, which we still refer to as clipped [20], which will serve as our privacy baseline approach.


### 4.2. Experimental Settings

In this experiment, we generate the synthetic data of the mixed distribution of two components. To generate each of the algorithm, we consider the random initialization method for the selection of initial parameter values. In the results, we used to measure the resulting estimation error. We set signal-to-noise ratioθ∗/σ=3. For the privacy parameter ϵ, we set ϵ=0.5,0.8,1, and then the parameter δ=PrY>ϵσ2/Δ+Δ/2 needs to calculate because it is the function of ϵ.


### 4.3. Experimental Results

As can be seen from Figure1, we fixed n=1000,d=20. When the budget of our method is set at different values, the estimation error decreases significantly with the increase of iteration time. When the budget is 0.2,0.5, and 1, the optimal value is 1,2, and 2, respectively. It is difficult for us to determine the optimal value C.Figure 1
Estimation error of GMM clipped vs. iterationt under different clipping threshold C and budgets ϵ. (a) n = 1000; d = 20; ϵ  = 0.2, (b) n = 1000; d = 20; ϵ = 0.5, and (c) n = 1000; d = 20; ϵ = 1.
(a)(b)(c)In Figure2, under the lower dimension case, we test how the data dimension d, privacy budget ϵ, and data size n affect the estimation error θ−θ∗2 of algorithms on the Gaussian mixture model over iteration t. We can see that the estimation error of Algorithm 1 in GMM decreases when ϵ increases, n increases, or d decreases. However, we can see that when the budget ϵ is small, the effect of our algorithm is performed badly, and the estimation error declines unstably with the increase of the number of iterations.Figure 2
Estimation error of GMM w.r.t. privacy budgetϵ, data dimension (lower) d, data size n, and iteration t. (a) n = 2000; d = 10, (b) n = 2000; ϵ  = 0.5, and (c) d = 10, ϵ = 0.5.
(a)(b)(c)In Figure3, we can see that, in the face of high-dimensional data, the effect of estimation error θ−θ∗2 needs a relatively large sample to be guaranteed. We conducted experiments with higher dimensions d=40,80,160 and different sample sizes of 2000,5000, and 10 000, respectively. It can be seen that when the sample size n is large enough, the estimation error can be guaranteed to decrease significantly with the number of iterations t. As shown in Figure 3, with the increase of sample size, our algorithm is equally effective in high-dimensional space, which is not comparable with Wang et al.’s [2] algorithm.Figure 3
Estimation error of GMM w.r.t. privacy budgetϵ, data dimension (higher) d, data size n, and iteration t. (a) n = 2000; d = 100, (b) n = 2000; ϵ = 0.5, and (c) d = 100, ϵ = 0.5.
(a)(b)(c)


## 4.1. Baseline Methods

In this part, we will compare the two methods primarily. For convenience, we will refer to the gradient EM algorithm as EM, which will serve as a nonprivate baseline method. The other is the clipped differential private EM algorithm, which we still refer to as clipped [20], which will serve as our privacy baseline approach.


## 4.2. Experimental Settings

In this experiment, we generate the synthetic data of the mixed distribution of two components. To generate each of the algorithm, we consider the random initialization method for the selection of initial parameter values. In the results, we used to measure the resulting estimation error. We set signal-to-noise ratioθ∗/σ=3. For the privacy parameter ϵ, we set ϵ=0.5,0.8,1, and then the parameter δ=PrY>ϵσ2/Δ+Δ/2 needs to calculate because it is the function of ϵ.


## 4.3. Experimental Results

As can be seen from Figure1, we fixed n=1000,d=20. When the budget of our method is set at different values, the estimation error decreases significantly with the increase of iteration time. When the budget is 0.2,0.5, and 1, the optimal value is 1,2, and 2, respectively. It is difficult for us to determine the optimal value C.Figure 1
Estimation error of GMM clipped vs. iterationt under different clipping threshold C and budgets ϵ. (a) n = 1000; d = 20; ϵ  = 0.2, (b) n = 1000; d = 20; ϵ = 0.5, and (c) n = 1000; d = 20; ϵ = 1.
(a)(b)(c)In Figure2, under the lower dimension case, we test how the data dimension d, privacy budget ϵ, and data size n affect the estimation error θ−θ∗2 of algorithms on the Gaussian mixture model over iteration t. We can see that the estimation error of Algorithm 1 in GMM decreases when ϵ increases, n increases, or d decreases. However, we can see that when the budget ϵ is small, the effect of our algorithm is performed badly, and the estimation error declines unstably with the increase of the number of iterations.Figure 2
Estimation error of GMM w.r.t. privacy budgetϵ, data dimension (lower) d, data size n, and iteration t. (a) n = 2000; d = 10, (b) n = 2000; ϵ  = 0.5, and (c) d = 10, ϵ = 0.5.
(a)(b)(c)In Figure3, we can see that, in the face of high-dimensional data, the effect of estimation error θ−θ∗2 needs a relatively large sample to be guaranteed. We conducted experiments with higher dimensions d=40,80,160 and different sample sizes of 2000,5000, and 10 000, respectively. It can be seen that when the sample size n is large enough, the estimation error can be guaranteed to decrease significantly with the number of iterations t. As shown in Figure 3, with the increase of sample size, our algorithm is equally effective in high-dimensional space, which is not comparable with Wang et al.’s [2] algorithm.Figure 3
Estimation error of GMM w.r.t. privacy budgetϵ, data dimension (higher) d, data size n, and iteration t. (a) n = 2000; d = 100, (b) n = 2000; ϵ = 0.5, and (c) d = 100, ϵ = 0.5.
(a)(b)(c)


## 5. Conclusions

In this paper, we study the differential privacy model with discrete Gaussian mechanism noise. Through the process of data scaling and truncation, the model effectively solves the influence of high-dimensional data on the model. Through the experimental part and theoretical proof, we can see that the estimation error of the model adding discrete Gaussian noise is faster than that of the model adding continuous Gaussian noise in the low dimension than that of the clipped model. The effect is much better than that of [2] in the case of high dimension. At the same time, in the previous lemma section, we can see that our model has more compact bounds, because of the smaller variance of discrete Gaussian noise.



---

*Source: 7962489-2021-12-30.xml*