# Differential Privacy for Clustering Under Continual Observation

Max Dupré la Tour, Monika Henzinger, David Saulpic22footnotemark: 2 McGill
UniversityIST Austria

###### Abstract

We consider the problem of clustering privately a dataset in $\mathbb{R}^{d}$
that undergoes insertion and deletion of points. Specifically, we give an
$\varepsilon$-differentially private clustering mechanism for the $k$-means
objective under continual observation. This is the first approximation
algorithm for that problem with an additive error that depends only
logarithmically in the number $T$ of updates. The multiplicative error is
almost the same as non privately. To do so we show how to perform dimension
reduction under continual observation and combine it with a differentially
private greedy approximation algorithm for $k$-means.

##  1 Introduction

The massive, continuous and automatic collection of personal data of public as
well as private organisations has raised privacy concerns, in legal terms
[Uni18] but also in terms of citizens’ demands [oNYT20, Dem21]. To answer
those, formal privacy standards for algorithms were defined and developed: the
most prominent one is Differential Privacy [DMNS06]. It allows to have a
formal definition of _privacy_ , and therefore to give algorithms with
provable privacy guarantees. Differentially private algorithms are now
deployed quite massively. For instance, the U.S. Census Bureau uses it to
release information from a private Census [Abo18], Apple collects data from
its phone’s users with an algorithm that respects differential privacy
[20116a, 20116b], and Google develops an extensive library of private
algorithms ready to be used [Gue19]. Differential privacy ensures that those
algorithms “behave roughly the same way” on two databases that differ by a
single element. The idea behind it is that one cannot infer from the result
whether a specific element is present in the database, i.e. protecting against
membership-inference attacks.

However, this guarantee is only valid for a _static_ database. As real-life
data often evolves over time – as in Apple’s example, where personal data is
collected and transferred every day – a definition of privacy that accounts
for such changes is necessary. To address that issue, an extension of
differential privacy was proposed by Dwork, Naor, Pitassi, and Rothblum
[DNPR10]: an algorithm that respects privacy _under continual observation_ is
given a sequence of updates to its data set, one per time step, and computes
an output at each time step, such that differential privacy is preserved for
all time steps. A sequence of publications has studied maintaining a mere
counter under that model [DNPR10, CSS11, JRSS21, GKMN22, HUU23, FHU22], and
other basic tools such as frequency estimation [EMM+23], histograms [CR22],
heavy hitters [LT23], and various graph properties [FHO21].

In this article, we consider a more complex problem, namely clustering. This
is one of the most central problems in unsupervised machine learning, with
many applications ranging from community detection to duplicate detection. One
example of an application is to report clusters of people infected by a
disease, based on the web search in geographic regions. The input data for
that application is inherently evolving – new web searches are continuously
performed – and highly sensitive. The question we ask is therefore:

Is it possible to maintain a provably good clustering that is private under
continual observation?

###  1.1 Our Results.

In order to answer this question, we need to formalize what a good clustering
means. For that, we will focus on one of the most prominent clustering
objectives, namely the $k$-means problem. In this problem, the input data are
points in a metric space, and the goal is to find $k$ points from the space
(the _centers_) in order to minimize the cost, namely the sum of the squared
distance of each point to its closest center. We focus more precisely on the
case where the data comes from a high-dimensional Euclidean space
$\mathbb{R}^{d}$, arguably the main use case for $k$-means clustering.

The $k$-means problem has been heavily studied and is very well understood in
the non-private setting (see e.g. Cohen-Addad et al. [CAEMN22] for the static
case, Henzinger and Kale [HK20] for dynamic, and references therein), as well
as with (static) differential privacy constraint [SK18, CEL+22]. In the static
differentially private setting, two types of results emerge: those with
optimal _multiplicative_ error [GKM20, CGKM21, Ngu20] (and large additive
error), and those with optimal _additive_ error (and large multiplicative one)
[CNX21].

However, nothing is known about maintaining a cluster for a sensitive dataset
that is evolving over time. We initiate the study of differentially private
clustering under continual observation and present the first approximation
algorithm for $k$-means clustering that is differentially private under
continual observation. More specifically, our algorithm has the same optimal
multiplicative error, as [GKM20] for the static case and an additive error
that depends only polylogarithmically on the length of the update sequence.

More formally, the setting is as follows: the algorithm is given a _diameter_
$\Lambda\in\mathbb{R}^{+}$, and a stream of input data of length $T$, i.e., at
each time step, a point from the $d$-dimensional ball $B(0,\Lambda)$ (centered
in the origin with radius $\Lambda$) is either added or removed from the
dataset. After each update, our algorithm needs to output a solution that
minimizes the $k$-means cost in the metric space $(\mathbb{R}^{d},\ell_{2})$.
We denote the optimal cost at time $t$ by $\textsc{opt}_{t}$, $T$ the total
number of time steps and $n$ the maximal size of the dataset. For the
definition of privacy that we use, namely _$\epsilon$ \- differential privacy
($\varepsilon$-DP)_, we say that two input streams are _neighboring_ if they
differ in at most one time step, i.e., in a single input point. We give more
details in Section 2. We show the following result.

######  Theorem 1.

For any $\alpha>0$, there exists an algorithm that is
$\varepsilon$-differentially private under continual observation and computes,
with probability at least $0.99$ for all time steps $t$ simultaneously, a
solution to $k$-means and its cost in $\mathbb{R}^{d}$ with cost at most

$(1+\alpha)w^{*}\cdot\textsc{opt}_{t}+k^{O_{\alpha}(1)}d^{2}\log(n)^{4}\cdot\log(T)^{3+0.001}\cdot\Lambda^{2}/{\varepsilon},$

where $w^{*}$ is the best approximation ratio for non-private, static
$k$-means clustering.

For the slightly weaker $(\varepsilon,\delta)$-differential privacy, the
additive error decreases to
$k^{O(1)}d^{2}\log(1/\delta)\cdot\log(n)^{4}\log(T)^{2+0.001}\cdot\Lambda^{2}/\varepsilon$.
Our result is actually even stronger: it computes a solution not only to
$k$-means, but to all $k^{\prime}$-means for $k^{\prime}\leq k$, with the same
multiplicative and additive error guarantee as above. This allows, for
instance, to use the standard elbow method111This is a heuristic to compute
the “right” value of $k$, as follows: the curve of the $k$-means cost as a
function of $k$ has an inflection point, which is defined as “right” value of
$k$. to select the “best” value for $k$, without any further loss of privacy.
Note that the algorithm does not need to know $n$ in advance, nor the total
number of time steps.

To understand our additive error term, we note that, even in the static
setting, any algorithm must suffer from an additive error
$\Omega\left(\frac{kd}{\varepsilon}\cdot\Lambda^{2}\right)$ [GLM+10, CNX21].
Under continual observation any differentially-private $k$-means algorithm
with multiplicative error $(1+\alpha)$ (for some small $\alpha>0$) can be used
to solve the differentially-private counting problem and, thus, the lower
bound of $\Omega(\log(T))$ for the additive error of continual counting
implies an $\Omega(\log(T))$ lower bound for the additive error of $k$-means.

Our algorithm uses a differentially-private counting algorithm under continual
observation in a black-box manner, which contributes an $\Omega(\log(T)^{2})$
term to the additive error. This is slightly increases by a
$\log(T)^{1/2+0.001}$ factor in our algorithm. Note, that any improvement in
the additive error of $\epsilon$-DP continual counting would immediately
improve the additive error of our algorithm.

#### Extension to $k$-median.

Our techniques partially extend to $k$-median, for which the cost function is
the sum of distances to the centers (instead of the distances squared). We
show the following result:

######  Theorem 2.

For any $\alpha>0$, there exists an algorithm that is
$\varepsilon$-differentially private under continual observation and computes,
for all time steps $t$ individually, a solution to $k$-median and its cost in
$\mathbb{R}^{d}$ with cost at most

$(2+\alpha)w^{*}\cdot\textsc{opt}_{t}+k^{O_{\alpha}(1)}d^{3}\log(n)^{4}\cdot\log(T)^{3/2}\cdot\Lambda/{\varepsilon},$

with probability at least $0.99$, where $w^{*}$ is the best approximation
ratio for non-private, static $k$-median clustering.

The two differences are the approximation factor, which is $2w^{*}$ instead of
$w^{*}$ in the case of $k$-means, and the success probability, which is $0.99$
at each time step individually instead of all time steps simultaneously. In
the following we present the result for $k$-means and explain at the end how
to deal with the $k$-median cost function.

###  1.2 Previous Works and Their Limits.

The problem of $k$-median and $k$-means clustering with points in
$\mathbb{R}^{d}$ under (static) differential privacy has been almost closed in
the last few years. From the lower-bound perspective, any algorithm must
suffer a multiplicative factor $\Omega(1)$, as in the non-private case. Table
1 summarizes the state-of-the-art results for upper bounds – stated for
$k$-means, with the same picture for $k$-median. We stress that our algorithm
has the same multiplicative guarantee as the static algorithms of Ghazi et al.
[GKM20] and Nguyen [Ngu20]. Minimizing the additive term while maintaining a
constant multiplicative approximation is an interesting open challenge, both
in the static and the dynamic setting.

Table 1: Previous work on (static) differentially-private $k$-means. (*) indicates that the algorithm is $(\varepsilon,\delta)$-differentially-private. $w^{*}$ is the best approximation ratio for non-private $k$-means clustering.  | Multiplicative error | Additive error
---|---|---
Balcan et al. [BDL+17] | $O\left(\log(n)^{3}\right)$ | $(k^{2}+d)\cdot\operatorname{poly}\log(n)\cdot\Lambda^{2}/\varepsilon$
Stemmer and Kaplan [SK18] (*) | $O(1)$ | $O(k^{1.01}d^{0.51}+k^{1.5})\cdot\Lambda^{2}/\varepsilon$
Ghazi et al. [GKM20], Nguyen [Ngu20] | $(1+\alpha)w^{*}$ | $(kd+k^{O(1)})\log(n)^{O(1)}\cdot\Lambda^{2}/\varepsilon$
Chaturvedi et al. [CNX21] (*) | $O(1)$ | $\tilde{O}(k\sqrt{d})\cdot\Lambda^{2}/\varepsilon$

However, those private algorithms for $k$-means fall short of being accurate
under continual observation for two reasons. We highlight them before
presenting our algorithm that is designed to work around those challenges.

(1) The first reason is that they all rely on dimension reduction. In the
static setting, this is performed as follows: first, project all data points
onto a low dimensional subspace with dimension $\hat{d}$. Then, solve
$k$-means privately on this low dimensional subspace, where an exponential
dependency in $\hat{d}$ is affordable, and compute the clusters of the
solution. Finally, for each cluster, compute a private mean in the original
$\mathbb{R}^{d}$ space. By sequential composition, this provides a private
algorithm. Applying this method blindly under continual observation would,
however, yield an additive error of $\Omega(T)$ as the number of sequential
compositions required for projecting back would be $\Omega(T)$ – instead of a
single one in the static case. One needs, thus, to provide a new way of
projecting back to the original $\mathbb{R}^{d}$ space tailored to continual
observation.

(2) The second hurdle those algorithms face is that, even in low dimensional
space, they rely on machinery such as the exponential mechanism that is hard
to use under continual observation. For instance, it is not known how to use
the exponential mechanism in that setting, which is crucially used in
Chaturvedi et al. [CNX21]. All other $\varepsilon$-dp static $k$-means
algorithms partition the data set and compute a histogram for the different
sets (as in [SK18] and [GKM20]).

Under continual observation, it is known how to maintain a histogram
maintaining $m$ counters 222A histogram over $\ell$ sets maintains $\ell$
counters that are initially 0 such that at each time step each counter can
increase or decrease by at most 1. with additive error $O(m\cdot\log(T)^{2})$
[CSS11, FHO21, CR22, HSS23] and, thus, our idea is to reduce maintaining a
differentially private clustering to maintaining such histograms. The main
challenge is to find a suitable partition for which to maintain the histogram.
To avoid any potential privacy-leak due to dynamically changing partitions, we
want to make the partition independent of the data set. Therefore, we do not
use a partition of the data set, but instead, partition the metric space
$\mathbb{R}^{d}$ into fixed subregions and maintain one counter per subregion
in the histogram.

Note that the static $\varepsilon$-DP $k$-median algorithm from Cohen-Addad et
al. [CEL+22] also proceeds that way: it requires only counts for sets that are
fixed regardless of the input (those are cells of a quadtree). However, its
multiplicative approximation guarantee is
$O(\operatorname{poly}(d)\cdot\log(n))$: it is, thus, heavily reliant on
dimension reduction to reduce the dependence of the additive error on $d$, and
has additionally an unfortunate multiplicative dependency in $\log(n)$.

Parallel work. Epasto, Mukherjee, and Zhong [EMZ23] released very recently a
similar work on private $k$-means under dynamic updates. Their results are
incomparable: their main focus was on designing an algorithm using low memory,
which they manage to do in _insertion-only_ streams. For those streams, they
achieve essentially the same approximation guarantees as ours in their
Corollary 14. They can also have a smaller additive error, to the price of a
large constant multiplicative error, see their Corollary 13.

### Our Techniques.

We focus from now on the ”pure” $\varepsilon$-differential privacy setting,
and defer the results and discussion of $(\varepsilon,\delta)$-DP to Appendix
G.

In this work, we present an algorithm designed to overcome those difficulties
under continual observation. First, to address (2), we simplify a non-private
$O(1)$-approximation algorithm from Mettu and Plaxton [MP00] so that it works
with a fixed, hierarchical decomposition of $\mathbb{R}^{d}$ and merely
requires counting how many input points are in each cell of the decomposition.
Combining this with any continual, $\varepsilon$-DP histogram algorithm allows
to solve $k^{\prime}$-means under continual observation, for any $k^{\prime}$,
however with additive error exponential in $d$ and $O(1)$-multiplicative
error. The resulting set of centers has been computed in a DP manner and thus,
for some large enough value of $k^{\prime}$, we can treat it as a _coreset_ ,
i.e. a set of points that “represents” the input points with regards to
$k$-means cost (see [Ngu20]). We then run the best-known non-DP $k$-means
algorithm on this coreset at every time step. This results in the following
theorem.

######  Theorem 3.

Consider an input stream of additions and deletions of points from
$B(0,\Lambda)$ in the metric space $(\mathbb{R}^{d},\ell_{2})$. For any
$\alpha>0$, there exists an algorithm that is $\varepsilon$-differentially
private under continual observation and computes, for each time step $t$, a
solution to $k$-means that has cost at most

$(1+\alpha)w^{*}\cdot\textsc{opt}_{t}+\frac{k2^{O(d)}\log(n)^{4}}{\varepsilon}\cdot\log(T)^{3/2}\cdot\Lambda^{2},$

with probability $0.99$, where $w^{*}$ is the best approximation ratio for
non-private and static $k$-means.

To show a similar result without an exponential dependency in $d$, we overcome
Challenge (1) _Showing how to make dimension reduction work under continual
observation with small additive error is the main contribution of our work._

This works as follows: we use standard dimension reduction (which conveniently
is independent of the input data), run the above algorithm in the resulting
low-dimensional metric space, and show how to lift a low-dimensional
clustering back into the original space. The centers in the low-dimensional
space define a clustering, and we use the means of all such clusters in the
original $\mathbb{R}^{d}$ as our solution. To compute these means in a DP-
manner, we use the counters for each cell from the $\varepsilon$-DP histogram.
As the additive error in each mean computation for each high-dimensional
center is the sum of the additive error of the counters of all cells of its
cluster, we need to make sure that each cluster consists of only $k^{O(1)}$
cells of our decomposition. We had carefully designed our decomposition so
that this is true. Additionally, to make this work, we need to keep multiple
counters per cell, namely the number of points as well as the sum of the
points by coordinate.

Unfortunately, the resulting algorithm is only correct with $O(1)$ probability
_per time step_ and want to get a constant success probability _over all time
steps_ . The standard technique of simply decreasing the failure probability
in each time step does not work as the additive error would be polynomial in
$T$. Thus, instead we boost the success probability of each time step by
running $\log(T)$ many low-dimensional clustering algorithms, leading only to
an increase of the additive error by $\log(T)^{1/2}$. However, to then pick
the best solution out of them is not easy as it requires to evaluate the cost
of each solution in a DP-manner. We show how to do this based on additional
counters we maintain in our histogram.

### Organization of the paper

In the main body of the paper, we focus on the problem of $k$-means under
$\varepsilon$-DP. We first present our basis algorithm, that produces a good
approximation given only counts on some regions of the dataset. Then, we show
how to use it privately under continual observation, with an additive error
scaling with $2^{d}$, and show Theorem 3. We show next how to use dimension
reduction to reduce the additive error, and how to evaluate the cost of a
solution in order to boost the probability of success and show Theorem 1. We
then briefly mention how to extend the result to $k$-median, and show theorem
2. Most of the proof are presented in the Appendix, as well as the discussion
on $(\varepsilon,\delta)$-differential privacy.

##  2 Preliminaries

In a metric space $(X,\operatorname{dist})$, we define the following _cost
function_. For any $P,\mathcal{S}\subset X$,
$\operatorname{cost}(P,\mathcal{S}):=\sum_{p\in
P}\operatorname{dist}(p,\mathcal{S})^{2}$. With a slight abuse of notation,
when $P=\\{p\\}$ or $\mathcal{S}=\\{s\\}$ is a singleton, we will write
$\operatorname{cost}(p,\mathcal{S})$ instead of
$\operatorname{cost}(\\{p\\},\mathcal{S})$, and $\operatorname{cost}(P,s)$
instead of $\operatorname{cost}(P,\\{s\\})$.

The $k$-means problem in $(X,\operatorname{dist})$ is the following. We are
given a set $P\subseteq X$ of points and a positive integer $k$. The goal is
to compute a set of $k$ points $\mathcal{S}$ that minimizes
$\operatorname{cost}(P,\mathcal{S})$. We call any set of $k$ points from $X$ a
_solution_. The points in a solution are called _centers_.

An algorithm is a $(\alpha,\beta)$-approximation to the $k$-means problem if
its cost is at most $\alpha\textsc{opt}+\beta$, where opt is the optimal
$k$-means cost on the data set. As mentioned in the introduction, in continual
observation, the optimal solution at time $t$ is noted $\textsc{opt}_{t}$, $n$
is the maximum size of the data set across time, and $T$ is the total number
of time steps.

#### Assumption.

As usual in studying clustering under differential privacy, we will assume all
points come from the ball
$B_{d}(0,\Lambda)=\left\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq\Lambda\right\\}$.
Without such an assumption, the lower bound of [CNX21] shows that one cannot
compute a solution with bounded additive error. For simplicity, we will assume
that $\Lambda=1$ in all our proofs. This is without loss of generality: if the
dataset is instead in $B_{d}(0,\Lambda)$, then rescaling merely yields an
additive error multiplied by $\Lambda^{2}$ for $k$-means.

###  2.1 Net Decomposition

A $\delta$-net of $X$ is a subset $Z\subset X$ satisfying the two following
properties:

  1. 1.

_Packing:_ for all distinct $z,z^{\prime}\in Z$ we have
$\operatorname{dist}(z,z^{\prime})>\delta$

  2. 2.

_Covering:_ for all $x\in X$ we have $\operatorname{dist}(x,Z)\leq\delta$

It is well known that the unit ball in $\mathbb{R}^{d}$ has a $\delta$-net for
all $\delta>0$ [GKL03]. For any level
$i\in\left\\{1,\dots,\lceil\log(n)\rceil\right\\}$, let $Z_{i}$ be a
$2^{-(i+1)}$-net of $B(0,1)$. An element of $Z_{i}$ is a _net point_ of
_level_ $i$. In order to uniquely define the level of a net point, we make the
assumption that all $Z_{i}$ are disjoint. We use the notation
$\operatorname{level}(z)$ to denote the level of a net point $z$. For any net
point $z\in Z_{i}$ we define the following notions:

  * •

For any $l>0$, the $l$-neighborhood of $z$ is $N^{l}(z):=B(v,l2^{-i})$. The
covering property of nets can be restated as follows: for any level $i$ and
any point $x$, there exists $z\in Z_{i}$ such that $x\in N^{0.5}(z)$.

  * •

The _children_ of $z$ are the net points of level $i+1$ in $N^{4}(z)$. We
stress the fact that the children relationship cannot be represented as a
tree: each net point can be the child of many net points from one level
higher.

  * •

Given an input set $P$, the value of $z$ is
$\operatorname{Value}(z):=2^{-2i}|N^{1}(z)\cap P|$.

From a classical property of nets, we can deduce the next lemma proven in the
appendix A

######  Lemma 4.

The two following properties hold:

  * •

For every $i$, $|Z_{i}|\leq 2^{id+3}$.

  * •

For every point $x$ and $i$, $x$ is in the $1$-neighborhood of at most
$2^{2d}$ net points of $Z_{i}$.

###  2.2 Differential Privacy

We start with the formal definition of differential privacy under continual
observation. Let $\sigma$ be a stream of updates to a dataset: $\sigma(t)$
corresponds to either the addition of a new item to the dataset, the removal
of one, or a “no operation” time (where nothing happens to the dataset). Two
streams are neighboring if they differ by the addition of a single item at a
single time step (and possibly its subsequent removal). This is the so-called
_event-level_ privacy [DNPR10]. Let $\mathcal{M}$ be a randomized mechanism
that associates a stream $\sigma$ to an output
$\mathcal{M}(\sigma)\in\mathcal{X}$. For an $\varepsilon\in\mathbb{R}^{+}$,
$\mathcal{M}$ is $\varepsilon$-differentially private under continual
observation if, for any pair of neighboring streams $\sigma,\sigma^{\prime}$,
and any possible set of outcomes $\mathcal{S}\subseteq\mathcal{X}$, it holds
that

$\Pr\left[\mathcal{M}(\sigma)\in\mathcal{S}\right]\leq\exp(\varepsilon)\Pr\left[\mathcal{M}(\sigma^{\prime})\in\mathcal{S}\right].$

The main tool we will use for the design of private algorithm is a histogram
mechanism, that allows to count how many points are in sets. Due to space
constraint, we define formally this mechanism in appendix A. Essentially,
given a stream of update and ground sets $G_{1},...,G_{m}$, such that each
input element is part of at most $b$ sets, one can maintain the count of how
many elements are in each $G_{i}$, privately under continual observation, with
additive error
$O(b)\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(m/\beta)\right)$.

We use crucially this histogram construction to prove the following lemma. It
allows to count over clusters of solutions to $k$-means that evolve over time.

######  Lemma 5.

Let $1>\alpha>0$, and $\sigma$ be a stream of addition or deletion of points
from a ground set $G\subseteq\mathbb{R}^{d}$ of length $T$, and let $X_{t}$ be
the set of points at time $t$ with $1\leq t\leq T$. Let $f:G\rightarrow[-1,1]$
be a function, and for each time $t$ let $\mathcal{C}^{t}$ be a set of $k$
centers. There is an $\varepsilon$-DP algorithm that releases a value
$\Sigma_{i}^{t}$ for each $i=1,...,k$ and time $t$, with the following
guarantee:

  * •

for any time $t$, there is a partition $C^{t}_{1},...,C^{t}_{k}$ of $X_{t}$
such that assigning points of $C^{i}_{t}$ to the center $\mathcal{C}^{t}_{i}$
yields a $k$-means solution with cost
$(1+\alpha)\operatorname{cost}(X_{t},\mathcal{C}^{t})+O(1/\alpha)$,

  * •

for any time $t$, it holds with probability $1-\beta$ such that
$\left|\Sigma_{i}^{t}-\sum_{p\in C^{t}_{i}}f(p)\right|\leq
k\cdot\alpha^{-O(d)}\cdot\log(n)^{3}\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(1/\beta)\right)$.

In this lemma, the sets of centers $\mathcal{C}^{t}$ are arbitrary and can
change completely at each time step – which in particular means we cannot
apply standard histogram techniques. We also note that the clusters
$C^{t}_{1},...,C^{t}_{k}$ do not necessarily corresponds to the optimal
clusters for centers $\mathcal{C}^{t}$: however, this clustering gives a
solution with almost the same cost. We will abuse notations and consider them
as the clusters associated with $\mathcal{C}^{t}$: the additive term
$O(1/\alpha)$ will be negligible compared to other sources of error. Last, the
probability statement is only for the estimation of $\sum_{p\in
C^{t}_{i}}f(p)$: the construction of the partition $C^{t}_{1},...,C^{t}_{k}$
is deterministic.

##  3 A Well-Structured Static Clustering Algorithm

In this section, we present a non-private algorithm that is well structured
(in the sense that it can be easily turned into a private algorithm, as we
will see), and works in low dimensional space. Our algorithm is highly
inspired by the static greedy algorithm for $k$-means proposed by Mettu and
Plaxton [MP00]. This essentially reduces the problem to computing a histogram,
for which there are known algorithms working privately under continual
observation.

More precisely, the algorithm computes a solution with a constant
multiplicative approximation factor, taking as an input a mere summary of the
data: given the recursive net decomposition described in section 2.1, the
algorithm merely requires a function $\operatorname{NoisyValue}$ that assigns
a weight to every net point. This function is an approximation to the value of
net points, as formalized in definition 6.

The algorithm works in $k$ rounds: at each round, a new center is placed
greedily as follows. Initially, all net points are _available_. At the
beginning of a round, the algorithm selects the available net point with
maximal $\operatorname{NoisyValue}$. To find the precise location of the next
center, the algorithm recursively selects the child of the current net point
that has maximum $\operatorname{NoisyValue}$, until the last level: the new
center is the last net point. Then, the algorithm removes a number of net
points from the set of available ones: namely, all those whose
$89$-neighborhood contain the new center. The algorithm is formally described
in algorithm 1. Note that we didn’t attempt to improve the constants
appearing, as they only affect marginally the running time.

Algorithm 1 $\textsc{RecursiveGreedy}(\operatorname{NoisyValue},k)$

1:Input: a function $\operatorname{NoisyValue}$ that assigns a non-negative
number to any net point

2:Define the set of available net points to be all the net points
$\cup_{i}Z_{i}$.

3:for $j$ from $1$ to $k$ do

4: $l\leftarrow 1$

5: Let $z_{j}^{1}$ be the available net point with largest
$\operatorname{NoisyValue}(z_{j}^{1})$

6: while $\operatorname{level}(z)<\lceil\log(n)\rceil$ do

7: Let $z_{j}^{l+1}$ be the child of $z_{j}^{l}$ with largest
$\operatorname{NoisyValue}\left(z_{j}^{l+1}\right)$

8: $l\leftarrow l+1$

9: $c_{j}\leftarrow z_{j}^{l}$

10: for all available net point $z$ do

11: if $c_{j}\in N^{89}(z)$ then

12: Remove $z$ from the set of available net points

13:Output: the solution $\mathcal{C}=(c_{1},\dots,c_{k})$

As explained in the introduction, the algorithm works provided a noisy summary
of the input, namely $\operatorname{NoisyValue}$. Those will be chosen to
approximate the real value of each net point.

######  Definition 6 ($\Theta$-threshold condition).

For any $\Theta\geq 1$, we say that the function $\operatorname{NoisyValue}$
verifies the $\Theta$-threshold condition if for each net point $z$,

  * •

when $\operatorname{NoisyValue}(z)\geq\Theta$, then
$\operatorname{NoisyValue}(z)\in[\operatorname{Value}(z)/2,2\cdot\operatorname{Value}(z)]$,
and

  * •

when $\operatorname{NoisyValue}(z)<\Theta$, then $\operatorname{Value}(z)\leq
2\cdot\Theta$.

The utility of this algorithm is stated in the following theorem, proven in
appendix B

######  Theorem 7.

For any threshold $\Theta\geq 1$, if $\operatorname{NoisyValue}$ verifies the
$\Theta$-threshold condition, then the algorithm
$\textsc{RecursiveGreedy}(\operatorname{NoisyValue},k)$ computes a
$\left(O(1),O(k\cdot\Theta)\right)$-approximate solution to the $k$-means
problem.

##  4 Differential Privacy in Low Dimension: Proof of Theorem 3

Using an observation from [Ngu20], it is possible to turn any private constant
factor approximation into an algorithm with the best possible non-private
approximation ratio, henceforth proving Theorem 3. The key idea is that, for
any $\alpha>0$, any $O(1)$-approximate solution to $k^{\prime}$-means, with
$k^{\prime}=k\alpha^{-O(d)}\log(n/\alpha)$, has cost at most
$\alpha\textsc{opt}_{k}$, where $\textsc{opt}_{k}$ is the optimal cost using
$k$ centers.

Therefore, given a non-private algorithm $\mathcal{A}$ with approximation
guarantee $w^{*}$, the following algorithm is private and has multiplicative
approximation $(1+\alpha)w^{*}$, and additive error
$k\cdot\alpha^{-O(d)}\log(n)^{4}\cdot\log(T)^{3/2}\cdot{\varepsilon}^{-1}$:
(1) We find privately an $O(1)$-approximation $\mathcal{S}$ to
$k^{\prime}$-clustering (described below), and then (2) we estimate privately
the size of each cluster using mechanism $\mathcal{M}^{\prime}$ from Lemma 5.
Let $P^{\prime}$ be the dataset formed by the centers of $\mathcal{S}$,
weighted by the private number of points in their respective cluster. (3)
Then, using $\mathcal{A}$, we compute a $w^{*}$-approximate solution of
$k$-means on $P^{\prime}$, which is our final output. [Ngu20] formally shows
the privacy and utility guarantee of this static algorithm. The privacy stems
from the privacy of $\mathcal{S}$, and the private estimate of the size of
each cluster. The computation of $\cal A$ is simply a postprocessing step that
does not affect the privacy guarantee. The utility guarantee follows from the
triangle inequality: the cost of replacing any point by its center in
$\mathcal{S}$ is negligible compared to the cost of the optimum solution. We
make the argument formal in Section C.2.

####  $\varepsilon$-DP $O(1)$-approximation algorithm.

Thus, we give an algorithm that computes a constant-factor approximation –
which can be improved using the techniques of [Ngu20]. For this, we show how
to compute a private summary of the data that can be used by Algorithm 1,
namely, we want to maintain approximate values of net points that fulfill the
$\Theta$-threshold condition, for $\Theta=3d\cdot
2^{2d}\log(n)^{2}\log(T)^{3/2}\log(1/\beta)/\epsilon$. This allows to compute
a constant-factor approximation.

To do so we merely use standard histograms (see Lemma 17 in Appendix). Indeed,
the value of a net point can be computed from the number of points in its
1-neighborhood, thus, maintaining privately the number of points in each
1-neighborhood of net points with small additive error suffices.

We let $\cal M$ be the histogram algorithm of Lemma 17. At time $t$, the
algorithm determines in which 1-neighborhood the updated point belongs to and
uses it as a parameter for an update operation in $\cal M$. Thus, for any net
point $z$, $\cal M$ maintains the size of $N^{1}(z)\cap X_{t}$, which is the
set of points from the stream present at time $t$ in $N^{1}(z)$.

Algorithm 2 $\textsc{MakePrivate}(P,\varepsilon)$

1:for each time step $t$ when given update operation $u(p)$ with
$u\in\\{insert,delete\\}$ do

2: Give $u(p)$ to $\cal M$ which returns for each net point $z$ an estimate
$c(z,t)$ of $|N^{1}(z)\cap X_{t}|$

3: For each level $\ell$ and net point $z$ at level $\ell$, define $v(z,t)$ to
be the value of $z$ at time $t$ computed with counts $c(z,t)$:
$v(z,t):=2^{-2\ell}c(z,t)$

4:Output: $v(z,t)$ and $c(z,t)$ for all $z$

To show that his algorithm is a constant-factor approximation we show that the
values computed with MakePrivate are private and that they satisfy the
assumption of Theorem 7. Thus, combining this algorithm with Theorem 7 yields
a private constant factor approximation. We formalize this in the following
lemma proven in appendix C:

######  Lemma 8.

Consider an input stream of additions and deletions of points from
$B_{d}(0,1)$. There exists an algorithm that is $\varepsilon$-differentially
private under continual observation and computes, at each time step $t$, a
solution to $k$-means that has cost at most

$O(1)\cdot\textsc{opt}_{t}+kd2^{2d}\cdot\frac{\log(n)^{2}\log(T)^{3/2}}{\varepsilon},$

with probability $0.99$, where $n$ is the maximum size of the dataset at any
given time.

##  5 Differential Privacy in High Dimensions

To reduce the additive error to polynomial in $d$, we use the following
result, that states that the cost of any clustering is roughly preserved when
projecting onto $O(\log(k))$ dimensions. For a set $P$, its average is
$\mu(P):={1/|P|}\cdot\sum_{p\in P}p$, and for a projection
$\pi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{\hat{d}}$ let
$\pi(P):=\left\\{\pi(p),p\in P\right\\}$

######  Lemma 9 (Theorem 1.3 in Makarychev, Makarychev, Razenshteyn [MMR19],
see also Becchetti et al. [BBC+19]).

Fix some $1/4\geq\alpha>0$ and $1>\beta>0$. There exists a family of random
projection $\pi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{\hat{d}}$ for some
$\hat{d}=O(\log(k/\beta)\alpha^{-2})$ such that, for any set
$P\in\mathbb{R}^{d}$, it holds with probability $1-\beta$ that for any
partition of $P$ into $k$ parts $P_{1},...,P_{k}$,

$\sum_{j=1}^{k}\operatorname{cost}\big{(}\pi(P_{j}),\mu(\pi(P_{j}))\big{)}\in\left(1\pm\alpha\right)\cdot\frac{\hat{d}}{d}\cdot\sum_{j=1}^{k}\operatorname{cost}(P_{j},\mu(P_{j})).$

This lemma allows us to compute clusters in the low dimensional space,
incurring an additive error
$\alpha^{-O(\hat{d})}=(k/\beta)^{O(\log(1/\alpha))}$ instead of
$2^{O(\hat{d})}$ using the algorithm from previous section. However, an
additional step is required to lift the solution from $\mathbb{R}^{\hat{d}}$
back into the original space $\mathbb{R}^{d}$ and recover the centers in that
space.

Our technique is as follows: we project onto $\mathbb{R}^{\hat{d}}$ using
Lemma 9 with success probability $99/100$, find a clustering in that space
using Theorem 3, and apply Lemma 5 to that clustering to compute key values,
allowing to recover centers in the original $\mathbb{R}^{d}$ space. Crucially,
Lemma 5 is applied only on clusters _from the low-dimensional space_ , and the
additive error scales only with $2^{O(\hat{d})}=k^{O(\log(1/\alpha))}$. This
produces at each time step a correct solution with probability $4/5$. This
algorithm fails on many time steps (roughly a fifth of them): we show in
Section 5.2 how to boost the probability, and give an algorithm that with
probability $1-\beta$ is correct at _all_ time steps.

###  5.1 An Algorithm for $k$-Means in All Dimensions, with Low Success
Probability

#### Computing a Private Summary of the Data Points.

In order to use Lemma 9 and project back the computed solution, we slightly
change the private summary computed from the points as follows. First, each
point is projected onto $\hat{d}=O(\log(k/\beta))$ dimensions, and a
clustering is computed in that space. Using Lemma 5, one can then for each
cluster $C^{\prime t}_{j}$ in $\mathbb{R}^{\hat{d}}$ estimate the number of
points in $C^{\prime t}_{j}$ as well as estimate the sum of all points in
$C^{\prime t}_{j}$ _using their $d$-dimensional coordinates, i.e., in
$\mathbb{R}^{d}$_. This happens in Algorithm 3. In line 8 of Algorithm 3, we
take the ratio of these two values, which gives the mean of each cluster in
the original space $\mathbb{R}^{d}$ – which is the optimal $1$-mean solution
for this cluster. As a technicality, we need to ensure that all projected
points are in the ball $B_{\hat{d}}(0,\log(n))$: this happens with high
probability and allows to preserve privacy in the (unlikely) case the
projection fails. Since the diameter of the projected dataset is now
$\log(n)$, all additive errors from the previous section are rescaled by
$\log(n)$ (since we assumed the diameter was $1$, for simplicity).

Algorithm 3 $\textsc{MakePrivate-HighDimension}(P,\varepsilon,\alpha,\beta)$

1:Let $\pi$ be a dimension reduction given by Lemma 9 with success probability
$0.99$, and let $\hat{d}$ be the dimension of $\pi(P)$

2:for $p\in P$ do

3: define $p^{\prime}$ to be the projection onto the $\hat{d}$-dimensional
ball $B_{\hat{d}}(0,\log(n))$ of the point $\sqrt{\frac{d}{\hat{d}}}\pi(p)$.

4:Let $P^{\prime}$ be the set of all points $p^{\prime}$.

5:Maintain an approximate solution $\mathcal{C}^{t}$ for $k$-means on
$P^{\prime}$, using Algorithm 4 with parameter $\varepsilon/(d+3)$

6:Use the algorithm from Lemma 5 with precision parameter $\alpha$, centers
$\mathcal{C}^{t}$, privacy parameter $\varepsilon/(d+3)$ and probability
$\beta/(d+3)$. The outcome of the algorithm is a partition of $P^{\prime}$
into clusters ${C^{\prime}}_{1}^{t},...,{C^{\prime}}_{k}^{t}$, and for each
${C^{\prime}}_{j}^{t}$:

  * •

the number of points $n_{j}^{t}:=|{C^{\prime}}_{j}^{t}|$ ,

  * •

the sum
$\textsc{SumNorm}(j,t):=\sum_{p:p^{\prime}\in{C^{\prime}}_{j}^{t}}\left\|p\right\|_{2}$

  * •

for each dimension $i\in\left\\{1,...,d\right\\}$,
$\textsc{Sum}(j,t)_{i}=\sum_{p:p^{\prime}\in{C^{\prime}}_{j}^{t}}p_{i}$

7:Define $\textsc{Sum}(j,t)$ to be the vector with coordinates
$\textsc{Sum}(j,t)_{i}$.

8:$\mathfrak{c}_{j}(t)\leftarrow\frac{\textsc{Sum}(j)}{n_{j}^{t}}$

9:Output: the centers $\mathfrak{c}_{j}(t)$, the values $n_{j}^{t}$,
$\textsc{SumNorm}(j,t)$ and $\textsc{Sum}(j,t)$ for all
$j\in\left\\{1,...,k\right\\}$ and all time $t$.

To simplify the equations, we will note in the following
$\mathcal{E}(\varepsilon,\beta,n)=\frac{\log(n)^{2}\log(T)}{\varepsilon}\cdot\left(\log(1/\beta)+\sqrt{\log
T}\right)$. The value SumNorm will only be used later in Section 5.2, but we
defined it here already for simplicity. The proof of the next lemma can be
found in Appendix D.

######  Lemma 10.

Algorithm 3 is $\varepsilon$-differentially private. Furthermore, the two
following properties hold:

  * •

for each time $t$, with probability at least $0.99$, the clustering in line 6
is an
$\left((1+\alpha)w^{*},k^{O(1)}\log(n)^{2}\mathcal{E}(\varepsilon,0.01,n)\right)$-approximation,

  * •

for each time $t$ and cluster ${C^{\prime}}_{j}^{t}$ computed line 6, it holds
with probability $1-\beta$ that:

    * –

$\big{|}n_{j}^{t}-|{C^{\prime}}_{j}^{t}|\big{|}\leq\mathcal{E}(\varepsilon,\beta,n)\cdot
d\cdot\log(n)\cdot k^{O(1)}$,

    * –

$\left\|\textsc{Sum}(j,t)-\sum_{p:p^{\prime}\in{C^{\prime}}_{j}^{t}}p\right\|_{2}\leq
O(1)\cdot
d^{3/2}\cdot\mathcal{E}(\varepsilon,\beta,n)\cdot\log(n)\cdot\log(d)\cdot
k^{O(1)}$, and

    * –

$\left|\sum_{x\in C_{j}}\|x\|_{2}^{2}-\textsc{SumNorm}(j,t)\right|\leq
k^{O(1)}d\mathcal{E}(\varepsilon,\beta,n)\log(n)$

#### Solving $k$-Means From the Private Summary.

Using the information of Sum and the estimated number of points in each
cluster, we can compute an estimate of the location of each cluster’s mean in
$\mathbb{R}^{d}$. This is what is done in line 8 of Algorithm 3, and the proof
that the additive error remains controlled is in Lemma 11.

######  Lemma 11.

For any constant $\alpha>0$, the centers
$\mathfrak{c}_{1}(t),...,\mathfrak{c}_{k}(t)$ computed line 8 of Algorithm 3
with failure probability $\beta=1/10$ form a
$((1+\alpha)w^{*},\leavevmode\nobreak\ k^{O(1)}\cdot
d^{2}\cdot\log(n)^{4}\cdot\log(T)^{3/2}\cdot{\varepsilon}^{-1})$-approximate
solution with probability $4/5$.

###  5.2 Boosting the probabilities

Algorithm 3 MakePrivate-HighDimension outputs centers for each time steps that
can be used to create a clustering which is, with constant probability, a
$\left((1+\alpha)w^{*},\leavevmode\nobreak\ k^{O(1)}\cdot
d^{3}\cdot\log(n)^{3}\log(T)^{3/2}\cdot{\varepsilon}^{-1}\right)$-approximate
solution. This probability is only constant, as the dependence of the additive
error on the failure probability of the dimension reduction is
polynomial:333This dependency is hidden in Lemma 11 as we used a success
probability $0.99$. To make it explicit, note that if the target success
probability of the dimension reduction is $\beta_{d}$, then
$2^{\hat{d}}=(k/\beta_{d})^{O(1)}$: $1/\beta_{d}$ appears thus with the same
exponent as $k$ in the additive error. therefore, increasing the success
probability naively would dramatically increase the additive error. However,
we want a result that holds for _all_ time steps with constant probability.
Instead of simply increasing the success probability to $1/T$ and performing a
union bound over all steps (which would yield an additive error
$\operatorname{poly}(T)$), we proceed as described in the introduction – run
several copies and output the solution with best cost – to get the following
lemma. Theorem 1 is a direct consequence of this lemma by setting
$\kappa=0.001$.

######  Lemma 12.

For any $\kappa>0$, there is an $\varepsilon$-DP algorithm that, with
probability $1-\beta$, computes for all time steps $t$ simultaneously a
$\left((1+\alpha)w^{*},k^{O(1)}\cdot
d^{2}\log(1/\beta)\log(n)^{4}\cdot\log(T)^{3+\kappa}\cdot\varepsilon^{-1}\cdot\kappa\right)$-approximation
to $k$-means.

As mentioned, the main difficulty in proving Lemma 12 is to evaluate the cost
of a clustering, privately and for all time steps simultaneously. Note that it
is crucial that the estimated cost is correct at all time $t$ simultaneously:
we cannot increase the success probability of this estimates, as we precisely
use it to boost the probability of other steps.

To estimate the cost of a single cluster, we rely on the following identity
(see Lemma 26): for any set $X$, $\operatorname{cost}(X,\mu(X))=\sum_{x\in
X}\|x\|_{2}^{2}-\frac{1}{|X|}\cdot\left\|\sum_{y\in X}x\right\|_{2}^{2}$.
Therefore, to maintain the clustering cost, it is enough to maintain, for each
cluster $C^{t}_{j}$, both (1) $\sum_{x\in C^{t}_{j}}\|x\|_{2}^{2}$, which is
precisely $\textsc{SumNorm}(j,t)$, and (2) $\sum_{x\in C^{t}_{j}}x$, which is
$\textsc{Sum}(j,t)$. Those two quantities are maintained by Algorithm 3. By
Lemma 10, $\textsc{SumNorm}(j,t)$ is an estimate of $\sum_{x\in
C^{t}_{j}}\|x\|_{2}^{2}$, up to an additive error
$k^{O(1)}d\mathcal{E}(\varepsilon,\beta,n)\log(n)$. Therefore, we can show the
following lemma:

######  Lemma 13.

For any time $t$ and any cluster ${C^{\prime}}^{t}_{j}$ from the call to Lemma
5 in Algorithm 3, define
$C^{t}_{j}:=\left\\{p:p^{\prime}\in{C^{\prime}}^{t}_{j}\right\\}$. When the
probability parameter of Algorithm 3 is $\beta/T$, then it holds with
probability $1-\beta$ that, for all time $t$ and cluster $j\in\\{1,...,k\\}$
simultaneously,

$\left|\operatorname{cost}(C^{t}_{j},\mu(C^{t}_{j}))-\left(\textsc{SumNorm}(j,t)-\frac{\left\|\textsc{Sum}(j,t)\right\|_{2}^{2}}{n_{j}}\right)\right|\leq
k^{O(1)}\cdot\frac{d^{3/2}\cdot\log(n)^{3}\log(T)\log(T/\beta)}{\varepsilon}.$

This allows therefore to maintain an approximate estimate of the cost of the
solution: thus, it is possible to boost the success probability by running
several copies of the algorithm and output one with best estimated cost. We
give proof and more details in Appendix D.

##  6 Privately Counting on Clusters

This section proves our key Lemma 5. For this, we show how to break the ball
$B_{d}(0,1)$ into _fixed_ sets $G_{1},...,G_{m}$, such that each $C^{t}_{i}$
can be described as the union of few $G_{j}$. In this way, computing the sum
$\sum_{p\in C_{i}^{t}}f(p)$ is reduced to computing $\sum_{p\in G_{j}}f(p)$,
for which we can apply Lemma 17.

Such a decomposition can be constructed e.g. via net trees [HM06]: we describe
its construction in Appendix E. Those sets $G_{1},...,G_{m}$ are such that
$m=O\left(n^{d}\right)$ and any point from $B_{d}(0,1)$ appears in $b=\log(n)$
sets. Thus, standard counting mechanisms (see Lemma 17 in Appendix) apply,
with additive error
$O\left(d\cdot\log(n)^{2}\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(1/\beta)\right)\right)$.

Therefore, in order to maintain $\sum_{p\in C_{i}^{t}}f(p)$, we only need to
show how to express this sum with few $\sum_{p\in G_{i}\cap X_{t}}f(p)$. This
is done in the next lemma, shown in Appendix E.

######  Lemma 14.

Fix an $1>\alpha>0$, and $\mathcal{G}=\left\\{G_{1},...,G_{m}\right\\}$ as
above, and let $\mathcal{C}=\left\\{c_{1},...,c_{k}\right\\}$ be any set of
centers. Then, it is possible to compute a partition $\mathcal{A}$ of
$B_{d}(0,1)$ together with an assignment $a:\mathcal{A}\rightarrow\mathcal{C}$
of parts to centers, such that (1) each part of $\mathcal{A}$ is a set from
$\mathcal{G}$, (2) $|\mathcal{A}|\leq k\cdot\alpha^{-O(d)}\log(n)$, and (3)
for any set $P$,

$\left|\operatorname{cost}(P,\mathcal{C})-\sum_{A\in\mathcal{A}}\sum_{p\in
P\cap
A}\operatorname{dist}(p,a(A))\right|\leq\alpha\operatorname{cost}(P,\mathcal{C})+\frac{9}{\alpha}.$

The proof of Lemma 5 follows easily, as sketched before: using standard
counting mechanisms (Lemma 17), one can maintain $\sum_{p\in A}f(p)$, for all
$A\in\mathcal{A}$, with additive error
$O\left(d\cdot\log(n)^{2}\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(1/\beta)\right)\right)$.
Since each cluster $C_{i}$ is the union of $k\cdot\alpha^{-2d}\log(n)$ many
$A\in\mathcal{A}$, the additive error is simply multiplied by
$k\cdot\alpha^{-O(d)}\log(n)$, which concludes the proof of Lemma 5.

##  7 Extension to $k$-median – proof of theorem 2

We now sketch how to prove the following theorem. See 2

For this, we follows the same path as for our $k$-means algorithm. Our
algorithm for $k$-means works in three steps: first, project onto a low-
dimensional space, and solve in this space. Second, lift the solution up, and
third boost the probabilities. We follow the same path for $k$-median, with a
few caveats.

First, we note that the algorithm for low dimensions from theorem 7 extends
directly to $k$-median: nothing in the argument is special about squared
distances – and the original result from [MP00] works for both $k$-means and
$k$-median. The techniques from [Ngu20] extends directly as well: this yields
an algorithm with multiplicative approximation $w^{*}$ and additive error
$2^{O(d)}k\log(n)^{2}\frac{\log(T)^{3/2}}{\varepsilon}$.

The dimension-reduction theorem of lemma 9 also works for $k$-median. However,
given a clustering in the projected space, computing the centers in the
original space is not as easy as for $k$-means. For this, we show that the
mean is actually a $2$-approximation of the $1$-median:

######  Lemma 15.

Let $P$ be a set of point in $\mathbb{R}^{d}$, with optimal $1$-median $m$ and
optimal $1$-mean $\mu$. Then,

$\sum_{p\in P}\|p-\mu\|\leq 2\sum_{p\in P}\|p-m\|.$

###### Proof.

Our goal is to bound the distance between $m$ and $\mu$. Assume for simplicity
that $m$ is the origin, and consider the line $\ell$ going through the origin
and $\mu$. Let $P_{\ell}$ be the set $P$ projected onto $\ell$. Since the mean
is linear, $\mu$ is also the mean of $P_{\ell}$, i.e., $\mu=\frac{\sum_{p\in
P_{\ell}}p}{|P|}$. Therefore, we have $|P|\|\mu\|\leq\sum_{p\in
P_{\ell}}\|p\|$: since projection only decrease the norm, this is at most
$\sum_{p\in P}\|p\|$.

Rephrasing, this means that $\|\mu-m\|\leq\frac{\sum_{p\in P}\|p-m\|}{|P|}$:
the distance between the mean and the $1$-median is at most the $1$-median
cost divided by $|P|$. Therefore, $\sum_{p\in P}\|p-\mu\|\leq\sum_{p\in
P}\|p-m\|+|P|\|\mu-m\|\leq 2\sum_{p\in P}\|p-m\|$. This concludes the lemma. ∎

Therefore, given a clustering in low-dimensional space, using the mean of each
cluster in high-dimensional space yields a mere factor $2$ additional loss.
Techniques developed in section 5 allow to compute privately the mean under
continual observation.

The third step of our $k$-means algorithm, boosting the probabilities,
requires to be able to compute privately under continual observation the cost
of a $k$-means solution: for this we used lemma 13. How to extend to
$k$-median, and therefore boosting the probabilities, is interesting future
work. Without the third step we get the result stated in theorem 2.

We additionally note that the simple lemma 15 can be applied to other
settings, e.g., to extend the result from [CNX21] to get a locally-private
algorithm for $k$-median as well.

##  8 Conclusion

We present the first $\varepsilon$-differentially private $k$-means clustering
algorithm under continual observation. It has almost the same multiplicative
error as the best static non-private algorithm and an additive error of
$\operatorname{poly}(k,d,\log(n),\log(T))\Lambda^{2}/\epsilon$, i.e., unlike a
naive approach it is _not_ exponential in $d$ and _not_ linear in $T$.

Our techniques extend to $k$-median, with a slightly worsen multiplicative
approximation guarantee, as well as with a weaker success probability. Filling
the gap is an interesting open question.

## References

  * [20116a] WWDC 2016.  Engineering privacy for your users, June 2016.  https://developer.apple.com/videos/play/wwdc2016/709/.
  * [20116b] WWDC 2016.  Wwdc 2016 keynote, June 2016.  https://www.apple.com/apple-events/june-2016/.
  * [Abo18] John M Abowd.  The us census bureau adopts differential privacy.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2867–2867, 2018.
  * [BBC+19] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for _k_ -means: beyond subspaces and the johnson-lindenstrauss lemma.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039–1050. ACM, 2019.
  * [BDL+17] Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang.  Differentially private clustering in high-dimensional Euclidean spaces.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 322–331. PMLR, 06–11 Aug 2017\.
  * [CAEMN22] Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan.  Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1621–1628, 2022.
  * [CEL+22] Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Muñoz Medina, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii.  Scalable differentially private clustering via hierarchically separated trees.  In Aidong Zhang and Huzefa Rangwala, editors, KDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022, pages 221–230. ACM, 2022.
  * [CGKM21] Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi.  Locally private k-means in one round.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1441–1451. PMLR, 2021.
  * [CNX21] Anamay Chaturvedi, Huy L. Nguyen, and Eric Xu.  Differentially private k-means via exponential mechanism and max cover.  In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 9101–9108. AAAI Press, 2021.
  * [CR22] Adrian Rivera Cardoso and Ryan Rogers.  Differentially private histograms under continual observation: Streaming selection into the unknown.  In International Conference on Artificial Intelligence and Statistics, pages 2397–2419. PMLR, 2022.
  * [CSS11] T.-H. Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011.
  * [Dem21] David Deming.  Balancing privacy with data sharing for the public good, February 2021\.  https://www.nytimes.com/2021/02/19/business/privacy-open-data-public.html.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum.  Differential privacy under continual observation.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724, 2010.
  * [DR+14] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [EMM+23] Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong.  Differentially private continual releases of streaming frequency moment estimations.  arXiv preprint arXiv:2301.05605, 2023.
  * [EMZ23] Alessandro Epasto, Tamalika Mukherjee, and Peilin Zhong.  Differentially private clustering in data streams.  2023\.
  * [FHO21] Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost.  Differentially private algorithms for graphs under continual observation.  In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 42:1–42:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [FHU22] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay.  Constant matters: Fine-grained complexity of differentially private continual observation using completely bounded norms.  CoRR, abs/2202.11205, 2022.
  * [FHU23] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay.  Constant matters: Fine-grained complexity of differentially private continual observation using completely bounded norms.  International Conference on Machine Learning, 2023.
  * [GKL03] Anupam Gupta, Robert Krauthgamer, and James R. Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534–543. IEEE Computer Society, 2003.
  * [GKM20] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi.  Differentially private clustering: Tight approximation ratios.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems, 2020.
  * [GKMN22] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Jelani Nelson.  Private counting of distinct and k-occurring items in time windows.  arXiv preprint arXiv:2211.11718, 2022.
  * [GLM+10] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar.  Differentially private combinatorial optimization.  In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106–1125. SIAM, 2010.
  * [Gue19] Miguel Guevara.  Enabling developers and organizations to use differential privacy, 2019\.
  * [HK20] Monika Henzinger and Sagar Kale.  Fully-dynamic coresets.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 57:1–57:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [HM06] Sariel Har-Peled and Manor Mendel.  Fast construction of nets in low-dimensional metrics and their applications.  SIAM J. Comput., 35(5):1148–1184, 2006.
  * [HSS23] Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner.  Differentially private data structures under continual observation for histograms and related queries.  CoRR, abs/2302.11341, 2023.
  * [HUU23] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay.  Almost tight error bounds on differentially private continual counting.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039. SIAM, 2023.
  * [JRSS21] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith.  The price of differential privacy under continual observation.  arXiv preprint arXiv:2112.00828, 2021.
  * [KOV17] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  IEEE Trans. Inf. Theory, 63(6):4037–4049, 2017.
  * [LT23] Christian Janos Lebeda and Jakub Tetek.  Better differentially private approximate histograms and heavy hitters using the misra-gries sketch.  CoRR, abs/2301.02457, 2023.
  * [MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of johnson-lindenstrauss transform for _k_ -means and _k_ -medians clustering.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038. ACM, 2019.
  * [MP00] Ramgopal R. Mettu and C. Greg Plaxton.  The online median problem.  In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 339–348. IEEE Computer Society, 2000.
  * [Ngu20] Huy L. Nguyen.  A note on differentially private clustering with large additive error.  CoRR, abs/2009.13317, 2020.
  * [oNYT20] The Editorial Board of New York Times.  Privacy cannot be a casualty of the coronavirus, April 2020.  https://www.nytimes.com/2020/04/07/opinion/digital-privacy-coronavirus.html.
  * [SK18] Uri Stemmer and Haim Kaplan.  Differentially private k-means with constant multiplicative error.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 5436–5446, 2018.
  * [Uni18] European Union.  General data protection regulation, 2018.  https://gdpr.eu/.

##  Appendix A Extended Preliminaries Section 2

In this section, we will prove Lemma 4 and introduce two additional results
essential for subsequent proofs.

See 4

###### Proof.

The Lemma directly follows from this classical property of nets that we prove
for completeness:

For any $\delta>0$, any $\delta$-net $Z$ of a set $X\subset\mathbb{R}^{d}$,
any point $x\in X$, and any $l>0$, the ball $B(x,l\cdot\delta)$ contains at
most $2^{d}(l+0.5)^{d}$ points of $Z$.

By the packing property of nets, any ball of radius $\delta/2$ around a point
in $Z\cap B(x,l\cdot\delta)$ is disjoint from other such balls. Furthermore,
these balls are entirely contained within $B(x,(l+0.5)\cdot\delta)$. The
volume of a ball of radius $\delta/2$ is a $(1/(2(l+0.5))^{d})$ fraction of
the volume of a ball of radius $(l+0.5)\cdot\delta$. Therefore, we can derive
the inequality $|Z\cap B(x,l\cdot\delta)|\leq 2^{d}(l+0.5)^{d}$. ∎

To deal with squared distances, we will also use generalization of triangle
inequality:

######  Fact 16 (Squared Triangle Inequality).

Let $a,b,c$ be an arbitrary set of points in a metric space with distance
function $d$. Then for any $\alpha>0$

$d(a,b)^{2}\leq(1+\alpha)d(a,c)^{2}+\left(\frac{1+\alpha}{\alpha}\right)d(b,c)^{2}$

###### Proof.

By the regular triangle inequality, $d(a,b)^{2}\leq(d(a,c)+d(c,b))^{2}$. We
note $x=d(a,c),y=d(b,c)$, and observe that $\alpha
x^{2}+y^{2}\alpha-2xy=(\sqrt{\alpha}x-y/\sqrt{\alpha})^{2}\geq 0$, and
therefore $(x+y)^{2}\leq(x+y)^{2}+\alpha
x^{2}+y^{2}/\alpha-2xy=(1+\alpha)x^{2}+(1+1/\alpha)y^{2}$, which concludes. ∎

The main tool we will use for the design of private algorithm is the following
mechanism for histograms, it is a slight extension of Lemma 11 in [FHO21]:

######  Lemma 17.

Let $\sigma$ be a stream of length $T$ of addition or deletion of points from
a ground set $G$, and let $P_{t}$ be the set of points at time $t$ with $1\leq
t\leq T$. Let $f:G\rightarrow[-1,1]$ be a function, and let
$G_{1},...,G_{m}\subseteq G$ be such that at any $p\in G$ is included in at
most $b$ $G_{i}$. There is an $\varepsilon$-DP algorithm that, for all time
step individually, with probability $1-\beta$, estimates for each set $G_{i}$
the value of $\sum_{p\in G_{i}\cap P_{t}}f(p)$, with additive error
$O(b)\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(m/\beta)\right)$.

###### Proof.

Let $\varepsilon^{\prime}=\varepsilon/b$. Given a sequence of numbers from
$[-L,L]$ a _continual counting mechanism_ outputs, after the arrival of each
number $x_{i}$, an estimate of the sum $\sum_{i=1}^{t}x_{i}$. The binary
mechanism is an $\varepsilon^{\prime}$-differentially private continual
counting mechanism that estimates the sum $\sum_{i=1}^{t}x_{i}$. With
probability at least $1-\beta$ the additive error of all time steps is
$O(L\varepsilon^{\prime-1}\log(T)^{2}\log(1/\beta))$ [DNPR10, CSS11, FHO21].
Note that the proof given in these references only shows the claim for numbers
from $\\{-L,-L+1,\dots,L-1,L\\}$, but the same proof goes through verbatim for
numbers from $[-L,L]$. Further note that the additive error bound in these
references is stated only on a per-time step basis, i.e., with probability at
least $1-\delta$, the additive error at any _individual_ time step is
$O(L\varepsilon^{\prime-1}\log(T)^{3/2}\log(1/\delta)).$ However, as observed
in [JRSS21] the bound on the additive error for any individual time step can
be improved to
$O(\varepsilon^{\prime-1}\log(T)(\sqrt{\log(T)}+\log(1/\delta)))$ using the
first part of Corollary 2.9 of [CSS11].

To prove the lemma we run the $\varepsilon^{\prime}$-differentially private
binary mechanism separately for each set $G_{i}$ for $i=1,\dots,m$. This is
identical to running a histogram algorithm where each set $G_{i}$ corresponds
to a counter in the histogram algorithm. We give the full analysis here, as
only the case $b=1$ has been studied in the literature on
$\varepsilon$-differentially algorithms (but $b\geq 1$ has been studied for
$(\varepsilon,\delta)$-differentially private algorithm,s using a different
algorithm), and we crucially rely on the fact that $b$ is small in our
analysis.

Whenever a point $p\in G$ is inserted, $f(p)$ is added to the binary mechanism
for all the sets $p$ belongs to, whenever it is deleted $-f(p)$ is added to
the binary mechanism for all the sets $p$ belongs to. Between any two updates,
the binary mechanism outputs the same sum estimate no matter how often it is
queried. Thus, we can analyze the privacy loss as if the mechanism outputted
exactly one estimate after each update.

_Privacy analysis._ The data from each update operation is only used for $b$
$\varepsilon^{\prime}$-differentially mechanism. By the composition theorem
(Theorem 3.16 in [DR+14]) it follows that it is
$b\cdot\varepsilon^{\prime}=\varepsilon$-differential private.

_Utility analysis._ We set $\delta=\beta/m$. It follows that, for any time
step $t$, with probability at least $1-\beta$ for all $m$ binary mechanisms
the additive error is
$O(L\cdot\varepsilon^{\prime-1}\log(T)(\sqrt{\log(T)}+\log(1/\delta)))=$
$O(L\cdot b\cdot\varepsilon^{-1}\log(T)(\sqrt{\log(T)}+\log(m/\beta)))$ ∎

Note that, in the previous mechanism, the sets $G_{1},...,G_{m}$ are _fixed_
and cannot depend on the time $t$. This means that we cannot use it directly
to estimate, say, the size of a cluster at time $t$ – even if we can compute
privately the center of each cluster. As estimating such quantities is crucial
for our algorithms, we will present a generic mechanism to do so. It is stated
in Lemma 5, we defer the proof to Section 6. The basic idea is to compute at
each time $t$ the size of each cluster as the sum of $k\cdot 2^{O(d)}\log(n)$
many sets of the fixed partition $G_{1},...,G_{m}$.

##  Appendix B Missing Proofs for the Well-Structured Static Clustering
Algorithm (Section 3)

This section is devoted to the proof of Theorem 7. For the sake of clarity, we
will restate the algorithm and the theorem here.

See 1

See 7

Our first remark on the algorithm is the following: at the time where a net
point $z_{j}^{l}$ is selected by the algorithm in line 7, it is available.

######  Lemma 18.

At any moment of the algorithm, if a net point is available, its children are
also available.

###### Proof.

Let $z_{1}$ be a cell of level $i$, and let $z_{2}$ be a child of $z_{1}$. We
have by definition $z_{2}\in N^{4}(z_{1})$ and
$\operatorname{dist}(z_{1},z_{2})\leq 4\cdot 2^{-i}$. We will prove that if
$z_{2}$ becomes unavailable, then $z_{1}$ also becomes unavailable.

Suppose that a new center $c_{j}$ is selected, and $z_{2}$ is no longer
available. This means that $c_{j}\in N^{89}(z_{2})$,and
$\operatorname{dist}(z_{2},c_{j})\leq 89\cdot 2^{-(i+1)}=44.5\cdot 2^{-i}$.
Now using the triangle inequality we have

$\operatorname{dist}(z_{1},c_{j})\leq\operatorname{dist}(z_{1},z_{2})+\operatorname{dist}(z_{2},c_{j})\leq
4\cdot 2^{-i}+44.5\cdot 2^{-i}=48.5\cdot 2^{-i}$

Therefore $c_{j}\in N^{48.5}(z_{1})\subset N^{89}(z_{1})$ and $z_{1}$ also
becomes unavailable when $c_{j}$ is selected. ∎

In what follows, we fix a solution $\Gamma$ with $k$ centers. Our goal is to
compare the cost of the solution $\mathcal{C}$ output by the algorithm and the
cost of $\Gamma$. For $\gamma\in\Gamma$, let $P_{\gamma}$ be $\gamma$’s
cluster, namely all points of $P$ assigned to $\gamma$ in the solution
$\Gamma$. For this, we analyze the cost of each cluster $P_{\gamma}$
independently, as follows.

We split $\Gamma$ into two parts: $\Gamma_{1}$ is the set of $\gamma\in\Gamma$
such that there exists a net point $z$ of level $\lceil\log(n)\rceil$ such
that $\gamma\in N^{1/2}(z)$ and $z$ is still available at the end of the
algorithm, and $\Gamma_{2}=\Gamma-\Gamma_{1}$. Centers in $\Gamma_{2}$ are
very close to centers in $\mathcal{C}$ (at distance at most $O(1/n)$), and the
cost of their cluster is therefore well captured by $\mathcal{C}$. The bulk of
the work is to show that clusters in $\Gamma_{1}$ are also well approximated
by $\mathcal{C}$.

For $\gamma\in\Gamma_{1}$ we define $z_{\gamma}$ to be a net point of the
smallest level such that $\gamma\in N^{1/2}(z_{\gamma})$ and $z_{\gamma}$ is
still available at the end of the algorithm. We split $P_{\gamma}$ into two
parts: $In(P_{\gamma}):=P_{\gamma}\cap N^{1}(z_{\gamma})$ and
$Out(P_{\gamma})=P_{\gamma}-In(P_{\gamma})$.

By definition of $z_{\gamma}$, we know there exists a center of $\mathcal{C}$
”not too far” from $z_{\gamma}$. This allows us to bound the cost of
$Out(P_{\gamma})$ in the solution $\mathcal{C}$. Furthermore, we can relate
the cost of $In(P_{\gamma})$ to the value of $z_{\gamma}$, as done in the
following lemma.

######  Lemma 19.

For all $\gamma\in\Gamma_{1}$, we have:

$\displaystyle\operatorname{cost}(In(P_{\gamma}),\mathcal{C})\leq
181^{2}\cdot\operatorname{Value}(z_{\gamma})$ (1)
$\displaystyle\operatorname{cost}(Out(P_{\gamma}),\mathcal{C})\leq
359^{2}\cdot\operatorname{cost}(Out(P_{\gamma}),\Gamma)$ (2)

And for all $\gamma\in\Gamma_{2}$, we have:

$\operatorname{cost}(P_{\gamma},\mathcal{C})\leq
2\operatorname{cost}(P_{\gamma},\Gamma)+2|P_{\gamma}|(90/n)^{2}.$ (3)

###### Proof.

We start by considering the case where $\gamma$ belongs to $\Gamma_{1}$. Let
$z^{*}_{\gamma}$ be net point of level $\operatorname{level}(z_{\gamma})-1$
such that $\gamma\in N^{0.5}(z^{*}_{\gamma})$. By definition of $z_{\gamma}$,
the net point $z^{*}_{\gamma}$ is not available. Therefore, there is a point
of $\mathcal{C}$ in $N^{89}(z^{*}_{\gamma})$. We have
$\operatorname{dist}(z^{*}_{\gamma},\mathcal{C})\leq 89\cdot
2^{-\operatorname{level}(z^{*}_{\gamma})}=178\cdot
2^{-\operatorname{level}(z_{\gamma})}$, and
$\operatorname{dist}(\gamma,z^{*}_{\gamma})\leq 0.5\cdot
2^{-\operatorname{level}(z^{*}_{\gamma})}=2^{-\operatorname{level}(z_{\gamma})}$
because $\gamma\in N^{0.5}(z^{*}_{\gamma})$. This implies by the triangle
inequality that $\operatorname{dist}(\gamma,\mathcal{C})\leq 179\cdot
2^{-\operatorname{level}(z_{\gamma})}$.

Now for any $x\in P_{\gamma}$, we have

$\operatorname{cost}(x,\mathcal{C})=\operatorname{dist}(x,\mathcal{C})^{2}\leq(\operatorname{dist}(\gamma,\mathcal{C})+\operatorname{dist}(\gamma,x))^{2}$

We can now bound the cost of $In(P_{\gamma})$ and prove Equation 1. If $x\in
N^{1}(z_{\gamma})$, we have
$\operatorname{dist}(\gamma,x)\leq\operatorname{dist}(\gamma,z_{\gamma})+\operatorname{dist}(z_{\gamma},x)\leq
0.5\cdot
2^{-\operatorname{level}(z_{\gamma})}+2^{-\operatorname{level}(z_{\gamma})}\leq
2\cdot 2^{-\operatorname{level}(z_{\gamma})}$, and therefore
$\operatorname{cost}(x,\mathcal{C})\leq(179\cdot
2^{-\operatorname{level}(z_{\gamma})}+2\cdot
2^{-\operatorname{level}(z_{\gamma})})^{2}=181^{2}\cdot
2^{-2\operatorname{level}(z_{\gamma})}$. Summing this inequality over all
$x\in In(P_{\gamma})$, we get

$\operatorname{cost}(In(P_{\gamma}),\mathcal{C})\leq\sum_{x\in
N^{1}(z_{\gamma})\cap P}181^{2}\cdot
2^{-2\operatorname{level}(z_{\gamma})}=181^{2}\operatorname{Value}(z_{\gamma}).$

We turn to $Out(P_{\gamma})$ and show Equation 2. We have
$\operatorname{dist}(\gamma,z_{\gamma})\leq 0.5\cdot
2^{-\operatorname{level}(z_{\gamma})}$, so if $x$ is outside
$N^{1}(z_{\gamma})$, we have $\operatorname{dist}(\gamma,x)\geq 0.5\cdot
2^{-\operatorname{level}(z_{\gamma})}$. Hence

$\displaystyle\operatorname{cost}(x,\mathcal{C})$
$\displaystyle\leq(\operatorname{dist}(\gamma,\mathcal{C})+\operatorname{dist}(\gamma,x))^{2}$
$\displaystyle\leq(179\cdot
2^{-\operatorname{level}(z_{\gamma})}+\operatorname{dist}(\gamma,x))^{2}$
$\displaystyle\leq(2\cdot
179\operatorname{dist}(\gamma,x)+\operatorname{dist}(\gamma,x))^{2}$
$\displaystyle=359^{2}\operatorname{dist}(\gamma,x)^{2}=359^{2}\operatorname{cost}(x,\Gamma)$

Summing this inequality over all $x\in Out(P_{\gamma})$, we get

$\operatorname{cost}(Out(P_{\gamma}),\mathcal{C})\leq
359^{2}\operatorname{cost}(Out(P_{\gamma}),\Gamma).$

Otherwise if $\gamma\in\Gamma_{2}$, let $z$ be a net point of level
$\lceil\log(n)\rceil$ such that $\gamma\in N^{0.5}(z)$. By definition of
$\Gamma_{2}$, $z$ is unavailable at the end of the algorithm, therefore there
exists a center $c_{j}\in\mathcal{C}$ such that $c_{j}\subset N^{89}(z)$. This
allows us to bound the distance between $c_{j}$ and $\gamma$. We have
$\operatorname{dist}(c_{j},\gamma)\leq\operatorname{dist}(c_{j},z)+\operatorname{dist}(z,\gamma)\leq
89\cdot 2^{-\lceil\log(n)\rceil}+0.5\cdot
2^{-\lceil\log(n)\rceil}\leq\frac{90}{n}$, so for all $x\in X$:

$\displaystyle\operatorname{cost}(x,\mathcal{C})$
$\displaystyle\leq(\operatorname{dist}(\gamma,x)+\operatorname{dist}(c_{j},\gamma))^{2}$
$\displaystyle\leq 2\operatorname{dist}(\gamma,x)^{2}+2(90/n)^{2}$

Summing this inequality over all $x\in P_{\gamma}$, we get

$\displaystyle\operatorname{cost}(P_{\gamma},\mathcal{C})$ $\displaystyle\leq
2\operatorname{cost}(P_{\gamma},\Gamma)+2|P_{\gamma}|(90/n)^{2}.\qed$

###  B.1 An Easy Instructive Case.

We now show how to conclude the proof of Theorem 7 based on Lemma 19, under
the following assumption. Suppose all net points that are available at the end
of the algorithm have a value less than $2\cdot\Theta$. Then we can directly
use Lemma 19 to conclude the proof of Theorem 7. Although unrealistic, this
provides a good intuition on our proof of Theorem 7.

Indeed, summing (2) for all $\gamma\in\Gamma_{1}$, we get (and this holds
regardless of the assumption):

$\displaystyle\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}Out(P_{\gamma}),\mathcal{C})$
$\displaystyle=\sum_{\gamma\in\Gamma_{1}}\operatorname{cost}(Out(P_{\gamma}),\mathcal{C})\leq
359^{2}\cdot\sum_{\gamma\in\Gamma_{1}}\operatorname{cost}(Out(P_{\gamma}),\Gamma)$
$\displaystyle\leq 359^{2}\cdot\operatorname{cost}(P,\Gamma)$

Summing 3 for all $\gamma\in\Gamma_{2}$, we get :

$\displaystyle\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{2}}P_{\gamma},\mathcal{C})$
$\displaystyle\leq 2\cdot\operatorname{cost}(P,\Gamma)+n\cdot(90/n)^{2}$
$\displaystyle\leq 2\cdot\operatorname{cost}(P,\Gamma)+90^{2}$

All net points $z_{\gamma}$ are still available at the end of the algorithm,
and with our assumption have a value at most $2\cdot\Theta$. Summing (1) for
all $\gamma\in\Gamma_{1}$, we get:

$\displaystyle\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}In(P_{\gamma}),\mathcal{C})$
$\displaystyle=\sum_{\gamma\in\Gamma_{1}}\operatorname{cost}(In(P_{\gamma}),\mathcal{C})\leq
181^{2}\cdot\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(z_{\gamma})$
$\displaystyle\leq 181^{2}\cdot\sum_{\gamma\in\Gamma_{1}}2\Theta\leq
181^{2}\cdot 2k\Theta$

Summing the three part, we get
$\operatorname{cost}(P,\mathcal{C})\leq(359^{2}+2)\operatorname{cost}(P,\Gamma)+181^{2}\cdot
2k\Theta+90^{2}$ and Theorem 7 is proven (recall that $\Theta\geq 1$).

In the rest of the proof, we show how to bound
$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(z_{\gamma})$ without the need
for any assumption.

###  B.2 Bounding the Values.

To do so, we first relate the value of a net point to the cost of its
1-neighborhood, in the solution $\Gamma$. We say that a net point $z$ is
covered by $\Gamma$ if $\Gamma\cap N^{2}(z)\neq\emptyset$.

######  Lemma 20.

If a net point $z$ is not covered by $\Gamma$, then
$\operatorname{cost}(N^{1}(z)\cap P,\Gamma)\geq\operatorname{Value}(z)$.

###### Proof.

Let $x\in N^{1}(z)\cap P$. Since there is no point of $\Gamma$ in $N^{2}(z)$,
$\operatorname{dist}(x,\Gamma)\geq 2^{-\operatorname{level}(z)}$ and thus
$\operatorname{cost}(x,\Gamma)\geq 2^{-2\operatorname{level}(z)}$. Summing
this inequality over all $x\in N^{1}(z)\cap P$, we get

$\operatorname{cost}(N^{1}(z)\cap P,\Gamma)=\sum_{x\in
N^{1}(z)}\operatorname{cost}(x,\Gamma)\geq|P\cap N^{1}(z)|\cdot
2^{-2\operatorname{level}(z)}=\operatorname{Value}(z)\qed$

We can now provide a bound on the sum of values, based on the previous lemma.
For this, we aim at matching each $z_{\gamma}$ (for $\gamma\in\Gamma_{1}$)
with a net point that is not covered, such that the 1-neighborhood of those
points is disjoint. Then, it will be possible to bound the sum of values using
the upper bound of Lemma 20. In order to define the matching, we need the
following lemma.

######  Lemma 21.

Assume that, at the end of the algorithm, there is a net point available with
a value greater than $2\cdot\Theta$. Then, for all $j\in\\{1,\dots,k\\}$ and
each of the sequences $(z_{j}^{l})_{l}$ defined in Algorithm 1, there exists
an index $l_{j}$ such that:

  * •

$\operatorname{NoisyValue}(z_{j}^{l_{j}})$ is greater than the maximum noisy
value of a point available at the end of the algorithm,

  * •

for all $j,j^{\prime}$, for all $l\geq l_{j}$, $l^{\prime}\geq l_{j^{\prime}}$
$N^{2}(z_{j}^{l})\cap N^{2}(z_{j^{\prime}}^{l^{\prime}})=\emptyset$

###### Proof sketch, see Section B.3.

The proof is inspired by the original one from Mettu and Plaxton [MP00]. We
sketch it here very briefly and refer to Section B.3 for more details. We
describe a procedure to compute the $l_{j}$, starting with $l_{j}=1$ for all
$j$, and note that with this choice the first condition is verified by the
design of the algorithm: when $z_{j}^{1}$ is picked it (on line 5 of Algorithm
1), it maximizes the noisy value among the available net points. To enforce
the second condition, we proceed as follows: as long as we can find
$j<j^{\prime}$ and $l\geq l_{j}$, $l^{\prime}\geq l_{j^{\prime}}$ such that
$N^{2}(z_{j}^{l})\cap N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$, we
update $l_{j}=l_{j}+1$.

We show in Section B.3 that this procedure is well defined, that it preserves
by induction the first property and therefore when it terminates, the two
conditions are satisfied. ∎

We are now ready to prove Theorem 7. Our goal is to find $k$ net points not
covered by $\Gamma$ with disjoint $1$-neighborhood and with values larger than
those of the $z_{\gamma}$. Then, applying Lemma 20 would allow to conclude
$\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}In(P_{\gamma}),\mathcal{C})\leq
O(1)\cdot\sum_{\gamma}\operatorname{Value}(z_{\gamma})\leq
O(1)\cdot\operatorname{cost}(P,\Gamma)$. We explain in the next proof how to
compute those net points.

###### Proof of Theorem 7.

In order to bound the sum of values of $z_{\gamma}$, we will apply the
previous Lemma 20 to $k$ high-value net points not covered by $\Gamma$.
Specifically, we will define a function $\phi$ that maps centers of
$\Gamma_{1}$ to net points such that, for all $\gamma\in\Gamma_{1}$:

  * •

for all $\gamma^{\prime}\in\Gamma_{1}$ with $\gamma\neq\gamma^{\prime}$,
$N^{1}(\phi(\gamma))\cap N^{1}(\phi(\gamma^{\prime}))=\emptyset$,

  * •

$\phi(\gamma)$ is not covered by $\Gamma$,

  * •

the value of $z_{\gamma}$ is less than
$\max(2\cdot\Theta,\operatorname{Value}(\phi(\gamma))/4)$.

Given such a matching $\phi$, we can conclude as follows. Using Lemma 19 and
the proof of Section B.1 we get:

$\displaystyle\operatorname{cost}(P,\mathcal{C})$
$\displaystyle=\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}Out(P_{\gamma}),\mathcal{C})+\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}In(P_{\gamma}),\mathcal{C})+\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{2}}P_{\gamma},\mathcal{C})$
$\displaystyle\leq
359^{2}\operatorname{cost}(,\Gamma)+90^{2}+181^{2}\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(z_{\gamma})$

Summing the inequality of the third property of $\phi$ gives
$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(z_{\gamma})\leq
2k\cdot\Theta+\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(\phi(\gamma)))$.
Combined with Lemma 20 and the fact that the $N^{1}(\phi(\gamma))$ are
disjoints, we can therefore conclude:

$\displaystyle\operatorname{cost}(P,\mathcal{C})$ $\displaystyle\leq
359^{2}\operatorname{cost}(P,\Gamma)+90^{2}+181^{2}\cdot\left(2k\cdot\Theta+\sum_{\gamma\in\Gamma_{1}}\operatorname{cost}(N^{1}(\phi(\gamma))\cap
P,\Gamma)\right)$ $\displaystyle\leq
359^{2}\operatorname{cost}(P,\Gamma)+90^{2}+181^{2}\cdot\left(2k\cdot\Theta+\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}N^{1}(\phi(\gamma))\cap
P,\Gamma)\right)$ $\displaystyle\leq
359^{2}\operatorname{cost}(P,\Gamma)+90^{2}+181^{2}\cdot\left(2k\cdot\Theta+\operatorname{cost}(P,\Gamma)\right)$
$\displaystyle\leq O(1)(\operatorname{cost}(P,\Gamma)+2k\cdot\Theta).$

The rest of the proof is dedicated to the construction of a matching $\phi$
with the three desired properties. We construct a more general function
$\tilde{\phi}$ that maps centers of $\Gamma$ to net points. The restriction of
$\tilde{\phi}$ to $\Gamma_{1}$ will verify the desired properties. Let $l_{j}$
be the indices provided by Lemma 21. We have three cases: for all $j$ such
that $c_{j}$ is covered, let $\gamma^{2}_{j}\in\Gamma$ be an arbitrary element
covering it. For any net point $z$ of level $\lceil\log(n)\rceil$ such that
$\gamma^{2}_{j}\in N^{0.5}(z)$, we have by the triangle inequality
$\operatorname{dist}(c_{j},z)\leq\operatorname{dist}(c_{j},\gamma^{2}_{j})+\operatorname{dist}(\gamma^{2}_{j},z)\leq
2\cdot 2^{-\lceil\log(n)\rceil}+0.5\cdot 2^{-\lceil\log(n)\rceil}=2.5\cdot
2^{-\lceil\log(n)\rceil}$. In particular, $z$ is unavailable at the end of the
algorithm and $\gamma^{2}_{j}\in\Gamma_{2}$ by definition of $\Gamma_{2}$. We
define $\tilde{\phi}(\gamma^{2}_{j})=z_{j}^{l_{j}}$.

Otherwise for all $j$ such that at least one of the net points of the sequence
$(z_{j}^{l})_{l\geq l_{j}}$ is covered but not the last one. We define
$\lambda_{j}\geq l_{j}$ to be the smallest index such that for all
$l\geq\lambda_{j}$ $z_{j}^{l}$ is not covered, and $\gamma^{1}_{j}$ to be an
arbitrary element of $\Gamma$ that covers $z_{j}^{\lambda_{j}-1}$. We define
$\tilde{\phi}(\gamma^{1}_{j})=z_{j}^{\lambda_{j}}$. $\tilde{\phi}$ is
completed to be an arbitrary one-to-one matching between all remaining
$\gamma$ and all $z_{j}^{l_{j}}$, for $j$ such that none of the net points of
the sequence $(z_{j}^{l})_{l\geq l_{j}}$ are covered.

Note that the second item of lemma 21 guarantees that if $\gamma$ covers a net
point of a sequence, it can not cover a net point of another sequence: this
ensures that our definition of $\tilde{\phi}$ is consistent. We can now verify
that $\phi$ defined as the restriction of $\tilde{\phi}$ to $\Gamma_{1}$
verifies the three desired properties.

  * •

For all $j$, since $\lambda_{j}\geq l_{j}$, Lemma 21 ensures that for all
$\gamma\neq\gamma^{\prime}$ $N^{2}(\tilde{\phi}(\gamma))\cap
N^{2}(\tilde{\phi}(\gamma^{\prime}))=\emptyset$. In particular
$N^{1}(\tilde{\phi}(\gamma))\cap
N^{1}(\tilde{\phi}(\gamma^{\prime}))=\emptyset$.

  * •

If $\gamma\in\Gamma_{1}$, $\tilde{\phi}(\gamma)$ is not covered by $\Gamma$ by
construction.

  * •

For the third item, we distinguish three cases. For all $\gamma\in\Gamma$:

    * –

Either $\gamma$ is one of the $\gamma^{1}_{j}$. In that case, let $z$ be a net
point of same level as $\tilde{\phi}(\gamma)$ such that
$\operatorname{dist}(z,\gamma^{1}_{j})\leq 2^{-(\operatorname{level}(z)+1)}$.
$\gamma^{1}_{j}$ is covering $z_{j}^{\lambda_{j}-1}$ so $z$ could have been
chosen by the algorithm instead of $\tilde{\phi}(\gamma)$, therefore
$\operatorname{NoisyValue}(C)\leq\operatorname{NoisyValue}(\tilde{\phi}(\gamma))$.
Furthermore, $N^{1}(z_{\gamma})\subset N^{1}(z)$. Therefore,
$\operatorname{Value}(z_{\gamma})\leq\operatorname{Value}(z)$. By the
$\Theta$-threshold condition, if $\operatorname{NoisyValue}(z)<\Theta$ then

$\operatorname{Value}(z_{\gamma})\leq\operatorname{Value}(z)\leq
2\cdot\Theta.$

Otherwise if $\operatorname{NoisyValue}(z)\geq\Theta$ then

$\operatorname{Value}(z_{\gamma})\leq\operatorname{Value}(z)\leq\operatorname{NoisyValue}(z)/2\leq\operatorname{NoisyValue}(\tilde{\phi}(\gamma))/2\leq\operatorname{Value}(\tilde{\phi}(\gamma))/4.$

    * –

Or $\gamma$ is one of the $\gamma^{2}_{j}$. In that case,
$\tilde{\phi}(\gamma)$ does not need to verify the third property because
$\gamma_{j}^{2}\in\Gamma_{2}$

    * –

Or $\gamma$ is not one of the $\gamma^{1}_{j}$ or $\gamma^{2}_{j}$, then
$\tilde{\phi}(\gamma)$ is of the form $z_{j}^{l_{j}}$. By the lemma 21,
$\operatorname{NoisyValue}(z_{\gamma})\leq\operatorname{NoisyValue}(z_{j}^{l_{j}})$
because $z_{\gamma}$ is available at the end of the algorithm. Using the
$\Theta$-threshold condition, we have

$\displaystyle\operatorname{Value}(z_{\gamma})$
$\displaystyle\leq\operatorname{NoisyValue}(z_{\gamma})/2\leq\operatorname{NoisyValue}(z_{j}^{l_{j}})/2\leq\operatorname{Value}(z_{j}^{l_{j}})/4.\qed$

###  B.3 Properties of Algorithm 1: Proof of Lemma 21

Before proving Lemma 21, we show some preliminary results. We begin by
establishing a simple Lemma that sets a limit on the distance between two net
points that are selected during the same execution of loop line 6 of Algorithm
1.

######  Lemma 22.

Let $z_{j}^{l}$ and $z_{j}^{l^{\prime}}$ be two net points selected by the
algorithm at the $j$-th iteration of the loop line 6 of Algorithm 1, with
$l^{\prime}>l$. Then $\operatorname{dist}(z_{j}^{l},z_{j}^{l^{\prime}})\leq
8\cdot 2^{-\operatorname{level}(z_{j}^{l})}$.

###### Proof.

The distance between $z_{j}^{l}$ and one of its child is at most $4\cdot
2^{-\operatorname{level}(z_{j}^{l})}$. By induction, we have:

$\displaystyle\operatorname{dist}(z_{j}^{l},z_{j}^{l^{\prime}})$
$\displaystyle\leq\sum_{i=0}^{l^{\prime}-l-1}\frac{4\cdot
2^{-\operatorname{level}(z_{j}^{l})}}{2^{i}}\leq 8\cdot
2^{-\operatorname{level}(z_{j}^{l})}\qed$

The next Lemma is the key to prove that the procedure to compute the $l_{j}$’s
terminates and verifies the conditions of Lemma 21

######  Lemma 23.

If there exists at the end of the algorithm an available net point with value
greater than $2\cdot\Theta$, then for every $j,j^{\prime},l,l^{\prime}$ such
that $N^{2}(z_{j}^{l})\cap N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$
and $j<j^{\prime}$,

  * •

$\operatorname{level}(z_{j^{\prime}}^{1})\geq\operatorname{level}(z_{j}^{l})+4$

  * •

$\operatorname{NoisyValue}(z_{j}^{l+1})\geq\operatorname{NoisyValue}(z_{j^{\prime}}^{1})$

###### Proof.

Let $j,j^{\prime},l,l^{\prime}$ such that $N^{2}(z_{j}^{l})\cap
N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$ and $j<j^{\prime}$. We start
by proving the first point by contradiction: suppose that
$\operatorname{level}(z_{j^{\prime}}^{1})\leq\operatorname{level}(z_{j}^{l})+3$.
We extend the sequence starting from $z_{j^{\prime}}^{l^{\prime}}$ to prove
the existence of a ”descendant” of $z_{j^{\prime}}^{1}$ of level
$\operatorname{level}(z_{j}^{l})+3$ in $N^{3}(z_{j}^{l})$. We will then prove
that this descendant became unavailable when $c_{j}$ was selected,
contradicting Lemma 18.

More precisely, we pick recursively a sequence $y_{0},\dots,y_{i^{*}}$ such
that $y_{0}=z_{j^{\prime}}^{l^{\prime}}$ and $y_{i+1}$ is an arbitrary child
of $y_{i}$ such that in $N^{2}(z_{j}^{l})\cap N^{2}(y_{i+1})\neq\emptyset$ and
$\operatorname{level}(y_{i^{*}})\geq\operatorname{level}(z_{j}^{l})+4$. This
is doable since $N^{2}(z_{j}^{l})\cap
N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$. Thus exists a net point $y$
in the sequence
$z_{j^{\prime}}^{1},\dots,z_{j^{\prime}}^{l^{\prime}},y_{1},\dots,y_{i^{*}}$
of level $\operatorname{level}(z_{j}^{l})+3$. It should be noted that Lemma 18
guarantees the availability of all the net points within the sequence
$z_{j^{\prime}}^{1},\dots,z_{j^{\prime}}^{l^{\prime}},y_{1},\dots,y_{i^{*}}$,
including $y$, when the algorithm selects $z_{j^{\prime}}^{1}$.

We have $\operatorname{dist}(z_{j}^{l},y_{i^{*}})\leq 2\cdot
2^{-\operatorname{level}(z_{j}^{l})}+2\cdot
2^{-(\operatorname{level}(z_{j}^{l})+4)}\leq 16\cdot
2^{-\operatorname{level}(y)}+2^{-\operatorname{level}(y)}=17\cdot
2^{-\operatorname{level}(y)}$ and by Lemma 22
$\operatorname{dist}(y_{i^{*}},y)\leq 8\cdot 2^{-\operatorname{level}(y)}$. On
the other hand, a simple corollary of Lemma 22 is that
$\operatorname{dist}(c_{j},z_{j}^{l})\leq 8\cdot
2^{-\operatorname{level}(z_{j}^{l})}=64\cdot 2^{-\operatorname{level}(y)}$.
Using the triangle inequality, we get:

$\displaystyle\operatorname{dist}(c_{j},y)$
$\displaystyle\leq\operatorname{dist}(c_{j},z_{j}^{l})+\operatorname{dist}(z_{j}^{l},y_{i^{*}})+\operatorname{dist}(y_{i^{*}},y)$
$\displaystyle\leq 64\cdot 2^{-\operatorname{level}(y)}+17\cdot
2^{-\operatorname{level}(y)}+8\cdot 2^{-\operatorname{level}(y)}$
$\displaystyle=89\cdot 2^{-\operatorname{level}(y)}$

Therefore, $y\in N^{89}(z_{c_{j}})$ and this leads to a contradiction since
$y$ became unavailable when $c_{j}$ was selected and therefore is not
available when $z_{j^{\prime}}^{1}$ is picked because $j>j^{\prime}$. This
conclude the proof of the first point.

We turn to the second point. Applying Lemma 22, we get
$\operatorname{dist}(z_{j^{\prime}}^{l^{\prime}},z_{j^{\prime}}^{1})\leq
8\cdot 2^{-\operatorname{level}(z_{j^{\prime}}^{1})}\leq 0.5\cdot
2^{-\operatorname{level}(z_{j}^{l})}$. On the other hand $N^{2}(z_{j}^{l})\cap
N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$ gives
$\operatorname{dist}(z_{j}^{l},z_{j^{\prime}}^{l^{\prime}})\leq 2\cdot
2^{-\operatorname{level}(z_{j}^{l})}+2\cdot
2^{-\operatorname{level}(z_{j}^{l}+4)}\leq 2.5\cdot
2^{-\operatorname{level}(z_{j}^{l})}$. Using the triangle inequality, we have

$\displaystyle\operatorname{dist}(z_{j}^{l},z_{j^{\prime}}^{1})$
$\displaystyle\leq\operatorname{dist}(z_{j}^{l},z_{j^{\prime}}^{l^{\prime}})+\operatorname{dist}(z_{j^{\prime}}^{l^{\prime}},z_{j^{\prime}}^{1})$
$\displaystyle\leq 2.5\cdot 2^{-\operatorname{level}(z_{j}^{l})}+0.5\cdot
2^{-\operatorname{level}(z_{j}^{l})}$ $\displaystyle=3\cdot
2^{-\operatorname{level}(z_{j}^{l})}$

And $z_{j^{\prime}}^{1}$ is in the $3$-neighborhood of $z_{j}^{l}$. Now let
$w$ be a net point of level $\operatorname{level}(z_{j}^{l})+1$ such
$z^{1}_{j^{\prime}}\in N^{0.5}(w)$. Such a point exist by the covering
property of nets. We have $N^{1}(z_{j^{\prime}}^{1})\subset N^{1}(w)$, hence
$\operatorname{Value}(w)\geq 8\cdot\operatorname{Value}(z_{j^{\prime}}^{1})$.
Moreover $w$ is in $N^{4}(z_{j}^{l})$ and therefore $w$ is a child of
$z_{j}^{l}$. The algorithm picked $z_{j}^{l+1}$ over $w$, so
$\operatorname{NoisyValue}(z_{j}^{l+1})\geq\operatorname{NoisyValue}(w)$. We
know that at the end of the algorithm there exists an available net point with
value greater than $2\cdot\Theta$. By the $\Theta$-threshold condition, the
noisy value of this net point is at least $\Theta$. The algorithm picked
$z_{j^{\prime}}^{1}$ over this net points, so
$\operatorname{NoisyValue}(z_{j^{\prime}}^{1})\geq\Theta$ and

$\displaystyle\operatorname{NoisyValue}(z_{j}^{l+1})$
$\displaystyle\geq\operatorname{NoisyValue}(w)\geq\operatorname{Value}(w)/2\geq
4\operatorname{Value}(z_{j^{\prime}}^{1})\geq
2\operatorname{NoisyValue}(z_{j^{\prime}}^{1}).\qed$

We can now turn to the proof of Lemma 21, that we recall here for convenience:
See 21

###### Proof.

We describe a procedure to compute the $l_{j}$’s. Start with $l_{j}=1$ for all
$j$, and note that with this choice the first condition is verified by design
of the algorithm: when $z_{j}^{1}$ is picked (on line 5 of Algorithm 1), it
maximizes the noisy value among the available net points. In particular,
$z_{j}^{1}$ has value larger than any cell that is still available at the end
of the algorithm. Then, to enforce the second condition, we proceed as
follows: as long as we can find $j<j^{\prime}$ and $l\geq l_{j}$,
$l^{\prime}\geq l_{j^{\prime}}$ such that $N^{2}(z_{j}^{l})\cap
N^{2}(z_{j^{\prime}}^{l^{\prime}})\neq\emptyset$, we update $l_{j}=l_{j}+1$.

The first item of Lemma 23 guarantees that this procedure is well defined,
namely that $z_{j}^{l}$ is not the last net point of the sequence and that
$z_{j}^{l_{j}+1}$ does indeed exist. Furthermore, the second item of that
Lemma ensures that
$\operatorname{NoisyValue}(z_{j}^{l_{j}+1})\geq\operatorname{NoisyValue}(z_{j^{\prime}}^{1})$,
which itself is greater than $\operatorname{NoisyValue}(z)$ for any net point
$z$ that is available at the end of Algorithm 1. Therefore, the first
condition remains satisfied after each update. At each step, one of the
$l_{j}$ get incremented, so this procedure must terminates because by the
maximum level is $\lceil\log(n)\rceil$: when it ends, both conditions are
satisfied, which concludes the proof. ∎

##  Appendix C Missing Proofs for the $\varepsilon$-DP Algorithm in the Low
Dimensional Setting (Section 4)

Recall that by _low-dimensional setting_ we mean that we present an algorithm
whose additive error is exponential in the dimension $d$, i.e., whose additive
error is only small for small $d$.

###  C.1 A Differentially Private Constant-Factor Approximation Algorithm

In this subsection, we analyze Algorithm 2, and show Lemma 8.

See 8

To simplify the equations, we will note in the following
$\mathcal{E}(\varepsilon,\beta,n)=\frac{\log(n)^{2}\log(T)}{\varepsilon}\cdot\left(\log(1/\beta)+\sqrt{\log
T}\right)$. As a direct consequence of Lemma 17, we have the following fact:

######  Fact 24.

Algorithm 2 $\textsc{MakePrivate}(P,\varepsilon)$ satisfies
$\varepsilon$-differential privacy. Moreover, it holds at each time step $t$,
with probability $1-\beta$, that for all net point $z$,
$\big{|}c(z,t)-|N^{1}(z)\cap P_{t}|\big{|}\leq
d2^{2d}\mathcal{E}(\varepsilon,\beta,n).$

###### Proof.

This directly stems from Lemma 17, applied with $G=B(0,1)$ and $G_{j}$ be the
1-neighborhoods of all net points. We have $b=2^{2d}\log(n)$ and
$m=O\left(n^{d}\right)$ as guaranteed by Lemma 4. ∎

Using this fact, we can show that the output of Algorithm 2 satisfies the
conditions of Theorem 7:

######  Lemma 25.

Let $\Theta\geq 3R$, where $R=d\cdot 2^{2d}\mathcal{E}(\varepsilon,\beta,n)$
is the upper bound from 24. For each time step $t$, it holds with probability
$1-\beta$ that, for all net point $z$:

  * •

if $v(z,t)\geq\Theta$, then
$v(z,t)\in[\operatorname{Value}(z,t)/2,2\operatorname{Value}(z,t)]$,

  * •

otherwise, if $v(z,t)<\Theta$, then $\operatorname{Value}(z,t)\leq
2\cdot\Theta$.

###### Proof.

Fix a time step $t$. By 24, it holds with probability $1-\beta$ that for all
$z$, $\big{|}c(z,t)-|N^{1}(z)\cap P_{t}|\big{|}\leq R$.

Since $\operatorname{Value}(z,t)=2^{-2\ell}c(z,t)$ and $2^{-2\ell}\leq 1$,
this implies immediately that $|v(z,t)-\operatorname{Value}(z,t)|\leq R$. The
condition on $\Theta$ implies therefore that
$|v(z,t)-\operatorname{Value}(z,t)|\leq\Theta/3$.

First, in the case where $v(z,t)\geq\Theta$, then
$\operatorname{Value}(z,t)\geq\frac{2\Theta}{3}$. Therefore,
$v(z,t)\geq\operatorname{Value}(z,t)-\Theta/3\geq\operatorname{Value}(z,t)-\frac{\operatorname{Value}(z,t)}{2}$.
Similarly,
$v(z,t)\leq\operatorname{Value}(z,t)+\Theta/3\leq\frac{3\operatorname{Value}(z,t)}{2}$.
This concludes the first part: it holds that
$v(z,t)\in[\frac{\operatorname{Value}(z,t)}{2},\frac{3\operatorname{Value}(z,t)}{2}]$.

In the case where $v(z,t)<\Theta$, note that $\operatorname{Value}(z,t)\leq
v(z,t)+\Theta/3$: therefore, if $v(z,t)\leq\Theta$, then
$\operatorname{Value}(z,t)\leq 2\cdot\Theta$. ∎

Equipped with those results, we can conclude the proof of our constant-factor
approximation: essentially, we proved that the values computed with
MakePrivate are private and that they satisfy the assumption of Theorem 7.
Thus Theorem 7 shows that an algorithm with the desired approximation
guarantees exists.

###### Proof of Lemma 8.

We set the target probability $\beta=0.99$. The algorithm first uses
$\textsc{MakePrivate}(P,\varepsilon)$ to compute $v(A,t)$, and then
$\textsc{RecursiveGreedy}(v,k)$ to compute a solution for $k$-means. By 24,
the values $v(A,t)$ are private: by post-processing, the whole algorithm is
therefore $\varepsilon$-DP. For the approximation guarantee, Lemma 25 ensures
that the values $v$ satisfy the assumption of Theorem 7 with $\Theta=d\cdot
2^{2d}\mathcal{E}(\varepsilon,\beta,n)$, at each step with probability
$1-\beta$. Theorem 7 therefore shows that the solution computed at time $t$ is
an $(O(1),O(k)\cdot\Theta)$-approximation to $k$-means.

With $\beta=0.99$, the additive error is therefore of the order
$kd2^{2d}\mathcal{E}(\varepsilon,0.99,n)=kd2^{2d}\frac{\log(n)^{2}\log(T)^{3/2}}{\varepsilon}$.444Note
that we could have obtained an additive error $\frac{\log(n)\log(T)(\sqrt{\log
T}+\log(n))}{\varepsilon}$ instead, but we opted for simplicity, as in later
applications for high dimensions this will be anyway dominated by applications
of Lemma 5. ∎

###  C.2 Improving the approximation ratio from $O(1)$ to $(1+\alpha)w^{*}$-

In this section we show how to improve the approximation ratio of our
$\varepsilon$-differentially private algorithm from constant to
$(1+\alpha)w^{*}$, for any $0<\alpha\leq 1/4$, where $w^{*}$ is the
approximation ratio of the best non-differentially private, static $k$-means
clustering algorithm.

Given the mechanism $\mathcal{M}^{\prime}$ from Lemma 5 with $f\equiv 1$, our
implementation of the algorithm described in Section 4 in continual
observation setting follows the ideas described in Section 4.

Algorithm 4 $\textsc{Private-Clustering}(P,\varepsilon)$, given a non-private
algorithm $\mathcal{A}$

1:Let $v(\cdot,\cdot),c(\cdot,\cdot)=\textsc{MakePrivate}(P,\varepsilon)$

2:for Each time $t$ do

3: Let $c_{1}^{t},...,c_{k^{\prime}}^{t}$ be the centers computed by
$\textsc{RecursiveGreedy}(v(\cdot,t),k^{\prime})$

4: For $j$ in $1,...,k^{\prime}$, let $n_{j}^{t}$ be the estimated number of
points in cluster $C_{j}^{t}$ with mechanism $\mathcal{M}^{\prime}$ and
failure probability $\beta=0.01$

5: Let $\mathcal{S}^{t}$ be the solution computed via $\mathcal{A}$ on the
dataset $P^{\prime}_{t}$ containing $n_{j}^{t}$ copies of $c_{j}^{t}$, for all
$j$.

6:Output: at time $t$, $\mathcal{S}^{t}$.

See 3

###### Proof of Theorem 3.

This algorithm is private under continual observation: as shown in Lemma 8,
line 1 and 4 are private, and therefore robustness to post-processing ensures
privacy of the solution computed line 5.

For the utility guarantee, we reproduce here the analysis of [Ngu20]. He
showed that, for $k^{\prime}=k\alpha^{-O(d)}\log(n/\alpha)$, then
$\textsc{opt}_{k^{\prime}}\leq\alpha^{2}\textsc{opt}_{k}$, where
$\textsc{opt}_{k}$ is the optimal cost using $k$ centers and
$\textsc{opt}_{k^{\prime}}$ with $k^{\prime}$.

Therefore, the solution computed in our second step has cost
$O(\alpha^{2})\textsc{opt}_{k}+O(k^{\prime})\cdot\frac{d2^{2d}\log(n)^{2}\log(T)^{3/2}}{\varepsilon}$,
from Lemma 8. Lemma 14 ensures the clusters computed with
$\mathcal{M}^{\prime}$ yield a solution with additive error
$O(k^{\prime})\cdot\alpha^{-O(d)}\log(n)^{3}\log(T)^{3/2}/\varepsilon$, and
therefore the total additive error is
$k\cdot\alpha^{-O(d)}\log(n)^{4}\log(T)^{3/2}/\varepsilon$

In step 4, for each of the $k\cdot 2^{O(d)}\log(n)$ cells, the estimated count
from Lemma 17 is off by at most $\frac{\log(T)^{3/2}}{\varepsilon}\cdot
d\cdot\log(n/\beta)^{2}$.

This ensures that the dataset $P^{\prime}_{t}$ defined line 5 is a good proxy
for the dataset $P_{t}$ at time $t$: more precisely, for any candidate
solution $S$, we have that

$\displaystyle|\operatorname{cost}(P,S)-\operatorname{cost}(P^{\prime},S)|$
$\displaystyle\leq\frac{\log(T)^{3/2}}{\varepsilon}\cdot
d\cdot\log(n/\beta)^{2}+\sum_{j=1}^{k^{\prime}}\sum_{p\in{C^{\prime}}^{t}_{j}}|\operatorname{cost}(p,S)-\operatorname{cost}(c_{j}^{t},S)|$
$\displaystyle\leq\frac{\log(T)^{3/2}}{\varepsilon}\cdot
d\cdot\log(n/\beta)^{2}+\sum_{j=1}^{k^{\prime}}\sum_{p\in{C^{\prime}}^{t}_{j}}\alpha\operatorname{cost}(p,S)+\frac{1+\alpha}{\alpha}\operatorname{cost}(p,c_{j}^{t})$
$\displaystyle\leq\alpha\operatorname{cost}(p,S)+\frac{1+\alpha}{\alpha}\left(O(\alpha^{2})\textsc{opt}_{k}+k\cdot\alpha^{-O(d)}\frac{\log(n)^{4}\log(T)^{3/2}}{\varepsilon}\right)$
$\displaystyle\leq\alpha\operatorname{cost}(p,S)+O(\alpha)\textsc{opt}_{k}+k\cdot\alpha^{-O(d)}\frac{\log(n)^{4}\log(T)^{3/2}}{\varepsilon}$

Therefore, computing a $w^{*}$-approximation on this modified instance yields
a solution with cost at most $(1+\alpha)w^{*}\textsc{opt}_{k}+\frac{k\cdot
2^{O_{\alpha}(d)}\log(n)^{4}\cdot\log(T)^{3/2}}{\varepsilon}$, which concludes
the theorem. ∎

##  Appendix D Missing Proofs for the $\varepsilon$-DP Algorithm in the High
Dimensional Setting (Section 5)

Recall that by _high-dimensional setting_ we mean that we target an algorithm
whose additive error is only polynomial in the dimension $d$.

See 10

###### Proof.

The privacy guarantee follows from composition: computing $\mathcal{C}^{t}$ in
line 6 is $\varepsilon/(d+3)$-DP, the computation of
$\left\\{n_{j}^{t}\right\\}_{j,t}$ is $\varepsilon/(d+3)$-DP, similarly to the
computation of $\textsc{SumNorm}(j,t)$ and the one of each
$\textsc{Sum}(j,t)_{i}$ is $\varepsilon/(d+3)$-DP. Therefore, the algorithm is
$\varepsilon$-DP. We note that the clusters ${C^{\prime}}_{j}^{t}$ are not
released by the algorithm, and therefore leak no privacy.

The probability of success of the projection is $0.99$. In that case, with
high probability all points $\sqrt{\frac{d}{\hat{d}}}\pi(p)$ are in the ball
$B_{\hat{d}}(0,\log(n))$, the projection of line $3$ does not change the
location of points, as shown in [Ngu20]. This step is nonetheless necessary to
guarantee that the diameter (and therefore, the privacy loss) is bounded in
case the dimension reduction fails.

In the case the projection succeeds, the first bullet in the lemma statement
is as well a direct consequence of Theorem 3 and Lemma 5: the additive error
is dominated by the one from Theorem 3 and is
$O\left(k\alpha^{-O(\hat{d})}\log(n)^{4}\cdot\frac{\log(T)^{3/2}}{\varepsilon/(d+2)}\right)=d\mathcal{E}(\varepsilon,0.99,n)\log(n)^{2}k^{O(1)}$,
which concludes the first bullet of the lemma.

To show the second bullet, we use again Lemma 5 for the estimation of
$\textsc{Sum}(j,t)$: for each coordinate $i$, Lemma 5 is applied with function
$f_{i}(p^{\prime})=p_{i}$ (and it holds that $f_{i}(p)\leq 1$ since $p\in
B_{d}(0,1)$), and success probability $1-\beta/(d+3)$:

$\displaystyle\left\|\textsc{Sum}(j,t)-\sum_{p:p^{\prime}\in{C^{\prime}}_{j}^{t}}p\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{d}\left(\textsc{Sum}(j,t)_{i}-\sum_{p\in
C^{t}_{j}}p_{i}\right)^{2}$
$\displaystyle\leq\sum_{i=1}^{d}\left(k2^{O(\hat{d})}\log(n)^{3}\frac{\log(T)(\sqrt{\log
T}+\log(d/\beta))}{\varepsilon/d}\right)^{2}$ $\displaystyle\leq
d\cdot\left(k^{O(1)}\log(n)^{3}\frac{\log(T)(\sqrt{\log
T}+\log(d/\beta))}{\varepsilon/d}\right)^{2}$
$\displaystyle=d^{3}\cdot\left(\log(d)\mathcal{E}(\varepsilon,\beta,n)\log(n)k^{O(1)}\right)^{2}.$

Taking the square root concludes. Finally, we bound $\textsc{SumNorm}(j,t)$ by
a direct application of Lemma 5, using the function
$f(p^{\prime})=\|p\|_{2}^{2}$ (for which it holds again that
$f(p^{\prime})\leq 1$). With probability $1-\beta/(d+3)$ it holds that:

$\displaystyle\left|\sum_{x\in
C_{j}}\|x\|_{2}^{2}-\textsc{SumNorm}(j,t)\right|$ $\displaystyle\leq
k\alpha^{-O(\hat{d})}\log(n)^{3}\frac{\log(T)(\sqrt{\log
T}+\log(d/\beta))}{\varepsilon/d}$ $\displaystyle\leq
dk^{O(1)}\cdot\mathcal{E}(\varepsilon,\beta,n)\log n.$

This concludes the proof of the lemma. ∎

See 11

###### Proof.

Note that the call to Algorithm 3 fixes the target failure probability $\beta$
to $1/10$. The privacy guarantee follows from Lemma 10. For simplicity of
notation, we fix a time $t$ and remove mentions of the time in our analysis.

We need to show that the centers $\mathfrak{c}_{1},...,\mathfrak{c}_{k}$
computed by Algorithm 3 induce a solution in $\mathbb{R}^{d}$ that has cost
comparable to the one induced by the clustering
${C^{\prime}}_{1},...,{C^{\prime}}_{k}$ computed in Algorithm 3 in line $6$.

The implicit clustering is a good approximation. Note that $C^{\prime}_{j}$ is
a cluster for the dataset $P^{\prime}$: we let $C_{j}$ be the cluster of $P$
formed of points $p$ in $\mathbb{R}^{d}$ with $p^{\prime}\in C^{\prime}_{j}$.
We first show that assigning each of $C_{1},...,C_{k}$ to its mean
$\mu(C_{j})=\frac{\sum_{p\in C_{j}}p}{|C_{j}|}$ is a good approximation to the
$k$-means clustering for $P$.

The dimension reduction $\pi$ succeeds with probability $0.99$. In that case,
since the cost of any partition is preserved up to a factor $(1\pm\alpha)$,
then any $(a,b)$-approximation for $\pi(P)$ is an
$((1+\alpha)a,b)$-approximation for $P$. Now, Theorem 3 shows that, in
$\mathbb{R}^{\hat{d}}$, the clusters $C^{\prime}_{1},...,C^{\prime}_{k}$ are
an
$\left((1+\alpha)w^{*},k^{O(1)}\mathcal{E}(\varepsilon,1/10,n)\log(n)^{2}\right)$-approximate
solution for $\pi(P)$ with probability $9/10$.

Therefore, with a union-bound, it happens with probability at least $1-2\cdot
1/10=4/5$ (when both dimension reduction and the previous argument are
successful) that clustering each $C_{j}$ to its mean yields an
$\left((1+\alpha)w^{*},k^{O(1)}\mathcal{E}(\varepsilon,1/10,n)\log(n)^{2}\right)$-approximate
solution for $P$.

Bounding the error in each cluster. To conclude the proof of the theorem it is
enough to show that for all $j\in\left\\{1,...,k\right\\}$,
$\operatorname{cost}(C_{j},\mathfrak{c}_{j})\leq\operatorname{cost}(C_{j},\mu(C_{j}))+k^{O(1)}\cdot
d^{2}\cdot\frac{\log(n)^{4}\log(T)^{3/2}}{\varepsilon}.$

To do so, we first prove that $\mathfrak{c}_{j}$ is close to
$\mu(C_{j})=\frac{\sum_{p\in C_{j}}p}{|C_{j}|}$ and then bound the desired
cost difference: For this, we use that both the numerator and denominator are
well approximated. Indeed, Lemma 10 ensures that for $\beta=1/10$:

$\displaystyle|n_{j}-|C_{j}||$ $\displaystyle\leq\mathfrak{e},$ (4)
$\displaystyle\left\|\textsc{Sum}(j)-\sum_{p\in C_{j}}p\right\|_{\infty}$
$\displaystyle\leq\mathfrak{e}\cdot d^{1/2}\log(d),$ (5)

where $\mathfrak{e}=k^{O(1)}\mathcal{E}(\varepsilon,1/10,n)\cdot
d\log(n)=k^{O(1)}d\cdot\log(T)^{3/2}\log(n)^{3}/\varepsilon$

If a cluster contains fewer than $2\cdot\mathfrak{e}$ points, then regardless
of the position of $\mathfrak{c}_{j}$ its $1$-means cost is upper-bounded by
$2\mathfrak{e}$ – as the diameter of $P$ is $1$ in $\mathbb{R}^{d}$– and this
is accounted for by the additive error. Otherwise, we can show that
$\mathfrak{c}_{j}$ is very close to $\mu(C_{j})$, using Equation 5, Equation
4, and the fact that $|C_{j}|\geq 2\mathfrak{e}$ for all $j$ as follows:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{n_{j}}-\mu(C_{j})\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\left(\frac{\textsc{Sum}(j)}{n_{j}}-\frac{\textsc{Sum}(j)}{|C_{j}|}\right)+\left(\frac{\textsc{Sum}(j)}{|C_{j}|}-\frac{|C_{j}|\mu(C_{j})}{|C_{j}|}\right)\right\|_{2}$
(4) $\displaystyle\leq$
$\displaystyle\left\|\textsc{Sum}(j)\right\|_{2}\left(\frac{1}{|C_{j}|-\mathfrak{e}}-\frac{1}{|C_{j}|}\right)+\frac{\left\|\textsc{Sum}(j)-|C_{j}|\mu(C_{j})\right\|_{2}}{|C_{j}|}$

Using Eq. 5, and $(1-x)^{-1}\leq 1+2x$ for $x\leq 1/2$, this is upper-bounded
by:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{n_{j}}-\mu(C_{j})\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\left\|\textsc{Sum}(j)\right\|_{2}\left(\frac{1}{|C_{j}|}+\frac{2\mathfrak{e}}{|C_{j}|^{2}}-\frac{1}{|C_{j}|}\right)+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}$
$\displaystyle\leq$
$\displaystyle\frac{|C_{j}|\left\|\mu(C_{j})\right\|_{2}+\left\|\textsc{Sum}(j)-|C_{j}|\mu(C_{j})\right\|_{2}}{|C_{j}|}\cdot\frac{2\mathfrak{e}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}$
(Eq. 5) $\displaystyle\leq$
$\displaystyle\left(\left\|\mu(C_{j})\right\|_{2}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}\right)\frac{2\mathfrak{e}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}$
$\displaystyle C_{j}\subset B_{d}(0,1):$ $\displaystyle\leq$
$\displaystyle\left(1+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}\right)\frac{2\mathfrak{e}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}}{|C_{j}|}$
(8) $\displaystyle\leq$
$\displaystyle\frac{O(d^{1/2}\log(d)\cdot\mathfrak{e})}{|C_{j}|},$

where the last line follows from $|C_{j}|\geq 2\mathfrak{e}$.

Finally, we get, using the folklore property that for any set $X$ and point
$y$,
$\operatorname{cost}(X,y)=\operatorname{cost}(X,\mu(X))+|X|\left\|\mu(X)-y\right\|_{2}^{2}$
(see e.g. [BBC+19]):

$\displaystyle\operatorname{cost}(C_{j},\mathfrak{c}_{j})$
$\displaystyle=\operatorname{cost}(C_{j},\mu(C_{j}))+|C_{j}|\cdot\left\|\mathfrak{c}_{j}-\mu(C_{j})\right\|_{2}^{2}$
$\displaystyle\leq\operatorname{cost}(C_{j},\mu(C_{j}))+\frac{O(\left(d^{1/2}\log(d)\cdot\mathfrak{e}\right))^{2}}{|C_{j}|}$
$\displaystyle\leq\operatorname{cost}(C_{j},\mu(C_{j}))+k^{O(1)}\cdot
d^{2}\log(d)^{2}\cdot\frac{\log(n)^{3}\log(T)^{3/2}}{\varepsilon},$

where the last line uses again $|C_{j}|\geq 2\mathfrak{e}$. Summing over all
clusters concludes the proof: the additive error is dominated by the additive
error incurred by the algorithm of Theorem 3, and is $k^{O(1)}\cdot
d^{2}\cdot\frac{\log(n)^{4}\log(T)^{3/2}}{\varepsilon}$. ∎

###  D.1 Boosting the Success Probabilities (Section 5.2)

To boost the probabilities so that the algorithm outputs solutions that are
good at all steps simultaneously, we will run several copies and at each time
output the solution with best cost. For that, it is necessary to measure the
cost of a cluster. Our first lemma formalizes how to do this without having
access to its center – which will be helpful to not lose additional privacy.

######  Lemma 26.

For any set $X$, $\operatorname{cost}(X,\mu(X))=\sum_{x\in
X}\|x\|_{2}^{2}-\frac{\left\|\sum_{y\in X}x\right\|_{2}^{2}}{|X|}$.

###### Proof.

Using properties of squared distances, we have the following:

$\displaystyle\operatorname{cost}(X,\mu(X))$ $\displaystyle=\sum_{x\in
X}\|x-\mu(X)\|_{2}^{2}=\sum_{x\in X}\sum_{i=1}^{d}|x_{i}-\mu(X)_{i}|^{2}$
$\displaystyle=\sum_{x\in
X}\sum_{i=1}^{d}x_{i}^{2}+\mu(X)_{i}^{2}-2x_{i}\mu(X)_{i}$
$\displaystyle=\sum_{x\in
X}\|x\|_{2}^{2}+\|\mu(X)\|_{2}^{2}-2\sum_{i=1}^{d}x_{i}\mu(X)_{i}.$

Here, we note that $\mu(X)=\frac{1}{|X|}\sum_{y\in X}y$: therefore,
$\sum_{x\in
X}\|\mu(X)\|_{2}^{2}=|X|\cdot\|\mu(X)\|_{2}^{2}=\frac{\left\|\sum_{y\in
X}y\right\|_{2}^{2}}{|X|}$. Furthermore, $\mu(X)_{i}=\frac{1}{|X|}\sum_{y\in
X}y_{i}$, and so:

$\displaystyle\sum_{x\in X}\sum_{i=1}^{d}x_{i}\mu(X)_{i}$
$\displaystyle=\sum_{i=1}^{d}\left(\frac{1}{|X|}\sum_{y\in
X}y_{i}\right)\left(\sum_{x\in X}x_{i}\right)$
$\displaystyle=\frac{1}{|X|}\sum_{i=1}^{d}\left(\sum_{x\in X}x_{i}\right)^{2}$
$\displaystyle=\frac{\left\|\sum_{x\in X}x\right\|_{2}^{2}}{|X|}.$

Combining those equations concludes the lemma:

$\displaystyle\operatorname{cost}(X,\mu(X))$ $\displaystyle=\sum_{x\in
X}\|x\|_{2}^{2}+\|\mu(X)\|_{2}^{2}-2\sum_{i=1}^{d}x_{i}\mu(X)_{i}$
$\displaystyle=\sum_{x\in X}\|x\|_{2}^{2}-\frac{\left\|\sum_{y\in
X}x\right\|_{2}^{2}}{|X|}.\qed$

See 13

###### Proof.

Fix any time $t$ and cluster $C^{\prime}_{j}$. We note that, since
$C^{\prime}_{j}$ is a cluster of points in dimension $\hat{d}=O(\log(k))$, all
calls to Lemma 5 incur with probability $1-\beta/T$ an error
$k^{O(1)}\log(n)^{3}\cdot\frac{\log(T)}{\varepsilon}\left(\sqrt{\log
T}+\log(T/\beta)\right)$.

From Lemma 26, it holds that

$\operatorname{cost}(C_{j},\mu(C_{j}))=\sum_{x\in
C_{j}}\|x\|_{2}^{2}-\frac{\left\|\sum_{x\in
C_{j}}x\right\|_{2}^{2}}{|C_{j}|}.$ (9)

We bound the difference with
$\textsc{SumNorm}(j)-\frac{\left\|\textsc{Sum}(j)\right\|_{2}^{2}}{n_{j}}$
term by term, and let
$\mathfrak{e}^{\prime}:=dk^{O(1)}\cdot\mathcal{E}(\varepsilon,\beta/T,n)\log
n=dk^{O(1)}\frac{\log(n)^{3}\log(T)}{\varepsilon}\log(T/\beta)$ for
simplicity.

Essentially, Lemma 10 ensures that, for any time step $t$, it holds with
probability at least $1-\beta/T$ that all $d+3$ values returned by Algorithm 3
are within their respective error bounds, i.e., $n_{j}$ is a good estimate of
$|C_{j}|$, $\textsc{SumNorm}(j)$ is a good estimate of $\sum_{p\in
C_{j}}\left\|p\right\|_{2}$, and $\textsc{Sum}(j)$ is a good estimate of
$\sum_{p\in C_{j}}p$ (as the calls to the algorithm of Lemma 5 are with
parameter $\beta/(dT+3T)$, and there are $d+3$ calls in Algorithm 3). By a
union-bound, those properties hold with probability $1-\beta$ for all time
steps simultaneously.

_Case 1:_ First, in the case where $|C_{j}|\leq 2\mathfrak{e}^{\prime}$, then
Lemma 10 and the fact that all points belong to the unit ball, i.e.,
$\|p\|_{2}\leq 1$, ensure that $\textsc{Sum}(j)\leq\|\sum_{p:p^{\prime}\in
C_{j}}p\|_{2}+\|\textsc{Sum}(j)-\sum_{p:p^{\prime}\in C_{j}}p\
\|_{2}\leq\sum_{p:p^{\prime}\in
C_{j}}\|p\|_{2}+\|\textsc{Sum}(j)-\sum_{p:p^{\prime}\in C_{j}}p\|_{2}\leq
2\mathfrak{e}^{\prime}+O(d^{1/2}\log(d)\mathfrak{e}^{\prime})\leq
O(d^{1/2}\log(d)\mathfrak{e}^{\prime})$. We can bound SumNorm similarly: Lemma
10 shows that $\textsc{SumNorm}(j,t)\leq\sum_{x\in
C_{j}^{t}}\|x\|_{2}^{2}+\mathfrak{e}^{\prime}\leq|C_{j}^{t}|+\mathfrak{e}^{\prime}\leq
3\mathfrak{e}^{\prime}$. Therefore, with probability at least $1-\beta$,
$\left|\operatorname{cost}(C_{j},\mu(C_{j}))-\left(\textsc{SumNorm}(j,t)-\frac{\left\|\textsc{Sum}(j)\right\|_{2}^{2}}{n_{j}}\right)\right|\leq
O(d^{1/2}\log(d)\mathfrak{e}^{\prime})$, as all terms are at most
$O(d^{1/2}\log(d)\mathfrak{e}^{\prime})$, which concludes this case.

_Case 2:_ In the other case, when $|C_{j}|\geq 2\mathfrak{e}^{\prime}$, then,
Lemma 10 with failure probability $\beta/T$ ensures that, with probability
$1-\beta/T$ it holds that for all cluster $C_{j}$,

$\displaystyle\left|\sum_{x\in
C_{j}}\|x\|_{2}^{2}-\textsc{SumNorm}(j,t)\right|$ $\displaystyle\leq
dk^{O(1)}\cdot\mathcal{E}(\varepsilon,\beta/T,n)\log n=\mathfrak{e}^{\prime}.$

A union-bound over all time steps $t$ ensures that this inequality holds with
probability $1-\beta$ for all time steps simultaneously.

For the second term of Equation 9, we use exactly the same reasoning as in
Equation (8) from the proof of Lemma 11: it holds with probability $1-\beta$,
for any time $t$:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{|n_{j}|}-\mu(C_{j})\right\|_{2}\leq\frac{\mathfrak{e}^{\prime}d^{1/2}\log(d)}{|C_{j}|}.$

We formally prove this claim in 27. Furthermore, we know that
$\left|n_{j}-|C_{j}|\right|\leq\mathfrak{e}^{\prime}$ and
$\|\mu(C_{j})\|_{2}^{2}\leq 1$ for all $1\leq j\leq k$. Therefore, the
following holds:

$\displaystyle\frac{\left\|\textsc{Sum}(j)\right\|_{2}^{2}}{n_{j}}$
$\displaystyle\geq
n_{j}\cdot\left(\|\mu(C_{j})\|_{2}-\left\|\frac{\textsc{Sum}(j)}{n_{j}}-\mu(C_{j})\right\|_{2}\right)^{2}$
$\displaystyle\geq(|C_{j}|-\mathfrak{e}^{\prime})\cdot\left(\|\mu(C_{j})\|_{2}^{2}-2\|\mu(C_{j})\|_{2}\frac{\mathfrak{e}^{\prime}d^{1/2}\log(d)}{|C_{j}|}\right)$
$\displaystyle\geq|C_{j}|\cdot\|\mu(C_{j})\|_{2}-\mathfrak{e}^{\prime}\|\mu(C_{j})\|_{2}^{2}-2\|\mu(C_{j})\|_{2}\mathfrak{e}^{\prime}d^{1/2}\log(d)$
$\displaystyle\geq|C_{j}|\cdot\|\mu(C_{j})\|_{2}-\mathfrak{e}^{\prime}-2\mathfrak{e}^{\prime}d^{1/2}\log(d)$
$\displaystyle\geq|C_{j}|\cdot\|\mu(C_{j})\|_{2}-k^{O(1)}\frac{d^{3/2}\log(d)\log(n)^{3}\log(T)}{\varepsilon}\log(T/\beta).$

One can similarly show that

$\frac{\left\|\textsc{Sum}(j)\right\|_{2}^{2}}{n_{j}}\leq|C_{j}|\cdot\|\mu(C_{j})\|_{2}+k^{O(1)}\cdot\frac{d^{3/2}\log(d)\cdot\log(n)^{3}\log(T)\log(T/\beta)}{\varepsilon}.$

Therefore, we can conclude:

$\left|\operatorname{cost}(C_{j},\mu(j))-\left(\textsc{SumNorm}(j)-\frac{\left\|\textsc{Sum}(C_{j})\right\|_{2}^{2}}{n_{j}}\right)\right|\leq
k^{O(1)}\cdot\frac{d^{3/2}\log(d)\cdot\log(n)^{3}\log(T)\log(T/\beta)}{\varepsilon}$

∎

######  Fact 27.

Let
$\mathfrak{e}^{\prime}=k^{O(1)}\frac{d\log(n)^{3}\log(T)}{\varepsilon}\log(T/\beta)$,
and $C_{j}$ be a cluster with $|C_{j}|\geq 2\mathfrak{e}^{\prime}$. With
probability $1-\beta$, it holds for any time $t$ that:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{|n_{j}|}-\mu(C_{j})\right\|_{2}\leq\frac{\mathfrak{e}^{\prime}d^{1/2}\log(d)}{|C_{j}|}.$

###### Proof.

This proof is identical to the one for showing Equation (8), using the bound
$|C_{j}|\geq\mathfrak{e}^{\prime}$ instead of $|C_{j}|\geq\mathfrak{e}$. We
repeat it for completeness. Lemma 10 ensures that with probability $1-\beta$:

$\displaystyle|n_{j}-|C_{j}||$ $\displaystyle\leq\mathfrak{e}^{\prime},$ (10)
$\displaystyle\left\|\textsc{Sum}(j)-\sum_{p\in C_{j}}p\right\|_{\infty}$
$\displaystyle\leq\mathfrak{e}^{\prime}\cdot d^{1/2}\log(d),$ (11)

Combining triangle inequality and Eq. 10, we have:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{n_{j}}-\mu(C_{j})\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\left(\frac{\textsc{Sum}(j)}{n_{j}}-\frac{\textsc{Sum}(j)}{|C_{j}|}\right)+\left(\frac{\textsc{Sum}(j)}{|C_{j}|}-\frac{|C_{j}|\mu(C_{j})}{|C_{j}|}\right)\right\|_{2}$
(10) $\displaystyle\leq$
$\displaystyle\left\|\textsc{Sum}(j)\right\|_{2}\left(\frac{1}{|C_{j}|-\mathfrak{e}^{\prime}}-\frac{1}{|C_{j}|}\right)+\frac{\left\|\textsc{Sum}(j)-|C_{j}|\mu(C_{j})\right\|_{2}}{|C_{j}|}$

Using Eq. 11, and $(1-x)^{-1}\leq 1+2x$ for $x\leq 1/2$, this is upper-bounded
by:

$\displaystyle\left\|\frac{\textsc{Sum}(j)}{n_{j}}-\mu(C_{j})\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\left\|\textsc{Sum}(j)\right\|_{2}\left(\frac{1}{|C_{j}|}+\frac{2\mathfrak{e}^{\prime}}{|C_{j}|^{2}}-\frac{1}{|C_{j}|}\right)+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}$
$\displaystyle\leq$
$\displaystyle\frac{|C_{j}|\left\|\mu(C_{j})\right\|_{2}+\left\|\textsc{Sum}(j)-|C_{j}|\mu(C_{j})\right\|_{2}}{|C_{j}|}\cdot\frac{2\mathfrak{e}^{\prime}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}$
(Eq. 5) $\displaystyle\leq$
$\displaystyle\left(\left\|\mu(C_{j})\right\|_{2}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}\right)\frac{2\mathfrak{e}^{\prime}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}$
$\displaystyle C_{j}\subset B_{d}(0,1):$ $\displaystyle\leq$
$\displaystyle\left(1+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}\right)\frac{2\mathfrak{e}^{\prime}}{|C_{j}|}+\frac{d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime}}{|C_{j}|}$
$\displaystyle\leq$
$\displaystyle\frac{O(d^{1/2}\log(d)\cdot\mathfrak{e}^{\prime})}{|C_{j}|},$

where the last line follows from $|C_{j}|\geq 2\mathfrak{e}^{\prime}$. ∎

We know from 11 that the solution at any time step is correct with probability
$4/5$, and moreover Lemma 13 estimates with probability $1-\beta$ the cost at
any time step. Knowing $T$ in advance, one solution to boost probabilities
would be to run $\lfloor\log(T)\rfloor$ independent copies of
$\textsc{Private-$k$-Means}(P,\varepsilon/\log(T),1/5)$: at each time step at
least one of those copies will be a good approximation with probability
$1-1/5^{\lfloor\log(T)\rfloor}\approx 1-1/T$. Selecting the cheapest according
to Lemma 13 would therefore conclude that with constant probability the
solution at each time $t$ is a good approximation.

In the case where $T$ is unknown, one can instead run $\lfloor\log(T)\rfloor$
instances of $\textsc{Private-$k$-Means}(P,\varepsilon,1/5)$, with parameters
defined as follows: the instance started at time $t=2^{i}$ has privacy
parameter $\varepsilon_{i}$. Starting an instance at time $2^{i}$ means that
we create a stream that inserts one by one each point currently in the data,
in the order they appeared, and run a copy of algorithm Private-$k$-Means
starting with this stream and continuing with the actual updates.

This whole algorithm is $O(\sum\varepsilon_{i})$-DP, using standard
composition. Furthermore, the utility increases only by a factor
$\max_{i\leq\log(T)}\frac{1}{\varepsilon_{i}}$. We will use the fact that
$s(\kappa):=\sum i^{-1-\kappa}=O(1/\kappa)$ and
$\max_{i\leq\log(T)}{i^{1+\kappa}}=\log(T)^{1+\kappa}$: thus, setting
$\varepsilon_{i}=\frac{\varepsilon}{s(\kappa)i^{1+\kappa}}$ ensures that, with
constant probability, the algorithm is $\varepsilon$-differentially private
and gives essentially an $\left((1+\alpha)w^{*},k^{O(1)}\cdot
d^{2}\log(1/\beta)\log(n)^{4}\log(T)^{3+\kappa}\cdot{\varepsilon^{-1}}\right)$-approximation
to $k$-means. The next algorithm and lemma make formal this proof sketch.

The formal algorithm we use to boost the probabilities is the following:

Algorithm 5 BoostProbabilities$(P,\varepsilon,\beta,\kappa)$

1:let $s(\kappa)=\sum_{i\geq 1}i^{-1-\kappa}$, and $c_{1},c_{2}$ be two large
enough constants ($c_{1}\geq
3/\log(5/2),c_{2}\geq\log(\pi^{2}/6\beta)/\log(5/2)$)

2:For $i=\left\\{1,...,c_{1}\lfloor\log(t)\rfloor+c_{2}\right\\}$, run a copy
of $\textsc{Private-$k$-Means}(P,\varepsilon/(s(\kappa)i^{1+\kappa}),1/5)$.

3:Estimate the cost of each solution using Lemma 13.

4:Output centers corresponding to the solution with cheapest cost.

The next lemma is a more precise formulation of Theorem 1 – which directly
follows by setting $\kappa=0.001$.

See 12

###### Proof.

We show that algorithm 5 satisfies the lemma. The composition theorem and the
properties of Algorithm 3 shown in Lemma 11 ensure that the resulting
algorithm is $\varepsilon$-DP as
$\sum_{i=1}^{c_{1}\log(T)+c_{2}}\frac{\varepsilon}{s(\kappa)i^{1+\kappa}}\leq\varepsilon$
(by definition of $s(\kappa)$).

Furthermore, each instance provides at time $t$, with probability $4/5$, an
approximation with multiplicative factor unchanged compared to Lemma 11, and
additive error increased (due to the rescaling of $\varepsilon$) by a factor
$s(\kappa)i^{1+\kappa}\leq
s(\kappa)(c_{1}\log(t)+c_{2})^{1+\kappa}=O(\kappa)\cdot\left(\log(T)^{1+\kappa}+\log(1/\beta)^{1+\kappa}\right)$.

Since all copies are independent, at least one succeeds with probability
$1-(2/5)^{c_{1}\log(T)+c_{2}}\geq 1-\frac{6\beta}{\pi^{2}\cdot T^{2}}$.
Namely, at least one solution is an approximation with multiplicative factor
$(1+\alpha)w^{*}$ and additive at most (where we took the maximum for each
exponent of the additive terms from lemma 11 and lemma 13):

$\displaystyle
k^{O(1)}\cdot\frac{d^{2}\cdot\log(n)^{4}\log(T)\log(T/\beta)}{\varepsilon/(s(k)i^{1+\kappa})}$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
k^{O(1)}\cdot\frac{d^{2}\cdot\log(n)^{4}\log(T)^{3+\kappa}\log(1/\beta)}{\varepsilon}$

We conclude the proof with a union-bound over all $T$ steps: for this choice
of $c_{1},c_{2}$, with probability $1-\frac{\beta\cdot
6}{\pi^{2}}\cdot\sum_{t=1}^{T}1/t^{2}\geq 1-\beta$, the solution is correct at
any time $t$. ∎

##  Appendix E Missing Proof for Privately Counting in Clusters (Section 6)

In this section we show the proof of Lemma 14, which is the last missing piece
to complete the proof of the crucial Lemma 5.

To define the sets $G_{1},...G_{m}$, we make use of a _hierarchical
decomposition_
$\mathcal{G}=\left\\{\mathcal{G}_{1},...,\mathcal{G}_{\lceil\log(n)\rceil}\right\\}$
with the following properties:

  1. 1.

for all $i=0,...,\lceil\log(n)\rceil$, $\mathcal{G}_{i}$ is a partition of
$B_{d}(0,1)$. Each part $A$ of $\mathcal{G}_{i}$ is called a cell of level
$i$, denoted $\operatorname{level}(A)=i$, and has diameter at most $2^{-i}$.

  2. 2.

The partition $\mathcal{G}_{i+1}$ is a refinement of the partition
$\mathcal{G}_{i}$, namely every part of $\mathcal{G}_{i+1}$ is strictly
contained in one part of $\mathcal{G}_{i}$. $\mathcal{G}_{0}$ is merely
$\left\\{B_{d}(0,1)\right\\}$.

  3. 3.

for any point $p\in B_{d}(0,1)$, any level $i$ and any $r\geq 1$, the ball
$B_{d}(p,r2^{-i})$ intersects at most $r^{O(d)}$ many cells of level $i$.

For a cell $A$ of level $i+1$, we denote by $\textsc{Parent}(A)$ the unique
cell of level $i$ containing $A$.

The sets $G_{1},...,G_{m}$ on which we will apply Lemma 17 are the cells at
each level. Since they are $\log(n)$ levels, each being a partition, any point
from $B_{d}(0,1)$ appears in $b=\log(n)$ sets. Furthermore,
$m=O\left(n^{d}\right)$ (by the third property with $r=1/n$), and so Lemma 17
applies with additive error
$O\left(d\cdot\log(n)^{2}\cdot\frac{\log(T)}{\varepsilon}\cdot\left(\sqrt{\log(T)}+\log(1/\beta)\right)\right)$.

Therefore, in order to maintain $\sum_{p\in C_{i}^{t}}f(p)$, we only need to
show how to express this sum with few $\sum_{p\in G_{i}\cap P_{t}}f(p)$ (where
$P_{t}$ is the dataset at time $t$). For this, we use the hierarchical
decomposition described above, and identify few cells that are far from any
center, compared to their diameter. All points in such a cell are roughly
equivalent for the given clustering, and therefore we can serve them all by
the same center. This idea is formalized in the next lemma:

See 14

###### Proof.

Let $\ell=\lceil 10/\alpha\rceil$. For any cell $A$ of the decomposition, fix
an arbitrary point $v_{A}\in A$. We call the $\ell$-neighborhood of $A$ all
cells at the same level as $A$ that intersect with the ball $B\left(v_{A},\ell
2^{-\operatorname{level}(A)}\right)$. Note that this includes $A$. Let
$\mathcal{A}$ be the set of cells $A$ such that their $\ell$-neighborhood does
not contain a center of $\mathcal{C}$, but the $\ell$-neighborhood of
$\textsc{Parent}(A)$ does contain one. Add furthermore to $\mathcal{A}$ the
cells at level $\lceil\log(n)\rceil$ that contain a center in their
$\ell$-neighborhood.

We first bound the size of the set $\mathcal{A}$ obtained. For this, we will
count for each level how many cells have a center in their
$\ell$-neighborhood, and how many children each cell has. First, for a fixed
level $i$ and center $c^{*}$, the decomposition ensures that there are at most
$\ell^{O(d)}$ many cells intersecting $B_{d}(c^{*},2\ell 2^{-i})$. Note that
any cell $A$ that contains $c^{*}$ in its $\ell$-neighborhood must intersect
$B_{d}(c^{*},2\ell 2^{-i})$: indeed, if $B$ is the cell containing $c^{*}$
this means there is a point in $B$ at distance at most $\ell 2^{-i}$ of
$v_{A}$. Since the diameter of $B$ is at most $2^{-i}$, $c^{*}$ is at distance
at most $\ell 2^{-i}+2^{-i}$ of $v_{A}$, and therefore $A$ intersects with the
ball $B_{d}(c^{*},2\ell 2^{-i})$.

Now, using the third property of decomposition, any cell $A$ of level $i$ is
the parent of at most $2^{O(d)}$ many cells. Indeed, all those cells are
included in $A$: this means they are contained in a ball of radius $2^{-i}$,
and since they are at level $i+1$, third property ensures that there are at
most $2^{O(d)}$ many of them.

Therefore, at any level, at most $k\cdot\ell^{O(d)}=k\cdot\alpha^{-O(d)}$
cells $A$ are added, as $N^{\ell}(\textsc{Parent}(A))$ must contain one
center. Hence, $|\mathcal{A}|\leq k\cdot\alpha^{-O(d)}\log(n)$.

$\mathcal{A}$ is a partition of $B_{d}(0,1)$. Now, we show that $\mathcal{A}$
is a partition of $B_{d}(0,1)$. For this, we observe that if a cell $A$
contains a center in its $\ell$-neighborhood, then $\textsc{Parent}(A)$ also
contains one. First, we argue that the cells in $\mathcal{A}$ cover the whole
unit ball. For a point $p$ in the ball, consider the sequence of parts
containing it. There are two cases: Either the smallest part at level
$\lceil\log(n)\rceil$ contains a center in its $\ell$-neighborhood, and, thus,
it is added to $\mathcal{A}$; or it does not, and then the largest part of the
sequence that does not contain a center in its $\ell$-neighborhood is added to
$\mathcal{A}$. Note that such a largest part must exist, as the cell of level
$0$ contains all centers.

Next we argue that all cells in $\mathcal{A}$ are disjoint. Consider two
intersecting cells $A$ and $B$ in $\mathcal{A}$. By property 2 of the
decomposition, it must be that one is included in the other: assume wlog that
$A\subset B$ (therefore $\operatorname{level}(A)>\operatorname{level}(B)$).
Note that if $A$ is on level $\log(n)$ and has a center in its
$\ell$-neighborhood, then trivially $N^{\ell}(\textsc{Parent}(A))$ contains a
center. Thus, for all $A\in\cal A$ it holds that
$N^{\ell}(\textsc{Parent}(A))$ contains a center. But
$\textsc{Parent}(A)\subseteq B$: therefore, $N^{\ell}(B)$ contains a center,
which implies that $B\notin\mathcal{A}$. Thus, $A$ and $B$ cannot be both in
$\mathcal{A}$, which concludes the proof that $\mathcal{A}$ is a partition of
$B_{d}(0,1)$.

Assigning cells to center. We can now define $c$ as follows: for each cell
$A\in\mathcal{A}$, we define
$a(A)=\operatorname{argmin}_{i}\operatorname{dist}(v_{A},c_{i})$ to be the
closest point from $\mathcal{C}$ to $v_{A}$.

We first define an assignment for a cell $A\in\mathcal{A}$ at level $\log(n)$.
In this case, triangle inequality ensures that paying the diameter of $A$ for
each point allows to serve all points in $A$ with the same center. Formally,
let $a(A)$ be the closest center to $v_{A}$. For any $p\in A$, we have using
16:

$\displaystyle\operatorname{dist}(p,a(A))^{2}$