Clustering Algorithms for the Centralized and Local Models∗
Kobbi Nissim†

Uri Stemmer‡

arXiv:1707.04766v1 [] 15 Jul 2017

July 15, 2017

Abstract
We revisit the problem of finding a minimum enclosing ball with differential privacy: Given
a set of n points in the Euclidean space Rd and an integer t ≤ n, the goal is to find a ball of the
smallest radius ropt enclosing at least t input points. The problem is motivated by its various
applications to differential privacy, including the sample and aggregate technique, private data
exploration, and clustering [20, 21, 15].
Without privacy concerns, minimum enclosing ball has a polynomial time approximation
scheme (PTAS), which computes a ball of radius almost ropt (the problem
√ is NP-hard to solve
exactly). In contrast, under differential privacy, until this work, only a O( log n)-approximation
algorithm was known.
We provide new constructions of differentially private algorithms for minimum enclosing ball
achieving constant factor approximation to ropt both in the centralized model (where a trusted
curator collects the sensitive information and analyzes it with differential privacy) and in the
local model (where each respondent randomizes her answers to the data curator to protect her
privacy).
We demonstrate how to use our algorithms as a building block for approximating k-means
in both models.

∗

Research supported by NSF grant No. 1565387.
Dept. of Computer Science, Georgetown University and Center for Research on Computation and Society (CRCS),
Harvard University. kobbi.nissim@georgetown.edu.
‡
Center for Research on Computation and Society (CRCS), Harvard University. u@uri.co.il.
†

1

Introduction

We revisit the problem of finding a minimum enclosing ball with differential privacy and provide
efficient algorithms for both the centralized curator model and the local model. The problem is
motivated by its various applications to differential privacy: it can be used as the aggregation
function in the sample and aggregate framework [20, 21] as well as serve as a building block in
private data exploration, and clustering [15]. Given a set of n points in the Euclidean space Rd and
an integer t ≤ n, the goal is to find a ball of smallest radius ropt enclosing at least t input points.
Definition 1.1 (revised in Definition 2.1). An instance of the 1-cluster problem is a collection of n
points in the d-dimensional Euclidean space and a target parameter t ≤ n. Let ropt be the radius of
the smallest ball containing at least t of the points. A (∆, w)-approximate solution for the instance
consists of a ball of radius at most w · ropt containing at least t − ∆ of the points.
Our recent work with Vadhan [21]
√ provided an efficient differentially private (∆,
√ w)-approximation
algorithm for 1-cluster for t > O( d log n/) with ∆ = O(log n/) and w = O( log n) (for clarity
we omit the dependency on some of the√parameters). In words, this algorithm identifies with differential privacy
√ a ball of radius O(ropt · log n) containing at least t − O(log n/) points, provided
that t > O( d log n/). This algorithm works in the centralized curator model, where all data is
collected and processed by a trusted curator.
A new construction based on locality sensitive hashing: Our first contribution is a new
algorithm for the centralized curator model. Our new algorithm LSH-GoodCenter has two main
components. First, a family of locality sensitive hash functions [17] is utilized to identify a small
number of disjoint subsets of the input points, such that (at least) one of these subsets is contained
in an (approximately) minimal enclosing ball. The identification is indirect in that it provides a
predicate that evaluates to one on the “identified” input points and zero on all other input points.
Then, these identified points are averaged with differential privacy to locate a point within their
enclosing ball. We give a construction following these lines for solving 1-cluster in the d-dimensional
Euclidean space. The resulting algorithm provides constant approximation to ropt (i.e., w = O(1)).
Furthermore, the construction lends itself to metrics other than the Euclidean metric, provided
that locality preserving hashing exist and that some “averaging” can be performed in the metric
with differential privacy. Table 1 summarizes this result in comparison with previous algorithms
for the problem.

1.1

Local algorithms

Local algorithms are a sub-class of differentially private algorithms where each individual respondent randomizes her own data to guarantee her own privacy. Hence, respondents in a local algorithm
do not need to trust a centralized curator with their data. The accuracy of local algorithms is,
generally, lower than what is achievable with a trusted curator, however, where data exists in
abundance, local algorithms can provide a practical alternative for computing over sensitive data
with minimal trust assumptions. Indeed, recent industrial implementation of differential privacy
by Google [12] and Apple [24] are reported to utilize local algorithms.
A local algorithm for 1-cluster: Our second contribution is an algorithm for 1-cluster in the
local model. The main part of the construction, Algorithm LDP-GoodCenter, combines locality
1

[20]
(centralized model)
[21]
(centralized model)
This work
(centralized model)
This work
(local model)

Needed cluster size – t
Additive loss in cluster size – ∆
n
o
2
t ≥ max 0.51n, O( d2 log2 |X|)

∆=

1


√
w = O( d/)

· log log(d|X|)


∗
· log1.5 1δ · 2O(log (|X|d))

∗
∆ = 1 · log 1δ · 2O(log (|X|d))
√

0.1
∗
t ≥ n · d · log1.5 1δ · 2O(log (|X|d))

0.1
∗
∆ = n  · log 1δ · 2O(log (|X|d))

t ≥ O 1 · n0.67 · d1/3 · log(n|X|)

∆ = O 1 · n0.67 · log(n|X|)
t≥

√

Approximation factor
in radius – w

d


√
w = O( log n)

w = O(1)

w = O(1)

Table 1: Algorithms for 1-cluster

sensitive hashing with the recent optimal heavy hitters local algorithm of Bassily et al. [2] to
identify a subset of input points that fall within an approximately minimal enclosing ball. We
then approximate the average of the identified points using a new (and simple) construction for
approximating averages of points under local differential privacy. Importantly, the respondents
running time and communication complexity is only polylogarithmic in the number of participants,
and the running time for the data curator is slightly super linear.

1.2

Application to clustering

Feldman et al. [15] showed that an algorithm for privately solving the 1-cluster problem can be used
for privately computing approximations to the k-means of the input, by iterating the algorithm for
(roughly) k 0 = k · log(n) times and finding k 0 balls that cover most of the data points (the k 0 centers
can then be post-processed to find k centers that approximate the k-means of the data points). Our
new algorithm for the 1-cluster problem immediately yields new bounds on the achievable error for
privately approximating the k-means.
k-mean clustering in the local model: We show that the construction of [15] can be implemented in the local model. Together with our local algorithm for the 1-cluster problem, this results
in the first local differentially private algorithm that computes a provable approximation of the
k-means clustering problem. As with our local algorithm for the 1-cluster problem, the running
time and the communication complexity of the users is only polylogarithmic in the number of
participants.

2

Preliminaries

Notation. Throughout the paper, we use X to denote a finite totally ordered data domain, and
use X d for the corresponding d-dimensional domain. We identify X d with points in the real d2

dimensional unit cube, quantized with grid step 1/(|X| − 1). Datasets are (ordered) collections of
elements from some data universe U (e.g., U = X or U = X d or U = Rd ). Two datasets S, S 0 ∈ U n
are called neighboring if they differ on at most one entry.

2.1

1-cluster

The reason for our explicit embedding of the finite ordered domain X in R is that certain computations are impossible for differential privacy when the input domain is the unit interval [0, 1].
An example is the Interior Point problem [6] where the task is, given n points in the unit interval
x1 , x2 , . . . , xn , to output a value in the range [min(x1 , . . . , xn ), max(x1 , . . . , xn )]. This impossibility result carries over to the 1-cluster problem (through a reduction from the interior point
problem) [21]. With this fact in mind, we now redefine 1-cluster:
Definition 2.1. A 1-cluster problem (X d , n, t) consists of a d-dimensional domain X d and parameters n ≥ t. We say that algorithm M solves (X d , n, t) with parameters (∆, w, β) if for every input
database S ∈ (X d )n it outputs, with probability at least 1 − β, a center c and a radius r such that
(i) the ball of radius r around c contains at least t − ∆ points from S; and (ii) r ≤ w · ropt , where
ropt is the radius of the smallest ball in X d containing at least t points from S.

2.2

Preliminaries from differential privacy

Consider a database, where each entry contains information pertaining to an individual. An algorithm operating on databases is said to preserve differential privacy if a change of a single record
of the database does not significantly change the output distribution of the algorithm. Intuitively,
this means that individual information is protected: whatever is learned about an individual could
also be learned with her data arbitrarily modified (or without her data).
Definition 2.2 (Differential Privacy [9]). A randomized algorithm M : U n → Y is (, δ) differentially private if for every two neighboring datasets S, S 0 ∈ U n and every T ⊆ Y we have
Pr[M (S) ∈ T ] ≤ e · Pr[M (S 0 ) ∈ T ] + δ, where the probability is over the randomness of M .
2.2.1

The Laplace and Gaussian Mechanisms

The most basic constructions of differentially private algorithms are via the Laplace and Gaussian
mechanisms as follows.
Definition 2.3 (Lp -Sensitivity). A function f mapping databases to Rd has Lp -sensitivity k if
kf (S) − f (S 0 )kp ≤ k for all neighboring S, S 0 .
Theorem 2.4 (Laplace mechanism [9]). A random variable is distributed as Lap(λ) if its probability
1
∗
d
density function is f (y) = 2λ
exp(− |y|
λ ). Let  > 0, and assume f : U → R has L1 -sensitivity k.

d
The mechanism that on input S ∈ U ∗ outputs f (S) + Lap( k ) is (, 0)-differentially private.
Theorem 2.5 (GaussianpMechanism [7]). Let , δ ∈ (0, 1), and assume f : U ∗ → Rd has L2 sensitivity k. Let σ ≥ k 2 ln(1.25/δ). The mechanism that on input S ∈ U ∗ outputs f (S) +
d
N (0, σ 2 ) is (, δ)-differentially private.
3

2.2.2

Stability based histogram [8, 23, 3]

Given a database S ∈ U ∗ , consider the task of choosing a “good” solution out of a possible solution
set F where “goodness” is measured by a quality function q : U ∗ × F → N assigning “scores” to
solutions from F (w.r.t. the given database S). One of the constructions in differential privacy –
the exponential mechanism [19] – can privately identify an approximately optimal solution f ∈ F
provided that q has low-sensitivity and that |S| & log |F |.
By focusing on cases where the number of possible solutions with “high” scores is limited, it is
possible to relax the requirement that |S| & log |F |, using what has come to be known as stability
based techniques. In this work we use stability based techniques for the following task: Given a
dataset S ∈ U n and a partition P of U , find a set p ∈ P containing (approximately) maximum
number of elements of S.
n
Theorem 2.6 ([3, 5, 25]). Fix β, , δ, n, and let t ≥ 12
 ln( βδ ). There exists an (, δ)-differentially
n
private algorithm that given S ∈ U returns a collection L ⊂ P of sets in the partition P such
that |{x ∈ S : x ∈ p}| ≥ t/4 for every p ∈ L (hence, there are at most 4n/t sets in the collection
L); and, with probability at least (1 − β), the collection L contains every set p ∈ P such that
|{x ∈ S : x ∈ p}| ≥ t.

2.2.3

The sparse vector technique [10]

Consider a sequence of low sensitivity functions f1 , f2 , . . . , fk , which are given (one by one) to a
data curator (holding a database S). Algorithm AboveThreshold by Dwork et al. [10] privately
identifies the first query fi whose value fi (S) is greater than some threshold t:
Theorem 2.7 (Algorithm AboveThreshold [10]). There exists an (, 0)-differentially private algorithm A such that for k rounds, after receiving a sensitivity-1 query fi : U ∗ → R, algorithm A
either outputs > and halts, or outputs ⊥ and waits for the next round. If A was executed with a
database S ∈ U ∗ and a threshold parameter t, then the following holds with probability (1 − β): (i)
If a query fi was answered by > then fi (S) ≥ t − 8 log(2k/β); (ii) If a query fi was answered by ⊥
then fi (S) ≤ t + 8 log(2k/β).
2.2.4

Composition theorems

We construct algorithms that use several differentially private mechanisms as subroutines, and
analyze the overall privacy using the following composition theorems:
Theorem 2.8 (Basic composition [7, 8]). A mechanism that permits k adaptive interactions with
(, δ)-differentially private mechanisms (and does not access the database otherwise) is (k, kδ)differentially private.
Theorem 2.9 (Advanced composition [11]). Let , δ, δ 0 > 0. A mechanism that permits k adaptive
interactions with (, δ)-differentially private mechanisms (and
p does not access the database otherwise) is (0 , kδ + δ 0 )-differentially private, for 0 = 2k2 +  2k ln(1/δ 0 ).

3

Our Algorithms

Let X d be a a finite subset of the Euclidean space Rd . We consider the following problem under
differential privacy:
4

Definition 3.1 (The problem of minimum enclosing ball with t points). Given a set S of n points
in X d and a parameter t ≤ n, find a ball of minimal radius ropt enclosing at least t input points.
In this section we give an informal description of our algorithms for this problem and highlight
some of the ideas behind the constructions. Any informalities made herein will be removed in the
sections that follow. Consider the following relaxed variant of the above problem:
Definition 3.2 (Minimum enclosing ball – promise version). Given a set S of n points in X d , an
integer t ≤ n, and a radius r ∈ R s.t. there exists a ball in X d containing at least t points from S,
the goal is to find a ball of radius r enclosing at least t input points.
That is, in addition to the input set S and the parameter t, in this promise problem we are also
given a target radius r, and our goal is to identify a ball of that radius that contains t of the input
points, under the promise that such a ball exists.
As was observed in [21], it suffices to solve the promise problem. To see this, fix a database
S ∈ (X d )n , and let ropt denote the smallest radius s.t. there is a ball of that radius containing t
points from S. Assume that we have an algorithm A for the promise problem. Now, for every
possible choice for a radius r, consider applying A on the database S with the radius r to obtain a
center cr . As A solves the promise problem, for every choice for r s.t. r ≥ ropt , we will have that
the ball of radius r around the obtained center cr contains at least t points from S. Using standard
tools from differential privacy (e.g., the Laplace mechanism), we can now privately estimate, for
every r, the number of input points contained in the ball of radius r around cr . Afterwards we
can return the center cr∗ and the radius r∗ such that r∗ is the minimal radius for which (our
estimation for) the number of points in the corresponding ball is at least ≈ t. In fact, as we are
only aiming for a solution with an approximated radius r, it suffices to only consider radiuses in
powers of 2. As our domain X d is finite, there are at most log(d|X|) such choices, so this will
introduce error at most polylog(d|X|) in our estimations (meaning that we will identify a ball
containing ≈ t − polylog(d|X|) input points). Furthermore, a binary search for the radius r∗ (out
of all the possible powers of 2) would reduce the error to polyloglog(d|X|). Using the privacypreserving recursion on binary search of [3] it is possible to reduce the incurred error even further,
∗
to 2O(log (d|X|)) . In the rest of this section we focus on solving (or rather approximating) the promise
problem under differential privacy. To that end, let us take an even closer look at the problem, and
define the following restricted variant:
Definition 3.3 (Promise problem, restricted to t = n). Given a set S of t points in X d and a
radius r ∈ R s.t. there exists a ball in X d containing all t input points, the goal is to locate a ball
of radius r enclosing all t input points.
Intuitively, this makes the problem easier since we no longer have to identify which of the n
points are in the 1-cluster (i.e., which t points can be enclosed in a ball of radius r). Indeed, without
privacy concerns, this restricted variant of the problem is easier, and algorithms for the restricted
problem are sometimes used as a subroutine for approximating the general problem.1 Similarly,
Nissim et al. [21] showed that in order to obtain a private approximation for the unrestricted
problem (Definition 3.2) it suffices to privately approximate the restricted problem (Definition 3.3).
1

Computing an exact solution to the problem of a minimum ball enclosing t points is NP-hard, even for the case
where t = n. However, better approximation algorithms exist for the restricted case where t = n. The restricted
version has a FPTAS while the general problem does not (assuming that P 6= N P ). See, e.g., [22].

5

√
However, their reduction introduced a factor of log n in the radius of the computed ball. Our
main technical contribution can be thought of as a new reduction from the problem of privately
approximating a solution for the general problem to privately approximating a solution for the
restricted problem while introducing only a constant blowup in the radius.
We first briefly describe the techniques of [21] for privately approximating the restricted problem:
Assume that we are given a set S of t input points in Rd , and a radius r such that the set S can
be enclosed in a ball of radius r. Our goal is to locate a center c such that a ball of radius O(r)
around c contains all of S. The strategy here is conceptually simple – compute (an estimate for)
the average of the points in S. Indeed, as S is of diameter 2r, a ball of radius 2r around this average
contains all of S. Estimating
√ the average of S can be done privately using the√Gaussian mechanism,
d·r
with error proportional to |S|d times the diameter of S, i.e., proportional to |S|
. Hence, assuming
√
that t = |S| & d, a ball of radius O(r) around the (privately obtained) estimation for the average
contains all of S.2

3.1

Our contributions

Our final task is to transform a private algorithm for the restricted promise problem
into a private
√
algorithm for the unrestricted promise problem, without incurring a blowup of log n in the radius.
As we next explain, this can be achieved using locality sensitive hashing. Informally, a locality
sensitive hash function aims to maximize the probability of a collision for similar items, while
minimizing the probability of collision for dissimilar items. Formally,
Definition 3.4 ([17]). Let M be a metric space, and let r>0, c>1, 0≤q<p≤1. A family H of
functions mapping M into domain U is an (r, cr, p, q) locality sensitive hashing family (LSH) if for
all x, y ∈ M (i) Prh∈R H [h(x) = h(y)] ≥ p if dM (x, y) ≤ r; and (ii) Prh∈R H [h(x) = h(y)] ≤ q if
dM (x, y) ≥ cr.
Now, let S ∈ Rn be an input database and let r ∈ R be s.t. there exists a ball of radius r
that contains at least t points from S. Let P ⊆ S denote the guaranteed set of t input points
contained in a ball of radius r. Assume that we have an (r, cr, p, q) locality sensitive hashing family
H mapping Rd to some domain U , and sample a function h ∈R H. Intuitively, if q (the collision
probability of dissimilar elements) is less than n−2 , then w.h.p. we will have that all dissimilar
elements (i.e., at distance more than cr) are mapped into different hash values. On the other hand,
as P ⊆ S is of diameter r, we expect that ≈ p · |P | = pt of the elements of P will be mapped into
the same hash value. In the following sections we show that this intuition is indeed correct, and
that with noticeable probability the following two events occur (over the choice of h ∈ H):
(E1 ) For every x, y ∈ S s.t. kx − yk ≥ cr it holds that h(x) 6= h(y); and,
(E2 ) There exists a hash value in U , denoted u∗ , such that |{x ∈ P : h(x) = u∗ }| ≥

p
2

· t.

Event (E1 ) states that if two points in S are mapped into the same hash value, then these points
are close. Event (E2 ) states that there is a “heavy” hash value u∗ ∈ U , such that “many” of the
points in P are mapped into u∗ .
2

For technical reasons, we cannot apply the Gaussian mechanism directly. Following [21], before using the Gaussian
mechanism, we first privately compute a box of diameter ≈ r that contains all of S, and use it to bound the diameter
of S.

6

Using standard stability based arguments (see, e.g., Theorem 2.6), we can now privately identify
a list L containing all such “heavy” hash values u ∈ U (in particular, we will have that u∗ ∈ L).
Once we have the list L, we can use every u ∈ L as a “filter” on S that isolates clustered points:
Su = {x ∈ S : h(x) = u}. Observe that, by Event E1 , for every u ∈ L we have that Su can be
enclosed in a ball of radius cr. Hence, for every u ∈ L we can use a private algorithm for the
restricted promise problem on the database Su with the radius cr, to obtain a center yu s.t. a ball
of radius O(cr) around yu contains all of Su .
So, we have generated a set of centers Y , such that there exists yu∗ ∈ Y for which a ball of
radius O(cr) centered at yu∗ contains all of Su∗ . As Su∗ contains some of the points from the
guaranteed cluster P ⊆ S of diameter 2r, we get that the ball of radius O(cr + 2r) = O(cr) around
yu∗ contains all of P , and hence, contains at least t points from S. All that remains is to privately
identify a center y ∈ Y s.t. the ball of radius O(cr) around it contains ≈ t points from S. This can
be done privately, e.g., using the sparse vector technique (see Theorem 2.7).
Choosing the LSH parameters. Recall that for the discussion above we needed that q (the
collision probability of dissimilar elements) is less than n−2 . In addition, in order to obtain a
constant factor approximation in the radius, we want to have c = O(1). Under those requirements,
existing LSH constructions can achieve p = n−b for some small constant b > 0 (for example, see [1]).
This, in turn, means that we need to have t  n−b in order for Event E2 above to be meaningful.
We obtain the following theorem.
Theorem 3.5. Let n, t, β, , δ be s.t.
t≥O

n0.1 ·


√

d

!
 
 s  
√
∗
1
nd
1
log
log
log
· 9log (2|X| d) .
β
βδ
βδ

There exists an (, δ)-differentially private algorithm that solves the 1-cluster problem (X d , n, t) with
parameters (∆, w) and error probability β, where w = O (1) and
 0.1
 
 

√
n
1
1
log∗ (2|X| d)
∆=O
log
log
·9
.

βδ
β
In words, there exists an efficient (, δ)-differentially private algorithm that (ignoring logarithmic
0.1
factors) is capable of identifying a ball of radius O(ropt ) containing t − Õ( n  ) points, provided
√
that t ≥ Õ(n0.1 · d/). The exponent 0.1 in the factor n0.1 is arbitrary and can be reduced
to any constant by appropriately choosing the LSH parameters. See Section 4 for the complete
construction and analysis.
3.1.1

1-cluster in the local model

In Section 5 we show that many of the ideas discussed above have analogues for the local model,
where each individual holds her private information locally, and only releases the outcomes of
privacy-preserving computations on her data. While our construction for the local model is conceptually similar to the centralized construction, several modifications are required. These include
introducing a new protocol for computing averages of points in Rd (satisfying local differential
privacy), and a modified “filtering” usage of the locality sensitive hash function.
7

We obtain the following theorem, which is similar in spirit to Theorem 3.5, albeit with weaker
guarantees.
Theorem 3.6. Let S = (x1 , . . . , xn ) ∈ (X d )n be a database which is distributed across n players
(each holding one point in X d ). Let t, β,  be s.t.
r


1 0.67 1/3
1
t≥O
·n
· d · log(dn|X|) log( ) .

β
There exists an algorithm, satisfying -local differential privacy (LDP), that identifies a center y
and a radius r s.t. with probability at least 1 − β,
1. r = O(ropt ), where ropt is the radius of a smallest ball containing at least t points from S.
2. The number of points from S contained in the ball of radius r around y is at least t − ∆, where
r


1 0.67
1
n
∆=O
·n
· log(d|X|) log( ) log( ) .

β
β
Our algorithm uses three rounds of communication with the users. Constructing a non-interactive
LDP algorithm for the 1-cluster problem (while maintaining constant error in the radius) remains
an intriguing open problem.

4

Locating a small cluster – the centralized setting

We begin with an algorithm for the trusted curator model. As discussed in Section 3, we use a tool
from [21] that enable us to focus on the task of locating a ball of radius r, under the assumption
that r is given to us and that r is such that there exists a ball of radius r enclosing at least t of the
input points.

4.1
4.1.1

Additional preliminaries
Tool from prior work: Algorithm GoodRadius [21]

Let S ⊆ X n be a set of input points. Given a parameter t, consider the task of privately identifying
a radius r s.t. there exists a ball of radius r containing ≈ t points from S, and furthermore, r is not
much bigger than the smallest such possible radius. Using privacy preserving recursion on binary
search [3], Nissim et al. [21] obtained the following construction:
Theorem 4.1 (Algorithm GoodRadius, [21]). Let S ∈ (X d )n be a database containing n points
from X d and let t, β, , δ be parameters. There exists a poly(n, d, log |X|)-time (, δ)-differentially
private algorithm that on input S outputs a radius r ∈ R s.t. with probability at least (1 − β):


∗
1
1. There is a ball in X d of radius r containing at least t−O 1 log( βδ
) · 9log (|X|·d) input points.
2. r ≤ 4 · ropt where ropt is the radius of the smallest ball in X d containing at least t points
from S.

8

4.1.2

Random rotation

We also use the following technical lemma to argue that if a set of points P is contained within a
ball of radius r in Rd , then by randomly rotating the Euclidean√space we get that (w.h.p.) P is
contained within an axis-aligned rectangle with side-length ≈ r/ d.
Lemma 4.2 (e.g., [26]). Let P ∈ (Rd )m be a set of m points in the d dimensional Euclidean space,
and let Z = (z1 , . . . , zd ) be a random orthonormal basis for Rd . Then,
i
h
p
Pr ∀x, y ∈ P : ∀1 ≤ i ≤ d : |hx − y, zi i| ≤ 2 ln(dm/β)/d · kx − yk2 ≥ 1 − β.
Z

4.2

Algorithm GoodCenter

We are now ready to present algorithm LSH-GoodCenter. Given a radius r computed by algorithm
GoodRadius (Theorem 4.1), the algorithm privately locates a ball of radius O(r) containing & t
points.
The privacy properties of LSH-GoodCenter follow directly from composition (see Section 2.2.4).
The analysis appears in Appendix A.
Lemma 4.3. Algorithm LSH-GoodCenter preserves (2, 2δ)-differential privacy.
We now proceed with the utility analysis of algorithm LSH-GoodCenter. We will assume the
existence of a family H of (r, cr, p=n−b , q=n−2−a )-sensitive hash functions mapping Rd to a universe
U , for some constants a > b, r > 0, and c > 1.
Lemma 4.4. Let LSH-GoodCenter be executed with the family H on a database S containing n
points in Rd , with parameters β = n−a /20 and t, , δ s.t.
!
√
 r
d
nd
1
t ≥ O nb ·
log
log( ) .

δ
δ
If there exists a ball of radius r in Rd containing at least t points
 from S, then with probability at
least n−a /4, the output ŷ in Step 7 is s.t. at least t − O 1 log(n) of the input points are contained
in a ball of radius 2r(c + 1) around ŷ.
Remark 4.5. We can think of a and b as small constants, e.g., a = 0.2 and b√= 0.1. Hence,
ignoring logarithmic factors, the above theorem only requires t to be as big as n0.1 d/. Note that
the algorithm only succeeds with small probability – namely, with probability n−a /4. This can easily
be amplified using repetitions (roughly na = n0.2 repetitions).
Proof. First recall that by the properties of the family H, for every x, y ∈ Rd s.t. kx − yk ≥ cr we
have that Prh∈H [h(x) = h(y)] ≤ q = n−2−a . Using the union bound we get
Pr [h(x) 6= h(y) for all x, y ∈ S s.t. kx − yk ≥ cr] ≥ (1 − n−a /2).

h∈R H

Let P ⊆ S denote the guaranteed set of t input points that are contained in a ball of radius r,
and let x ∈ P be an arbitrary point in P . By linearity of expectation, we have that
E [|{y ∈ P : h(y) 6= h(x)}|] ≤ t(1 − p) = t(1 − n−b ).

h∈H

9

Hence, by Markov’s inequality,


t(1 − n−b )
≤ 1 − n−a .
Pr |{y ∈ P : h(y) 6= h(x)}| ≥
h∈H
1 − n−a
So,




1 − n−b
Pr |{y ∈ P : h(y) = h(x)}| ≥ t 1 −
≥ n−a .
h∈H
1 − n−a

Simplifying, for large enough n (specifically, for na−b ≥ 2) we get


t
−b
Pr |{y ∈ P : h(y) = h(x)}| ≥ · n
≥ n−a .
h∈H
2

So far we have established that with probability at least n−a /2 over the choice of h ∈ H in
Step 1 the following events occur:
(E1 ) For every x, y ∈ S s.t. kx − yk ≥ cr it holds that h(x) 6= h(y); and,
(E2 ) There exists a hash value in U , denoted u∗ , such that |{y ∈ P : h(y) = u∗ }| ≥

t
2

· n−b .

Event (E1 ) states that if two points in S are mapped into the same hash value, then these
points are close. Event (E2 ) states that there is a “heavy” hash value u∗ ∈ U , such that “many” of
the points in P are mapped into u∗ . We proceed with the analysis assuming that these two events
occur.
In Step 2 we use Theorem 2.6 to identify a list L ∈ U ∗ that, w.p. (1 − β), contains all “heavy”
hash values u ∈ U . In particular, with probability at least (1 − β) we have that u∗ ∈ L. We proceed
with the analysis assuming that this is the case.
In Step 3 we generate a random orthonormal basis Z. By Lemma 4.2, with probability at least
(1 − β), for everypx, y ∈ S and for every zi ∈ Z, we have that the projection of (x − y) onto zi is of
length at most 2 ln(dn/β)/d · kx − yk. In particular, for every hash value u ∈ L we have that the
projection of p
Su , {x ∈ S : h(x) = u} onto every axis zi ∈ Z fits within an interval of length at
most p = 2rc ln(dn/β)/d.
In Step 4 we use Theorem 2.6 again to identify, for every u ∈ L and for every axis zi ∈ Z,
an interval of length 3p containing all of u. For our choice of t, all of these applications together
succeed with probability
at least (1 − β). This results, for every u ∈ L, in a box B(u) of side length
√
3p and diameter 3p d containing all of Su .
For every u ∈ L denote the average of the points in Su as yu . In Step 5 we use the Gaussian
mechanism to compute the noisy average ŷu of Su for every u ∈ L. The noise magnitude reduces
with the size of the sets |Su |, and for our choice of t (recall that |Su | ≥ t/4 for every u ∈ L), with
probability at least (1 − β) we have that kyu − ŷu k ≤ cr for every u ∈ L.
Recall that there exists a hash value u∗ ∈ L such that some of the points from the guaranteed
cluster P are mapped (by h) into u∗ . Let v ∈ P be such that h(v) = u∗ . A ball of radius 2r around
v contains all of P , as P is of radius r. In addition, by (E1 ), a ball of radius cr around yu∗ contains
all of Su∗ . As, kyu∗ − ŷu∗ k ≤ cr, we get that a ball of radius 2cr around ŷu∗ contains all of Su∗ ,
and in particular, contains v. Thus, a ball of radius 2cr + 2r around ŷu∗ contains all of P , that
is, contains at least t input points. Hence, by the properties of algorithm AboveThreshold, with
probability at least (1 − β), the loop in Step 7 ends with algorithm AboveThreshold retuning >,
10

identifying a point ŷu such that a ball of radius 2cr + 2r around it contains at least t − 65
 log(2n/β)
input points.
All in all, with probability at least n−a /2 − 5β = n−a /4 we have that algorithm GoodCenter
outputs a point ŷ such that a ball of radius 2r(c + 1) around it contains at least t − 65
 log(2n/β)
input points.
Theorem 3.5 now follows by combining Theorem 4.1 (algorithm GoodRadius) with Lemmas 4.3
and 4.4 (algorithm LSH-GoodCenter).

5

Locating a small cluster – the distributed setting

We begin by describing private computation in the local model where each individual holds her
private information locally, and only releases the outcomes of privacy-preserving computations on
her data. This is modeled by letting the algorithm access each entry xi in the input database
S = (x1 , . . . , xn ) ∈ X n separately, and only via differentially private local randomizers.
Definition 5.1 (Local Randomizer, LR Oracle [18]). A local randomizer R : X → W is a randomized algorithm that takes a database of size n = 1. Let S = (x1 , . . . , xn ) ∈ X n be a database.
An LR oracle LRS (·, ·) gets an index i ∈ [n] and a local randomizer R, and outputs a random value
w ∈ W chosen according to the distribution R(xi ).
Definition 5.2 (Local differential privacy). An algorithm satisfies (, δ)-local differential privacy
(LDP) if it accesses the database S only via the oracle LRS with the following restriction: for
all possible executions of the algorithm and for all i ∈ [n], if LRS (i, R1 ), . . . , LRS (i, Rk ) are the
algorithm’s invocations of LRS on index i, then the algorithm B(x) = (R1 (x), R2 (x), . . . , Rk (x)) is
(, δ)-differentially private. Local algorithms that prepare all their queries to LRS before receiving
any answers are called noninteractive; otherwise, they are interactive.

5.1

Additional preliminaries

We now present additional preliminaries that enable our construction.
5.1.1

Counting queries and histograms with local differential privacy

The most basic task we can apply under local differential privacy is a counting query. Consider a
database S ∈ X n which is distributed across n users (each holding one element from X). Given
a predicate y : X → {0, 1}, consider the task of estimating the number of users holding a value x
√
such that y(x) = 1. This can be solved privately with error proportional to 1 n.
Notation. For a database S ∈ X n and a domain element x ∈ X, we use fS (x) to denote the
duplicity of x in S, i.e.,
fS (x) = |{xi ∈ S : xi = x}|.
Theorem 5.3 (e.g., [18]). Let  ≤ 1. Let S = (x1 , . . . , xn ) ∈ {0, 1}n be a database which is
distributed across n players (each holding one bit). There exists an algorithm satisfying q
-LDP that

returns an estimation a ∈ R s.t. with probability at least 1−β we have that |a−fS (1)| ≤
11

3


n · ln( β8 ).

Algorithm LSH-GoodCenter
Input: Database S ∈ Rd containing n points, radius r, target number of points in cluster t, failure
probability β, privacy parameters , δ, and another parameter c (reflecting multiplicative error in
the radius of the found ball).
Tool used: A family H of (r, c · r, p, q)-locality sensitive hash functions mapping Rd to a universe
U.
1. Sample a hash function h ∈ H mapping Rd to U . For u ∈ U define Su as the multiset
containing all elements of S that are mapped into u by h, i.e., Su , {x ∈ S : h(x) = u}.
2. Use algorithm from Theorem 2.6 with privacy parameters ( 4 , 4δ ) to identify L ⊂ U that, w.p.
q
√
)
(1 − β), L contains every hash value u ∈ U s.t. |Su | ≥ 960 d ln( nd
ln( 8δ ). Moreover, for
βδ
q
√
8
every u ∈ L we have that |Su | ≥ 240 d ln( nd
βδ ) ln( δ ).
% W.h.p. L contains a hash value u s.t. a lot of the input points from the guaranteed cluster of radius r
are mapped into u.

q
3. Let Z = (z1 , . . . , zd ) be a random orthonormal basis of Rd and p = 2rc ln( dn
β )/d.
For each basis vector zi ∈ Z, partition the axis in direction zi into intervals Ii =
{[j · p , (j + 1) · p) : j ∈ Z}.
4. For every hash value u ∈ L, identify (in an axis by axis manner) an axis aligned rectangle
containing all of Su . Specifically, for every u ∈ L:
(a) 
For each basis vector
zi ∈ Z, use algorithm from Theorem 2.6 with privacy parameters

δ
√ 
to choose an interval Ii (u) ∈ Ii containing a large number of points
, 8d
10

d ln(8/δ)

from Su . Let Iˆi (u) denote that chosen interval after extending it by p on each side (that
is Iˆi (u) is of length 3p).
(b) Let B(u) be the box in Rd whose projection on every basis vector zi ∈ Z is Iˆi (u). Define
Su0 = Su ∩ B(u).

% Observe that we defined Su0 = Su ∩ B(u) although we expect that Su ⊆ B(u). This will be useful
in the privacy analysis, as we now have a deterministic bound on the diameter of Su0 .

5. For every hash value u ∈ L: Use the Gaussian mechanism with privacy parameters ( 4 , 4δ ) to
compute the noisy average of the points in Su0 . Denote the outcome as ŷu .
6. Instantiate algorithm AboveThreshold (Theorem 2.7) with database S, privacy parameter
/4, and threshold t − 33
 log(2n/β).
7. For every hash value u ∈ L: Query algorithm AboveThreshold for the number of input points
contained in a ball of radius 2r(c + 1) around ŷu . If the answer is > then halt and return ŷu .
Otherwise continue.

12

A slightly more complicated task is when instead of a binary predicate, we have a function
y : X → U mapping domain elements to a (potentially) large set U . We use a tool from the recent
work of Bassily et al. [2] on heavy hitters in the local model.
Theorem 5.4 ([2]). Let  ≤ 1. Let U be a data universe, and let S = (u1 , . . . , un ) ∈ U n be a
database which is distributed across n players (each holding one row). There exists an algorithm
√
satisfying -LDP that returns a set L ⊆ (U × R) of size at most |L| ≤ n s.t. with probability 1 − β
we have
 q

1. For every (u, a) ∈ L we have that |a − fS (u)| ≤ O 1 n log( βn ) .
2. For every u ∈ U s.t. fS (u) ≥ O
5.1.2

 q
1




1
n log( |X|
β ) log( β )

, we have that u appears in the set L.

Concentration bounds

We will use the following variant of the Hoeffding bound for sampling without replacement.
Theorem 5.5 (Hoeffdings inequality, sampling without replacement [16]). Let X = (x1 , . . . , xN )
be a finite population of N points and X1 , . . . , Xn be a random sample drawn without replacement
from X . Let a = mini∈[N ] {xi } and b = maxi∈[N ] {xi }. Then, for all  > 0,
Pr

"

#


n
N
1 X
2n2
1X
Xi −
xi ≥  ≤ 2 exp −
.
n
N
(b − a)2
i=1

i=1

We also use the following tail bound on sums of λ-wise independent random variables.
Lemma 5.6 ([4]). Let λ ≥ 6 be an even integer. Suppose X1 , . . . , Xn are λ-wise independent
random variables taking values in [0, 1]. Let X = X1 + · · · + Xn and µ = E[X], and let α > 0.
Then,
 λ/2
nλ
Pr[|X − µ| ≥ α] ≤
.
α2
We also use a standard “Chernoff type” concentration bound for sums of i.i.d. samples from
Lap(b):
Lemma 5.7. Suppose X1 , . . . , Xn are independent samples from Lap( 1 ). That is, every Xi has
probability density function f (x) = 2 exp(−|x|). Let X = X1 + · · · + Xn . For every t ≥ 0 it holds
that


·t
Pr[|X| ≥ t] ≤ 6 exp − √
.
2n
Moreover, for every 0 ≤ t < 2n/ we have that

 2 2
 ·t
Pr[|X| ≥ t] ≤ 2 exp −
.
4n

13

5.2

Average of vectors in Rd

For our algorithms we will need a tool for privately computing averages of vectors in Rd . Specifically,
assume that there are n users, where user j is holding a point xj ∈ Rd . Moreover, assume that
we have a bound b ≥ 0 such that we are only interested in points xj ∈ Rd s.t. every coordinate of
xj is between 0 and b (let us them “interesting points”). We would like to obtain an estimation
(satisfying LDP) for the average of these interesting points. This can be achieved by having each
user send a noisy version of its point. An estimation for the average of the interesting points can
then be computed from the average of all the noisy points.
Algorithm R: Local Randomizer for LDP-AVG
Inputs: x ∈ R, privacy parameter , and range parameter b.
1. If x > b or x < 0 then set x = 0.
2. Let z ← x + Lap( b ).
3. Return z.

Algorithm LDP-AVG
Public parameters: Random partition of [n] into d subsets I1 , . . . , Id .
Setting: Each player j ∈ [n] holds a value vj ∈ Rd ∪ {⊥}. Define S = (v1 , . . . , vn ).
For j ∈ [n] let vj0 = vj if every coordinate of vj is in [0, b]. Otherwise set vj0 = ~0 ∈ Rd .
For j ∈ [n] let xj denote the `th coordinate of vj0 , where ` is s.t. j ∈ I` .
Define Se = (x1 , · · · , xn ).
e
Oracle access: LR Oracle to S and S.
1. For j ∈ [n] let zj ← LRSe(j, R) with parameters 2 , b.
P
2. For ` ∈ [d] define y` = |In` | j∈I` zj . Let y = (y1 , . . . , yd ) ∈ Rd .

3. Let t denote the number of users j holding a value vj ∈ Rd s.t. every coordinate of vj is
between 0 and b. Use Theorem 5.3 with parameter /2 to obtain a noisy estimation t̂ for t.
4. Return

1
t̂

· y.

Observation 5.8. Algorithm LDP-AVG satisfies -LDP.
Lemma 5.9. Let b > 0 be a parameter. Fix individual information vj ∈ Rd ∪ {⊥} for every user
j ∈ [n]. Let D ⊆ [n] denote the subset of users holding a value vj 6= ⊥ s.t. every coordinate
of vj
q

is between 0 and b, and denote |D| = t. Assume that n ≥ 8d ln( 8d
β ), and that t ≥

12


n log( 32
β ).

Then, with probability at least 1 − β, algorithm LDP-AVG returns a vector a ∈ Rd such that
s
1X
30bd
32d
a−
vj ≤
n ln(
).
t
t
β
j∈D

2

14

Remark 5.10. For simplicity, in Lemma 5.9 we assumed that “interesting points” are points
x ∈ Rd such that x ∈ B, where B is a box with side-length b, aligned with the origin. This can
easily be generalized to arbitrary axis-aligned boxes B with side-length b (that is, not necessarily
located at the origin) by, e.g., shifting the axes accordingly.
Remark 5.11. Observe that the
√ error in Lemma 5.9 decreases with t (the number of “interesting
points”). Specifically, for t√& nd we get that the error is proportional to the diameter of the box
of interesting points, i.e., db.
Remark 5.12. Note that every user in the above protocol sends (on step 3 of algorithm R) a real
number z. In fact, it suffices to have each user send only O(log n) bits, without effecting the error
guarantees
of

 Lemma 5.9. To see this, observe that we can truncate z to an interval of length
b
n
O  log( β ) . Indeed, by the properties of the Laplace distribution, w.h.p. this truncation has no
 q

effect on the computation. We can now discretize this interval with grid steps O tb nd log( βd ) ,
and have every user send the grid point closest to the
point z, which
can be represented using
 q

d
d
b
O(log n) bits. This introduces an error of at most O t n log( β ) per user, and hence error at
 q

 q

d
most O tb dn log( βd ) per coordinate, and thus, error at most O bd
n
log(
)
in L2 norm.
t
β
Proof of Lemma 5.9. Our goal is to relate y/t̂ (the output obtained on step 4) to


P
will now show that w.h.p. every coordinate of yt̂ − 1t j∈D vj is small.

1
t

P

j∈D vj .

We

First observe that by the Chernoff bound, assuming that n ≥ 8d ln( 8d
β ), with probability at

n
least 1 − β4 , for every ` ∈ [d] we have that 2d
≤ |I` | ≤ 2n
d . We continue the analysis assuming that
this is the case. Also, by Theorem 5.3, with probability at least 1 − β4 we have that t̂ (computed on
q
q
12
).
In
particular,
assuming
that
t
≥
n log( 32
step 3) satisfies |t − t̂| ≤ 6 n log( 32
β

β ) we get that
t
2

≤ t̂ ≤ 2t. We proceed with the analysis assuming that this is the case.
For ` ∈ [d], observe that y` (defined on Step 2 of the algorithm) can be expressed as
y` =

n X
n X
n X
(xj + ηj ) =
vj,` +
ηj ,
|I` |
|I` |
|I` |
j∈I` ∩D

j∈I`

(1)

j∈I`

where vj,` is coordinate ` of vj , and every ηj is sampled from Lap( 2b
 ). By the Hoeffding bound
(sampling without replacement, Theorem 5.5), with probability at least 1 − β4 we have that
X
n X
vj,` −
vj,` ≤ bn
|I` |
j∈I` ∩D

j∈D

s

15

p
1
ln(8/β) ≤ b dn ln(8/β).
2|I` |

(2)

Combining Equalities (1) and (2), and using the triangle inequality, we get
y` 1 X
−
vj,`
t
t̂
j∈D

≤

p


b dn ln(8/β)
1 1 X
n X
−
+
ηj +
vj,`
t
t̂
t̂|I` | j∈I
t̂ j∈D
`

≤

p
b dn ln(8/β)
n X
|t̂ − t| · b
+
ηj +
t̂
t̂|I` | j∈I
t̂

≤

2b p
4d X
12b
dn ln(8/β) +
ηj +
t
t
t

`

j∈I`

r
32
n log( ).
β

(3)

Finally, by Lemma 5.7 (tail bound for sum of i.i.d. samples from the Laplace
distribution), with
q
P
β
n
4b
8d
probability at least 1 − 4 , for every ` ∈ [d] we have that
j∈I` ηj ≤ 
d ln( β ). So,
16b
2b p
dn ln(8/β) +
(3) ≤
t
t

s

12b
8d
dn ln( ) +
β
t

s
r
30b
32
32d
).
n log( ) ≤
dn ln(
β
t
β



P
Overall, with probability at least 1−β we get that every coordinate of the vector yt̂ − 1t j∈D vj
q
dn ln( 32d
is at most 30b
t
β ) in absolute value. Hence, with probability at least 1 − β we have
y 1X
−
vj
t
t̂
j∈D

5.3

≤

30bd
t

2

s

n ln(

32d
).
β

Algorithm LDP-GoodCenter

We are now ready to present our local algorithm for the 1-cluster problem. As we mentioned in
the introduction, our algorithm can be used as a building block for privately approximating the
k-means clustering problem, by iterating the algorithm and finding (roughly) k balls that cover
most of the data points. To that end, during the ith iteration we will need the ability to exclude
from the computation the data points that were already covered in the previous iterations. This
is handled by an additional input to the algorithm, a predicate σ, denoting a portion of the data
universe to be excluded from the computation (meaning that if σ(x) = 1 then x is to be excluded).
Our main statement for the 1-cluster problem under LDP is the following.
Theorem 5.13. Fix a predicate σ : X d → {0, 1}. Let S = (x1 , . . . , xn ) ∈ (X d )n be a database
which is distributed across n players (each holding one point in X d ). Let t, β,  be s.t.
r

 !
n0.51 · d1/2
1
n0.67 · d1/3
1 1/3
t≥O
log(dn|X|) log( ) +
log(dn|X|) log( )
.

β
β
2/3
There exists an -LDP algorithm that identifies a center y and a radius r s.t. with probability at
least 1 − β,
16

1. r = O(ropt ), where ropt is the radius of a smallest ball containing at least t points from
Sσ = {x ∈ S : σ(x) 6= 1}.
2. The number of points from Sσ contained in the ball of radius r around y is at least t − ∆,
where
r


1 n1.01
1
n
· log(d|X|) log( ) log( ) .
∆=O
·
 t1/2
β
β
The main part of our construction is algorithm LDP-GoodCenter which, assuming t of the
input points are contained in a ball of radius r (given as an input parameter) identifies a ball
containing ≈ t points. As the radius r is not known in advance, we execute O(log |X|) copies
of LDP-GoodCenter in parallel with exponentially growing values of r (one of which provides a
constant factor approximation to ropt ). Another alternative is to perform a binary search on r,
hence paying in increasing round complexity to log log |X| but saving on composition, and hence
accuracy.
Algorithm LDP-GoodCenter
Input: Radius r, target number of points t, failure probability β, privacy parameter .
Optional input: A predicate σ : X d → {0, 1} (otherwise set σ ≡ 0).

Tool used: Family H of (r, c · r, p, q)-locality sensitive hash functions mapping Rd to a universe U .
Setting: Each player j ∈ [n] holds a value xj ∈ X d . Define S = (x1 , . . . , xn ).
1. Sample a hash function h ∈ H mapping Rd to U .

2. Use Theorem 5.4 with 4 to identify a list L of length at most 32n1+b /t containing all values
t
u ∈ U s.t. |{x ∈ S : h(x) = u}| ≥ 16
· n−b .
q
3. Let Z = (z1 , . . . , zd ) be a random orthonormal basis of Rd , and denote p = 2rc ln( dn
β )/d.
√
Partition every axis into intervals of length p, denoted as I = {I1 , I2 , . . . , I d|X| }.
4. Randomly partition S into subsets S41 , . . . , S4d of size |S4i | = nd . For every basis vector zi ∈ Z,
use Theorem 5.4 with 4 to obtain for every pair (I, u) ∈ I×U an estimation ai (I, u) for
|{x ∈ S4i : σ(x) 6= 1 and h(x) = u and hx, zi i ∈ I}|.
5. For every basis vector zi ∈ Z and for every hash value u ∈ L, denote I(i, u) =
ˆ u) by extending I(i, u) by p to each direction
argmaxI∈I {ai (I, u)}, and define the interval I(i,
ˆ
(that is, I(i, u) is of length 3p).
6. For every hash value u ∈ L, let B(u) denote the box in Rd whose projection on every axis
ˆ u).
zi ∈ Z is I(i,
|L|

n
7. Randomly partition S into subsets S71 , . . . , S7 of size |S7` | = |L|
. That is, for every u ∈ L
u
we have a subset S7 ⊆ S. For every u ∈ L use algorithm LDP-AVG with 4 to obtain an
approximation ŷu for the average of {x ∈ S7u : h(x) = u and x ∈ B(u) and σ(x) 6= 1} .

8. Output {ŷu : u ∈ L}.

17

Observation 5.14. Algorithm LDP-GoodCenter satisfies -LDP.
We now proceed with the utility analysis of algorithm LDP-GoodCenter. We will assume the
existence of a family H of (r, cr, p=n−b , q=n−2−a )-sensitive hash functions mapping Rd to a universe
U , for some constants a > b, r > 0, and c > 1.
Lemma 5.15. Fix a predicate σ : X d → {0, 1}. Let S = (x1 , . . . , xn ) ∈ (X d )n be a database which
is distributed across n players (each holding one row), and let P ⊆ {x ∈ S : σ(x) = 1} be a set of t
input points which can be enclosed in a ball of radius r. Let LDP-GoodCenter be executed with the
family H and with a radius r and with parameters β = n−a /24 and t,  s.t.
!
1
2
n 2 +b · d1/2
n 3 +b · d1/3
2/3
t≥O
(log(dn))
.
log(dn|X|) +

2/3
1+b

The algorithm outputs a set Y of 32·nt
vectors in Rd such that with probability at least n−a /4
there exists a vector y ∈ Y such that the ball of radius 3cr around y contains at least 1 point from
P.
Proof. First observe that, w.l.o.g., we can assume that the range U of every function in H is of
size |U | ≤ n3 . If this is not the case, then we can simply apply a (pairwise independent) hash
function with range n3 onto the output of the locally sensitive hash function. Clearly, this will not
decrease the probability of collusion for “close” elements (within distance r), and moreover, this
can increase the probability of collusion for “non-close” elements (at distance at least cr) by at
most n−3 = o(n−2−a ) = o(q).
Now recall that by the properties of the family H, for every x, y ∈ Rd s.t. kx − yk ≥ cr we have
that Prh∈H [h(x) = h(y)] ≤ q = n−2−a . Using the union bound we get
Pr [h(x) 6= h(y) for all x, y ∈ S s.t. kx − yk ≥ cr] ≥ (1 − n−a /2).

h∈R H

Let P ⊆ S denote the guaranteed set of t input points x ∈ S with σ(x) 6= 1 that are contained
in a ball of radius r, and let x ∈ P be an arbitrary point in P . By linearity of expectation, we have
that
E [|{y ∈ P : h(y) 6= h(x)}|] ≤ t(1 − p) = t(1 − n−b ).
h∈H

Hence, by Markov’s inequality,


t(1 − n−b )
Pr |{y ∈ P : h(y) 6= h(x)}| ≥
≤ 1 − n−a .
h∈H
1 − n−a
So,





1 − n−b
Pr |{y ∈ P : h(y) = h(x)}| ≥ t 1 −
≥ n−a .
h∈H
1 − n−a

Simplifying, for large enough n (specifically, for na−b ≥ 2) we get


t
Pr |{y ∈ P : h(y) = h(x)}| ≥ · n−b ≥ n−a .
h∈H
2

So far we have established that with probability at least n−a /2 over the choice of h ∈ H in
Step 1 the following events occur:
18

(E1 ) For every x, y ∈ S s.t. kx − yk ≥ cr it holds that h(x) 6= h(y); and,
(E2 ) There exists a hash value in U , denoted u∗ , such that |{y ∈ P : h(y) = u∗ }| ≥

t
2

· n−b .

Event (E1 ) states that if two points in S are mapped into the same hash value, then these
points are close. Event (E2 ) states that there is a “heavy” hash value u∗ ∈ U , such that “many” of
the points in P are mapped into u∗ . We proceed with the analysis assuming that these two events
occur.
Onstep 2, we identify a list L containing
all such “heavy” hash values u ∈ U . Assuming that

p
1
0.5+b
t ≥ O  ·n
· log(n/β) log(1/β) , Theorem 5.4 ensures that with probability at least 1 − β
∗
we have that u ∈ L. We continue with the analysis assuming that this is the case.
On Step 3 we generate a random orthonormal basis Z. By Lemma 4.2, with probability at least
(1 − β), for every x,py ∈ S and for every zi ∈ Z, we have that the projection of (x − y) onto zi is
of length at most 2 ln(dn/β)/d · kx − yk. In particular, for every hash value u ∈ L we have that
the projection ofpSu , {x ∈ S : h(x) = u} onto every axis zi ∈ Z fits within an interval of length
at most p = 2rc ln(dn/β)/d. Recall that we divide (on step 3) every axis zi ∈ Z into intervals of
length p, denoted as I = {I1 , I2 , . . . }. Hence, for every axis zi ∈ Z and for every u ∈ U , we have
that the projection of Su onto zi is contained within 1 or 2 consecutive intervals from I.
On step 4 we partition S into d subsets S4i ⊆ S of size nd . By the Hoeffding bound, assuming
q
that t ≥ 2 · n0.5+b · 2d ln( 2d
β ), with probability at least 1 − β, for every i ∈ [d], we have that
−b

u∗ |
|S4i ∩ Su∗ | ≥ |S2d
≥ t·n4d . Recall that the projection of Su∗ onto every axis zi ∈ Z fits within
(at most) 2 consecutive intervals from I. Hence, for every axis zi ∈ Z, at least 1 interval from
−b
I contains
at least half of the points from
S4i ∩ Su∗ , i.e., at least t·n8d points. Therefore, for


q
1
t ≥ O 1 · n0.5+b · d · log( dn|X|
β ) log( β ) , Theorem 5.4 ensures that with probability at least 1−β,

for every zi ∈ Z we have that I(i, u∗ ) = argmaxi∈I {ai (I, u∗ )} (defined on step 5) contains at least
ˆ u∗ ) obtained by extending I(i, u∗ ) by p to each
one point from Su∗ , and hence, the interval I(i,
direction, contains (the projection of) all of the points from Su∗ (onto the ith axis). As a result,
ˆ u∗ ), contains
the box B(u∗ ), defined on step 7 as the box whose projection onto every axis i is I(i,
all of Su∗ . We continue with the analysis assuming that this is the case.
|L|
On step 7 we partition S into |L| subsets S71 , . . . , S7 . For every u ∈ L we then use S7u to obtain
a an estimation ŷu for the average yu of the points x ∈ S7u s.t. h(x) = u and x ∈ B(u). By the
2
∗
u∗ |
Hoeffding bound, with probability at least 1 − β, we have that |S7u ∩ Su∗ | ≥ |S2|L|
≥ 128·nt 1+2b . If
that is the case, then as B(u∗ ) is of side length p, Lemma 5.9 ensures that with probability at least

2/3
2
+b
1/3 · log( dn )
3
. We continue
1 − β we have that kyu∗ − ŷu∗ k2 ≤ cr, provided that t ≥ 310
·
n
·
d
2/3
β
with the analysis assuming that this is the case.
Observe that yu∗ is the average of (some of) the points in Su∗ , and that every two points in Su∗
are within distance cr from each other. Hence, we get that a ball of radius 2cr around yu∗ contains
all of Su∗ . In particular, as Su∗ contains at least some of the points from P (the guaranteed cluster
radius r with t input points from S), we have that the ball of radius 2cr around yu∗ contains at
least 1 point from P . Therefore, as kyu∗ − ŷu∗ k2 ≤ cr we get that a ball of radius 3cr around ŷu∗
contains at least 1 points from P .
−a
Overall, with probability at least n 2 − 6β we have that the output on step 8 contains at least
one vector ŷ s.t. the ball of radius 3cr around ŷ contains at least one point from P .
19

Algorithm LDP-1Cluster
Input: Radius r, target number of points t, failure probability β, privacy parameters , δ.
Optional input: A predicate σ : X d → {0, 1} (otherwise set σ ≡ 0).

Tool used: Algorithm LDP-GoodCenter with success probability n−a /4, and error factor (in the
radius) at most 3c.
Setting: Each player j ∈ [n] holds a value xj ∈ X d . Define S = (x1 , . . . , xn ).
√
1. Denote J = log( d|X|) and K = 4 · na · ln(1/β). Randomly partition S into R · T subsets
n
S1,1 , . . . , SR,T of size JK
each.
2. For every j ∈ [J] and every k ∈ [K] apply LDP-GoodCenter on the database Sj,k with the
2j
t
radius |X|
, the predicate σ, privacy parameter 2 , and the parameter t0 = 2JK
. Obtain a set
of L =

64·n1+b
t

vectors: Ŷj,k = {ŷj,k,1 , . . . , ŷj,k,L }.

3. Randomly partition S into J · K · L subsets S1,1,1 , . . . , SJ,K,L of size

n
JKL

each.

4. For every j ∈ [J], every k ∈ [K], and every ` ∈ [L], use Theorem 5.3 on the database Sj,k,`
with 2 to obtain an estimation ĉj,k,` for the number of points x ∈ Sj,k,` enclosed in a ball of
2j
radius 5c |X|
around ŷj,k,` , for which σ(x) 6= 1.

5. Let j 0 be the smallest number in [J] for which there exist (k 0 , `0 ) ∈ [K]×[L] s.t.
r
1
32n
224 n1+a
· 1/2 · log(d|X|) log( ) log(
).
JKL · ĉj 0 ,k0 ,`0 ≥ t −

β
β
t
j0

2
Return the vector t̂j 0 ,k0 ,`0 and the radius 5c |X|
.

20

We are now ready to prove Theorem 5.13. The proof is via the construction of algorithm
LDP-1Cluster.
Proof of Theorem 5.13. The privacy properties of algorithm LDP-1Cluster are immediate. We
now proceed with the utility analysis.
Let ropt be the radius of the smallest ball in X d containing at least t points from {x ∈ S :
σ(x) 6= 1}, and let P denote a set of t such points. Let j ∗ denote the smallest integer s.t. ropt ≤
j∗

∗

2j
|X| ,

and denote r = 2|X| .
On step 1 we partition
S into JK subsets S1,1 , . . . , SJ,K . By the Hoeffding bound, assuming
q
that t ≥ 8 · n

1+a
2

·

log(d|X|) log( β1 ) log( 8n
β ), with probability at least 1 − β, for every k ∈ [K] we

have that |Sj ∗ ,k ∩ P | ≥ t0 =

t
2JK .

That is, for every k ∈ [K], the database Sj ∗ ,k contains at least
j∗

points from P , which can be enclosed in a ball of radius 2|X| = r. Hence, by the guarantees of
algorithm LDP-GoodCenter (Theorem 5.15), for every k ∈ [K], with probability at least n−a /4 we
have that Ŷj ∗ ,k contains a vector ŷ s.t. the ball of radius 3cr around ŷ contains at least 1 point
from P , provided that
r

 !
1
2
1
n 2 +a+b · d1/2
n 3 +a+b · d1/3
1 1/3
t≥O
log(dn|X|) log( ) +
log(dn|X|) log( )
.

β
β
2/3
t0

S
Therefore, as K = 4na ln( β1 ), we get that with probability at least (1 − β), the set k∈[K] Ŷj ∗ ,k
contains at least one vector, denoted ŷj ∗ ,k∗ ,`∗ , s.t. the ball of radius 3cr around it contains at least
1 point from P . We continue with the analysis assuming that this is the case. Observe that, as the
set P is of diameter (at most) 2r, we get that a ball of radius 5cr around ŷj ∗ ,k∗ ,`∗ contains all of P .
On step 3 we partition S into JKL subsets S1,1,1 , . . . , SJ,K,L . For every (j, k, `) ∈ [J]×[K]×[L],
we then use Theorem 5.3 to obtain an estimation ĉj,k,` for the number of points from Sj,k,` that
2j
are enclosed in the ball of radius 5c |X|
around ŷj,k,` . Let us denote the true number of points from
Sj,k,` in that ball as cj,k,` (Sj,k,` ). Similarly, let cj,k,` (S) denote the number of points from S in that
2j
ball, i.e., the number of points from S that are enclosed in the ball of radius 5c |X|
around ŷj,k,` .
By the Hoeffding bound, with probability at leastq
1 − β, for every (j, k, `) ∈ [J]×[K]×[L] we
have that |cj,k,` (S) − JKL · cj,k,` (Sj,k,` )| ≤ 32 ·

n1+a
t1/2

·

log(d|X|) log( β1 ) log( 32n
β ). In addition, by

the guarantees of Theorem 5.3, with probability at least 1q− β, for every (j, k, `) ∈ [J]×[K]×[L] we
n1+a
have that |JKL · cj,k,` (Sj,k,` ) − JKL · ĉj,k,` | ≤ 192
log(d|X|) log( β1 ) log( 7n
 · t1/2 ·
β ), and hence, for
every (j, k, `) ∈ [J]×[K]×[L] we have

224 n1+a
|cj,k,` (S) − JKL · ĉj,k,` | ≤
· 1/2 ·

t

r
1
32n
log(d|X|) log( ) log(
).
β
β

We continue with the analysis assuming that this is the case.
S
We have already established the existence of a vector ŷj ∗ ,k∗ ,`∗ ∈ k∈[K] Ŷj ∗ ,k s.t. the ball of radius
j∗

5c 2|X| around it contains all of P , i.e., contains at least t points from S. That is, cj ∗ ,k∗ ,`∗ (S) ≥ t,
and so
r
224 n1+a
1
32n
JKL · ĉj ∗ ,k∗ ,`∗ ≥ t −
· 1/2 · log(d|X|) log( ) log(
).
(4)

β
β
t
21

Hence, as j 0 , k 0 , `0 is defined on step 5 as the minimal j for which Inequality (4) holds, we get that
j0

2
≤ 2ropt . That is, the radius returned at the end of the execution is at most
j 0 ≤ j ∗ , and hence, |X|
10c · ropt . In addition, as j 0 (from step 5) satisfies Inequality (4), we get that the number of points
from S contained in the ball of radius 10c · ropt around ŷj 0 ,k0 ,`0 is at least
r
448 n1+a
1
32n
t−
· 1/2 · log(d|X|) log( ) log(
).

β
β
t

6

Application to k-means clustering

For a set of centers C ⊆ Rd and a point x ∈ Rd we denote dist(x, C) = minc∈C kx − ck2 . For a
finite set S ⊆ Rd , the sum of squared distances is defined as
X
cost(S, C) =
dist2 (x, C).
x∈S

If C = {c} we denote cost(S, c) = cost(S, {c}) for simplicity. For a weighted set S = {(x1 , α1 ), . . . , (x` , α` )},
the weighted cost is
X
cost(S, C) =
α · dist2 (x, C).
(x,α)∈S

Definition 6.1 (k-means). Let S be a (weighted or unweighted) finite set of points in Rd . A set
C ∗ of k centers (points) in Rd is called k-means of S if it minimizes cost(S, C) over every such set
C.
Definition 6.2 (Approximated k-means). Let S be a (weighted or unweighted) finite set of points
in Rd . A set C of k centers in Rd is a (γ, η)-approximation for the k-means of S if
cost(S, C) ≤ γ · cost(S, C ∗ ) + η,
where C ∗ is a k-means of S. When η = 0 we omit it and say that C is a γ-approximation for the
k-means of S.

6.1

k-means clustering – the centralized setting

As we mentioned in the introduction, Feldman et al. [15] showed that private algorithms for the
1-cluster problem translate to private algorithm for approximating the k-means of the data. Specifically, they showed the following theorem:
Theorem 6.3 ([15]). Fix a domain X d and a number k ≥ 1. Assume the existence of an (, δ)differentially private algorithm that, for every n ≥ nmin , solves the 1-cluster problem (X d , n, t= 3n
8k )
n
0
with parameters (∆, w) and error probability β, where ∆ ≤ 8k . Then, for every δ > 0, there exists
an (0 , 4k log(n)δ+δ 0 )-differentially private algorithm such that the following holds. Given a database
S ∈ (X d )n , with probability at least 1−O(β ·k ·log(n)), the algorithm returns a (γ, η)-approximation
to the k-means of S, where
r
1
2
d
0
γ = O(w · k),
η = O(nmin ) · diam(X ),
 = 8k log(n) log( 0 ) + 4k log(n)(e − 1).
δ
22

Using this transformation with the (private) algorithm of [21] for the 1-cluster problem, Feldman
et al. [15] obtained the following result.3
Theorem 6.4 ([15]). Fix β, , δ ≤ 1. There exists an (, δ)-differentially private algorithm that,
given a database S ∈ (X d )n , identifies with probability 1 − β a (γ,η)-approximation for the k-means
of S, where γ = O(k log(n)) and η = Õ 1 · d0.5 · k 1.5 · diam(X d ) .
Applying the transformation of Theorem 6.3 with our new algorithm for the 1-cluster problem,
we obtain the following result.

Theorem 6.5. Fix β, , δ ≤ 1. There exists an (, δ)-differentially private algorithm that, given a
database S ∈ (X d )n , identifies with probability 1 − β a (γ,
 η)-approximation for the k-means of S,
1
· d0.51 · k 1.51 · diam(X d ) .
where γ = O(k) and η = Õ 1.01

6.2

k-means clustering – the distributed setting

Towards obtaining our LDP algorithm for k-means, we start by presenting a non-private algorithm
that compute an approximation for the k-means (in fact, this is a family of algorithms, as the
algorithm can make arbitrary decisions throughout the execution). Afterwards we will show that
(a successful run of) our LDP algorithm can be identified with a possible execution of the nonprivate algorithm, showing that our private algorithm indeed computes an approximation for the
k-means. The non-private algorithm we use was first introduced by [13], and was modified by [15]
to obtain the transformation from 1-cluster to k-means in the centralized model.
Theorem 6.6 ([13, 15]). Every execution of algorithm Non-Private-k-Mean on a database S ∈
(X d )n with parameters ν, w, tmin , returns a set C of k centers such that
cost(S, C) ≤ O(w2 k) · cost(S, C ∗ ) + O (νk log(n) + tmin ) · diam(X d ),
where C ∗ are the optimal k-means of the input database S.
The analysis of algorithm Non-Private-k-Mean is almost identical to the analysis of [13, 15].
The only modification is that we allowed some “slackness” in the choices for Gi and αi , which will
be helpful for our LDP variant of the algorithm. The proof of Theorem 6.6 appears in the appendix
for completeness.
p
Lemma 6.7. LDP-k-Mean satisfies (0 , δ)-LDP for 0 = 24k log(n) ln(1/δ) + 12k log(n)(e − 1).

Lemma 6.7 follows directly from Theorem 2.9 (advanced composition). We now present the
utility analysis.

Lemma 6.8. Let S = (x1 , . . . , xn ) ∈ (X d )n be a p
database which is distributed across n players
(each holding one point in X d ), and denote ν = 16
n · log(8/β).

Let algorithm LDP-k-Mean be executed with an algorithm for the 1-cluster problem with parameters w, ∆, tmin , such that tmin ≥ 9ν + 6∆. Except with probability at most O(β · k log n), the
output C is s.t. there exists an execution of algorithm Non-Private-k-Mean on the database S with
parameters ν and w and t0min ≤ 8k
3 · tmin + ν that results in the same output C.
3

) and 2O(log
For simplicity, the Õ notation in theorems 6.4 and 6.5 hides factors of log( kn
βδ
on the additive error η.

23

∗

|X|)

from the statement

Algorithm Non-Private-k-Mean [13, 15]
Inputs: A set of n input points S ∈ (X d )n and an integer k ≥ 1.

Parameter: ν, w, tmin .

Output: A set C of k centers.
1. B ← ∅.
2. While |S| > tmin do (let i denote the index of the current iteration)
(a) ni ← |S|.

(b) Let ri,opt denote the radius of a smallest ball that contains
(c) Let ci ∈

Xd

3ni
8k

points from S.

and Gi ⊆ S be s.t.

i. Gi is contained within a ball of radius ri ≤ w · ri,opt around ci ,
ni
i
ii. 4k
≤ |Gi | ≤ 3n
8k .

(d) S ← S \ Gi .

(e) Arbitrarily choose |Gi | − ν ≤ αi ≤ |Gi |.
(f) B ← B ∪ {(ci , αi )}.

3. C ← an O(1)-approximation to the k-means of B.
4. Return C.

Combining Lemmas 6.7 and 6.8 with our LDP algorithm for the 1-cluster problem, yields the
following theorem.4
Theorem 6.9. Fix β, , δ ≤ 1. There exists an (, δ)-LDP algorithm that, for a (distributed)
database S ∈ (X d )n , identifies with probability 1 − β a (γ, η)-approximation for the k-means of S,
where γ = O(k) and η = Õ 1 · n0.67 · d1/3 · k 0.5 · diam(X d ) .

Proof of Lemma 6.8. We say that an application of step 4a is successful if it identifies a center ci
and a radius ri s.t. the ball of radius ri around ci contains at least (ti − ∆) points from Si , and
furthermore, ri ≤ w · r̂i,opt (where r̂i,opt is the radius of a smallest ball enclosing ti points from Si ).
Similarly, we say that the applications of steps 4b,4c,4e,4f are successful if they result in estimations
satisfying the stated requirements. As every such application succeeds with probability (1 − β),
and as there are at most 4k log n iterations, we have that all of these applications succeed together
with probability at least 1 − O(β · k log n). We proceed with the analysis assuming that this is true,
in which case we say that the entire execution is successful.
The proof proceeds by showing that for every successful execution of algorithm LDP-k-Mean
there exists an execution of algorithm Non-Private-k-Mean that results in the same output C.
Hence, successful executions of algorithm LDP-k-Mean enjoy the utility guarantees of algorithm
Non-Private-k-Mean.
Fix a successful execution of algorithm LDP-k-Mean, denoted as Exec1 (this amounts to fixing
all of the randomness throughout the computation). We analyze the set of points that are excluded
4

For simplicity, the Õ notation in Theorem 6.9 hides factors of log( kn|X|
) from the additive error η.
βδ

24

Algorithm LDP-k-Mean
Inputs: Privacy parameters , δ, failure probability β, and desired number of centers k.
Oracle: LR Oracle access to a database S ∈ (X d )n .

Tool used: An -LDPns algorithm for the 1-cluster problem with parameters w, ∆, tmin .
Output: A set C of k centers.
1. B ← ∅.

2. Define σ : X d → {0, 1} where σ(x) ≡ 0. We represent σ as a subset of X d , i.e., σ = ∅.
p
n1 · log(8/β).
3. Set i = 1. Denote n1 = n and n̂1 = n. Also denote ν = 16

% We assume that tmin ≥ 9ν + 6∆. Otherwise set tmin = 9ν + 6∆.

4. While (n̂i >

8k
3 tmin )

and (i ≤ 4k log n) do

(a) Use the algorithm for the 1-cluster problem with the predicate σ and parameter ti =
to obtain a center ci and a radius ri .

3n̂i
8k

% Let Si denote the data of all users holding an input element x s.t. σ(x) 6= 1. With probability (1 − β)

we have that the ball of radius ri around ci contains at least (ti − ∆) points from Si . Furthermore,

ri ≤ w · r̂i,opt , where r̂i,opt is the radius of a smallest ball enclosing ti points from Si .

(b) Let bi denote the number of users holding an input element x s.t. σ(x) 6= 1 and kx−ci k2 ≤
ri . Let b̂i be a noisy estimation (satisfying -LDP, e.g., using Theorem 5.3) for bi , such
that w.p. (1 − β) we have that bi − ν ≤ b̂i ≤ bi .

(c) Let hi : X d → {0, 1}
hash function s.t. for every x ∈ X d we have that
n be a random
o
Pr[hi (x) = 1] = min 1, 5n̂i , p̂i .
16kb̂i

e i denote the set of
% It suffices to use a λ-wise independent hash function for λ = ln(1/β). Let G

input points x ∈ Si such that kx − ci k2 ≤ ri and hi (x) = 1. Using a standard tail bound for sum
of λ-wise independent random variables (see, e.g., Lemma 5.6), with probability (1 − β) we have that
p
e i | ∈ p̂i · bi ± 8bi ln(1/β).
|G

(d) Let σ ← σ ∪ {x ∈ X d : kx − ci k2 ≤ ri and hi (x) = 1}.

% That is, roughly a p̂i fraction of the points in the found ball are excluded from the rest of the
computation.

(e) B ← B ∪ {(ci , α̂i )}, where α̂i = b̂i · p̂i − ν.

% Let αi denote the number of users that were excluded on the last step. With high probability we will

have that αi − 3ν ≤ α̂i ≤ αi

(f) Set i ← (i + 1), and let ni denote the number of users that are not excluded from the
computation, i.e., ni = |{x ∈ S : σ(x) 6= 1}|. Let n̂i be a noisy estimation (satisfying LDP, e.g., using Theorem 5.3) for ni , such that w.p. (1−β) we have that ni −ν ≤ n̂i ≤ ni .
5. C ← an O(1)-approximation to the k-means of B.
6. Return C.

25

e i (that is, G
e i is the set of input points x ∈ Si
on step 4d of iteration i of Exec1 , denoted as G
e i satisfies
such that kx − ci k2 ≤ ri and hi (x) = 1). We next show that, for every i, the set G
conditions (i),(ii) of step 2c of algorithm Non-Private-k-Mean. For condition (i), recall that as
e i is contained within a ball of radius w · r̂i,opt around ci , where r̂i,opt
step 4a succeeded, the set G
i
is the radius of a smallest ball enclosing ti = 3n̂
8k points from Si . Let ri,opt denote the radius of a
3ni
e i is
smallest ball enclosing 8k points from Si . As n̂i ≤ ni we have that r̂i,opt ≤ ri,opt , and hence, G
contained within a ball of radius w · ri,opt around ci , satisfying condition (i).
Let bi and b̂i be as in step 4b of the ith iteration of Exec1 (that is, bi denotes the number of
users holding an input element x s.t. σ(x) 6= 1 and kx − ci k2 ≤ ri , and b̂i is a noisy estimation
satisfying bi − ν ≤ b̂i ≤ bi ). As the execution is successful, we have that
bi ≥

3n̂i
3ni 3ν
−∆≥
−
− ∆.
8k
8k
8k

(5)

Assuming that tmin ≥ 9ν + 6∆, we have that
ni ≥ n̂i ≥

8k
tmin ≥ 24kν + 16k∆.
3

(6)

Plugging this into Inequality (5) we get that
5ni
+ ν.
(7)
16k
o
n
Recall that on step 4c we define p̂i , min 1, 5n̂i . By Inequality (7) and by the fact that
bi ≥

16kb̂i

ni − ν ≤ n̂i ≤ ni and bi − ν ≤ b̂i ≤ bi , we get that

5ni
ν
5ni
ν
− ≤ p̂i ≤
+ .
16kbi bi
16kbi bi
Finally, as step 4c succeeded, we have that
p
p
e i | ≤ p̂i · bi + 8bi ln(1/β),
p̂i · bi − 8bi ln(1/β) ≤ |G

(8)

(9)

which in combination with Inequalities (8) and (6) yields:
ni
e i | ≤ 3ni .
≤ |G
4k
8k

(10)

e i satisfying conditions (i) and (ii) of algorithm
So, every iteration of Exec1 identifies a set G
Non-Private-k-Mean, and excludes it from future iterations. In addition, by the fact that bi −ν b̂i ≤
e i | − 3ν ≤ α̂i ≤ |G
e i |, as
bi and by Inequality (9), we get that the weight α̂i (from step 4e) satisfies |G
is required on step 2e of algorithm Non-Private-k-Mean. This shows that Exec1 has a matching
execution of algorithm Non-Private-k-Mean such that the set of centers B is identical throughout
both of the executions. We next show that the stopping condition of both executions can also be
unified.
e i | ≥ ni . That
We have already established that in every iteration i of Exec1 we have that |G
4k
ni
is, in every iteration, at least 4k points are excluded from S, and hence, the number of iterations
is at most 4k log n. Thus, the loop of step 4 only halts when n̂i ≤ 8k
3 · tmin (and not because of the
26

condition on the number of iterations). As we next explain, this can be identified with the stopping
condition in Non-Private-k-Mean for a slightly different value t0min .
Consider the iteration i in which LDP-k-Mean halts. In that iteration we had that n̂i ≤ 8k
3 · tmin
8k
and that n̂i ≥ ni − ν. Hence, ni ≤ 3 · tmin + ν. In addition, as ni < ni−1 , there exists a number
t0min such that ni ≤ t0min < ni−1 and t0min ≤ 8k
3 · tmin + ν. The execution Exec1 would remain intact
had we replaced the condition of the while loop with (ni ≥ t0min ).
This shows that Exec1 has a matching execution of algorithm Non-Private-k-Mean, denoted
Exec2 , such that both executions have exactly the same number of iterations, and furthermore, the
set of centers B is identical in Exec1 and in Exec2 on every step of the executions. In particular,
this is the case at the end of the executions, which results in the same output C.

References
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor
in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 459–468,
2006.
[2] R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters.
arXiv.org, 2017.
[3] A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In APPROX-RANDOM, volume 8096 of Lecture Notes in Computer
Science, pages 363–378. Springer, 2013.
[4] M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In Proceedings of the 35th
Annual Symposium on Foundations of Computer Science, SFCS ’94, pages 276–287, Washington, DC, USA, 1994. IEEE Computer Society.
[5] M. Bun, K. Nissim, and U. Stemmer. Simultaneous private learning of multiple concepts. In
ITCS, pages 369–380. ACM, 2016.
[6] M. Bun, K. Nissim, U. Stemmer, and S. P. Vadhan. Differentially private release and learning
of threshold functions. In FOCS, pages 634–649, 2015.
[7] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy
via distributed noise generation. In S. Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture
Notes in Computer Science, pages 486–503. Springer, 2006.
[8] C. Dwork and J. Lei. Differential privacy and robust statistics. In M. Mitzenmacher, editor,
STOC, pages 371–380. ACM, 2009.
[9] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private
data analysis. In TCC, volume 3876 of Lecture Notes in Computer Science, pages 265–284.
Springer, 2006.
[10] C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In M. Mitzenmacher,
editor, STOC, pages 381–390. ACM, 2009.
27

[11] C. Dwork, G. N. Rothblum, and S. P. Vadhan. Boosting and differential privacy. In FOCS,
pages 51–60. IEEE Computer Society, 2010.
[12] U. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacypreserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer
and Communications Security, CCS ’14, pages 1054–1067, New York, NY, USA, 2014. ACM.
[13] D. Feldman, A. Fiat, M. Sharir, and D. Segev. Bi-criteria linear-time approximations for
generalized k-mean/median/center. In Proceedings of the Twenty-third Annual Symposium on
Computational Geometry, SCG ’07, pages 19–26, New York, NY, USA, 2007. ACM.
[14] D. Feldman, M. Schmidt, and C. Sohler. Turning Big data into tiny data: Constant-size
coresets for ¡italic¿k¡/italic¿-means, PCA and projective clustering, pages 1434–1453.
[15] D. Feldman, C. Xiang, R. Zhu, and D. Rus. Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In Proceedings of the 16th
ACM/IEEE International Conference on Information Processing in Sensor Networks, IPSN
’17, pages 3–15, New York, NY, USA, 2017. ACM.
[16] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American Statistical Association, 58(301):13–30, 1963.
[17] P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse
of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of
Computing, STOC ’98, pages 604–613, New York, NY, USA, 1998. ACM.
[18] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we
learn privately? SIAM J. Comput., 40(3):793–826, 2011.
[19] F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94–103.
IEEE Computer Society, 2007.
[20] K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data
analysis. In STOC, pages 75–84. ACM, 2007.
[21] K. Nissim, U. Stemmer, and S. P. Vadhan. Locating a small cluster privately. In Proceedings
of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems,
PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 413–427, 2016.
[22] V. Shenmaier. The problem of a minimal ball enclosing k points. Journal of Applied and
Industrial Mathematics, 7(3):444–448, 2013.
[23] A. Thakurta and A. Smith. Differentially private feature selection via stability arguments, and
the robustness of the lasso. In S. Shalev-Shwartz and I. Steinwart, editors, COLT, volume 30
of JMLR Proceedings, pages 819–850. JMLR.org, 2013.
[24] A. Thakurta, A. Vyrros, U. Vaishampayan, G. Kapoor, J. Freudiger, V. Sridhar, and D. Davidson. Learning new words, Mar. 14 2017. US Patent 9,594,741.
[25] S. Vadhan. The Complexity of Differential Privacy. 2016.
[26] P. Vazirani and P. Rao. Lecture notes in combinatorial algorithms and data structures.
28

A

Missing proofs

Lemma A.1. Algorithm LSH-GoodCenter preserves (2, 2δ)-differential privacy.
Proof. Algorithm LSH-GoodCenter interacts with its input database on steps 2, 4a, 5, 6, and 7.
Step 2 invokes the algorithm from Theorem 2.6 which is ( 4 , 4δ )-differentially private, to obtain
L ⊂ U . For every u ∈ L we make (in Step 4a) d applications of the algorithm from Theorem 2.6
that interact only with Su (and no other points in S). By the advanced composition (Theorem 2.9)
this preserves ( 4 , 4δ )-differential privacy w.r.t. Su . As the sets Su and Su0 are mutually disjoint,
Step 4a preserves ( 2 , 2δ )-differential privacy overall. Similarly, Step 5 interacts with the data for
at most n times (applying Gaussian mechanism). As each application of the Gaussian mechanism
is ( 4 , 4δ )-differentially private, we get that Step 5 preserves ( 2 , 2δ )-differential privacy. Steps 6,
and 7 initialize and use Algorithm AboveThreshold, which is ( 4 , 0)-differentially private. Overall,
GoodCenter is (2, 2δ)-differentially private by application of simple composition (Theorem 2.8).
Lemma A.2. Suppose X1 , . . . , Xn are independent samples from Lap( 1 ). That is, every Xi has
probability density function f (x) = 2 exp(−|x|). Let X = X1 + · · · + Xn . For every t ≥ 0 it holds
that


·t
√
Pr[|X| ≥ t] ≤ 6 exp −
.
2n
Moreover, for every 0 ≤ t < 2n/ we have that
 2 2
 ·t
Pr[|X| ≥ t] ≤ 2 exp −
.
4n
The proof of Lemma A.2 is standard. We include a proof here for completeness as we are unable
to find an appropriate reference.
Proof of Lemma A.2. By symmetry, it suffices to analyze Pr[X ≥ t]. Indeed, for every c > 0 we
have that


Pr[X ≥ t] = Pr[cX ≥ ct] = Pr ecX ≥ ect



n
≤ e−ct · E ecX = e−ct · E ecX1
.
(11)

Furthermore,



cX1

E e



=
=
=
=


Z ∞ 
 cX1

1
Pr X1 ≥ ln z dz
Pr e
≥ z dz =
c
0
0


Z 1 
Z ∞ 
1
1
Pr X1 ≥ ln z dz +
Pr X1 ≥ ln z dz
c
c
0
1





Z 1
Z ∞
 · ln z
1
 · ln z
1
1 − exp
dz +
exp −
dz
2
c
2
c
1
0
Z
Z
1 1 /c
1 ∞ −/c
1
1−
z dz +
z
dz =
,
2 0
2 1
1 − (c/)2
Z

∞

where the last equality follows by asserting that /c > 1 and solving the integrals. Plugging into
Equality (11) we get that

n
c 2
Pr[X ≥ t] ≤ e−ct · E ecX1
= e−ct · (1 − (c/)2 )−n ≤ e−ct · e2n·(  ) ,
29

where the last inequality holds whenever /c ≥ 1.2. The lemma now follows by choosing c =
√
(in which case /c ≥ 2 for every t ≤ 2n/) or by choosing c = / 2n.

B
C∗
Si
Si∗

2 t
4n

Proof of Theorem 6.6 [13, 15]
A set of k centers that minimizes cost(S, C) over the original database S over every such C.
The database S during the ith iteration.
The 3|Si |/4 points x ∈ Si with smallest value dist(x, C ∗ ).
Table 2: Notations for the analysis of algorithm Non-Private-k-Mean

Lemma B.1. In every iteration i we have that cost(Gi , ci ) ≤ w2 · cost(Si∗ , C ∗ )
|S ∗ |

Proof. By the pigeonhole principle there must be a center x ∈ C ∗ that serves m ≥ ki points in
∗ have x as their closest center in C ∗ . At least half
Si∗ , i.e., at least 1/k fraction of the points in Siq
2cost(Si∗ ,C ∗ )
|S ∗ |
of them (i.e., 2ki ) have distance at most r̃ =
to x, as otherwise we would get that
m
cost(Si∗ , C ∗ ) >

|Si∗ |
2k

·

2cost(Si∗ ,C ∗ )
m

≥ cost(Si∗ , C ∗ ).

We conclude that there is a ball of radius r̃ that contains at least m/2 ≥
from Si . By definition of ri,opt , we have that
r
2cost(Si∗ , C ∗ )
ri,opt ≤ r̃ =
.
m
That is,

|Si∗ |
2k

=

3|Si |
8k

points

m 2
r
≤ cost(Si∗ , C ∗ ).
2 i,opt

Hence,
cost(Gi , ci ) ≤ |Gi |·(w·ri,opt )2 ≤

3|Si |
|S ∗
m 2
·(w·ri,opt )2 = i ·(w·ri,opt )2 ≤ w2 · ri,opt
≤ w2 ·cost(Si∗ , C ∗ ),
8k
2k
2

where the first and second inequalities follow from the conditions on Gi on step 2(c) of the algorithm.
Lemma B.2.

|B|
X
i=1

cost(Gi , ci ) ≤ O(w2 · k) · cost(S, C ∗ ).

Proof. We order the points in S by S = (x1 , x2 , . . . , xn ), such that dist(xj1 , C ∗ ) ≤ dist(xj2 , C ∗ ) for
every j1 < j2 , where ties are broken arbitrarily. Let
Ui = {x1 , x2 , . . . , xn−|Si | },

Vi = {xn−|Si |+1 , . . . , xn−|Si |+|Si∗ | }.

30

Clearly, |Ui ∪ Vi | = |Ui | + |Vi | (as the sets Ui and Vi are disjoint). Moreover, as there are at most
(n − |Si |) elements outside of Si , we have that
|(Ui ∪ Vi ) ∩ Si | ≥ |Ui | + |Vi | − (n − |Si |)
= |Vi | = |Si∗ |.

So, the sets (Ui ∪ Vi ) and Si have at least |Si∗ | elements in common. As Si∗ contains the values
x ∈ Si with smallest distance dist(x, C ∗ ), and as (Ui ∪ Vi ) contain all such elements from S, we get
that these common elements contain Si∗ , that is, Si∗ ⊆ (Ui ∪ Vi ).
The set Vi contains the |Si∗ | points x ∈ (Ui ∪ Vi ) with the largest values dist(x, C ∗ ). Hence,
cost(Si∗ , C ∗ ) ≤ cost(Vi , C ∗ ). Combining this with Lemma B.1, and summing over every i we get
|B|
X
i=1

cost(Gi , ci ) ≤

|B|
X
i=1

w2 · cost(Vi , C ∗ ).

We now want to relate the right hand side of the above inequality to the input points S.
Specifically, we want to show that every point x ∈ S is included in at most O(k) sets Vi . To that
end, observe that:
1. The index of the last point in Vi is n − |Si | + |Si∗ | = n −

|Si |
4 .

2. The index of the first point in Vi+12k is n − |Si+12k | + 1 ≥ n − |Si | · (1 −

1 6k
4k )

>n−

|Si |
4 .

Hence, every point appears in O(k) sets in the sequence V1 , V2 , . . . . Hence,
|B|
X
i=1

cost(Gi , ci ) ≤

|B|
X
i=1

w2 · cost(Vi , C ∗ ) ≤ O(w2 · k) · cost(S, C ∗ ).

Lemma B.3.

√
√ 
cost(S, C) ≤ O(w2 k) · cost(S, C ∗ ) + O tmin · d + νk log(n) d .
Proof. Recall that every iteration defines αi as |Gi | − ν ≤ αi ≤ |Gi |. For every i, let Ĝi ⊆ Gi denote
an arbitrary subset of size αi . Let Ŝe = ∪Ĝi .
We use the weak triangle inequality [14] stating that for every x, y ∈ Rd and a closed set C ⊆ Rd
we have
12kx − yk22 λ
|dist2 (x, C) − dist2 (y, C)| ≤
+ dist2 (x, C).
λ
2

31

In our case, by letting x0 denote the associated ci to x ∈ Ŝe when x is deleted, and using λ = 1/2,
this implies
|cost(Ŝe , C) − cost(B, C)| =
≤

X

x∈Ŝe

dist2 (x, C) −

X

dist2 (x0 , C)

x∈Ŝe


X  12kx − x0 k2 λ
2
2
+ dist (x, C)
λ
2

x∈Ŝe

= 24

|B|
X
i=1

1
cost(Ĝi , ci ) + cost(Ŝe , C).
4

(12)

Hence,
|B|

X
3cost(Ŝe , C)
≤ cost(B, C) + 24
cost(Ĝi , ci ).
4
i=1

By the fact that C is an O(1)-approximation to the k-means of B, we get
cost(B, C) ≤ O(1) · cost(B, C ∗ ).
Similarly to (12),
∗

∗

|cost(Ŝe , C ) − cost(B, C )| ≤ 24

|B|
X
i=1

1
cost(Ĝi , ci ) + cost(Ŝe , C ∗ ).
4

Hence,
|B|

X
5
cost(B, C ) ≤ cost(Ŝe , C ∗ ) + 24
cost(Ĝi , ci ).
4
∗

i=1

So,



cost(Ŝe , C) = O cost(B, C) +


|B|
X
i=1

= O cost(B, C ∗ ) +


= O cost(B, C ∗ ) +




cost(Ĝi , ci )

|B|
X
i=1

|B|
X
i=1



cost(Ĝi , ci )


cost(Gi , ci )


= O cost(Ŝe , C ∗ ) + w2 k · cost(S, C ∗ )
= O(w2 k) · cost(S, C ∗ ).

Notice that cost(S, C) = cost(Ŝe , C) + cost(S \ Ŝe , C), where S \ Ŝe ≤ ν · |B| + tmin . As there
are at most O(k · log(n)) iterations (i.e., |B| = O(k · log(n))), we have that
32

cost(S, C) = cost(Ŝe , C) + cost(S \ Ŝe , C)

≤ O(w2 k) · cost(S, C ∗ ) + O (νk log(n) + tmin ) · diam(X d ).

33

