arXiv:1510.08546v1 [cs.CR] 29 Oct 2015

On Differentially Private Online Collaborative
Recommendation Systems
Seth Gilbert

Xiao Liu

Haifeng Yu

Abstract
In collaborative recommendation systems, privacy may be compromised, as users’ opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation
system, and we measure users’ privacy in terms of the standard differential privacy. We give the first quantitative analysis of the trade-offs
between recommendation quality and users’ privacy in such a system by
showing a lower bound on the best achievable privacy for any non-trivial
algorithm, and proposing a near-optimal algorithm. From our results, we
find that there is actually little trade-off between recommendation quality
and privacy for any non-trivial algorithm. Our results also identify the
key parameters that determine the best achievable privacy.
Keywords: differential privacy, collaborative recommendation system,
lower bound, online algorithm

1

Introduction

In this paper we consider an online collaborative recommendation system that
attempts to predict which objects its users will like. Imagine, for example, a
news website which publishes articles every day. When a user enjoys an article,
he/she votes on the article (e.g., upvotes it, likes it, +1s it, etc). Users can
also ask the system for a recommendation, i.e., to suggest an article that they
might like. After reading the recommended article, the user gives the system
feedback on the recommendation so that it can improve its recommendation
quality. In this paper, we work with a simplified, abstract version of this very
common paradigm.
Due to the way it works, a collaborative recommendation system has the
risks of leaking its users’ privacy. Clearly, there are trade-offs between recommendation quality and privacy: a system that gives completely random recommendations certainly leaks no one’s privacy, but it is also useless; in contrast, a
recommendation system that gives high quality recommendations has to make
“full use” of its users’ data, which is more prone to privacy leakage.
In this paper, we adopt ǫ-differential privacy [17] as our formal definition of
privacy, and we give the first quantitative analysis of these trade-offs for online

1

collaborative recommendation systems. Prior to this paper, the topic of differentially private recommendation systems has primarily been examined under
offline matrix models [12,13,21,22,26,30,40]. From the theoretical perspective,
our recommendation model can be viewed as a variant of an online learning
problem. Currently, there are only a limited number of existing papers on differentially private online learning [18, 24, 39], and their privacy models do not
fit the recommendation problem (see Section 3 for more details).
We first study the best achievable privacy for a fixed recommendation quality
by showing a near-tight lower bound on the privacy parameter ǫ (smaller ǫ means
better privacy). For example, if we were to guarantee a trivial recommendation
quality only, then we can achieve “perfect privacy” (i.e., ǫ = 0) by ignoring users’
opinions on objects and recommending randomly. As we set better and better
target recommendation quality, it might be expected that the best achievable ǫ
smoothly gets larger and larger. However, we show that the transition is sharp:
although ǫ = 0 is achievable for the trivial recommendation quality, the lower
bound of ǫ rises to a certain level as long as non-trivial recommendation quality
is to be guaranteed, and it remains essentially the same (up to a logarithmic
factor) as the target recommendation quality increases.
We then propose a novel ǫ-differentially private algorithm. Our algorithm’s ǫ
is within a logarithmic factor to the aforementioned lower bound, and meanwhile
its recommendation quality is also near-optimal up to a logarithmic factor, even
when compared to algorithms providing no privacy guarantee.
Our near matching results surprisingly imply that there are actually little
trade-offs between recommendation quality and privacy — an inherent “amount
of privacy” (up to a logarithmic factor) must be “leaked” for any algorithm with
non-trivial recommendation quality. Our results also identify the key parameters
that fundamentally determine the best achievable recommendation quality and
privacy. We provide more details about our results in Section 4.

2
2.1

Model and Problem Statement
Recommendation System Model

We now describe the model in more detail, abstracting away some of the complications in the scenario above in order to focus on the fundamental trade-offs.
We consider an online collaborative recommendation system that contains
voters, clients and objects, and it repeatedly recommends objects to clients
based on voters’ opinions on objects. A voter/client either likes or dislikes an
object. Voters submit their opinions on objects to the system in the form of
votes, where a vote by voter i on object j indicates that voter i likes object
j; clients receive recommendations from the system and provide feedback to
the system which tells whether they like the recommended objects or not. Since
every client has his/her own personalized preferences, the system will serve each
client separately.
We now describe how the model operates for a particular client C. The

2

system runs for T rounds. In each round t ∈ {1, . . . , T }, a set of m new candidate
objects arrives in the system, out of which the client C likes at least one of them.
We assume that m is a constant, and totally the system has mT objects over
all the T rounds. Let U denote the set of all the voters, and Bt denote the set
of candidate objects in the tth round. After Bt arrives, each voter i ∈ U votes
on one object in Bt ; the system then recommends one object bt ∈ Bt to the
client C (based on the voters’ votes and the previous execution history), and C
responses the system with his/her feedback which tells whether he/she likes bt
or not. The system proceeds into the next round after that.
We measure the recommendation quality by loss, which is defined as the
number of objects that the algorithm recommends to the client C but C dislikes.
A client C is fully characterized by specifying C’s preferences on every object.
However, in a recommendation system, whether a client C likes an object j
or not is unknown until the system has recommended j to C and gotten the
feedback.
We denote the votes of all the voters in U by VhUi, and we call VhUi the
voting pattern of U, or simply a voting pattern when U is clear from the context.
Given a client C and a voting pattern VhUi, a (randomized) recommendation
algorithm A maps the pair (C, VhUi) to a (random) sequence of objects in
B1 × · · · × BT . We call a particular sequence in B1 × · · · × BT a recommendation
sequence.

2.2

Differential Privacy in Recommendation Systems

Voters’ votes are assumed to be securely stored by the system, which are not
accessible from the public. Nevertheless, a curious client may still try to infer
voters’ votes by analyzing the recommendation results. In this paper, we adopt
differential privacy [17] as our definition of privacy. Roughly speaking, differential privacy protects privacy by ensuring that the outputs are “similar” for two
voting patterns VhUi and VhU ′ i if they differ by one voter. Such a pair of voting
patterns are called adjacent voting patterns, and they are formally defined as:
Definition 1 (Adjacent Voting Patterns). Two voting patterns VhUi and VhU ′ i
are adjacent voting patterns iff i) |U △ U ′ | = 1, and ii) for any voter i ∈ U ∩ U ′
and in any round t ∈ {1, . . . , T }, i always votes on the same object in both VhUi
and VhU ′ i.
Generalizing Definition 1, we say that two voting patterns VhUi and VhU ′ i
are k-step adjacent, if there exists a sequence of k + 1 voting patterns VhU0 i =
VhUi, VhU1 i, . . . , VhUk−1 i, VhUk i = VhU ′ i such that VhUℓ i and VhUℓ+1 i are adjacent for any ℓ = 0, . . . , k − 1.
Having defined adjacent voting patterns, we can then apply the standard
differential privacy in [17] to our setting:
Definition 2 (ǫ-Differential Privacy). A recommendation algorithm A preserves
ǫ-differential privacy if Pr[A(C, VhUi) ∈ S] ≤ eǫ Pr[A(C, VhU ′ i) ∈ S] for any
client C, any pair of adjacent voting patterns VhUi, VhU ′ i, and any subset S ⊆
B1 × · · · × BT , where the probabilities are over A’s coin flips.
3

2.3

Attack Model, Power of the Adversary

As indicated by Definition 1 and Definition 2, we protect voters’ privacy against
the client. We do not need to protect the client’s privacy because voters receive
nothing from the system.
Our research goal is to study the theoretical hardness of the aforementioned
recommendation problem, therefore we assume that there is an adversary with
unlimited computational power who controls how the voters vote and which
objects the client likes. The adversary tries to compromise our algorithm’s
loss/privacy by feeding the algorithm with “bad” inputs. From the perspective
of game theory, our recommendation model can be viewed as a repeated game
between the algorithm, who chooses the objects to recommend, and the adversary, who chooses the client’s preferences on objects and the voting pattern. For
our lower bounds, we consider an oblivious adversary that chooses the client’s
preferences on objects and the voting patterns in advance; for our upper bounds,
we consider an adaptive adversary whose choice in time t can depend on the
execution history prior to time t. By doing so, our results are only strengthened.

2.4

Notations

Next we introduce some notations that characterize the system. Some of them
are also the key parameters that determine the best achievable loss/privacy.
The client’s diversity of preferences. A client C’s diversity of preferences
DC is defined to be the number of rounds in which C likes more than one
objects.
The client’s peers. Inherently, a collaborative recommendation system can
achieve small loss only if some voters have similar preferences to the client. Let
the distance between a client C and a voter i be the total number of objects
that are voted on by i but are disliked by C. Given a radius parameter R ∈
{0, . . . , T }, we define a voter i to be a client C’s peer if their distance is within
R. Given a client C, a voting pattern VhUi and a radius parameter R, we can
count the number of C’s peers in U, and we denote it by PC,VhU i,R .
Other notations. We define n to be an upper bound of |U| (i.e., the number of voters), D to be an upper bound of DC (i.e., the client’s diversity of
preferences), and P to be a lower bound of PC,VhU i,R (i.e., the number of the
client’s peers). The reader may wonder why these parameters are defined as
upper/lower bounds. The purpose is to give a succinct presentation. Take n
as an example: since differential privacy needs to consider two voting patterns
with different numbers of voters, if we define n as the number of voters, it would
be unclear which voting pattern we are referring to. The reader can verify that
by choosing the right directions for the parameters (e.g., we define n to be an
upper bound, and P to be a lower bound), our definition does not weaken our
results.
4

Notation
T
Bt
m
C
U
VhUi
n
R

PC,VhU i,R
P
DC
D

Table 1: List of key notations.
.
Description
the number of rounds
the set of candidate objects in round t
the constant m is the number of candidate objects in each round,
i.e., m = |Bt | and totally the system has mT objects
a client
a set of voters
the voting pattern of U
n is an upper bound of the number of voters
R ∈ {0, . . . , T } is a parameter that defines the radius of the
client’s peer group, i.e., a voter is a client’s peer if their distance
is within R
the number of the client C’s peers in the voting pattern VhUi,
given the radius parameter is R
P is a lower bound of the number of the client’s peers
the client C’s diversity of preferences, i.e., the client C likes more
than one objects in DC rounds
D ∈ {0, . . . , T } is an upper bound of the clients’ diversities of
preferences

In general, we consider a large system that consists of many voters, many
objects (over all the rounds), and runs for a long time. That is, n and T can
be very large. In this paper, we also impose a (quite loose) requirement that
n = O(poly(T )), i.e., n is not super large compared to T .
In reality, a client shall find more peers as more voters join the system.
Otherwise, the client has an “esoteric tastes” and it is inherently hard for any
collaborative system to help him/her. Thus, in this paper, we consider the case
that P ≥ 6m, i.e., the client has at least a constant number of peers.
Table 1 summarizes the key notations in this paper.

2.5

Loss/Privacy Goal

In this paper, we consider the worst-case expected loss of the algorithm, that is,
we aim to bound the algorithm’s expected loss for any client C and any voting
pattern VhUi such that |U| ≤ n, DC ≤ D and PC,VhU i,R ≥ P . Notice that O(T )
loss can be trivially achieved by ignoring voters’ votes and recommending objects
randomly. However, such an algorithm is useless, and hence we consider the
more interesting case when sub-linear loss (in terms of T ) is to be guaranteed.
It can be shown that the worst-case expected loss is Ω(R) for any algorithm
(Theorem 6). Therefore, sub-linear loss is achievable only when R is sub-linear.

5

In this paper, we focus on the case when R = O(T η ) for some constant η < 1.1
For the privacy, we aim to preserve ǫ-differential privacy. We study the best
achievable ǫ-differential privacy for any given target loss.

3

Related Work

Recommendation Systems and Online Learning. The research on recommendation systems has a long history [1, 38]. A classic recommendation
model is the offline matrix-based model, in which the user-object relation is
represented by a matrix. In this paper, we consider a very different online
recommendation model. From the theoretical perspective, our model can be
viewed as a variant of the “Prediction with Expert Advice” (PEA) problem in
online learning [9]. Such an approach that models the recommendation systems
as online learning problems has been adopted by other researchers as well, e.g.,
in [2, 29, 31, 35, 41].
Differential Privacy. There has been abundant research on differential privacy [14–16,20]. Much of the early research focused on answering a single query
on a dataset. Progress on answering multiple queries with non-trivial errors was
made later on, for both offline settings [4,19,23,36] (where the input is available
in advance), and online settings [5, 10, 11, 18, 24, 27, 39] (where the input continuously comes). We will introduce the work on differentially private online
learning in [18, 24, 39] with more details soon after, as they are most related to
this paper.
Protecting Privacy in Recommendation Systems. People are well aware
of the privacy risks in collaborative recommendation systems. Two recent attacks were demonstrated in [32] (which de-anonymized a dataset published by
Netflix) and [6] (which inferred users’ historical data by combining passive observation of a recommendation system with auxiliary information).
Many of the existing privacy-preserving recommendation systems adopted privacy notions other than differential privacy (e.g., [3, 7, 8, 33, 34, 37]). For studies on differentially private recommendation systems, prior to our paper, most
of them were for offline matrix-based models. Some experimentally studied
the empirical trade-offs between loss and privacy (e.g., [13, 30, 40]); the others focused on techniques that manipulate matrices in privacy-preserving ways
(e.g., [12, 21, 22, 26]).
Differentially Private Online Learning. This paper is most related to
differentially private online learning, as our recommendation model is a variant
of the PEA problem in online learning. Currently, only a limited number of
1 Technically, the assumptions that n = O(polylog(T )), P ≥ 6m and R = O(T η ) are only
for showing the near-optimality of our lower bound. Our lower bound itself remains to hold
without these assumptions.

6

studies have been done on this area [18, 24, 39]. In [18], Dwork et al. proposed
a differentially private algorithm for the PEA problem by plugging privacypreserving online counters into “Follow the Perturbed Leader” algorithm [25].
In [24] and [39], differential privacy was considered under a more general online
learning model called “Online Convex Programming.”
Despite the similarity between our recommendation model and the learning
models in [18, 24, 39], there is an important difference. Since their research is
not for recommendation systems, they considered somewhat different notions of
privacy from ours. Roughly speaking, if interpreting their models as recommendation problems, then their privacy goal is to ensure that each voter is “followed”
with similar probabilities when running the algorithm with two adjacent voting
patterns. Such a guarantee is not sufficient for a recommendation system. For
example, an algorithm that always “follows” voter Alice is perfectly private in
terms of their privacy definition, but completely discloses Alice’s private votes.2
Besides the difference in privacy definition, we provide both lower bound and
upper bound results, while [18, 24, 39] only have upper bound results.

4

Our Results and Contributions

Main results. Our first result is a lower bound on the best achievable privacy:
Theorem 1. For any recommendation algorithm that guarantees L = O(T β )
worst-case expected loss (β < 1 is a constant) and preserves ǫ-differential privacy, ǫ = Ω( P1 (D + R + log TL )) = Ω( P1 (D + R + log T )), even for an oblivious
adversary.
Our second result is a near-optimal algorithm (the p-REC algorithm in Section 8.2):
Theorem 2. The p-REC algorithm guarantees O((R + 1) log Pn ) worst-case
T
expected loss, and it preserves O( P1 (D + R + 1) log R+1
)-differential privacy,
even for an adaptive adversary.
It can be shown that the worst-case expected loss is Ω(R + log Pn ) even
for algorithms with no privacy guarantee (Theorem 6). Thus, p-REC’s worstcase expected loss is within a logarithmic factor to the optimal. Recall that
R = O(T η ) for a constant η < 1 and log n = O(log T ), hence p-REC’s worstcase expected loss is within O(T β ) for some constant β < 1 too. Then, by
Theorem 1, p-REC’s privacy is also within a logarithmic factor to the optimal.
Discussion of our results. Theorem 1 shows that a minimal amount of
“privacy leakage” is inevitable, even for the fairly weak O(T β ) target loss.
Moreover, unlike many other systems in which the utility downgrades linear
to the privacy parameter ǫ, the loss in an online recommendation system is much
2 On the other hand, our privacy definition does not imply their definitions either. Therefore
these two types of privacy models are incomparable.

7

more sensitive to ǫ: according to Theorem 2, we can achieve near-optimal loss
T
for an ǫ = O( P1 (D + R + 1) log R+1
); meanwhile, only trivial loss is achievable
1
for just a slightly smaller ǫ = o( P (D +R+log T )). In other words, the trade-offs
between loss and privacy are rather little — the best achievable ǫ is essentially
the same (up to a logarithmic factor) for all the algorithms with O(T β ) worstcase expected loss.3 For this reason, instead of designing an algorithm that has
a tunable privacy parameter ǫ, we directly propose the p-REC algorithm that
simultaneously guarantees both near-optimal loss and privacy.
From our results, we identify the key parameters D, P and R that determine
the best achievable loss and/or privacy.
The parameter R characterizes the correlation between the client and the
voters, and it is not surprised that the best achievable loss is inherently limited by R, because a basic assumption for any collaborative system is the existence of correlation in the data (e.g., the low-rank assumption in matrix-based
recommendation systems), and the system works by exploring/exploiting the
correlation.
We notice that a larger P gives better privacy. This is consistent with our
intuition, as an individual’s privacy is obtained by hiding oneself in a population.
We also notice that the best achievable privacy linearly depends on the
client’s diversity of preferences D and the radius parameter R. The parameter D
looks to be unnatural at the first sight, and no prior research on recommendation
systems has studied it. The reason might be that most of the prior research
focused on the loss, and D has no impact on the loss (the loss should only be
smaller if a client likes more objects). Nevertheless, in this paper, we discover
that D is one of the fundamental parameters that determine the best achievable
privacy. We provide an intuitive explanation of ǫ’s linear dependence on D and
R with an illustrative example in Section 8.1.

5

Preliminaries

Let P and Q be two distributions over sample space Ω. The relative entropy
P
P(ω)
between P and Q is defined as ω∈Ω P(ω) ln Q(ω)
, where P(ω) and Q(ω) is
the probability of ω in P and Q, respectively. We adopt the conventions that
0 log 00 = 0, 0 log x0 = 0 for any x > 0 and x log x0 = ∞ for any x > 0. It is well
known that relative entropy is always non-negative for any distributions P and
Q [28].
In this paper, we often simultaneously discuss two executions A(C, VhUi)
and A(C, VhU ′ i) for some algorithm A, some client C and two voting patterns
VhUi and VhU ′ i. As a notation convention, we will use Pr[·] and Pr′ [·] to denote
the probability of some event in the execution of A(C, VhUi) and A(C, VhU ′ i),
respectively. For any recommendation sequence b = (b1 , . . . , bT ) ∈ B1 × · · · × BT
3 This statement actually holds for all the algorithms with o(T ) loss. In Theorem 1, we
choose O(T β ) target loss to get a clean expression for the lower bound on ǫ, and a similar
(but messier) lower bound on ǫ holds for o(T ) target loss too.

8

Pr[bt |b1 ,...,bt−1 ]
and
and any round t, we define the random variables Et (b) = ln Pr
′ [b |b ,...,b
t 1
t−1 ]
P
T
Pr[b]
E(b) = ln Pr′ [b] . It then follows that E(b) = t=1 Et (b). We also define random
variable Lt to be the loss of execution A(C, VhUi) in the tth round.
Finally, we list some useful properties of the following “truncated-and-shifted
exponential” function
(
0
if x ≤ ρ,
φ(x) =
λx
λρ
e −e
otherwise,

where −∞ < ρ < ∞ and λ > 0. These properties will be useful when analyzing
our algorithms.
′

′

Lemma 3. φ(x) ≤ eλ|x−x | φ(x′ ) + (eλ|x−x | − 1)eλρ for any reals x, x′ .
Proof. If x ≤ x′ , since φ(x) is non-decreasing, φ(x) ≤ φ(x′ ) and this lemma
holds trivially. When x > x′ , we have two cases:
• Case 1: x′ ≤ ρ. In this case, φ(x′ ) = 0 and
φ(x) = φ(x′ + (x − x′ ))
≤ φ(ρ + (x − x′ ))
′

= (eλ(x−x ) − 1)eλρ
′

′

= eλ(x−x ) φ(x′ ) + (eλ(x−x ) − 1)eλρ ;
• Case 2: x′ > ρ. In this case, we have
eλx
φ(x) + eλρ
λ(x−x′ )
=
.
′ = e
′
λρ
λx
φ(x ) + e
e
We get the desired result by rearranging terms.
This finishes the proof of Lemma 3.
Lemma 4.

φ(x)
φ(x′ )

′

≤ e2λ(x−x ) for any x ≥ x′ ≥ ρ +

ln 2
λ .

Proof. Given x ≥ x′ > ρ, it follows that
′
eλx − eλρ
≤ e2λ(x−x )
eλx′ − eλρ
′
′
⇔ eλx − eλρ ≤ e2λ(x−x ) (eλx − eλρ )
′

′

′

′

⇔ eλx (e2λ(x−x ) − eλ(x−x ) ) ≥ eλρ (e2λ(x−x ) − 1)
′

′

′

⇐ eλx eλ(x−x ) ≥ eλρ (eλ(x−x ) + 1)
′

′

eλx
eλ(x−x ) + 1
≥
λρ
e
eλ(x−x′ )
′
eλx
⇐ λρ ≥ 2
e
⇔

9

⇔ x′ ≥ ρ +

ln 2
.
λ

This finishes the proof of Lemma 4.
Lemma 5. Let θ1 , . . . , θn be non-negative reals. Then
n
X

φ(xi + θi ) + φ(xn+1 ) ≤

n
X

φ(xi ) + φ xn+1 +

θi

i=1

i=1

i=1

n
X

!

for any reals x1 ≤ · · · ≤ xn ≤ xn+1 .
Proof. We prove this lemma by induction. When n = 1, it is easy to verify that
φ(x1 + θ1 ) + φ(x2 ) ≤ φ(x1 ) + φ(x2 + θ1 ) if x1 ≤ x2 . Suppose this lemma holds
for all n = 1, . . . , k. When n = k + 1, we have
k+1
X

φ(xi + θi ) + φ(xk+2 )

i=1

=

k
X

φ(xi + θi ) + φ(xk+1 + θk+1 ) + φ(xk+2 )

i=1

≤

k
X

φ(xi ) + φ(xk+1 + θk+1 ) + φ xk+2 +

i=1

i=1

≤

k+1
X

θi

!

(by induction hypothesis)

φ(xi ) + φ xk+2 +

k+1
X

θi

i=1

i=1

!

.

(by induction hypothesis, since xk+2 +

This finishes the induction step.

6

k
X

Pk

i=1 θi

≥ xk+1 )

A Lower Bound on the Worst-case Expected
Loss

Before considering privacy, let us first look at the best achievable loss. We have
the following lower bound on the worst-case expected loss, even for algorithms
providing no privacy guarantee:
Theorem 6. The worst-case expected loss of any recommendation algorithm
is Ω(R + log Pn ), even for an algorithm providing no privacy guarantee and an
oblivious adversary.
Proof of Theorem 6. In [41], Yu et al. have shown that the worst-case expected
loss is Ω(log n) for the case of P = 1 (Theorem 6 in [41]). A direct adaption of their proof shows that the worst-case expected loss is at least 12 (m −
10

(n/P )
n
1)⌊ loglog
m ⌋ = Ω(log P ) for any P ≥ 1. In the remaining parts of this proof, we
show that the worst-case expected loss is Ω(R).
We will show this by constructing a client with random preferences. In each
of the first R rounds, we independently and uniformly at random choose one
object. We let the client like this object, and we let he/she dislike the other
objects. In each of the remaining T − R rounds, there is no randomness, the
client always likes the object with the smallest index in that round.
There is a fixed voting pattern VhUi containing P voters. In each round, all
the P voters always vote on the object with the smallest index in that round.
By doing so, we ensure that all these P voters are always peers of the client
regardless of the instantiation of the client’s random preferences.
1
)R for any recomOne easily sees that the expected loss is at least (1 − m
mendation algorithm A when running with the random client and the voting
pattern VhUi (over both the client’s coin flips and A’s coin flips), because the
1
expected loss in each of the first R rounds is 1 − m
, no matter what A does.
Therefore, there must exist one instantiation of preferences for the client such
1
)R. This finishes the proof.
that the expected loss is at least (1 − m

7

The Special Setting where D = R = 0

Now let us consider differential privacy in recommendation systems. In order
to better explain our ideas, we start by discussing the simple (yet non-trivial)
setting where D = R = 0. That is, the client likes exactly one object in every
round, and the client’s peers never vote on any object that the client dislikes.
We discuss the general setting where D + R ≥ 0 in the next section.

7.1

Lower Bound

When D = R = 0, we have the following lower bound on the best achievable
privacy.
Theorem 7. For any recommendation algorithm that guarantees L = o(T )
worst-case expected loss and preserves ǫ-differential privacy, if D = R = 0, then
ǫ = Ω( P1 log TL ), even for an oblivious adversary.
Theorem 7 directly follows from the following Lemma 8, by plugging L worstcase expected loss into it:
Lemma 8. If D = R = 0, then the worst-case expected loss is at least 12 T e−P ǫ
for any recommendation algorithm that preserves ǫ-differential privacy, even for
an oblivious adversary.
Proof. In this proof, we consider a particular setup in which there are two
objects αt and βt in each round t. Given a client C, let ṼC denote the voting
pattern which contains only P voters who are all C’s peers. We will construct
a client C ∗ for any recommendation algorithm A, such that the expected loss
of A(C ∗ , ṼC ∗ ) is at least 12 T e−P ǫ.
11

First consider a particular round t, we have the following claim:
Claim 1. If two clients Alice and Bob have the same preferences in all but
the tth round, then one of A(Alice, ṼAlice ) and A(Bob, ṼBob ) has at least 12 e−P ǫ
expected loss in the tth round.
To prove this claim, assume that Alice likes αt but Bob likes βt . We construct
a chain of 2P + 1 voting patterns:
(1)

(P )

(P )

(1)

VA , . . . , VA , V, VB , . . . , VB .
The voting in the tth round of these voting patterns is as follows: in the middle
voting pattern V, there are P voters voting on αt (who are Alice’s peers) and
another P voters voting on βt (who are Bob’s peers). To get voting pattern
(P )
VA , we remove one of Bob’s peers from V. We keep on doing this until we get
(1)
(P )
(1)
VA , which contains only Alice’s P peers. Similarly, we construct VB , . . . , VB
by repeatedly removing Alice’s peers. The voting in all the other T − 1 rounds
is simple: in every voting pattern, all the voters vote on the (common) object
that is liked by both Alice and Bob in every round. The reader can verify that
(1)
(1)
VA = ṼAlice and VB = ṼBob .
We will use the middle voting pattern V as a bridge to relate the execu(1)
(1)
tion A(Alice, VA ) with the execution A(Bob, VB ). Since Alice and Bob have
the same preferences in the first t − 1 rounds, the executions A(Alice, V) and
A(Bob, V) have the same distribution of recommending objects in the tth round.
Denote the common probability that the object βt is recommended in the tth
round by p.
Let pA be the probability that βt is recommended in the tth round of the ex(1)
(1)
ecution A(Alice, VA ). Notice that pA is also the expected loss of A(Alice, VA )
(1)
in the tth round. Since VA and V are P -step adjacent voting patterns, we have
−P ǫ
pA ≥ p · e
. Similarly, let pB be the probability that αt is recommended in
(1)
the tth round of the execution A(Bob, VB ), then pB is the expected loss of
(1)
A(Bob, VB ) in the tth round and pB ≥ (1 − p) · e−P ǫ . In summary, we always
have max{pA , pB } ≥ max{p, 1 − p} · e−P ǫ ≥ 12 e−P ǫ and therefore at least one of
Alice and Bob incurs at least 12 e−P ǫ expected loss in the tth round. This proves
our claim.
We now inductively construct the client C ∗ who incurs 12 e−P ǫ expected loss
in every round when running with ṼC ∗ . By the above claim, there exists a client
C1 who incurs at least 21 e−P ǫ expected loss in the first round when running with
ṼC1 . This finishes the base case.
Assume Ck is a client who incurs at least 12 e−P ǫ expected loss in every one
of the first k rounds when running with ṼCk . We construct another client Ck′
who has the same preferences with Ck in all but the (k + 1)th round. Then the
expected loss in every one of the first k rounds is the same for both A(Ck , ṼCk )
and A(Ck′ , ṼCk′ ) (because the voting in the first k rounds is the same in both
ṼCk and ṼCk′ ), and by the above claim, one of them has at least 21 e−P ǫ expected
12

loss in the (k + 1)th round. In other words, one of A(Ck , ṼCk ) and A(Ck′ , ṼCk′ )
has at least 12 e−P ǫ expected loss in every one of the first k + 1 rounds. This
finishes the induction step.

7.2

Algorithm

We propose the following Algorithm 1 for the simple setting where D = R = 0.
As we will see, it is a special case of the general p-REC algorithm in Section 8.2.
Therefore, we call it the p-RECsim algorithm (“sim” is short for “simple”).
Input
: A client C, a voting pattern VhUi
Output
: Recommend an object from Bt to client C in each round t
1
, weight[i] ← 1 for each
Initialization: γ ← 3Tm−1 , λ ← 2m ln T , ρ ← 2m
i∈U
Procedure Main()
foreach round t = 1, . . . , T do
obj ← RecommendByWeight(weight[ ]);
Recommend object obj to the client C;
feedback ← the client C’s feedback on object obj;
UpdateWeight(weight[ ], obj, feedback);
Procedure RecommendByWeight(weight[ ])
foreach object
j ∈ Bt do
P
xj,t ←

i∈Uj,t

P

i∈U

weight[i]

weight[i]

, where Uj,t is the set of voters who vote on

object j in round t;
Independently draw a Bernoulli random variable Zt with
Pr[Zt = 1] = γ;
if Zt = 1 then
Independently draw an object obj from Bt uniformly at random;
else
Independently draw an object obj from Bt according to the
following distribution: each object j ∈ Bt is drawn with
probability
( proportional to φ(xj,t ), where
0
if x ≤ ρ,
φ(x) =
λx
λρ
e −e
otherwise;
return obj;
Procedure UpdateWeight(weight[ ], obj, feedback)
if feedback = “dislike” then
weight[i] ← 0 for every voter i who votes on object obj;
else
weight[i] ← 0 for every voter i who does not vote on object obj;
Algorithm 1: The p-RECsim algorithm.

13

The p-RECsim algorithm maintains a weight value weight[i] for each voter i,
and it recommends objects according to voters’ weight in each round by invoking
the procedure RecommendByWeight(). When it receives the client’s feedback, it
invokes the procedure UpdateWeight() to update voters’ weight. In p-RECsim ,
each voter’s weight is either 1 or 0. A voter with 0 weight has no impact on the
algorithm’s output, and once a voter’s weight is set to 0, it will never be reset
to 1. Therefore, we can think of that UpdateWeight() works by “kicking out”
voters from the system. We call the voters who have not been kicked out (i.e.,
those who have non-zero weight) surviving voters.
The p-RECsim algorithm shares a similar structure to the classic Weighted
Average algorithm for the PEA problem [9], as they both introduce weight
to voters and output according to the weight. Our core contribution is the
dedicated probability of recommending objects. In each round t, p-RECsim
φ(xj,t )
1
, where xj,t
recommends object j with probability γ · m
+ (1 − γ) · P
k∈Bt φ(xk,t )
is the fraction of surviving voters voting on object j in round t. We have:
Theorem 9. If D = R = 0, then the p-RECsim algorithm guarantees O(log Pn )
worst-case expected loss and it preserves O( P1 log T )-differential privacy, even
for an adaptive adversary.
According to Theorem 6, p-RECsim ’s loss is within a constant factor to the
optimal. Then by Theorem 7, p-RECsim ’s ǫ is also within a constant factor
to the optimal ǫ among all the algorithms that guarantee O(T β ) worst-case
expected loss.
Loss analysis of the p-RECsim algorithm. In the remaining parts of this
section, we prove Theorem 9. First, we analyze p-RECsim ’s loss:
Theorem 10. If D = R = 0, then the p-RECsim algorithm guarantees O(log
worst-case expected loss, even for an adaptive adversary.

n
P)

Proof. First consider all the rounds with Zt = 0. In these rounds, p-RECsim
kicks out at least ρ fraction of surviving voters whenever the client incurs a
loss, because only the objects voted by at least ρ fraction of surviving voters
can be recommended. Since the number of surviving voters is initially at most
n and always at least P , it follows that the number of loss rounds is at most
n
n
1
log 1−ρ
P ≤ 2m ln P . For those rounds with Zt = 1, since there are γT such
rounds on expectation, they cause at most γT ≤ m
2 additional expected loss.
A high probability result can also be derived by applying Chernoff’s bound
on the random variables Zt ’s.
Privacy analysis of the p-RECsim algorithm. Next, we analyze p-RECsim ’s
privacy. We aim to show that
Theorem 11. If D = R = 0, then the p-RECsim algorithm preserves O( P1 log T )differential privacy, even for an adaptive adversary.
14

To show Theorem 11, consider the executions p-RECsim (C, VhUi) and pRECsim (C, VhU ′ i), where C is any client and VhUi and VhU ′ i are any pair of
adjacent voting patterns (U contains one more voter than U ′ ). To show that
p-RECsim preserves O( P1 log T )-differential privacy, it is sufficient to show that
|E(b)| = O( P1 log T ) for any recommendation sequence b = (b1 , . . . , bT ). From
now on, we will consider a fixed b, a fixed C and a fixed pair of VhUi and VhU ′ i.
Given the recommendation sequence b = (b1 , . . . , bT ), let
X
Wt (b) =
weight[i]
i∈U

be the number of surviving voters at the beginning of round t in execution
p-RECsim (C, VhUi), conditioned on that the recommendations in the first t −
1 rounds are b1 , . . . , bt−1 . Since p-RECsim never kicks out the client’s peers,
Wt (b) ≥ P ≥ 6m.
First, we upper-bound the “privacy leakage” in each single round:
Lemma 12. For any round t, |Et (b)| ≤ 3λ ·

1
Wt (b) .

Lemma 12 upper-bounds the “privacy leakage” in any single round. This
lemma would be easy to prove if we were to recommend object j in round t with
probability ∝ exp(λxj,t ), because if there were Wt (b) surviving voters, then the
values of xj,t could only differ by Wt1(b) in the executions of p-RECsim (C, VhUi)
and p-RECsim (C, VhU ′ i). By some relatively straightforward (but rather tedious) calculations, it can be shown that Lemma 12 is also true if we recomφ(xj,t )
1
+ (1 − γ) · P
mend object j in round t with probability γ · m
φ(xk,t ) . Roughly
k∈Bt

speaking, this is because that the distortion γ is small, and φ(x) ≈ eλx .
Proof of Lemma 12. Recall that U contains one more voter than U ′ . If the
extra voter in U has zero weight in the tth round (i.e., the extra voter has been
kicked out), then we have Pr[bt |b1 , . . . , bt−1 ] = Pr′ [bt |b1 , . . . , bt−1 ] and the proof
is done. In the remaining parts of this proof, we assume that the extra voter
has 1 weight.
Consider the tth round. Index the m candidate objects in Bt by {1, . . . , m}.
We use xj to denote the fraction of surviving voters voting on the jth object
in the execution p-RECsim (C, VhUi), where j = 1, . . . , m. Similarly, we use
x′j to denote the corresponding fraction in the execution p-RECsim (C, VhU ′ i).
Since there are Wt (b) surviving voters in the execution p-RECsim (C, VhUi), the
fractions xj and x′j can differ by at most Wt1(b) , i.e., |xj − x′j | ≤ Wt1(b) for any
j = 1, . . . , m.
Suppose the index of the recommended object bt is j ∗ , according to the
p-RECsim algorithm,
Pr[bt |b1 , . . . , bt−1 ] = γ ·
and
Pr ′ [bt |b1 , . . . , bt−1 ] = γ ·

φ(xj ∗ )
1
+ (1 − γ) · Pm
m
j=1 φ(xj )

φ(x′j ∗ )
1
+ (1 − γ) · Pm
′ .
m
j=1 φ(xj )

15

For simplicity, let us write Wt (b) as Wt hereafter in this proof. Our goal is to
Pr[bt |b1 ,...,bt−1 ]
show that e−3λ/Wt ≤ Pr
≤ e3λ/Wt , which is equivalent to
′ [b |b ,...,b
t 1
t−1 ]

φ(xj∗ )
 Pm

j=1 φ(xj )
φ(x′j∗ )
 Pm
′
j=1 φ(xj )

φ(x′j∗ )
′
j=1 φ(xj )
3λ/Wt P φ(xj∗ )
e
m
j=1 φ(xj )

≤ e3λ/Wt Pm

+

≤

+

Recall that |xj ∗ − x′j ∗ | ≤

1
Wt ,

(e3λ/Wt −1)γ
m(1−γ) ,
3λ/Wt
(e
−1)γ
m(1−γ) .

(1)

by Lemma 3, we have

φ(xj ∗ ) ≤ eλ/Wt φ(x′j ∗ ) + (eλ/Wt − 1)eλρ .
We also have

Pm
φ(xj )
Pj=1
m
′
j=1 φ(xj )

≥ e−2λ/Wt (see below, Lemma 13). It then follows that

eλ/Wt φ(x′j ∗ ) + (eλ/Wt − 1)eλρ
φ(x ∗ )
Pm j
Pm
≤
j=1 φ(xj )
j=1 φ(xj )

eλ/Wt φ(x′j ∗ ) (eλ/Wt − 1)eλρ
= Pm
+ Pm
j=1 φ(xj )
j=1 φ(xj )
≤

eλ/Wt φ(x′j ∗ )
(eλ/Wt − 1)eλρ
Pm
+ Pm
′
−2λ/W
t
e
j=1 φ(xj )
j=1 φ(xj )

φ(x′j ∗ )
(eλ/Wt − 1)eλρ
.
+
≤ e3λ/Wt Pm
1
′
)
φ( m
j=1 φ(xj )
Pm
1
Notice in the last step, we use the fact that j=1 φ(xj ) ≥ φ( m
) because there
λ/Wt

λρ

3λ/Wt

−1)γ
1
always exists one j with xj ≥ m
≤ (e m(1−γ)
. One can verify that (e φ( −1)e
1
m)
by our choice of γ and λ, hence we have proved the first inequality of (1). We
can show the second inequality of (1) in a completely symmetric way and prove
this lemma.

In the proof of Lemma 12, we use the following lemma:
Lemma 13. e−2λ/Wt ≤

Pm
φ(xj )
Pj=1
m
′
j=1 φ(xj )

≤ e2λ/Wt (xj ’s and x′j ’s are defined in the

proof of Lemma 12).
Proof. Suppose the extra voter votes on the object with index k. We then have
xk > x′k , and xj < x′j for all the other j 6= k. Since φ(x) is non-decreasing, it
then follows that φ(xk ) ≥ φ(x′k ), and φ(xj ) ≤ φ(x′j ) for all the other j 6= k.
Let θj = |xj − x′j |, we have
X
j6=k

θj = θk ≤

1
1
1
≤
≤
.
Wt
P
6m

1
1
and xℓ ≥ x′ℓ −θl ≥ x′ℓ − 6m
≥
Let ℓ = arg maxj {x′1 , . . . , x′j , . . . , x′m }, then x′ℓ ≥ m
5
1
6 · m . Depending on whether the extra voter votes on the object with index ℓ
or not, we have two cases:

16

• Case 1: k = ℓ. Partition all the m objects into two disjoint subsets: {ℓ}
and A
\ {ℓ}. We have that φ(xℓ ) ≥ φ(x′ℓ ) (because ℓ = k)
P= {1, . . . , m}P
and j∈A φ(xj ) ≤ j∈A φ(x′j ) (because ∀j ∈ A : φ(xj ) ≤ φ(x′j )). We
then have
Pm
P
φ(xℓ ) + j∈A φ(xj )
j=1 φ(xj )
P
Pm
′
′ = φ(x′ ) +
j∈A φ(xj )
ℓ
j=1 φ(xj )
≤

φ(xℓ )
φ(x′ℓ )

≤ e2λ/Wt .

(by Lemma 4)

For the other direction, it follows that
Pm
P
φ(xℓ ) + j∈A φ(xj )
j=1 φ(xj )
P
Pm
′
′ = φ(x′ ) +
j∈A φ(xj )
ℓ
j=1 φ(xj )
P
φ(xℓ ) + j∈A φ(xj )
P
=
φ(x′ℓ ) + j∈A φ(xj + θj )
P
φ(xℓ ) + j∈A φ(xj )
P
P
(by Lemma 5)
≥
φ(x′ℓ + j∈A θj ) + j∈A φ(xj )
P
P
j∈A φ(xj ) + φ(xℓ )
(since j∈A θj = θℓ = xℓ − x′ℓ )
= P
j∈A φ(xj ) + φ(xℓ )
= 1.

• Case 2: k 6= ℓ. Partition all the m objects into three disjoint subsets: {k},
{ℓ} and
m} \ {k, ℓ}. Since φ(xj ) ≤ φ(x′j ) for any j ∈ B, we
P B = {1, . . . ,P
have j∈B φ(xj ) ≤ j∈B φ(x′j ). It then follows that
Pm

j=1
Pm
j=1

φ(xj )

φ(x′j )

≤

Thus, to upper-bound
for

φ(xk )+φ(xℓ )
φ(x′k )+φ(x′ℓ ) .

=

φ(xk ) + φ(xℓ ) +

φ(x′k )
(

+

φ(x′ℓ )

+

1

if

φ(xk )+φ(xℓ )
φ(x′k )+φ(x′ℓ )

if

Pm
j=1 φ(xj )
Pm
′ ,
j=1 φ(xj )

P

Pj∈B
j∈B

φ(xj )

φ(x′j )

φ(xk )+φ(xℓ )
φ(x′k )+φ(x′ℓ )
φ(xk )+φ(xℓ )
φ(x′k )+φ(x′ℓ )

≤ 1,
> 1.

it is sufficient to show an upper bound

There are two subcases to consider:

– x′k ≤ xℓ . By Lemma 5, it follows that
φ(xk ) + φ(xℓ )
φ(x′k + θk ) + φ(xℓ )
=
′
′
φ(xk ) + φ(xℓ )
φ(x′k ) + φ(x′ℓ )
φ(x′k ) + φ(xℓ + θk )
.
≤
φ(x′k ) + φ(x′ℓ )
17

(2)

Notice that 0 ≤ (xℓ + θk ) − x′ℓ =
according to Lemma 4, we have
1≤

P

j∈B

θj ≤

1
Wt ,

and x′ℓ ≥ ρ +

ln 2
λ ,

′
φ(xℓ + θk )
≤ e2λ((xℓ +θk )−xℓ ) ≤ e2λ/Wt .
′
φ(xℓ )

Substitute this to (2), we get

Pm
φ(xj )
Pj=1
m
′
j=1 φ(xj )

≤ e2λ/Wt .

– x′k > xℓ . In this case, since φ(xk ) ≥ φ(x′k ) ≥ φ(xℓ ), φ(x′k ) ≤ φ(x′ℓ ),
we have
φ(xk ) + φ(xℓ )
φ(xk ) + φ(xk )
φ(xk )
≤
=
.
(3)
φ(x′k ) + φ(x′ℓ )
φ(x′k ) + φ(x′k )
φ(x′k )
Notice that x′k > xℓ ≥

5
6

·

1
m

≥ρ+

ln 2
λ ,

by Lemma 4, we have

′
φ(xk )
≤ e2λ(xk −xk ) ≤ e2λ/Wt .
′
φ(xk )

Substitute this to (3), we get

Pm
φ(xj )
Pj=1
m
′
j=1 φ(xj )

≤ e2λ/Wt .

Now we have shown one direction of the desired inequality in Case 2, for
the other direction, it follows that
Pm
P
φ(xk ) + φ(xℓ ) + j∈B φ(xj )
j=1 φ(xj )
P
Pm
′
′ = φ(x′ ) + φ(x′ ) +
j=1 φ(xj )
k
ℓ
j∈B φ(xj )
P
φ(xℓ ) + j∈B φ(xj )
P
(since φ(xk ) ≥ φ(x′k ))
≥
φ(x′ℓ ) + j∈B φ(x′j )
P
φ(xℓ ) + j∈B φ(xj )
P
=
φ(x′ℓ ) + j∈B φ(xj + θj )
P
φ(xℓ ) + j∈B φ(xj )
P
P
.
(4)
≥
φ(x′ℓ + j∈B θj ) + j∈B φ(xj )
P
The last step is due to Lemma 5. Notice that 0 ≤ (x′ℓ + j∈B θj ) − xℓ =
P
1
ln 2
′
j∈B∪{ℓ} θj = θk ≤ Wt , and xℓ ≥ ρ + λ , according to Lemma 4, we
have
P
φ(x′ℓ + j∈B θj )
≤ e2λ/Wt .
1≤
φ(xℓ )

Substitute this to (4), we get

Pm
j=1 φ(xj )
Pm
′
j=1 φ(xj )

≥ e−2λ/Wt .

The proof of Lemma 13 is done because we have shown e−2λ/Wt ≤
e

2λ/Wt

Pm
j=1 φ(xj )
Pm
′
j=1 φ(xj )

≤

in both Case 1 and Case 2.

Next, we show that a constant fraction of surviving voters are kicked out
whenever there is non-zero “privacy leakage:”
18

Lemma 14. For any round t, if |Et (b)| 6= 0, then Wt+1 (b) ≤ Wt (b) · (1 −

1
3m ).

Proof. Notice that |Et (b)| 6= 0 iff Pr[bt |b1 , . . . , bt−1 ] 6= Pr ′ [bt |b1 , . . . , bt−1 ]. Let
x and x′ be the fraction of surviving voters voting on the recommended object
bt in execution p-RECsim (C, VhUi) and p-RECsim (C, VhU ′ i), respectively. Since
1
.
there are Wt (b) surviving voters, |x − x′ | ≤ Wt1(b) ≤ P1 ≤ 6m
1
1
We claim that x > 3m . Assume for contradiction that x ≤ 3m
. Since
1
1
1
1
′
′
|x − x | ≤ 6m , both x and x will be no larger than 3m + 6m = 2m = ρ. Notice
that φ(ζ) = 0 for any variable ζ ≤ ρ, it then follows that φ(x) = φ(x′ ) = 0 and
1
, contradiction.
Pr[bt |b1 , . . . , bt−1 ] = Pr′ [bt |b1 , . . . , bt−1 ] = γ · m
If the clients dislikes the recommended object bt , by p-RECsim ’s rule of
1
fraction of surviving voters will be kicked out.
updating weight, x > 3m
If the clients likes bt , then there must exist another object ξ ∈ Bt which is
different from bt , such that Pr[ξ|b1 , . . . , bt−1 ] 6= Pr′ [ξ|b1 , . . . , bt−1 ]. Otherwise, if
all the other objects are recommended with the same probability in executions
p-RECsim (C, VhUi) and p-RECsim (C, VhU ′ i), so will be bt , contradiction. By
1
similar arguments, there are at least 3m
fraction of surviving voters voting
on the object ξ in both p-RECsim (C, VhUi) and p-RECsim (C, VhU ′ i). Since pRECsim kicks out all the voters who do not vote on bt (including those who vote
on ξ), again we get the desired result.
Lemma 12 states that |Et (b)| is O( Wtλ(b) ) = O( P1 log T ). Lemma 14 implies
that there can be at most O(log Pn ) rounds with |Et (b)| 6= 0. A combination of
these two lemmas immediately shows that overall we have O( P1 log T · log Pn )differential privacy. With a bit more careful analysis, we can remove the extra
log Pn factor and prove Theorem 11:
Proof of Theorem 11. Let t1 , . . . , tK be the rounds in which |Eti (b)| 6= 0, we
have
|E(b)| =

T
X

Et (b) ≤

t=1

T
X

|Et (b)| =

t=1

K
X

|Eti (b)| ≤ 3λ

K
X
i=1

i=1

1
.
Wti (b)

By Lemma 14, and the fact that Wt (b) is non-increasing with respect to t, we
1
. Therefore the sequence { Wt 1 (b) , . . . , Wt1 (b) }
have Wt1(b) ≤ Wt 1 (b) · 1 − 3m
i

i+1

is upper-bounded by the geometric sequence with
1−

1
3m

K

1

1

as the first term and

WtK (b)

as the common ratio. This implies that
K
X
i=1

and
|E(b)| ≤ 3λ

1
1
1
≤ 3m ·
≤ 3m · ,
Wti (b)
WtK (b)
P

K
X
i=1

as desired.

1
1
≤ 18m2 · log T = O
Wti (b)
P

19



1
log T
P



,

8
8.1

The General Setting where D + R ≥ 0
Lower Bound

In this section, we prove Theorem 1. If 0 ≤ D + R < 6 ln T and the target
loss L = O(T β ), then Ω(log TL ) = Ω(D + R + log TL ) and hence Theorem 1 is
implied by Theorem 7. When D+R ≥ 6 ln T , we have the following Theorem 15.
Theorem 1 is then proved because Ω(D+R) = Ω(D+R+log TL ) if D+R ≥ 6 ln T .
Theorem 15. For any recommendation algorithm that guarantees L = o(T )
worst-case expected loss and preserves ǫ-differential privacy, if D + R ≥ 6 ln T ,
then ǫ = Ω( P1 (D + R)), even for an oblivious adversary.
Before proving Theorem 15, we first explain the intuition behind the proof
by a simple illustrative example. Imagine that there is one client Alice, and two
voting patterns V1 and V2 . Both V1 and V2 contain only one voter named Bob,
but Bob may vote differently in V1 and V2 . We let Bob be Alice’s peer in both
V1 and V2 . For simplicity let us set R = 0, so Bob never votes on any object
that Alice dislikes. By Definition 1, V1 and V2 are 2-step voting patterns.
Now consider a particular round t with two candidate objects. If Alice likes
only one of the objects, then there is only one way for Bob to cast vote; otherwise
Bob will no longer be a peer of Alice. However, if Alice likes both objects, then
Bob can vote on different objects in V1 and V2 without breaking the promise
that he is Alice’s peer. Since Bob is the only information source of the system,
an recommendation algorithm A has to somehow “follow” Bob, and hence the
distributions of the executions A(Alice, V1 ) and A(Alice, V2 ) will be different. If
Alice’s diversity of preferences is D, then this situation can happen for D times,
which results an ǫ ∝ D. The linear dependency of ǫ on R is for a similar reason.
Proof of Theorem 15. We first prove Theorem 15 for the case where P = 1 and
6 ln T ≤ D + R ≤ T . Once we solve this case, the other cases can be easily
solved and we discuss them in the end of this proof.
To show Theorem 15 for the case where P = 1, it is sufficient to show that
for any given algorithm A, we can construct a client C and a pair of 2-step
Pr[b]
adjacent voting patterns VhUi, VhU ′ i, such that ln Pr
′ [b] = Ω(D + R) for some
recommendation sequence b ∈ B1 × · · · × BT and a sufficiently large T .
We consider a particular setup in which there are two objects αt and βt in
each round t. We construct the client C by setting C’s preferences on αt ’s and
βt ’s. We will always ensure that C likes both αt and βt in at most D rounds,
hence that DC ≤ D. For the voting patterns VhUi and VhU ′ i, we let each of
them contain one voter. Let U and U ′ be the only voter in voting pattern VhUi
and VhU ′ i, respectively. We ensure that both U and U ′ vote on at most R
objects that are disliked by the client C, hence both U and U ′ are C’s peers.
In sake of convenience, for any client C and any pair of voting patterns VhUi
and VhU ′ i as described above, we call the triple (C, VhUi, VhU ′ i) a configuration. We will introduce a random procedure of generating configurations for any

20

given algorithm A, and then use it to demonstrate the existence of one “bad”
configuration that has large privacy leakage.
We construct a “bad” configuration round by round. Imagine that we are
running the two executions A(C, VhUi) and A(C, VhU ′ i) simultaneously, and
now A is at the beginning of the tth round, with the previous recommendation
history being (b1 , . . . , bt−1 ). Let us write b<t = (b1 , . . . , bt−1 ) for short. At this
point, A will calculate the probabilities of recommending αt and βt , based on
the voter U ’s (or U ′ ’s) vote.
The voter U may vote on either αt or βt , and A’s probability of recommending objects depends on how U vote. We use pα to denote the probability
that the algorithm A “follows” the voter U when U votes on αt . That is, pα
is A’s probability of recommending αt when U votes on αt , conditioned on the
recommendation history is b<t . Similarly, we define pβ to be the probability
that A “follows” the voter U when U votes on βt . We define p′α and p′β to be
the counterparts of pα and pβ with voter U replaced by voter U ′ . I.e., p′α (p′β )
is the probability that A “follows” the voter U ′ when U ′ votes on αt (βt ).
In order to better explain the intuition behind this proof, let us temporarily
assume an adaptive adversary, therefore the adversary could see the recommendation history b<t and calculate pα , pβ , p′α and p′β by “simulating” A. It can then
(adaptively) construct a “bad” configuration by choosing one of the following 4
settings for round t, based on the values of pα , pβ , p′α and p′β :
• Setting 1 : the client likes αt , dislikes βt , and both U and U ′ vote on αt ;
• Setting 2 : the client dislikes αt , likes βt , and both U and U ′ vote on βt ;
• Setting 3 : the client likes both αt and βt , U votes on αt , and U ′ votes on
βt ;
• Setting 4 : the client likes αt , dislikes βt , U votes on αt , and U ′ votes on
βt .
The adaptive construction is as follows:
• Case 1 : 0 ≤ min{pα , pβ } ≤ 34 . We have two more subcases:
– Case 1.a: If pα ≤ 43 , then the adversary chooses Setting 1, in which
case we have
E[Lt |b<t ] = Pr[βt |b<t ]
= 1 − pα
1
≥ .
4
– Case 1.b: Else we must have pβ ≤
chooses Setting 2. We have

3
4,

in which case the adversary

E[Lt |b<t ] = Pr[αt |b<t ]
21

= 1 − pβ
1
≥ .
4
In summary, in Case 1, the adversary can always force the algorithm to
have a constant expected loss in round t.
• Case 2 : 34 < min{pα , pβ } ≤ 1.In this case, algorithm A “follows” voter U
with a large probability (at least 34 ) regardless how U votes. We have two
more subcases:
– Case 2.a: 0 ≤ p′β ≤ 21 , in which case A “follows” voter U ′ with only
a small probability (at most 21 ) if U ′ votes on βt . Recall that A
“follows” voter U with probability at least 34 no matter which object
U votes on. Thus, if the adversary lets both U and U ′ vote on βt , the
two distributions Pr[·|b<t ] and Pr′ [·|b<t ] will be sufficiently different,
and the algorithm A will “leak privacy.” Specifically, the adversary
will choose Setting 2 for Case 2.a and we have
Pr[βt |b<t ]
Pr[αt |b<t ]
+ Pr[βt |b<t ] · ln ′
′
Pr [αt |b<t ]
Pr [βt |b<t ]
1 − pβ
pβ
= (1 − pβ ) ln
+ pβ ln ′
1 − p′β
pβ

E[Et |b<t ] = Pr[αt |b<t ] · ln

1 1/4 3 3/4
ln
+ ln
4 1/2 4 1/2
> 0.13.
≥

(∵ pβ ≥

3
4

and p′β ≤ 21 )

That is, the expected “privacy leakage” in the tth round is at least a
constant.
– Case 2.b: 12 < p′β ≤ 1, in which case algorithm A “follows” voter U ′
with a large probability (at least 21 ) too if U ′ votes on βt . Since
A “follows” voter U with probability at least 43 no matter which
object U votes on, to make the distributions Pr[·|b<t ] and Pr′ [·|b<t ]
be sufficiently different and force the algorithm to “leak privacy,” the
adversary can let U vote on αt and U ′ vote on βt — this is how
Setting 3 and Setting 4 are constructed. Notice that the adversary
cannot keep choosing Setting 3 or Setting 4, because the client likes
more than one objects in at most D rounds, and U and U ′ can vote on
at most R objects that are disliked by the client. In our construction,
the adversary will choose Setting 3 for the first D rounds that are in
Case 2.b, and then choose Setting 4 for the next R rounds that are
in Case 2.b. The adversary arbitrarily chooses Setting 1 or Setting 2
for the remaining rounds that are in Case 2.b.
If Setting 3 or Setting 4 is chosen, we have
E[Et |b<t ] = Pr[αt |b<t ] · ln

Pr[βt |b<t ]
Pr[αt |b<t ]
+ Pr[βt |b<t ] · ln ′
Pr′ [αt |b<t ]
Pr [βt |b<t ]
22

= pα ln

pα
1 − pα
+ (1 − pα ) ln
′
1 − pβ
p′β

3 3/4 1 1/4
ln
+ ln
4 1/2 4 1/2
> 0.13.
≥

(∵ pα ≥

3
4

and p′β > 21 )

If Setting 1 or Setting 2 is chosen, we have
E[Et |b<t ] ≥ 0
because the relative entropy is always non-negative.
It can be shown that with this adaptive construction, E[E] = Ω(D + R) for
any algorithm A, which implies the existence of one recommendation sequence
Pr[b]
b such that E(b) = ln Pr
′ [b] = Ω(D + R). To see why E[E] = Ω(D + R), we first
notice that there cannot be too many rounds in Case 1 (including Case 1.a and
Case 1.b) on expectation, because A has to ensure o(T ) worst-case expected
loss. Therefore most of the rounds must be in Case 2.a or Case 2.b. If there
are many rounds in Case 2.a, then E[E] must be large because E[Et |b<t ] is at
least a constant in every Case 2.a round, and E[Et |b<t ] ≥ 0 in all the other
rounds (the relative entropy is always non-negative). Otherwise, there must be
many rounds in Case 2.b. In this case, the adversary can choose Setting 3 and
Setting 4 for Ω(D + R) times, and we will have E[E] = Ω(D + R).
The drawback of the above arguments is of course the assumption of an
adaptive adversary. To remove this assumption, an (oblivious) adversary will
choose Setting 1, Setting 2, Setting 3 or Setting 4 randomly in each round,
without looking at the recommendation history. In other words, we are to
construct a random configuration.
The random construction is as follows. In each round t, the adversary independently draws a random variable Xt such that

D+R

0 with probablitiy
,



2T


D+R
1
Xt = 1 with probablitiy (1 −
),

2
2T




2 with probablitiy 1 (1 − D + R ).
2
2T

The adversary chooses Setting 1 for the tth round if Xt = 1, and it chooses
Setting 2 for the tth round round if Xt = 2. If Xt = 0, the adversary does
the following: if it has chosen Setting 3 for less than D times before the tth
round, chooses Setting 3 ; else chooses Setting 4. Notice that in this random
construction, it is possible to get an “illegal” configuration (i.e., a configuration
with more than R rounds in Setting 4 ). However, since Pr[Xt = 0] = D+R
2T , the
expected number of rounds in which Xt = 0 is 21 (D + R). By Chernoff’s bound,
the probability that we have more than D + R rounds with Xt = 0 is at most

23

1
T

(here the condition D + R ≥ 6 ln T is used). In other words, our construction
generates a “legal” configuration with high probability.
This oblivious construction is analogous to the aforementioned adaptive one
in the following sense: previously, if A is in Case 1.a, Case 1.b or Case 2.a,
it will encounter a “bad” setting (which is Setting 1, Setting 2 and Setting 2,
respectively) for sure; now A encounters a “bad” setting with a constant proba1
bility 21 (1 − D+R
2T ) ≥ 4 . Moreover, in the oblivious construction, we also ensure
that there are sufficiently many rounds ( 21 (D + R) rounds on expectation) in
which Setting 3 or Setting 4 is chosen.
Due to this analogousness between these two constructions, we can derive a
similar lower bound for E[E] and prove Theorem 15 for the case of P = 1 and
6 ln T ≤ D + R ≤ T :
Let F be the universe of all possible configurations, for any configuration
F = (C, VhUi, VhU ′ i) ∈ F , we use Pr[·|F ], Pr′ [·|F ] and E[·|F ] to denote the
corresponding probabilities and expectations in the executions of A(C, VhUi)
and A(C, VhU ′ i).
Given any subset G ⊆ F , we define the following “conditional” relative entropies over G:
X
E[Et |G] =
E[Et |F ] · Pr[F |G]
F ∈G

and

E[E|G] =

T
X

E[Et |G]

t=1

=

X

E[E|F ] · Pr[F |G].

F ∈G

We emphasize that E[Et |G] and E[E|G] themselves are not necessarily to be
relative entropies, although E[Et |F ] and E[E|F ] are relative entropies for each
single F ∈ F .
Let F0 ⊆ F be the universe of all the “legal” configurations (i.e., the configurations with at most R rounds in Setting 4 ). We will show that E[E|F0 ] =
Ω(D + R). We can then conclude that there exists one “legal” configuration
Pr[b|F ]
F ∈ F0 , such that ln Pr
′ [b|F ] = Ω(D + R) for some recommendation sequence
b ∈ B1 × · · · × BT .
(1.a)
(1.b)
(2.a)
(2.b)
Define It
, It , It
, It
to be the indicator random variables such
that
(1.a)

= 1 iff the tth round is in Case 1.a;

(1.b)

= 1 iff the tth round is in Case 1.b;

(2.a)

= 1 iff the tth round is in Case 2.a;

(2.b)

= 1 iff the tth round is in Case 2.b.

• It
• It

• It
• It

24

Since the expected loss of A(C, VhUi) is at least 14 if the tth round is in Case 1.a
(1.a)
and Setting 1 is chosen (i.e., E[Lt |It
= 1 and Xt = 1] ≥ 41 ), we have
1
(1.a)
· Pr[It
= 1, Xt = 1]
4
1
(1.a)
= · Pr[It
= 1] · Pr[Xt = 1]
4

1
D+R
(1.a)
=
1−
· Pr[It
= 1]
8
2T
1
(1.a)
≥
· E[It
].
16

E[Lt ] ≥

(5)

(1.a)

(1.a)

The second step is because It
and Xt are independent (although It
may
depend on Xs for s < t). Take summation over t on both sides of (5), we get
" T
#
" T
#
X (1.a)
X
1
·E
It
.
(6)
E
Lt ≥
16
t=1
t=1
Similarly, since the expected loss of A(C, VhUi) is at least 14 if the tth round is
(1.b)
in Case 1.b and Setting 2 is chosen (i.e., E[Lt |It
= 1 and Xt = 2] ≥ 41 ), we
have
" T
#
#
" T
X (1.b)
X
1
·E
It
.
(7)
E
Lt ≥
16
t=1
t=1
Combine (6) and (7), we get
" T
#
X
1
·
E
Lt ≥
32
t=1

E

"

T
X

(1.a)
It

t=1

#

+E

" T
X
t=1

(1.b)
It

#!

.

(8)

Recall that the expectation of Et is at least 0.13 if the tth round is in Case 2.a
(2.a)
and Setting 2 is chosen (i.e., E[Et |It
= 1 and Xt = 2] ≥ 0.13), and that
expectation is at least 0 in other cases (because the relative entropy is always
non-negative), we have
(2.a)

E[Et |F0 ] ≥ 0.13 · Pr[It
= 1, Xt = 2|F0 ]


1
(2.a)
≥ 0.13 · Pr[It
= 1, Xt = 2] −
T


1
(2.a)
= 0.13 · Pr[It
= 1] · Pr[Xt = 2] −
T


 
D+R
1
1
(2.a)
1−
· Pr[It
= 1] −
= 0.13 ·
2
2T
T


1
1
(2.a)
≥ 0.13 ·
.
· E[It
]−
4
T
25

(9)

The second step is because
(2.a)

Pr[It
= 1, Xt = 2|F0 ]
1
(2.a)
(2.a)
=
(Pr[It
= 1, Xt = 2] − Pr[It
= 1, Xt = 2|F \ F0 ] · Pr[F \ F0 ])
Pr[F0 ]
(2.a)

≥ Pr[It

(2.a)

≥ Pr[It

= 1, Xt = 2] − Pr[F \ F0 ]
1
= 1, Xt = 2] − ,
T
(2.a)

(2.a)

and the third step is because It
and Xt are independent (although It
may
depend on Xs for s < t). Take summation over t on both sides of (9), we get
#
" T
X
E[E|F0 ] = E
Et F0
t=1

≥ 0.13 ·

#
!
" T
X (2.a)
1
−1 .
·E
It
4
t=1

(10)

Similarly, by the fact that the expectation of Et is at least 0.13 if the tth
(2.b)
round is in Case 2.b and Setting 3 or Setting 4 is chosen (i.e., E[Et |It
=
1 and Xt = 0] ≥ 0.13), we have
(2.b)

E[Et |F0 ] ≥ 0.13 · Pr[It
= 1, Xt = 0|F0 ]


1
(2.b)
≥ 0.13 · Pr[It
= 1] · Pr[Xt = 0] −
T


D+R
1
(2.b)
= 0.13 ·
· Pr[It
= 1] −
2T
T


D+R
1
(2.b)
= 0.13 ·
.
· E[It ] −
2T
T
Take summation over t on both sides of (11), we obtain
#
!
" T
X (2.b)
D+R
−1 .
·E
It
E[E|F0 ] ≥ 0.13 ·
2T
t=1
We are now ready to derive a lower bound for E[E|F0 ]:
hP
i
(2.b)
T
• If E
≥ T2 , by (12), we have
t=1 It


1
(D + R) − 1
E[E|F0 ] ≥ 0.13 ·
4
= Ω(D + R).

26



(11)

(12)

• If E

hP

(2.b)
T
t=1 It

E

"

i

T
X

<

T
2,

(1.a)
It

t=1

then
#

+E

"

T
X
t=1

By (8), we have
" T
#
X (2.a)
T
E
It
> −
2
t=1
≥

(1.b)
It

E

#

" T
X

+E

T
− 32 · E
2

" T
X
t=1

(2.a)
It

t=1

(1.a)
It

t=1

" T
X

#

+E

#

#

" T
X
t=1

>

T
.
2

(1.b)
It

#!

Lt .

Substitute this to (10), we get
" T
#!
!
X
T
E[E|F0 ] ≥ 0.13 ·
− 32 · E
−1
Lt
2
t=1


 
T
1
·
− o(T ) − 1
≥ 0.13 ·
4
2
1
·
4

= Ω(T )
= Ω(D + R).

The second step is because
" T
#
" T
#
" T
#
X
X
X
E
Lt = E
Lt F0 · Pr[F0 ] + E
Lt F \ F0 · Pr[F \ F0 ]
t=1

t=1

≤E

"

T
X

t=1

#

Lt F0 + T ·

t=1

≤ max E
F ∈F0

≤L+1
= o(T ).

" T
X
t=1

1
T

#

Lt F + 1

We have shown that Theorem 15 holds if 6 ln T ≤ D + R ≤ T and P = 1.
Now we prove Theorem 15 for the cases where D + R > T and/or P > 1.
When D + R > T (still assuming P = 1). When D + R > T , we can choose
another pair of D′ and R′ , such that D′ ≤ R, R′ ≤ R and D′ + R′ = T . If we
use D′ and R′ (instead of D and R) to do the above construction, we can show
that the E[E|F0 ] = Ω(D′ + R′ ). Recall that D ∈ {0, . . . , T } and R ∈ {0, . . . , T },
thus D + R ≤ 2T and Ω(D′ + R′ ) = Ω(D + R). This finishes the proof.
27

When P > 1. In the above proof for the case of P = 1, we construct two
voting patterns VhUi and VhU ′ i, each of which contains a single voter U and
U ′ , respectively. We can extend this proof to the case of P > 1 by considering a
voting pattern containing P voters who vote exactly the same as U , and another
voting pattern containing P voters who vote exactly the same as U ′ . Such a
pair of voting patterns are 2P -step adjacent to each other, and we will get an
additional factor of Θ( P1 ) in our lower bound for the ǫ.

8.2

Algorithm

We propose the following p-REC algorithm for the general setting where D+R ≥
0. The p-REC algorithm is a generalized version of the p-RECsim algorithm,
and it shares a similar structure as that of p-RECsim , except that the procedure
UpdateWeight() is replaced by UpdateCreditAndWeight(). In fact, we can get
back the p-RECsim algorithm by setting D = R = 0 in the p-REC algorithm.
Input
: A client C, a voting pattern VhUi
Output
: Recommend an object from Bt to client C in each round t
T
1
m
; λ ← 2m ln R+1
; ρ ← 2m
; for each
Initialization: γ ← (3T /(R+1))−1
i ∈ U: credit(D) [i] ← 2D, credit(R) [i] ← 2R + 1,
weight[i] ← 1
Procedure Main()
foreach round t = 1, . . . , T do
obj ← RecommendByWeight(weight[ ]);
Recommend object obj to the client C;
feedback ← the client C’s feedback on object obj;
UpdateCreditAndWeight(credit(D)[ ], credit(R) [ ], weight[ ], obj,
feedback);
Procedure UpdateCreditAndWeight(credit(D)[ ], credit(R) [ ], weight[ ],
obj, feedback)
if feedback = “dislike” then
credit(R) [i] ← credit(R) [i] − 1 for every voter i who votes on obj;
else
credit(D) [i] ← credit(D) [i] − 1 for every voter i who does not vote
on obj;
foreach voter i ∈ U do
if credit(R) [i] > 0 and credit(D) [i] + credit(R) [i] > 0 then
weight[i] ← 1;
else
weight[i] ← 0;
Algorithm 2: Privacy-preserving RECommendation (p-REC) algorithm.

28

In the beginning of the p-REC algorithm, each voter i ∈ U is initialized with two credit values credit(D) [i] = 2D (which we call D-credit ) and
credit(R) [i] = 2R + 1 (which we call R-credit ). In each round t, the algorithm
recommends objects in the same way as the p-RECsim algorithm by invoking
the RecommendByWeight() procedure. After it receives the client’s feedback,
the algorithm updates each voter’s credit and then calculate his/her weight by
invoking the UpdateCreditAndWeight() procedure.
To see the intuition behind the p-REC algorithm, let us analyze why the
p-RECsim algorithm fails in the general setting where D + R ≥ 0. If we run
p-RECsim in the general setting, we may end up with a situation where all the
client’s peers are kicked out from the system. A client’s peer can be (wrongly)
“kicked out” in two scenarios:
• when the client likes more than one objects in some round, the peer votes
on one such object, but another such object is recommended;
• when the peer votes on an object that the client dislikes, and that object
is recommended to the client.
However, since these two scenarios can happen for at most D + R times, a
natural idea is to give a voter D + R more “chances” before we kick out him/her.
Motivated by this, we could initialize each voter i with D + R + 1 credit, and
deduct i’s credit by 1 when i is caught to vote on an object the client dislikes,
or when the client likes the recommended object but i does not vote on it. We
kick out a voter only when he/she has no credit.
For some technical reasons that will be clear later, the p-REC algorithm
needs to introduce two types of credit (D-credit and R-credit), and deducts
different types of credit in different situations. It also initializes each voter with
2D (instead of D) D-credit and 2R + 1 (instead of R + 1) R-credit.
Loss analysis of the p-REC algorithm. In the remaining parts of this
section, we prove Theorem 2. We first analyze the loss of the p-REC algorithm,
we have:
Theorem 16. The p-REC algorithm guarantees O((R + 1) log Pn ) worst-case
expected loss, even for an adaptive adversary.
Proof. The proof of this theorem is very similar to the proof of Theorem 10.
First consider all the rounds with Zt = 0. Let Wt be the number of surviving
P
(R)
voters in the tth round and Ct = i∈U weight[i] · credit(R) [i] be the total Rcredit of all these Wt surviving voters in the tth round. If the client incurs a loss
in the tth round, at least ρ fraction of surviving voters will get their R-credit
deducted by 1. That is,
(R)
(R)
Ct+1 ≤ Ct − ρWt .
(13)
(R)

Since each voter has at most 2R + 1 R-credit, we have Ct

29

≤ (2R + 1)Wt .

Substitute this back to (13), we get
(R)

(R)

Ct+1 ≤ Ct


· 1−

ρ
2R + 1



.

(R)

ρ
In other words, Ct decreases by at least 2R+1
fraction whenever the client
incurs a loss. Notice that the total R-credit of all the surviving voters are
initially at most (2R + 1)n and always at least (R + 1)P (the client’s P peers
always have at least R + 1 R-credit), it then follows that the number of loss
n
ln (2R+1)n
rounds with Zt = 0 can be at most 2R+1
ρ
(R+1)P = O((R + 1) log P ).
For those rounds with Zt = 1, they cause at most γT = O(R) additional
expected loss.

Here we see the reason of introducing two types of credit: if we only had one
type of credit, the upper bound of loss would be O((D + R + 1) log Pn ), which is
not only linear to R, but also to D — this is logically wrong, because if a client
likes more objects, the loss should only be smaller.
Privacy analysis of the p-REC algorithm. Next we analyze the privacy
of the p-REC algorithm, we have:
T
)-differential
Theorem 17. The p-REC algorithm preserves O( P1 (D+R+1) log R+1
privacy, even for an adaptive adversary.

The proof of Theorem 17 follows a very similar structure to that of Theorem 11. Again, we consider two executions p-REC(C, VhUi) and p-REC(C, VhU ′ i)
for a fixed client C and a fixed pair of adjacent voting patterns VhUi, VhU ′ i (U
contains one more voter than U ′ ). Our goal is to show that |E(b)| = O( P1 (D +
T
) for any fixed recommendation sequence b = (b1 , . . . , bT ) ∈
R + 1) log R+1
B1 × · · · × BT .
We define the number of surviving voters Wt (b) in the same way as before.
P
In addition, we define Ct (b) = i∈U weight[i] · (credit(D) [i] + credit(R) [i]) to be
the total credit (D-credit plus R-credit) of all the surviving voters at the beginning of round t in the execution p-REC(C, VhUi), conditioned on that the
recommendations in the first t − 1 rounds are b1 , . . . , bt−1 . We have:
Lemma 18. For any round t, |Et (b)| ≤ 3(2D + 2R + 1) ·

λ
Ct (b) .

Proof. We can show |Et (b)| ≤ 3λ · Wt1(b) in exactly the same way as the proof
of Lemma 12. Recall that each voter has at most 2D + 2R + 1 total credit,
we therefore have Ct (b) ≤ (2D + 2R + 1)Wt (b). Lemma 18 is then proved by
substituting this back to |Et (b)| ≤ 3λ · Wt1(b) .
Lemma 19. For any round t, if |Et (b)| 6= 0, then


1
.
Ct+1 (b) ≤ Ct (b) · 1 −
3m(2D + 2R + 1)
30

Proof. By following the same arguments in the proof of Lemma 14, we can
1
show that at least 3m
fraction of surviving voters get their D-credit or R-credit
deducted by 1 after the tth round. That is,
Ct+1 (b) ≤ Ct (b) −

1
Wt (b).
3m

(14)

Since Ct (b) ≤ (2D + 2R + 1)Wt (b), substituting this back to (14), we have


1
,
Ct+1 (b) ≤ Ct (b) · 1 −
3m(2D + 2R + 1)
as desired.
Now we can prove Theorem 17:
Proof of Theorem 17. Let t1 , . . . , tK be the rounds in which |Eti (b)| 6= 0. By
replacing Lemma 12 and Lemma 14 with Lemma 18 and Lemma 19, respectively,
and then following the same arguments in the proof of Theorem 11, we can show
that
K
X
1
|E(b)| ≤ 3(2D + 2R + 1)λ
(15)
C
ti (b)
i=1
and

K
X
i=1

1
1
≤ 3m(2D + 2R + 1) ·
.
Cti (b)
CtK (b)

(16)

Since CtK (b) ≥ P (D + R + 1), substitute this to (16), we have
K
X
i=1

1
1
1
≤ 3m(2D + 2R + 1) ·
≤ 6m · .
Cti (b)
P (D + R + 1)
P

(17)

We get the desired result by substitute (17) back to (15).
Here the reason of giving each voter 2D initial D-credit and 2R + 1 initial Rcredit becomes clear: if we were to give each voter D initial D-credit and R + 1
initial R-credit, we could only get CtK (b) ≥ P instead of CtK (b) ≥ P (D +R+1),
which would introduce an extra Θ(D + R) factor in the result.

References
[1] Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering,
17(6):734–749, 2005. 6

31

[2] Baruch Awerbuch and Thomas P Hayes. Online collaborative filtering with
nearly optimal dynamic regret. In Proceedings of the 19th Annual ACM
Symposium on Parallelism in Algorithms and Architectures, pages 315–319.
ACM, 2007. 6
[3] Shlomo Berkovsky, Yaniv Eytani, Tsvi Kuflik, and Francesco Ricci. Enhancing privacy and preserving accuracy of a distributed collaborative filtering. In Proceedings of the 2007 ACM Conference on Recommender Systems, pages 9–16. ACM, 2007. 6
[4] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach
to non-interactive database privacy. In Proceedings of the 40th Annual
ACM Symposium on Theory of Computing, pages 609–618. ACM, 2008. 6
[5] Jean Bolot, Nadia Fawaz, S Muthukrishnan, Aleksandar Nikolov, and Nina
Taft. Private decayed predicate sums on streams. In Proceedings of the 16th
International Conference on Database Theory, pages 284–295. ACM, 2013.
6
[6] Joseph Calandrino, Ann Kilzer, Arvind Narayanan, Edward W Felten, Vitaly Shmatikov, et al. “You might also like:” privacy risks of collaborative
filtering. In Proceedings of the 2011 IEEE Symposium on Security and
Privacy, pages 231–246. IEEE, 2011. 6
[7] John Canny. Collaborative filtering with privacy. In Proceedings of the
2002 IEEE Symposium on Security and Privacy, pages 45–57. IEEE, 2002.
6
[8] John Canny. Collaborative filtering with privacy via factor analysis. In In
Proceedings of the 25th Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval, pages 238–245. ACM,
2002. 6
[9] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games.
Cambridge University Press, 2006. 6, 14
[10] T-H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially
private continual monitoring of heavy hitters from distributed streams. In
Privacy Enhancing Technologies, pages 140–159. Springer, 2012. 6
[11] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security,
14(3):26, 2011. 6
[12] Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. A nearoptimal algorithm for differentially-private principal components. The
Journal of Machine Learning Research, 14(1):2905–2943, 2013. 2, 6

32

[13] Richard Chow, Manas A Pathak, and Cong Wang. A practical system
for privacy-preserving collaborative filtering. In Proceedings of the 12th
IEEE International Conference on Data Mining Workshops (ICDMW),
pages 547–554. IEEE, 2012. 2, 6
[14] Cynthia Dwork. Differential privacy: A survey of results. Theory and
Applications of Models of Computation, pages 1–19, 2008. 6
[15] Cynthia Dwork. The differential privacy frontier. In Theory of Cryptography, pages 496–502. Springer, 2009. 6
[16] Cynthia Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1):86–95, 2011. 6
[17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptography,
pages 265–284, 2006. 1, 3
[18] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the 42nd
ACM Symposium on Theory of Computing, pages 715–724. ACM, 2010. 2,
6, 7
[19] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil
Vadhan. On the complexity of differentially private data release: Efficient
algorithms and hardness results. In Proceedings of the 41st Annual ACM
Symposium on Theory of Computing, pages 381–390. ACM, 2009. 6
[20] Cynthia Dwork and Adam Smith. Differential privacy for statistics: What
we know and what we want to learn. Journal of Privacy and Confidentiality,
1(2):2, 2010. 6
[21] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent
matrices. In Proceedings of the 44th annual ACM Symposium on Theory
of Computing, pages 1255–1268. ACM, 2012. 2, 6
[22] Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In Proceedings of the 45th annual ACM Symposium
on Theory of Computing, pages 331–340. ACM, 2013. 2, 6
[23] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism
for privacy-preserving data analysis. In Proceedings of the 51th Annual
IEEE Symposium on Foundations of Computer Science, pages 61–70. IEEE,
2010. 6
[24] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially
private online learning. In Proceedings of the 25th Annual Conference on
Learning Theory, pages 24.1–24.34, 2011. 2, 6, 7

33

[25] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision
problems. Journal of Computer and System Sciences, 71(3):291–307, 2005.
7
[26] Michael Kapralov and Kunal Talwar. On differentially private low rank
approximation. In Proceedings of the 24th Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1395–1414. SIAM, 2013. 2, 6
[27] Georgios Kellaris, Stavros Papadopoulos, Xiaokui Xiao, and Dimitris Papadias. Differentially private event sequences over infinite streams. Proceedings of the VLDB Endowment, 7(12), 2014. 6
[28] Solomon Kullback. Information theory and statistics. Courier Corporation,
1968. 8
[29] Wee Sun Lee. Collaborative learning for recommender systems. In Proceedings of the 18th International Conference on Machine Learning, pages
314–321, 2001. 6
[30] Frank McSherry and Ilya Mironov. Differentially private recommender
systems: Building privacy into the net. In Proceedings of the 15th ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 627–636. ACM, 2009. 2, 6
[31] Atsuyoshi Nakamura and Naoki Abe. Collaborative filtering using weighted
majority prediction algorithms. In Proceedings of the 15th International
Conference on Machine Learning, volume 98, pages 395–403, 1998. 6
[32] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of
large sparse datasets. In Proceedings of the 2008 IEEE Symposium on
Security and Privacy, pages 111–125. IEEE, 2008. 6
[33] Huseyin Polat and Wenliang Du. Privacy-preserving collaborative filtering.
International Journal of Electronic Commerce, 9(4):9–35, 2003. 6
[34] Huseyin Polat and Wenliang Du. SVD-based collaborative filtering with
privacy. In Proceedings of the 2005 ACM Symposium on Applied Computing, pages 791–795. ACM, 2005. 6
[35] Paul Resnick and Rahul Sami.
The influence limiter: Provably
manipulation-resistant recommender systems. In Proceedings of the 2007
ACM Conference on Recommender Systems, pages 25–32. ACM, 2007. 6
[36] Aaron Roth and Tim Roughgarden. Interactive privacy via the median
mechanism. In Proceedings of the 42nd ACM Symposium on Theory of
Computing, pages 765–774. ACM, 2010. 6
[37] Reza Shokri, Pedram Pedarsani, George Theodorakopoulos, and JeanPierre Hubaux. Preserving privacy in collaborative filtering through distributed aggregation of offline profiles. In Proceedings of the 2009 ACM
Conference on Recommender Systems, pages 157–164. ACM, 2009. 6
34

[38] Xiaoyuan Su and Taghi M Khoshgoftaar. A survey of collaborative filtering
techniques. Advances in artificial intelligence, 2009:4, 2009. 6
[39] Abhradeep Guha Thakurta and Adam Smith. (Nearly) optimal algorithms
for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems, pages 2733–2741, 2013.
2, 6, 7
[40] Yu Xin and Tommi Jaakkola. Controlling privacy in recommender systems.
In Advances in Neural Information Processing Systems, pages 2618–2626,
2014. 2, 6
[41] Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B Gibbons, and Feng
Xiao. Dsybil: Optimal sybil-resistance for recommendation systems. In
Proceedings of the 2009 IEEE Symposium on Security and Privacy, pages
283–298. IEEE, 2009. 6, 10

35

