# A Smart Privacy-Preserving Learning Method by Fake Gradients to Protect Users Items in Recommender Systems

Authors: Guixun Luo; Zhiyuan Zhang; Zhenjiang Zhang; Yun Liu; Lifu Wang
Journal: Complexity
 (2020)

---

## Abstract

In this paper, we study the problem of protecting privacy in recommender systems. We focus on protecting the items rated by users and propose a novel privacy-preserving matrix factorization algorithm. In our algorithm, the user will submit a fake gradient to make the central server not able to distinguish which items are selected by the user. We make the Kullback–Leibler distance between the real and fake gradient distributions to be small thus hard to be distinguished. Using theories and experiments, we show that our algorithm can be reduced to a time-delay SGD, which can be proved to have a good convergence so that the accuracy will not decline. Our algorithm achieves a good tradeoff between the privacy and accuracy.


---

## Body

## 1. Introduction

Recommender systems, which help the electronic commerce websites to give more useful suggestions, are becoming more and more important. However, to provide users with appropriate options, the server will collect users’ data, which includes lots of sensitive information.Data in electronic commerce, economics, supply chain, financial system [1–10], etc., are generally very sensitive. In the electronic commerce case, it is shown in many studies, such as [11, 12] that user data in recommender systems, shopping records, movies a user has watched, and ratings for the restaurants contain lots of very private information such as political attitudes, sexual orientation, etc. In this paper, we study the privacy-protecting problem in electronic commerce data. Privacy has been an important issue for a long time, not only in the recommender system but also in almost all algorithms in data mining and machine learning.Differential privacy [13] is a popular method to protect privacy in machine learning algorithms. For recommender systems, there are many works applying differential privacy, such as [14–16]. Differential privacy matrix factorization algorithms are introduced in [17, 18], etc. Traditional differential privacy method is centralized, in other words, relying on a trustworthy data collector. When we want the central server not to be able to get privacy information, local differential privacy (LDP) should be used. Every user will add noise to their private data in their own device before being submitted to the central server. Recommender systems with LDP are studied in [19–21]. LDP has been used in Google’s Chrome browser [22] and Apple IOS 10 [23] to collect user data.In local differential privacy, there are two important things to be protected. The first one is which items this user has rated and the second one is the ratings of the user. In some situations, which items have been rated is much more sensitive than the rating itself. For example, shopping record contains a lot of private information, but the ratings can only represent the quality of goods. The work in [19] can only protect the ratings but not both. Shin et al. [17] proposed a novel LDP matrix factorization algorithm to protect both kinds of privacy information based on the work in [24]. Their method is to let the user submit a noisy gradient, whose value is either B or −B. The algorithm is ε-LDP, and in each round of the training process, and since the output is binary, the adversary can not learn about which items are rated in a single iteration process.However, if the adversary can get noisy gradients in multiple iterations since the noisy gradients obey the Bernoulli distribution with a mean 0, the items which have not been rated can be identified by a statistical test. The intensity of the privacy protection for the ratings and items after multiple iterations can be guaranteed by composition theorems for LDP [25, 26]. If every iteration is ε-LDP, after k iterations, the final algorithm is at most kε-LDP. But these analyses are not a direct guarantee to protect the items rated by the users. We can turn to a new perspective on this question. After performing k iterations, given a sequence with length k denoted by yi, where yji is the gradient submitted in iteration i, let Prealyj be the probability that yj is a real gradient sequence and let Pfakeyj be the probability that yj is fake. Using these two probabilities, we can consider testing two hypotheses, the sequence is real and the sequence is fake. So now comes the question, how can we make it difficult to distinguish the two situations?In order to improve the ability of protecting privacy, we want the probability error to be large. Note that the average negative log probability of error is well-known deduced from the Chernoff–Stein lemma.Theorem 1 (Theorem 11.8.3 in [27]).
X∼Q is a random variable; consider the hypothesis test between two alternatives, Q=P1 and Q=P2, where DP1,P2, the K-L distance, is finite. Then the average negative log probability of error of this hypothesis testing is DP1,P2.Using this result, although we can not obtain the distribution of the real sequence, in Section4, we will show that for the Gaussian noise based differential privacy algorithm, we can estimate the mean value of K-L distance and optimize the value of fake gradient to make the two distributions to be difficult to distinguish.In this paper, we propose a novel algorithm such that if the item has not been rated by the user, the user will submit a fake gradient. Else, the user can submit the real one, but all the submitted data will eventually be noise added. The paper is organized as follows. InSection 2, we introduce differential privacy briefly as preliminaries. In Section 3, we introduce the framework of the general differential privacy matrix factorization algorithm. And in Section 4, we will show that our algorithm can reduce the average K-L distance between the fake and real gradient distributions, such that it can improve the intensity to protect the privacy items. Meanwhile, we can prove that our algorithm has the form of SGD with time delay, which can be proved that the accuracy of the model will not be reduced by our updating rules so that our algorithm achieves a tradeoff between accuracy and privacy. In Section 5, we use experiments to show the effectiveness of our algorithm. The related work is reviewed in Section 6. In the final section, we conclude.


## 2. Preliminaries

In this paper, the notations we used are listed in Table1.Table 1
Notations.
NotationMeaningmNumber of usersnNumber of itemsuThe user profile vectorvThe item profile vectorLu,vThe loss functionMThe set of the ratingsCBound of the norm of the gradient in privacy gradient descentηThe learning rateλThe regularization parametersββ-Smooth parpameters for the loss function


### 2.1. Differential Privacy

Differential Privacy is first introduced by Dwork et al. [13], the aim of which is to make it difficult for an attacker to obtain privacy from the output data by adding noise.Definition 1.
A randomized algorithmM:D⟶R with domain D and range R is ε,δ-Differential Privacy, if for two adjacent data d,d′∈D and for a subset S of range R, it holds that(1)PMd∈S≤eεPMd′∈S+δ.Note that this definition is to compare the two probability. Ifδ=0, it can be expressed as(2)lnPMd∈SPMd′∈S≤ε.Ifε is small, such that it is hard to distinguish whether the output data is come from d or d′. As in [28], one can link differential privacy with mutual-information.Another way to describe Differential Privacy is to use the distance between distributions. We say a randomized algorithmM:D⟶R is α,ε Renyi Differential Privacy if for all neighboring d′ and d′′ we have(3)DαMd′,Md=1α−1ln∫Md′zMdzαMdzdz≤ε.Whenα⟶1, D1 is the Kullback-Leibler distance, and when α=∞, Renyi Differential Privacy is equal to ε,0 Differential Privacy. So we can see Differential Privacy is to make the output distributions with different inputs to be indistinguishable(the distributions have small distances).One may ask how to achieveε,δ-Differential Privacy in machine learning process. A basic paradigm to achieve ”-differential privacy is to examine a query L2-sensitivity in [29].Definition 2.
f is a map from the data in the dataset D to a vector. The L2-sensitivity of f is Δ2f=maxd′,dfd−fd.Using this definition, we have the following theorem in [29].Theorem 2.
Iff is a map from D to ℝd. Then the randomized algorithm MD:fD+n where(4)Pn∝expεnΔ2f,achieves ε-Differential Privacy.This theorem provides a basic method to achieve Differential-Privacy-Machine-Learning.


## 2.1. Differential Privacy

Differential Privacy is first introduced by Dwork et al. [13], the aim of which is to make it difficult for an attacker to obtain privacy from the output data by adding noise.Definition 1.
A randomized algorithmM:D⟶R with domain D and range R is ε,δ-Differential Privacy, if for two adjacent data d,d′∈D and for a subset S of range R, it holds that(1)PMd∈S≤eεPMd′∈S+δ.Note that this definition is to compare the two probability. Ifδ=0, it can be expressed as(2)lnPMd∈SPMd′∈S≤ε.Ifε is small, such that it is hard to distinguish whether the output data is come from d or d′. As in [28], one can link differential privacy with mutual-information.Another way to describe Differential Privacy is to use the distance between distributions. We say a randomized algorithmM:D⟶R is α,ε Renyi Differential Privacy if for all neighboring d′ and d′′ we have(3)DαMd′,Md=1α−1ln∫Md′zMdzαMdzdz≤ε.Whenα⟶1, D1 is the Kullback-Leibler distance, and when α=∞, Renyi Differential Privacy is equal to ε,0 Differential Privacy. So we can see Differential Privacy is to make the output distributions with different inputs to be indistinguishable(the distributions have small distances).One may ask how to achieveε,δ-Differential Privacy in machine learning process. A basic paradigm to achieve ”-differential privacy is to examine a query L2-sensitivity in [29].Definition 2.
f is a map from the data in the dataset D to a vector. The L2-sensitivity of f is Δ2f=maxd′,dfd−fd.Using this definition, we have the following theorem in [29].Theorem 2.
Iff is a map from D to ℝd. Then the randomized algorithm MD:fD+n where(4)Pn∝expεnΔ2f,achieves ε-Differential Privacy.This theorem provides a basic method to achieve Differential-Privacy-Machine-Learning.


## 3. The Framwork of Perturbed Matrix Factorization Algorithm

The program of Matrix Factorization algorithm with privacy protection has been studied by many authors, such as [17, 19].When minimizing the cost function(5)Lu,v+λ∑iui2+∑jvj2=1n∑i,j∈Mrij−uiTvj2+λ∑iui2+∑jvj2.We can use gradient descent(6)uit+1=uit−η∇uiLut,vt+2λuit,vjt+1=vjt−η∇vjLut,vt+2λvjt.The vectorui is the user profile vector for user i, and vj is the item profile vector for item j.Note that we have(7)∑i,j∈Mrij−uiTvj2=∑i,jyijrij−uiTvj2,(8)∇vjLu,v=−2n∑igij=−2n∑iyijuirij−uiTvj,where yij=1 if i,j∈M else. yij=0In this type of program, the user profile vectorsui are saved and updated on the users’ own devices. As for the item profile vectors, all the users will send the gradient to the central server, and individual users should perturb their gradient gij using a random mechanism M. Then the central server sums all these gradients to update the item profile vectors vj. Using this random perturbation, ε-differential privacy can be achieved by adjusting the distribution of noise.The whole process is shown in Algorithm1.Algorithm 1: Perturbed Matrix Factorization algorithm.
Input: Random mechanism M, learning rate η, and redefined iteration number kOutput: Item profile matrix VRandomly initializeui0,vj0 for all i and j.fort=1,2,3…doInitializeGj=0 for all j in central server.fori=1,2,3,…,mdoOn user i: samplej uniformlyfrom{1,2,3,…,n}.ifyij=1thengij=uirij−uiTvjgij=gij/max1,gij2/Cgij′=MxijendelseGenerate a fake gradient ofFij.setgij=Fijgij′=MxijendGj=Gj+xij′ for all j.endFor all j:Gj=Gj/mvj=vj+ηGjfori=1,2,3…mdoUpdateui on a local device by gradient descent.endendNote that there are two types of private information. One is the ratings of the users and the other one is the items have been rated by the users.In order to protect the items, one way is to use the random response mechanism introduced inSection 4.1 of [17]. In this method, we generate a yij′ such that yij′=1 with probability p, and if the original yij=0, we set a fake rating rij=0 so the fake gradient is ui0−uiTvj by (8), and Gaussian noise is added to the final gradient sent to the central server to protect the ratings of users.However, it is shown in the discussion ofSection 4.1 of [17] that the error caused by these fake ratings is not small, which will influence the final model accuracy. The main reason is that there are many fake gradients, which lead to a great error in the expectation of the sum of gradients.One way is to solve this problem is to set the fake gradientFij to be zero. If yij=0, the user sends a random variable M0 to the central server. This method is used in [17], where Mx is a Bernoulli random variable with mean value x. However, the disadvantage of this method is that the distribution of gradients in the yij=0 case is very different from the distribution of the real gradient. For example, we can collect some data of gij sent by the user i, and use a statistical test to test if this data obeys the certain distribution of mean 0, then we can know whether yij=0.All in all, we need to strike a balance between privacy and accuracy. We need to provide a fake gradient to make sure the accuracy will not be greatly affected and let these two distributions, the fake one and the real one, to be statistically indistinguishable as far as possible.


## 4. The Main Results

In this paper, since we are concerned about the items of users, we will focus on considering the statistical distance ofyij=0 and yij=1 distributions. We propose a novel algorithm to protect items of the users. In our algorithm, the user will submit a noise-added fake gradient in the yij=0 case. The K-L distance between the real and fake distributions will be small so that they are hard to be distinguished. On the other hand, we will study how will the fake gradients influence the model accuracy. We will show that in our algorithm, the updating rules can be reduced to a time-delay SGD, which will not influence the accuracy.In our algorithm, the random mechanismM we choose is the Gaussian random mechanism, Md=Nd,σ2. One of the advantages is that there is a very good composition theorem [26] which gives a much tighter estimate on the multi-iteration privacy loss for Gaussian mechanism-based differential privacy gradient descent algorithm.Theorem 3 (Theorem 1 in [26]).
LetC be the gradient bound in privacy gradient descent, there exist two constants c1 and c2 such that the after k iterations, the Gaussian noisy privacy gradient descent algorithm is ε,δ-differentially private for any δ>0 if we choose(9)σ≥c2CTln1/δε.Generally,C is chosen to be a prior bound of the gradient norm, so we do not write it in the algorithm description explicitly.In the case of the Gaussian random mechanism, it is easy to calculate the K-L distance between distributions. In the following section, we will show that we can find a good choice of the fake gradient.


### 4.1. Estimating the K-L Distance between Two Distributions

Given a gradient sequenceyj with length k, a probability of yj can be represented in the following form.(10)Pyj=o1:k=∏i=1kPyji=oi|yji−1=oi−1.Using this form we can calculate K-L distance.Given two probability measuresP1 and P2 in length k sequence space, we have(11)DP1,P2=∫P1o1:k∑i=1klogP1oi|oi−1P2oi|oi−1do=∑i=1k∫P1oi|oi−1P1oi−1logP1oi|oi−1P2oi|oi−1doidoi−1=∑i=1k∫P1oi−1DP1oi|oi−1,P2oi|oi−1doi−1.In each iteration, the user will sent a perturbed gradientgij′ to the central server, which has the following forms:(12)gij′=uirij−uiTvj+N0,σ2,ifyij=1,Fij+N0,σ2,ifyij=0.The we havePrealot|ot−1=Pxt+ηij=ot, where xt is the gradient calculated from ot−1, so DPrealot|oi−1,Pfakeot|oi−1=DNxtij,σ2,NGij,σ2.This is the K-L distance between two Gaussian distributions with the sameσ. We can show that DNxtij,σ2,NGij,σ2=const+1/2σ2xtij−Gij2.From equation (11), if we want to optimize the K-L distance, we need to consider(13)∑t∫Prealxtij12σ2xtij−Fij2dxtij.Although we do not know the distribution of real gradients, this means value can be estimated by sampling. LetS be the set of user i such that yij=1.(14)∫Prealxtij12σ2xtij−Fij2dxtij∼∑i∈S12σ2xtij−Fij2.And in our algorithm, for a given itemj, all the users will use the same F—in other words, we Fij is independent of i. then the above equation is a function of the quadratic form.(15)∑i∈S12σ2xtij−Fj2.In order to minimize this K-L distance, we should setFj=∑i∈Sxij/#S. Gjt≈1/m∑i∈Suitrij−uiTtvjt=∇vjLvjt. However, at time t, the user i can not get the current gradient ∇vjLvjt. However, in the following section, we will show that in our algorithm we can estimate it from the previous gradient ∑igijt−1.


### 4.2. Algorithmic Description

In Algorithm1 with Gaussian random mechanism, we can see that the central server will receive the gradients submitted from the users, whose summation is as follows:(16)Gj=∑iwithyij=1uirij−uiTvj+N0,σ2+∑iwithyij=0Fj+N0,σ2.SupposeFj=0, Gj is just a Langevin stochastic gradient [30] whose expected value is the total gradient. When Fj≠0, using Gj to update the parameters will generally influence the accuracy of the model. One way to solve this problem is to subtract a value in the central server.(17)Gj=∑iwithyij=1uirij−uiTvj+N0,σ2+∑iwithyij=0Fj+N0,σ2−NjFj.In order to determine the value ofNj to make the Fj part small, we can use the Random Response mechanism.The random Response mechanism [31] is a well-known method to obtain statistical information on sensitive issues, e.g., the proportion of AIDS. In our algorithm, we will use the Random Response mechanism to count the number of yij=0 items, which is used for the central server to correct the sum of the gradients.The procedure of the Random Response mechanism is that the responder will give the true answer with probabilityp>0.5, and with probability 1-p, the answer will give an opposite answer.Theorem 4.
(Warner, 1965, in [31]). Suppose the number of the answer of y=0 is n1, and the total number of the responders is n. If p≠1/2, p−1/2p−1+n1/2p−1n is an unbiased estimate of the y=0 ratio with variance θ1−θ/n+p1−p/n2p−12, where θ is the real ratio of y=0 items.The variance isO1/n, so if the total number of the users is large enough, with a high probability, θ^≈θ.The whole process is shown in Algorithm2.Algorithm 2: Noisy matrix factorization with fake gradient.
Input: Redefined iteration number k, learning rate η, probability p for Random Response and Standard deviation of Gaussian distribution σ.Output: Item profile matrix VFor all itemsj, use the probability p Random Response method to estimate the ratio of the users with yij=0 as θj.Randomly initializeui0,vj0 for all i and j.fort=1,2,3…doInitializeGj=0, nj=0 for all j = 1, 2, …, n in central server.fori=1,2,3,…,mdoOn user i: sample B itemsS=S1,S2,…,SB uniformly from{1,2,3,…,n}forjinSdonj=nj+1ifyij=1thengij=uirij−uiTvjDrawgij′∼Nxij,σ2endelseift≠1thenFij=ΔVjendelseFij=ui0−uiTvjendgij=FijDrawgij′∼Nxij,σ2endendGj=Gj+xij′.endforj=1,2,…,ndoifnj=0thenGj=0ΔVj=0endelseGj=Gj−θjnj×ΔVjt−1ΔVjt=Gj/1−θjnjGj=Gj/mvj=vj+ηGjendendfori=1,2,3,…,mdoUpdateui on the local device by gradient descent.endendIt is easy to see that, in the central server, the update process has the following forms:(18)vjt+1=vjt−η∇vjLvjt,z+numj−θjnjnΔVj,where ∇vjLvjt,z is the sampling stochastic gradient and numj is the number of yij=0 terms in sampling.As forΔVj, we know that(19)ΔVjt=∑i∈Sgijt−1+#i∉S−θjnjΔVjt−11−θjnj∼∑i∈Sgijt−1#S.Note that since the regularization term bound the norm of matrixU and V, there exits a small constant β to make the loss function L(u, v) to be β−smooth, that is to say,(20)∇vjLvjt−1−∇vjLvjt2≤βvjt−1−vjt2.Since1/η≫β, ∇vjLvjt−1 is a good approximation of ∇vjLvjt.So we have the folowing:(21)vjt+1=vjt−η∇vjLvjt,z+μ∇vjLvjt−1,z+ζ.One can easily prove that the variances of all these estimations areO1/n.


### 4.3. The Influence of Model Accuracy

We can see the form of updating rule (21) is a stochastic gradient descent with time delay. It can be shown that even if μ a not small, time delay SGD will still have good convergence.The convergence of SGD with time delay is proved in [32]. In this paper, Lian proved the convergence of asynchronous stochastic gradient descent which has the same form as equation (21).Theorem 5.
(Theorem 1 in [32]). Assume the loss function is β−smooth, η is the learning rate, B is the batch size, and T is the time delay. If(22)βBη+2β2B2Tη∑kTη≤1,after K iterations, we have with high probability,(23)mink∇fxk2≤4fx1−fx∗βBKσ,Wherefx∗ is the global minimum of f and σ is the standard deviation of stochastic gradients.Proof of Theorem 5.
In this case, the stochastic gradientsGm,t sent by the node m at time t can be written as Gm,t=∇fxt−τm,t+ζt,m, where τm,t is the time delay of the gradient and ζt,m is the noise (including noise from the stochastic gradients and the Gaussian noise we added). In our case, ζt,m is a sub-Gaussian random variable. To simplify the description, we assume ζt,m is σ-sub-Gaussian.(24)fxτ+1−fx0=∑k=0τfxk+1−fxk≤∑k=0τ−Bη2∇fxk2+3η2L4−η2B∑m=1B∇fxk−τk,m2+β2TBη∑j=k−Tk−1η2∑m=1B∇fxj−τj,m2−η∇fxk,∑m=1Bζk,m+3η2β2∑m=1Bζk,m2+β2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2=∑k=0τ−Bη2∇fxk2+∑k=0τ3η2β4−η2B∑m=1B∇fxk−τk,m2+β2TBη∑j=k−Tk−1η2∑m=1B∇fxj−τj,m2−∑k=0τη∇fxk,∑m=1Bζk,m+3η2β2∑m=1Bζk,m2+β2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2≤∑k=0τ−Bη2∇fxk2+∑k=0τη23β4+β2BT2η−η2B∑m=1B∇fxk−τk,m2−∑k=0τη∇fxk,∑m=1Bζk,m+∑k=0τ3η2β2∑m=1Bζk,m2︸T2,a+∑k=0τβ2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2︸T2,b.
In order to estimateT2=T2,a+T2,b, we can use lemmas in [33].
Letζk=1/B∑m=1Bζk,m. With probability 1−e−ι, we have the following:(25)−∑k=0τηB∇fxk,ζk≤ηB8∑k=0τ∇fxk2+cησ2ι.
This is from Lemma 30 in [33].
With high probability,(26)∑k=0τ3η2β2∑m=1Bζk,m2≤3η2β2Bcσ2τ+1+ι.
And with high probability,(27)∑k=0τβ2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2≤β2TBη3Bcσ2τTBη+1+T+ι≤η2L2Bcσ2τ+1+ι.
We have the following:(28)T1≤ηB8∑k=0τ∇fxk2+cησ2ι+2η2βBcσ2τ+1+ι,η23β/4−β2MT2η−η/2B<0. With probability at least 1−3e−ι,(29)fxτ+1−fx0≤∑k=0τ−3Bη8∇fxk2+cησ2ι+2η2βBcσ2τ+1+ι.
The theorem follows.
This theorem has the same form as the convergence theorem of general and SGD, and in our case, we haveT=1. So we can show this time delay will not influence the convergence.


### 4.4. Privacy Loss in the Random Response Mechanism

At the start of our algorithm, we need to use the Random response mechanism to estimate the ratio ofyij, which will cause a privacy loss. However, we can show that since we need a large number of iterations in the machine learning algorithm, the initial privacy loss is insignificant.It is easy to prove that the Random response mechanism islnp/1−p-Differential Privacy. We know from Theorem 3 that ε∼Okln1/δ after k iterations. If n is large enough, we can choose a p near 0.5, and when k is large, lnp/1−p will be much less then ε.Noting that the K-L distance for a lengthk sequence is O(k), the discussion on the K-L distance is the same.


## 4.1. Estimating the K-L Distance between Two Distributions

Given a gradient sequenceyj with length k, a probability of yj can be represented in the following form.(10)Pyj=o1:k=∏i=1kPyji=oi|yji−1=oi−1.Using this form we can calculate K-L distance.Given two probability measuresP1 and P2 in length k sequence space, we have(11)DP1,P2=∫P1o1:k∑i=1klogP1oi|oi−1P2oi|oi−1do=∑i=1k∫P1oi|oi−1P1oi−1logP1oi|oi−1P2oi|oi−1doidoi−1=∑i=1k∫P1oi−1DP1oi|oi−1,P2oi|oi−1doi−1.In each iteration, the user will sent a perturbed gradientgij′ to the central server, which has the following forms:(12)gij′=uirij−uiTvj+N0,σ2,ifyij=1,Fij+N0,σ2,ifyij=0.The we havePrealot|ot−1=Pxt+ηij=ot, where xt is the gradient calculated from ot−1, so DPrealot|oi−1,Pfakeot|oi−1=DNxtij,σ2,NGij,σ2.This is the K-L distance between two Gaussian distributions with the sameσ. We can show that DNxtij,σ2,NGij,σ2=const+1/2σ2xtij−Gij2.From equation (11), if we want to optimize the K-L distance, we need to consider(13)∑t∫Prealxtij12σ2xtij−Fij2dxtij.Although we do not know the distribution of real gradients, this means value can be estimated by sampling. LetS be the set of user i such that yij=1.(14)∫Prealxtij12σ2xtij−Fij2dxtij∼∑i∈S12σ2xtij−Fij2.And in our algorithm, for a given itemj, all the users will use the same F—in other words, we Fij is independent of i. then the above equation is a function of the quadratic form.(15)∑i∈S12σ2xtij−Fj2.In order to minimize this K-L distance, we should setFj=∑i∈Sxij/#S. Gjt≈1/m∑i∈Suitrij−uiTtvjt=∇vjLvjt. However, at time t, the user i can not get the current gradient ∇vjLvjt. However, in the following section, we will show that in our algorithm we can estimate it from the previous gradient ∑igijt−1.


## 4.2. Algorithmic Description

In Algorithm1 with Gaussian random mechanism, we can see that the central server will receive the gradients submitted from the users, whose summation is as follows:(16)Gj=∑iwithyij=1uirij−uiTvj+N0,σ2+∑iwithyij=0Fj+N0,σ2.SupposeFj=0, Gj is just a Langevin stochastic gradient [30] whose expected value is the total gradient. When Fj≠0, using Gj to update the parameters will generally influence the accuracy of the model. One way to solve this problem is to subtract a value in the central server.(17)Gj=∑iwithyij=1uirij−uiTvj+N0,σ2+∑iwithyij=0Fj+N0,σ2−NjFj.In order to determine the value ofNj to make the Fj part small, we can use the Random Response mechanism.The random Response mechanism [31] is a well-known method to obtain statistical information on sensitive issues, e.g., the proportion of AIDS. In our algorithm, we will use the Random Response mechanism to count the number of yij=0 items, which is used for the central server to correct the sum of the gradients.The procedure of the Random Response mechanism is that the responder will give the true answer with probabilityp>0.5, and with probability 1-p, the answer will give an opposite answer.Theorem 4.
(Warner, 1965, in [31]). Suppose the number of the answer of y=0 is n1, and the total number of the responders is n. If p≠1/2, p−1/2p−1+n1/2p−1n is an unbiased estimate of the y=0 ratio with variance θ1−θ/n+p1−p/n2p−12, where θ is the real ratio of y=0 items.The variance isO1/n, so if the total number of the users is large enough, with a high probability, θ^≈θ.The whole process is shown in Algorithm2.Algorithm 2: Noisy matrix factorization with fake gradient.
Input: Redefined iteration number k, learning rate η, probability p for Random Response and Standard deviation of Gaussian distribution σ.Output: Item profile matrix VFor all itemsj, use the probability p Random Response method to estimate the ratio of the users with yij=0 as θj.Randomly initializeui0,vj0 for all i and j.fort=1,2,3…doInitializeGj=0, nj=0 for all j = 1, 2, …, n in central server.fori=1,2,3,…,mdoOn user i: sample B itemsS=S1,S2,…,SB uniformly from{1,2,3,…,n}forjinSdonj=nj+1ifyij=1thengij=uirij−uiTvjDrawgij′∼Nxij,σ2endelseift≠1thenFij=ΔVjendelseFij=ui0−uiTvjendgij=FijDrawgij′∼Nxij,σ2endendGj=Gj+xij′.endforj=1,2,…,ndoifnj=0thenGj=0ΔVj=0endelseGj=Gj−θjnj×ΔVjt−1ΔVjt=Gj/1−θjnjGj=Gj/mvj=vj+ηGjendendfori=1,2,3,…,mdoUpdateui on the local device by gradient descent.endendIt is easy to see that, in the central server, the update process has the following forms:(18)vjt+1=vjt−η∇vjLvjt,z+numj−θjnjnΔVj,where ∇vjLvjt,z is the sampling stochastic gradient and numj is the number of yij=0 terms in sampling.As forΔVj, we know that(19)ΔVjt=∑i∈Sgijt−1+#i∉S−θjnjΔVjt−11−θjnj∼∑i∈Sgijt−1#S.Note that since the regularization term bound the norm of matrixU and V, there exits a small constant β to make the loss function L(u, v) to be β−smooth, that is to say,(20)∇vjLvjt−1−∇vjLvjt2≤βvjt−1−vjt2.Since1/η≫β, ∇vjLvjt−1 is a good approximation of ∇vjLvjt.So we have the folowing:(21)vjt+1=vjt−η∇vjLvjt,z+μ∇vjLvjt−1,z+ζ.One can easily prove that the variances of all these estimations areO1/n.


## 4.3. The Influence of Model Accuracy

We can see the form of updating rule (21) is a stochastic gradient descent with time delay. It can be shown that even if μ a not small, time delay SGD will still have good convergence.The convergence of SGD with time delay is proved in [32]. In this paper, Lian proved the convergence of asynchronous stochastic gradient descent which has the same form as equation (21).Theorem 5.
(Theorem 1 in [32]). Assume the loss function is β−smooth, η is the learning rate, B is the batch size, and T is the time delay. If(22)βBη+2β2B2Tη∑kTη≤1,after K iterations, we have with high probability,(23)mink∇fxk2≤4fx1−fx∗βBKσ,Wherefx∗ is the global minimum of f and σ is the standard deviation of stochastic gradients.Proof of Theorem 5.
In this case, the stochastic gradientsGm,t sent by the node m at time t can be written as Gm,t=∇fxt−τm,t+ζt,m, where τm,t is the time delay of the gradient and ζt,m is the noise (including noise from the stochastic gradients and the Gaussian noise we added). In our case, ζt,m is a sub-Gaussian random variable. To simplify the description, we assume ζt,m is σ-sub-Gaussian.(24)fxτ+1−fx0=∑k=0τfxk+1−fxk≤∑k=0τ−Bη2∇fxk2+3η2L4−η2B∑m=1B∇fxk−τk,m2+β2TBη∑j=k−Tk−1η2∑m=1B∇fxj−τj,m2−η∇fxk,∑m=1Bζk,m+3η2β2∑m=1Bζk,m2+β2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2=∑k=0τ−Bη2∇fxk2+∑k=0τ3η2β4−η2B∑m=1B∇fxk−τk,m2+β2TBη∑j=k−Tk−1η2∑m=1B∇fxj−τj,m2−∑k=0τη∇fxk,∑m=1Bζk,m+3η2β2∑m=1Bζk,m2+β2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2≤∑k=0τ−Bη2∇fxk2+∑k=0τη23β4+β2BT2η−η2B∑m=1B∇fxk−τk,m2−∑k=0τη∇fxk,∑m=1Bζk,m+∑k=0τ3η2β2∑m=1Bζk,m2︸T2,a+∑k=0τβ2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2︸T2,b.
In order to estimateT2=T2,a+T2,b, we can use lemmas in [33].
Letζk=1/B∑m=1Bζk,m. With probability 1−e−ι, we have the following:(25)−∑k=0τηB∇fxk,ζk≤ηB8∑k=0τ∇fxk2+cησ2ι.
This is from Lemma 30 in [33].
With high probability,(26)∑k=0τ3η2β2∑m=1Bζk,m2≤3η2β2Bcσ2τ+1+ι.
And with high probability,(27)∑k=0τβ2Bη3∑j=k−τkmaxk−1∑m=1Bζj,m2≤β2TBη3Bcσ2τTBη+1+T+ι≤η2L2Bcσ2τ+1+ι.
We have the following:(28)T1≤ηB8∑k=0τ∇fxk2+cησ2ι+2η2βBcσ2τ+1+ι,η23β/4−β2MT2η−η/2B<0. With probability at least 1−3e−ι,(29)fxτ+1−fx0≤∑k=0τ−3Bη8∇fxk2+cησ2ι+2η2βBcσ2τ+1+ι.
The theorem follows.
This theorem has the same form as the convergence theorem of general and SGD, and in our case, we haveT=1. So we can show this time delay will not influence the convergence.


## 4.4. Privacy Loss in the Random Response Mechanism

At the start of our algorithm, we need to use the Random response mechanism to estimate the ratio ofyij, which will cause a privacy loss. However, we can show that since we need a large number of iterations in the machine learning algorithm, the initial privacy loss is insignificant.It is easy to prove that the Random response mechanism islnp/1−p-Differential Privacy. We know from Theorem 3 that ε∼Okln1/δ after k iterations. If n is large enough, we can choose a p near 0.5, and when k is large, lnp/1−p will be much less then ε.Noting that the K-L distance for a lengthk sequence is O(k), the discussion on the K-L distance is the same.


## 5. Experiments

We now show the performance of our algorithm. We evaluate three types of privacy gradient descent algorithms:(i)
Algorithm1, the noisy gradient descent with Fij=ui0−uiTvj. The users will submit a gradient Fij=ui0−uiTvj+ζ if yij=0, where ζ is a N0,σ2 Gaussian random variable.(ii)
Algorithm2, noisy gradient descent with Fij=ζ.(iii)
Algorithm 3, our algorithm in this paper.In theFij=0 case, the only noise in the total gradient is caused by Gaussian noise added to the users’ device. This algorithm will be accurate but has no ability to protect the item's privacy. We will show that the performance of our algorithm is very close to the case Fij=0 and much better than the algorithm using fake ratings.We test on MovieLens 100k dataset [34]. This version contains 100k ratings of 1682 movies submitted by 982 users. This dataset is very sparse. In order to test the performance in different situations of sparsity, for every user, we choose a set F of items to be selected to provide fake gradients. We consider different cases that #F=#S (50% fake gradient density), #F=3#S (75% fake gradient density) to test the algorithm. We set the profile vector dimension d=15, regularization parameters λ=0.001, learning rate η=0.1, σ2=1 and use AdaDelta to optimize. The test RMSE is shown in Figures 1 and 2.Figure 1
RMSE with 50% density.Figure 2
RMSE with 75% density.After 400 iterations, the test RMSE is listed in Table2.Table 2
RMSE in experiments.
Density (%)MethodRMSEFij=ui0−uiTvjFij=0Our algorithm501.71411401.01618151.0167035752.36607260.99667931.0073330We see that when the density of fake rating increases, the test RSME of fake rating algorithm is growing rapidly, and the performance algorithm is very close to the zero mean fake gradient algorithm.


## 6. Related Work

Differential privacy introduced by Dwork [13] is a very strong guarantee to protect privacy. The original version of differential privacy consider a trusted server to provide data to queriers, and the aim is to prevent access to user privacy from queries.Local differential privacy algorithm, such as RAPPORT [22], is to make sure the central server can not access the privacy of the users. The main technology is to add some noise before submitting the data to the server. In the Chrome browser, Google uses a randomized response mechanism to collect the data of the users’ clicks. Also, there are many works to use local differential privacy to perform machine learning algorithms. For example, Google uses local differential privacy Federated Learning [35] to learn a language model in order to improve the performance of the inputting method.One of the difficulties in differential privacy machine learning is that when training a model using many iterations, the privacy guarantees will decline rapidly. Differential privacy for multi-iterations is studied in [25, 26] and a much tighter composition theorem is given.Private recommender system is studied by many authors such as [17–20, 36, 37]. References [17, 18] are based on a matrix factorization recommender system. The algorithm is to adding some noise in users’ devices locally to protect privacy. The algorithm in [17] can protect both the ratings and the items of the user. Their work is based on the work in [24], where they propose a new randomization mechanism and show that their mechanism is better when the dimension of data is large.


## 7. Conclusion

In this paper, we propose a novel privacy matrix factorization algorithm. In our algorithm, we use the Random Response method to estimate the selection ratios of the items, and then we use the average value of the gradients in the previous time as the fake gradient to be sent to the central server. Using our method, we can improve the indistinguishability of the real gradient and fake distributions so that improve the ability to protect user private items. Meanwhile, we show that our algorithms will not cut down the accuracy of the model since the updating rule can be reduced to SGD with time delay, which can be proved to convergence to gradient zero points.



---

*Source: 6683834-2020-12-17.xml*