Differentially Private Matrix Factorization

1 Introduction

Recommendation systems (RSes), which provide users personalized recommendations of contents and services, have been demonstrated to be extremely valuable for boosting websites' revenue and improving user experience. However, everything has two sides, so do these systems. To offer useful recommendations, a RS usually requires users to supply their personal preferences for various items, which raise serious privacy concerns.

Many early studies [A¨ımeur et al., 2008; McSherry and Mironov, 2009; Calandrino et al., 2011] have shown that even those user preferences typically considered insensitive (e.g., ratings of movies and TV viewing history) may be exploited to infer a user's health condition, political inclinations, and even his real identity. What's worse, we have no way to guarantee that recommenders do not abuse user data for financial benefits [Canny, 2002; Nikolaenko et al., 2013]. So, an appealing question is raised: is it possible to build a recommendation system without the recommender learning the users' ratings of items?

∗This work was supported by NSFC-61321491, NSFC61425024, and NSFC-61300235

There are many collaborative filtering techniques available to build a recommendation system. Matrix factorization (abbrev. MF) [Koren et al., 2009; Cand`es and Recht, 2009] is among the most popular and successful. It wins the famous Netflix prize competition [Koren et al., 2009], and is being used in a lot of real-world recommendation systems. So, this paper aims to propose a privacy-preserving MF scheme.

Just as the name suggests, MF aims to factorize the useritem rating matrix R into the product of two smaller matrices U and V , which are considered to capture latent features of users and items, respectively. The core of this method is to utilize some machine learning algorithm, e.g., Stochastic Gradient Descent, to search for U and V that minimize the prediction errors on the set of known ratings. A privacypreserving MF scheme should guarantee that the execution of the learning algorithm exposes only V to the recommender but never any information about individual ratings or even U.

Nikolaenko et al. [2013] first study this problem, and propose an elegant solution through a cryptographic technique known as garbled circuits. Nevertheless, garbled circuits are considered computation expensive even if they have significantly reduced time overheads by exploiting the sparsity characteristic of users' rating matrix. In this paper, we aim to propose a more lightweight solution under the constraint of differential privacy [Dwork et al., 2006], which is a recently hot privacy model with provable privacy guarantees but fewer computation overheads. Specifically, we make the following contributions:

(1) We first consider the scenario where the recommender is trusted, which means personal ratings can be exposed to the recommender. The goal here is to ensure that the final item profile matrix V to be published satisfies ϵ-differential privacy. Our proposal utilizes objective-perturbation technique, which is first proposed in [Chaudhuri and Monteleoni, 2009] to implement differentially private logistic regression, to achieve this goal. We figure out the required distribution of the noise component for objective perturbation in MF.

(2) We then extend the above proposal to the scenario where the recommender is untrusted. For this purpose, we decouple the computations on private ratings from the recommender to users in each iteration of learning. The recommender is only responsible for aggregating perturbed local results in a differentially private way. We address the challenge to decompose the noise component for objective perturbation into small pieces that can be determined locally and independently by users. We also propose a third-party-based optimization to reduce the noises needed to add in each iteration for improving the precision of results.

1. The above proposal assumes that every user remains online during the whole process MF. However, MF may last for more than one week so that it is impractical to make such assumption. Therefore, we further present an improvement to make our proposal support the more practical setting that allows users to leave and join during MF.

(4) We conduct experiments based on two datasets. The results demonstrate that our proposal is efficient enough and, moreover, the privacy protection measures bring limited side effects on the precision of learning results.

2 RelatedWork

There have been some work introducing differential privacy to recommender systems. Nevertheless, most of them [McSherry and Mironov, 2009; Machanavajjhala et al., 2011; Park and Acharya, 2011] consider that the recommender is trusted and allowed to explicitly aggregate users' ratings. Their only goal is to guarantee that the distribution of the results published by the recommender is insensitive to any individual record and thus prevent other parties from inferring a single user's ratings. Xin and Jaakkola [2014] are the first to deal with the untrusted recommender without using cryptographic tools. Similar with our work, they separate sensitive computations that can be executed on the user side from those must be carried out on the server. However, their proposal demands the existence a group of public users who are willing to share their ratings with the recommender, which is not fulfilled in our scenario. In addition, this proposal does not satisfy differential privacy, i.e., is not provably secure.

As the core of MF is a machine learning algorithm, our work is also quite related to another area: differentially private machine learning [Chaudhuri and Monteleoni, 2009; Chaudhuri et al., 2011]. Work in this area aims to implement differentially private versions of prevailing machine learning algorithms such as logistic regression and support vector machines. These algorithms mostly focus on the single-party setting, where all the user data has been aggregated on a singe trusted party. Their goal is to guarantee that any published model that is learned from the data satisfies differential privacy. Rajkumar and Agarwal [2012] propose an elegant differentially private stochastic gradient descent algorithm for the multi-party setting. Note that stochastic gradient descent is a key solution to MF. Unfortunately, we cannot directly apply this proposal since the scenario we consider in this paper is not completely the same with theirs although both of them involve multi-parties. The biggest difference is that the parties in their setting are organizations owning a large number of users's data, while the ones in our setting are individual users owning their own data. As we mentioned in Sec. 4.2, if we directly apply their approach, the precision of the obtain model will be extremely low. Moreover, their proposal can only guarantee a slightly weaker form of differential privacy instead of the original form.

3 Preliminaries

3.1 Matrix Factorization

This paper considers the standard setting of collaborating filtering, in which n users rate a small subset of m items. We denote by R = [rij]n×m the full rating matrix, and by R ⊂ [n] × [m] the user-item pairs that have values in R, i.e., for which ratings have been generated. Note that R is usually extremely sparse, i.e., W = |R| = Θ(m+ n) ≪ m× n. The goal of a recommendation system is to predict the blank ratings for the user-item pairs in [n] × [m] \ R.

MF is one of the most popular methods for solving this problem. In its basic form, each user i is characterized by a profile vector ui ∈ Rd , and each item j is characterized by a profile vector vj ∈ Rd . User i's rating of item j, which is denoted by rij, is then approximated by the inner product of ui and vj, i.e., uTi vj. The dimension d of these vectors are very small, say 20 to 100. The recommender computes the profile matrix U = [uTi ]i∈[n] and V = [vT j ]i∈[m] by performing the following regularized least squares minimization (RLSM):

where both λ and µ are positives. The same as the work in Nikolaenko et al. [2013], we focus on the popular approach, stochastic gradient descent (abbr. SGD), to minimize Equation (1). Denote by E(U, V ) the squared prediction error. i.e., E(U, V ) = ∑(i,j)∈R(rij - uTi vj)2 . SGD iteratively learns U and V based on the following updating rules:

where γ > 0 is a small gain factor and

The initial U(0) and V (0) are composed of uniformly random norm 1 rows.

3.2 Differential Privacy

Differential privacy becomes a hot privacy model recently as it provides provable privacy guarantees but introduces fewer computation overheads. It requires that the output of any computation based on a underlying database is insensitive to the removal and the addition of a particular record. This indicates that it is privacy harmless for a record owner to include his record in the database. We formally give the definition of different privacy below [Mohammed et al., 2011].

Definition 1 (ϵ-differential privacy) A randomized algorithm Ag is differentially private if and only if any two databases D and D′ contain at most one different record (i.e., |D△D′ | ≤ 1), and for any possible anonymized output O ∈ Range(Ag): Pr[Ag(D) = O] ≤ eϵ × Pr[Ag(D′ ) = O], where the probability is taken over the randomness of Ag.

In the above equation, ϵ is positive, and it is believed that the smaller its value is, the stronger the privacy guarantee is.

3.3 Setting

This paper considers a recommender system including two types of actors: users and the recommender. Every user i ∈ [n] wants to preserve her ratings. The recommender is untrusted, which means he is curious about and even may misuse users' ratings for making profits.

Our objective is to design a differentially private MF scheme to allow the recommender to obtain the accurate item profile matrix, i.e., V , but neither the user profile matrix, i.e., U, nor the individual ratings. Note that we should prevent the recommender from getting U since they can derive users' ratings precisely by computing the product of U and V . As Nikolaenko et al. [2013] mentioned, once V is learned and published, a user i can infer her user profile ui by solving (1) w.r.t. ui via ridge regression. With both ui and V , she can further predict her preferences on all the items locally.

4 Differentially Private Matrix Factorization

4.1 Scenario with Trusted Recommender

We first consider the simple centralized scenario, where the recommender is assumed to have collected the ratings of users and wants to learn and publish V satisfying ϵdifferential privacy. In this scenario, the recommender is considered to be trusted and never disclose users' privacy. Matrix U must be kept secret, otherwise the attacker can predict a specific user's ratings of all the items as long as she knows which vector in U corresponds to this user.

We apply the objective perturbation method, which is first proposed by [Chaudhuri and Monteleoni, 2009], to fulfill the above goal. Its basic idea is to achieve differential privacy by randomly perturbing the objective function instead of perturbing the output of the leaning algorithm. Specifically, in our case, the objective in (1) is perturbed as follows:

where N = [ηj ]d×m is a noise matrix for objective perturbation. Because U is kept confidential, the recommender can first perform the original RLSM in (1), and then use the obtained U as a constant profile matrix when minimize (6). That is why (6) contains only one matrix variable, i.e., V .

Theorem 1 Let [minr,maxr] (minr,maxr ∈ R) be the range of users' rating values. If each vector ηj ∈ N in (6) is independently and randomly picked from the density function p(ηj) ∝ e- ϵ‖ηj‖ 2∆ , where ∆ = maxr -minr, the derived V satisfies ϵ-differential privacy.

Proof 1 Let D = {ri1j1 , ri2j2 , · · · , riW-1jW-1 , rpq} and D′ = {ri1j1 , ri2j2 , · · · , riW-1jW-1 , r′pq } be two sets of ratings differing at one record rpq. Here, {(i1, j1), (i2, j2), · · · , (iW-1, jW-1, (p, q))} = R. Let N and N ′ be the noise matrices in (6) when training with D and D′ , respectively. Obviously, ˜ C(V ) is differentiable anywhere.

Let ¯ V be the derived item profile matrix minimizes both the optimization problems, we have ∀j ∈ {1, 2, · · · ,m}, ▽vj ˜ C(D, ¯ vj) = ▽vj ˜ C(D′ , ¯ vj) = 0. Thereby,

If j ̸= q, we can derive from (7) that:

So, ∀j ̸= q, ‖ηj‖ = ‖η′j ‖.

If j = q, we can derive that:

Since ‖up‖ ≤ 1 and |rpq - r′pq | ≤ ∆, we obtain that ‖ηj - η′j ‖ ≤ 2∆.

As ‖ηq - η′q ‖ ≤ 2∆, the above ratio is no more than eϵ .

In this scenario, we do not jointly optimize (6) w.r.t. U and V because it would invalidate Theorem 1. We cannot guarantee that the values of ui at the both sides of Eqa (7) are equal in this case. As a result, it would significantly increase the difficulty of deriving the distribution of eta, which is critical for our proposal.

4.2 Scenario with Untrusted Recommender

We now try to extend our proposal to the scenario described in Sec. 3.3. In this new setting, the central recommender is considered to be non-trusted. Therefore, users can no longer feel free to send their raw ratings of items to the recommender.

Fortunately, we observe from (2) that the adaption of a user's profile vector ui only relies on user i's own ratings rather than those of other users, which means all these computations can be performed locally instead of centrally on the recommender side. Therefore, user profile vectors can be kept secret on the user side, and thus protected against the recommender. Certainly, user i has to request the immediate profile vectors of items that he has rated from the recommender in each round. So long as these item profile vectors satisfying ϵdifferential privacy, the user profile vector derived from them must satisfy ϵ-differential privacy as well, which means no user can learn private ratings of others in this process.

Different from the user profile vectors, the adaption of each item profile vector vj in each iteration relies on multiple users' ratings of item j as well as their private user profile vectors, which means such computations involve multiparties. We may leverage existing secure multi-party computing methods based on cryptographic techniques to protect user privacy in this process, however these methods usually rely on too many heavyweight cryptographic operations that are far from practical. In this paper, we try to implement a multi-party version of the objective perturbation method described in the last section to address this challenge.

Specifically, after the objective is perturbed as (6), the updating rule of vj in (3) becomes

where ηj is a random noise vector whose density function p(ηj) = k · e- ϵ‖ηj‖ 2∆ . Suppose that Userj = {i1, i2, · · · , ik} are k users that have rated item j. Our proposal decomposes this update and make these users each compute a piece of information, i.e., her local gradient ̂∇is vj (t) = ∇is vj (t) + ηis j , where ∇is vj (t) = -2ui(t)(rij - ui(t)T vj(t)) and ∑s=1,2,··· ,k ηis j = ηj. They then forward these partial results to the recommender, who combines them to update vj(t). However, this extension encounters two challenges in order to satisfy ϵ-differential privacy:

(1) According to Theorem 1, the objective perturbation will preserve differential privacy if each noise vector ηj ∈ N has the density

However, in the distributed scenario, ηj is no longer selected individually by the recommender. So, the first challenge is j such that the re-

(2) The objective perturbation guarantees that publishing final V does not breach ϵ-differential privacy. Nevertheless, in the current setting, the untrusted recommender obtain not vj ) from each user after each iteration. Although each of these results include a noise vector, the recommender can easily eliminate their effect: Considering the following difference between results of consecutive iterations

how the k users can independently select ηis sulting sum ∑s=1,2,··· ,k ηis j follows the distribution of (10)? only final V but also a series of immediate results (i.e., ̂∇is

the recommender learns the difference between the true local gradients and the effect of ηisj has been eliminated. This may help the recommender predict some information about user is's ratings, and thus compromise privacy constraint. We name this attack difference attack.

Our solution to the first problem relies on the lemma below.

Lemma 1 If each element in every ηj of (6) is independently and randomly picked from Laplace (0, 2∆√d/ϵ), the derived item profile matrix V satisfies ϵ-differential privacy.

Proof 2 We still follow the proof of 1 and come to (8). Suppose that ηq = [x1, x2, · · · , xd]T . As each element xi is independently randomly picked from the Laplace (0, 2∆√dϵ) distribution, its probability density function is p(xi) =

So, we obtain the conclusion.

Besides this lemma, we also have the following theorem:

Theorem 2 If random number h ∼ Exponential(1), and random number c ∼ N(0, 1) independent of h, then X = µ + b√2hc ∼ Laplace(µ, b). Here, the notation "∼" means "distributed as".

Proof 3 Please see [Kotz et al., 2001].

We can then use the above theorem to guide each user is ∈ Userj to pick ηj is independently such that the resulting sum ηj satisfying (10). In particular, before the first round of iteration, the recommender picks a random number vector Hj ∈ Rd , of which each element Hj[l] ∼ Exponential(1), and sends it to every user in Userj. Then, user is independently selects a random vector Cis , where each element Cis [l] ∼ N(0, 1/k) and computes ηis j according to

She will use ηis j to compute ̂∇is vj in each round. It is easy to prove that the resulted sum of ηis j on k users satisfies (10).

Here, although Hj is picked by the recommender, he has no ways to predict the real value of ηis j due to the existence of Cis determined by the user locally. Thus, it is infeasible for him to remove this noise piece from ̂∇is vj . In addition, users can easily monitor whether the recommender generates Cis [l] following Exponential(1). Revealing one user's piece noise to the recommender can only harm himself, not give the recommender extra information about the values of other users.

For the scend challenge, Rajkumar and Agarwal [2012] propose a smart solution by adding another noise vector ρis j (t) to each local gradient:

Note that ρis j (t) should be re-sampled during each iteration. They show that the privacy leak due to (11) can be prevented if ρis j (t) can guarantee that ∇is vj (t) + ρis j (t) satisfies ϵ-differential privacy. In our case, it is easy to prove this requirement is fulfilled if the value of ρis j (t) is generated ac-

Unfortunately, if each local gradient value sent to the recommender includes such noise, the utility of V that we obtain is significantly affected according to our experiment. The previous work does not encounter this problem because it considers a different scenario: the parties participating in the distributed learning are organizations having aggregated the records of many users, rather than end users. As a result, the number of parties is far smaller than that in our scenario, which indicates that much fewer noises are introduced in each iteration. Thus, the utility of the final result is affected not as significantly as in our case.

We exploit a semi-honest third-party to address this problem. Here, semi-honest means that this party follows the protocol but is curious about user's privacy. In particular, our solution is composed of the following four steps:

1. When user is requests vj(t) from the recommender in the beginning of the t-th iteration, the server generates a random noise vector ψis j (t), of which the elements are i.i.d. on [0, P]. Here, we denote by P a big integer. It then returns ψis j (t) together with vj(t) to user is.
2. User is first computes ˜∇is vj (t) = ∇is vj (t) + ηis j +˜ ρis j (t). Note that the noise vector ˜ ρis j (t)) here is different fromρis j (t) in (13). We will describe its valuation later. Afterwards, the user further computes φis j (t) = ˜∇is vj (t) + ψis j (t)modP, and forwards it to the third-party.
3. The third-party aggregates the results from users in Userj and computes φj(t) = ∑ks=1 φis j (t)modP. The result is forwarded to the recommender.
4. The recommender computes ˜∇vj (t) = φj(t) - ∑ks=1 ψis j (t)modP, and uses it to update vj(t).

Due to the existence of ψis j (t), it is infeasible for the curious third-party to learn any useful information about the real value of ∇is vj (t) in the above process provided that it does not collude with the recommender. Thereby, the rating value risj is also protected against the third-party. By applying this optimization, to defend against the difference attack we mentioned earlier, we require ∑ks=1 (∇is vj (t) + ˜ ρis j (t)) rather than every ∇is vj (t) + ρis j (t) to satisfy ϵ-differential privacy. It is easy to prove that so long as

such requirement is fulfilled. Each user uis can use the same method proposed earlier for picking ηj is (t) to pick ˜ ρis j (t) based on Theorem 2. It is easy to demonstrate that ˜ ρis j (t) is much smaller than ρis j (t) with a high probability, which means our scheme above can significantly reduce the side effects on the utility of the learning result.

4.3 Further Practical Consideration

By now, our proposal requires every user to stay online all the time during MF. Nevertheless, this is impractical as MF may last for one or several weeks and there must exist users' leaving and joining during such a long time. Fortunately, according to our experiments on Netflix datasets, SGD-based MF is robust against dynamic changes of users. In the experiments, we make users leave and join with specific proabilites before every iteration, and the adaption in each learning is just based on the data of currently online users. The results show that the precision of the final results is slightly affected.

However, our protection proposal confronts a big challenge under this dynamic setting: it is difficult for different groups of users to produce random variables with the same sum. Note that, in our current design, every noise vector ηj for objective perturbation equals the sum of random vectors locally picked by all the users in Userj. This vector should remain constant in different iterations. Nevertheless, in the dynamic setting, as online users in Userj are always changing, ηj will vary in differential iterations, which result in that final V no longer satisfies ϵ-differential privacy.

We make use of the semi-honest third-party described earlier to address this problem. In this improvement, before starting MF, we add an additional initialization phase to determine every ηj in advance. In particular, this initialization works as follows:

1. The recommender randomly picks k online users, i.e., UO = {ui1 , ui2 , · · · , uik }, and sends each uis ∈ UO a random vector βis j , of which the elements are i.i.d. on [0, P].
2. Then, user uis picks the local noise vector ηis j the same as before, and computes τ is j = ηis j + βis j modP. The result is forwarded to the third-party.
3. The third-party aggregates the results from each user and computes ˜ τj = αj + ∑ks=1 τ is j modP, where αj is another random vector, of which the elements are i.i.d. on [0, P]. The result is sent to the recommender.
4. The recommender then derives ̂ τj = αj + ∑ks=1 ηis j modP by removing each βis j , and keeps it secret.

When MF starts, every iteration executes the same as described in the end of Sec. 4.2 except three exceptions: First, in Step 1, if there are k′ online users collaborating to update vj, the recommender randomly divides ̂ τj into k′ pieces, and sends every user uis in this group a piece ̂ τ is j . Second, user uis will use ̂ τ is j to replace ηis j in Step 2. Third, in Step 3 the third-party minuses αj from φj(t) before uploading.

It is easy to find that by applying the above adaption, ηj no longer varies in different iterations and equals the sum of ηis j , determined by the k online users in the initialization process. Moreover, it is infeasible for the recommender or the thirdparty to infer the true value of ηj if they do not collude. The recommender may compute ˜∇vj (t) - ̂ τj to remove ηj from ˜∇vj (t). However, this operation will introduce a new and more random noise, i.e., -αj, which can better protect the user privacy. The situation is the same for the third-party.

• (a) ϵ = 0.1, change iterations
• (b) 100 iterations, change ϵ

Figure 2: CDF of prediction errors for MovieLens in S1: the recommender is trusted

5 Evaluation

We now evaluate the performance of our proposal based on two public datasets. The first one is reduced from the wellknown Netflix dataset. Specifically, it is composed of 191668 users' ratings of 100 movies. The movies were selected uniformly & randomly from the original dataset, and all the users' ratings of these movies were included. We repeated each experiment by selecting different sets of movies, and did not observe obvious differences among the results. The second one is MovieLens 100k, which consists of 943 users' ratings of 1682 movies. For simplicity, we below refer to them as Netflix and MoveLens, respectively. The range of ratings is on a 5 star range for both.

It is obvious that our privacy-protection mechanismmainly brings two kinds of side-effects on MF: First, it introduces inaccuracies due to the perturbations of the objective and intermediate results. Second, it brings communication overheads among users, the recommender and the third-party in each iteration, which dominate the time costs of the whole system. So, our evaluations mainly use MF accuracy and communication overheads as the key metrics.

For MF accuracy, we mainly consider two metrics. The first is the cumulative distribution function (CDF) of prediction errors, i.e., {|r′ij - rij||(i, j) ∈ R}. We denote by r′ij the ratings predicted by the inner product of ui and vj derived fromMF, and by ri,j the real ratings of users. The second one is the mean increase of prediction errors compared with the baseline, i.e., the original MF scheme without any protection running 100 iterations. We do not take [Nikolaenko et al., 2013]'s mechanism as the baseline because its computation loads are several orders of magnitude greater than ours although they used a much smaller dataset. In addition, as they introduce few noises, their accuracy infinitely approaches the unprotected MF.

We implement our proposals for all the three scenarios considered in this paper: (S1) the recommender is trusted; (S2) the recommender is untrusted but the online users are static; (S3) the recommender is untrusted and the online users are dynamic. For each scenario, we vary ϵ and the iteration counts. The gain factor γ is 2-5 . The parameters λ and µ in (1) are both set to 0.001. The dimension d of all the profile vectors is set to 50.

The results of the first metric for S1 are present in Fig. 1 and Fig. 2. We find that the precision increases with the iteration number and the privacy budget ϵ. Specifically, the side effects of objective perturbation on MF precision become negligible when ϵ ≥ 0.15 for Netflix after 70 iterations. According to Fig. 7(a), the mean increase of prediction errors is below 0.03 compared with the baseline. The results for MovieLens are much better: the MF precision becomes extremely approaching the baseline just after 40 iterations when ϵ = 0.05. According to Fig. 8(b), the mean increase of prediction errors even slightly deceases compared with the baseline. This is because the precision of the raw MF (i.e., the baseline) is not so high that introducing noises in learning may help some elements escape from local optimums.

The results for S2 are present in Fig. 3 and Fig. 4. We can find that the results of this scenario are very close to those of S1 for both datasets, which indicates that the additional noises added in each iteration for defending against the difference attack (Please refer to Sec. 4.2) will not significantly affect MF precision as well. In particular, the mean increase

• (a) ϵ = 0.8, change iterations
• (b) 10000 iterations, change ϵ

Figure 6: CDF of prediction errors for MovieLens in S3: the recommender is untrusted and the online users are dynamic

of prediction errors for Netflix is around 0.14 when ϵ = 0.15 (Please see Fig. 7(a)), and this value declines to near 0 for MovieLens (Please see Fig. 8(a)).

For S3, we first assume that the users get online and offline with probability of 0.005 and 0.01, respectively, after each iteration. The recommender randomly selects at most 1000 and 100 of the online users to participate in the learning in each iteration for Netflix and MoveLens, respectively. The results are shown in Fig. 5 and Fig. 6. We find that for Netflix if we slightly relax the privacy requirement, i.e., improve ϵ from 0.1 to 0.8, the precision of the results can also become extremely close to the baseline after 10000 iterations. In particular, according to Fig. 7(b) the mean increase of prediction errors is below 0.1 when ϵ = 0.8. The increase of iteration rounds is due to that each iteration only covers the data of 1000 online users but not all the 191668 users. In addition, although the iteration round increases, the time cost for each iteration greatly decreases. The performance on MovieLens is still much better than Netflix: the curves in Fig. 6 has become indistinguishable from the baseline after 10000 iterations even when ϵ ≥ 0.05.

We also evaluate our proposals when the joining and leaving probabilities are varied. The results are present in Fig. 9 and Fig. 10. We can find that as the joining probability increases between [0.005, 0.02], the mean increase of prediction errors compared with the baseline declines. This is easy to understand because a larger joining probability indicates more offline users getting online in each iteration, which results in that the MF process can cover a wider set of users after the same number of iterations. Compared with the joining probability, the effect of the leaving probability is not so

ǫ

ǫ

(a) Scenario 1 and 2 (100 iterations) (b) Scenario 3 (10000 iterations)

(a) Scenario 1 and 2 (100 itera-

tions)

(b) Scenario 3 (10000 itera-

tions)

Figure 8: Mean increases of prediction errors for MovieLens compared with the baseline

obvious, especially for Netflix. This is because the base number of online users are much smaller than that of the offline users in the beginning, and thus the slight changing of the leaving probability cannot greatly change the composition of users participating in each iteration.

We next evaluate the communication overheads of our proposal. In S1, MF is performed completely by the recommender, who does not communicate with users. Thus, our proposal introduces no communication overheads. However, the proposals designed for S2 and S3 require cooperations among the recommender, the users and the third-party, and thus do bring communication overheads. Since S2 is not practical, we only consider S3 here.

In this scenario, according to our simulation, if a user rated no more than 20 items, she only needs to download at most 12KB data from the recommender and uploads at most 5KB data to the third-party in each iteration. This indicates that our proposal is efficient enough to be deployed on mobile devices. In addition, for Netflix if the total number of items that the 1000 online users rated are at most 10000 (the number in the real-world is usually much smaller than this value), the total data that the third-party has to send to the recommender in each iteration is less than 3MB, which is still very efficient.

According to our experiment on Netflix, the average times for doing optimization on each client and the third party in each iteration are about 5.7 × 10-4ms and 400ms, respectively. It is infeasible to conduct real experiments to measure the time costs for communication since we are lack of a testbed with 1000 concurrent users. Nevertheless, the litera-

• (a) Leaving probability=0.01
• (b) Joining probability=0.01
• (a) Leaving probability=0.01
• (b) Joining probability=0.01

Figure 10: Effects of joining and leaving probabilities in S3 for MovieLens (10000 iterations, ϵ = 0.1)

ture [Kimpe et al., 2012; Crovella et al., 1999] shows that it is not so difficult for an average provider to build a web system that can handle 1000 concurrent users (each may download or upload a file about 10kb) with the average response time below 1s. So, it is safe to assume that the total time for each iteration can be confined to 5s. Although this is slower than the baseline (0.46s), it is much faster than [Nikolaenko et al., 2013]'s mechanism which took 2.5hr to finish one iteration based on a smaller dataset. For MovieLens, since there are up to 100 users participating in learning in each iteration, the communication overheads are no greater than those of Netflix according to our analysis.

6 Conclusion and FutureWork

We conclude that a differentially private MF mechanism is feasible when the central server is untrusted. The results show that our proposals have little side effects on the precision of results and the efficiency is also high. People can leverage these proposals to build recommender systems in a privacypreserving way. To the best of our knowledge, we are the first to apply differential privacy to the task of MF.

A promising future work is to adapt our proposal to improved variants of the raw MF, such as WNMF (i.e., Weighted Non-negative MF). According to our experiments, such mechanism may significantly improve the precision of MF.