$\operatorname{dist}(x_{i}^{l},y_{j_{max}})\leq
2^{-\operatorname{level}(x_{i}^{l})}+2^{-\operatorname{level}(y_{j_{max}})}\leq
2\cdot 2^{-\operatorname{level}(x_{i}^{l})}=4\cdot
2^{-\operatorname{level}(y)}.$

Applying Lemma D.6 to the sequence
$B(y,2^{-\operatorname{level}(y)}),\dots,B(y_{j_{max}},2^{-\operatorname{level}(y_{j_{max}})})$,
we get $\operatorname{dist}(y_{j_{max}},y)\leq 20\cdot
2^{-\operatorname{level}(y)}$. Using the triangle inequality, we finally
obtain

$\operatorname{dist}(x_{i}^{l},y)\leq\operatorname{dist}(x_{i}^{l},y_{j_{max}})+\operatorname{dist}(y_{j_{max}},y)\leq
24\cdot 2^{-\operatorname{level}(y)}.$

On the other hand, applying Lemma D.6 again, we get
$\operatorname{dist}(c_{i},x_{i}^{l})\leq 20\cdot
2^{-\operatorname{level}(x_{i}^{l})}=40\cdot 2^{-\operatorname{level}(y)}$ and
therefore
$\operatorname{dist}(c_{i},y)\leq\operatorname{dist}(c_{i},x_{i}^{l})+\operatorname{dist}(x_{i}^{l},y)\leq
64\cdot 2^{-\operatorname{level}(y)}\leq 100\cdot
2^{-\operatorname{level}(y)}.$ Hence, the ball
$B(y,2^{-\operatorname{level}(y)})$ became unavailable when $c_{i}$ was
selected and is not available when $\sigma_{i^{\prime}}^{1}$ is picked because
$i^{\prime}>i$. But Lemma D.5 guarantees the availability of all the balls
within the sequence
$\sigma_{i^{\prime}}^{1},\dots,\sigma_{i^{\prime}}^{l^{\prime}},B(y_{1},2^{-\operatorname{level}(y_{1})}),\dots,B(y_{j_{max}},2^{-\operatorname{level}(y_{j_{max}})})$,
including $B(y,2^{-\operatorname{level}(y)})$, when the algorithm selects
$\sigma_{i^{\prime}}^{1}$. We have a contradiction and this concludes the
proof of the first point.

We turn to the second point. The idea is to prove the existence of a net point
$x$ of level $\operatorname{level}(x_{i}^{l})+1$ such that the ball
$B(x,2^{-\operatorname{level}(x)})$ is a child of $\sigma_{i}^{l}$, and such
that $\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))$ is greater than
$\operatorname{Value}(\sigma_{i^{\prime}}^{1})$. Given that the algorithm
selects a child with the maximum value up to $\theta$, this will allow us to
conclude.

More precisely, we start by deriving a bound on
$\operatorname{dist}(x_{i}^{l},x_{i^{\prime}}^{1})$. Applying Lemma D.6 we get
$\operatorname{dist}(x_{i^{\prime}}^{l^{\prime}},x_{i^{\prime}}^{1})\leq
20\cdot 2^{-\operatorname{level}(x_{i^{\prime}}^{1})}$. By the fist point of
the Lemma, we know that
$\operatorname{level}(x_{i^{\prime}}^{1})\geq\operatorname{level}(x_{i}^{l})+2$
and therefore
$\operatorname{dist}(x_{i^{\prime}}^{l^{\prime}},x_{i^{\prime}}^{1})\leq
5\cdot 2^{-\operatorname{level}(x_{i}^{l})}$. On the other hand we have
$\sigma_{i}^{l}\cap\sigma_{i^{\prime}}^{l^{\prime}}\neq\emptyset$ and so
$\operatorname{dist}(x_{i}^{l},x_{i^{\prime}}^{l^{\prime}})\leq 2\cdot
2^{-\operatorname{level}(x_{i}^{l})}$. Using the triangle inequality, we
finally get
$\operatorname{dist}(x_{i}^{l},x_{i^{\prime}}^{1})\leq\operatorname{dist}(x_{i}^{l},x_{i^{\prime}}^{l^{\prime}})+\operatorname{dist}(x_{i^{\prime}}^{l^{\prime}},x_{i^{\prime}}^{1})\leq
7\cdot 2^{-\operatorname{level}(x_{i}^{l})}$.

Now let $x$ be a net point of level $\operatorname{level}(x_{i}^{l})+1$ such
that $x_{i^{\prime}}^{1}\in B(x,2^{-\operatorname{level}(x)}/2)$, such a point
exist by the covering property of nets. We have
$\operatorname{dist}(x_{i}^{l},x)\leq\operatorname{dist}(x_{i}^{l},x_{i^{\prime}}^{1})+\operatorname{dist}(x_{i^{\prime}}^{1},x)\leq
7\cdot 2^{-\operatorname{level}(x_{i}^{l})}+2^{-\operatorname{level}(x)}/2\leq
10\cdot 2^{-\operatorname{level}(x_{i}^{l})}$. Therefore the ball
$B(x,2^{-\operatorname{level}(x)})$ is a child of $\sigma_{i}^{l}$ and could
have been chosen by the algorithm instead of $\sigma_{i}^{l+1}$. The algorithm
selects a child of $\sigma_{i}^{l}$ with the maximum value up to $\theta$.
Hence
$\operatorname{Value}(\sigma_{i}^{l+1})\geq\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))-\theta$.

To conclude the proof, it just remains to show that
$\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))\geq\operatorname{Value}(\sigma_{i^{\prime}}^{1})$.
We will show that for any $p\in P\cap\sigma_{i^{\prime}}^{1}$, the
contribution of $p$ to the value of $\sigma_{i^{\prime}}^{1}$ is lower than
its contribution to the value of $B(x,2^{-\operatorname{level}(x)})$. Let $p$
be a point of $P\cap\sigma_{i^{\prime}}^{1}$, the contribution of $p$ to the
value of $\sigma_{i^{\prime}}^{1}$ is
$(2^{-\operatorname{level}(x_{i^{\prime}}^{1})}-\operatorname{dist}(p,x_{i^{\prime}}^{1}))^{z}$.
We have established that
$\operatorname{level}(x_{i^{\prime}}^{1})\geq\operatorname{level}(x_{i}^{l})+2=\operatorname{level}(x)+1$.
Therefore we can bound $2^{-\operatorname{level}(x_{i^{\prime}}^{1})}\leq
2^{-\operatorname{level}(x)}/2$. Moreover, $x_{i^{\prime}}^{1}$ is by
construction in $B(x,2^{-\operatorname{level}(x)}/2)$, hence using the
triangle inequality we get
$\operatorname{dist}(p,x_{i^{\prime}}^{1})\geq\operatorname{dist}(p,x)-\operatorname{dist}(x,x_{i^{\prime}}^{1})\geq\operatorname{dist}(p,x)-2^{-\operatorname{level}(x)}/2$.
We can now bound the contribution of $p$ to the value of
$\sigma_{i^{\prime}}^{1}$

$\displaystyle(2^{-\operatorname{level}(x_{i^{\prime}}^{1})}-\operatorname{dist}(p,x_{i^{\prime}}^{1}))^{z}$
$\displaystyle\leq(2^{-\operatorname{level}(x)}/2-(\operatorname{dist}(p,x)-2^{-\operatorname{level}(x)}/2))^{z}$
$\displaystyle\leq(2^{-\operatorname{level}(x)}-\operatorname{dist}(p,x))^{z}.$

This is precisely the contribution of $p$ to the value of
$B(x,2^{-\operatorname{level}(x)})$. Summing this inequality for all $p\in
P\cap\sigma_{i^{\prime}}^{1}$, we obtain
$\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))\geq\operatorname{Value}(\sigma_{i^{\prime}}^{1})$,
concluding the proof. ∎

###### Proof Lemma D.4.

We are now ready to prove Lemma D.4. We recall for convenience the procedure
to compute the $l_{i}$’s, described at the beginning of Section D.3. Start
with $l_{i}=1$ for all $i$, and note that with this choice, the first
condition is verified by the design of the algorithm: when $\sigma_{i}^{1}$ is
picked, it maximizes the value up to $\theta$ among the available balls. In
particular, $\sigma_{i}^{1}$ has a value larger up to $\theta$ than any ball
still available at the end of the algorithm.

To enforce the second condition, proceed as follows: as long as we can find
$i<i^{\prime}$ and $l\geq l_{i}$, $l^{\prime}\geq l_{i^{\prime}}$ such that
$\sigma_{i}^{l}\cap\sigma_{i^{\prime}}^{l^{\prime}}\neq\emptyset$, update
$l_{i}=l+1$. The first item of Lemma D.7 guarantees that this procedure is
well-defined, namely that $\sigma_{i}^{l}$ is not the last ball of the
sequence, and that $\sigma_{i}^{l+1}$ does indeed exist. Furthermore, the
second item of that Lemma ensures that
$\operatorname{Value}(\sigma_{i}^{l_{i}+1})\geq\operatorname{Value}(\sigma_{i^{\prime}}^{1})-\theta\geq
M_{\operatorname{Value}}-\theta$. Therefore, the first condition remains
satisfied after each update.

At each step, one of the $l_{i}$ gets incremented, so this procedure must
terminate because the maximum level is $\lceil\log(n)\rceil$: when it ends,
both conditions are satisfied, concluding the proof. ∎

####  D.3.2 Back to the proof of Theorem 3.4

Our goal is to identify $k$ disjoint balls with values greater than those of
$B_{\gamma}$ using Lemma D.4 and then apply Lemma D.3 to finalize the proof.

###### Proof of Theorem 3.4.

To prove the theorem, we define a function $\phi$ that maps the center of
$\Gamma_{1}$ to balls of $\mathcal{B}$ such that for all
$\gamma\in\Gamma_{1}$:

  1. 1.

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

  2. 2.

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

  3. 3.

The value of $B_{\gamma}$ is less than
$\operatorname{Value}(\phi(\gamma))+\theta$.

Given such a matching $\phi$, we can conclude as follows. Summing the
inequality of the third property of $\phi$ gives

$\displaystyle\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(B_{\gamma})$
$\displaystyle\leq
k\cdot\theta+\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(\phi(\gamma)).$

Each $\phi(\gamma)$ is not covered by the second property of $\phi$, so we can
apply Lemma D.3. Moreover those balls are disjoint because of the first
property of $\phi$ and we obtain

$\displaystyle\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(\phi(\gamma))$
$\displaystyle\leq\sum_{\gamma\in\Gamma_{1}}\operatorname{cost}(\phi(\gamma),\Gamma)$
$\displaystyle\leq\operatorname{cost}(\bigcup_{\gamma\in\Gamma_{1}}\phi(\gamma),\Gamma)$
$\displaystyle\leq\operatorname{cost}(P,\Gamma).$

Putting everything together we finally get

$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}(B_{\gamma})\leq
k\cdot\theta+\operatorname{cost}(P,\Gamma).$

Combining this with Equation 8, this conclude the proof of Theorem 3.4.

The rest of the proof is dedicated to the construction of the matching $\phi$
with the three desired properties. We construct a more general function $\phi$
that can also map the centers of $\Gamma_{0}$. The restriction of $\phi$ to
$\Gamma_{1}$ will verify the desired properties. Let $l_{i}$ be the indices
provided by Lemma D.4. We have $3$ steps in the construction of $\phi$:

  * •

First, for any $i$ such that the last ball of the sequence $\sigma_{i}$ is
covered, we let $B=(c_{i},2^{-\lceil\log n\rceil})$ be this last ball (with
center at $c_{i}\in C_{k}$) and chose arbitrarily $\gamma_{i}\in\Gamma$
covering $B$. We define $\phi(\gamma_{i})=B$. We note that, in this case,
$\gamma_{i}\in\Gamma_{0}$ – since $\operatorname{dist}(c_{i},\gamma_{i})\leq
2^{-\lceil\log n\rceil}$ .

  * •

Second, for any $i$ such that at least one of balls of the pruned sequence
$(\sigma_{i}^{l})_{l\geq l_{i}}$ is covered but not the last one. We define
$\lambda_{i}\geq l_{i}$ to be the smallest index such that for all
$l\geq\lambda_{i}$ $\sigma_{i}^{l}$ is not covered. Let $\gamma_{i}$ be an
arbitrary element of $\Gamma$ that covers $\sigma_{i}^{\lambda_{i}-1}$. We
define $\phi(\gamma_{i})=\sigma_{i}^{\lambda_{i}}$.

  * •

Last, for any element in $\Gamma_{1}$ that is still unmatched, we extend
$\phi$ to form an arbitrary one-to-one matching between the remaining elements
$\gamma\in\Gamma_{1}$ and all $\sigma_{i}^{l_{i}}$, where $i$ is such that
none of the balls in the pruned sequence $(\sigma_{i}^{l})_{l\geq l_{i}}$ are
covered.

Note that the second item of Lemma D.4 guarantees that if $\gamma\in\Gamma$
covers a ball of a pruned sequence, it cannot cover a ball of another pruned
sequence (as those balls are disjoints): this ensures that our definition of
$\phi$ is consistent and that $\phi$ is one-to-one. We can now verify it
satisfies the three desired properties.

Property 1. For any $\gamma,\gamma^{\prime}\in\Gamma_{1}$, let $i$ such that
$\phi(\gamma)$ is a ball of the pruned sequence $(\sigma_{i}^{l})_{l\geq
l_{i}}$, and let $i^{\prime}$ such that $\phi(\gamma^{\prime})$ is a ball of
the pruned sequence $(\sigma_{i^{\prime}}^{l})_{l\geq l_{i^{\prime}}}$. By
construction of $\phi$ we have $i\neq i^{\prime}$ and therefore Lemma D.4
ensures that $\phi(\gamma)\cap\phi(\gamma^{\prime})=\emptyset$.

Property 2. For any $\gamma\in\Gamma_{1}$, $\phi(\gamma)$ is not covered by
$\Gamma$ by construction.

Property 3. Fix a $\gamma\in\Gamma_{1}$. We distinguish two cases, based on
whether $\phi(\gamma)$ was defined at the second or last step of the procedure
(it cannot be defined at the first, as $\gamma$ involved there are in
$\Gamma_{0}$). We aim at showing
$\operatorname{Value}(B_{\gamma})\leq\operatorname{Value}(\phi(\gamma))+\theta$.

  * •

If $\phi(\gamma)$ is defined in the last step, then it is of the form
$\sigma_{i}^{l_{i}}$, and Lemma D.4 ensures that
$\operatorname{Value}(\sigma_{i}^{l_{i}})\geq
M_{\operatorname{Value}}-\theta$. Combined with the fact that $B_{\gamma}$ is
available at the end of the algorithm (and therefore by definition of
$M_{\operatorname{Value}}$, $\operatorname{Value}(B_{\gamma})\leq
M_{\operatorname{Value}}$), we obtain directly
$\operatorname{Value}(B_{\gamma})\leq\operatorname{Value}(\phi(\gamma))+\theta$.

  * •

Otherwise, $\phi(\gamma)$ is defined in the second step, and
$\phi(\gamma)=\sigma_{i}^{\lambda_{i}}$. The proof follows a structure similar
to the one of Lemma D.4. We will show that there exists a ball
$B(x,2^{-\operatorname{level}(x_{i}^{\lambda_{i}})})$ in $\mathcal{B}$, that
contains $B_{\gamma}$ and is a child of $\sigma_{i}^{\lambda_{i}-1}$. In that
case, since the algorithm opted for $\sigma_{i}^{\lambda_{i}}$ over
$B(x,2^{-\operatorname{level}(x_{i}^{\lambda_{i}})})$, we get
$\operatorname{Value}(\sigma_{i}^{\lambda_{i}})\geq\operatorname{Value}(B(x,2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}))-\theta$.
Since this ball contains $B_{\gamma}$, it has greater value, which concludes
the proof of Property 3. Therefore, we only need to show the existence of such
a ball. Note that we don’t actually need that $B_{\gamma}$ is contained in it,
only that its value is greater than $\operatorname{Value}(B_{\gamma})$: we
will only show this simpler property.

Let $x_{\gamma}$ be the center of $B_{\gamma}$. We start by proving that
$\operatorname{level}(x_{\gamma})\geq\operatorname{level}(x_{i}^{\lambda_{i}})+1$.
Assume by contradiction that
$\operatorname{level}(x_{\gamma})\leq\operatorname{level}(x_{i}^{\lambda_{i}}).$
We are going to prove that in that case, $x_{\gamma}$ is too close to the
center $c_{i}$ and therefore is not available at the end of the algorithm,
contradicting the definition of $B_{\gamma}$.

First, by definition of $B_{\gamma}$ we know that
$\operatorname{dist}(x_{\gamma},\gamma)\leq
2^{-\operatorname{level}(x_{\gamma})}/2$. Second, since $\gamma$ is an element
covering $\sigma_{i}^{\lambda_{i}-1}$, it holds that
$\operatorname{dist}(\gamma,x_{i}^{\lambda_{i}-1})\leq
2^{-\operatorname{level}(x_{i}^{\lambda_{i}-1})}=2\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}\leq 2\cdot
2^{-\operatorname{level}(x_{\gamma})}.$ Third applying Lemma D.6 we get
$\operatorname{dist}(x_{i}^{\lambda_{i}-1},c_{i})\leq 20\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}-1})}\leq 40\cdot
2^{-\operatorname{level}(x_{\gamma})}$. Combining these three inequalities
using the triangle inequality we obtain

$\displaystyle\operatorname{dist}(x_{\gamma},c_{i})$
$\displaystyle\leq\operatorname{dist}(x_{\gamma},\gamma)+\operatorname{dist}(\gamma,x_{i}^{\lambda_{i}-1})+\operatorname{dist}(x_{i}^{\lambda_{i}-1},c_{i})$
$\displaystyle\leq(0.5+2+40)\cdot 2^{-\operatorname{level}(x_{\gamma})}$
$\displaystyle\leq 100\cdot 2^{-\operatorname{level}(x_{\gamma})}.$

Therefore $B_{\gamma}$ is not available at the end of the algorithm,
contradicting the definition of $B_{\gamma}$. This finalize the proof of the
inequality
$\operatorname{level}(x_{\gamma})\geq\operatorname{level}(x_{i}^{\lambda_{i}})+1$.

We now identify the desired child of $\sigma_{i}^{\lambda_{i}-1}$. Let $x$ be
a net point of level $\operatorname{level}(x_{i}^{\lambda_{i}})$ such that
$\operatorname{dist}(x,x_{\gamma})\leq
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}/2$ (such a point exist by the
covering property of nets). We show that $B(x,2^{-\operatorname{level}(x)})$
is a child of $\sigma_{i}^{\lambda_{i}-1}$. Since $\gamma$ is covering
$\sigma_{i}^{\lambda_{i}-1}$, it holds that
$\operatorname{dist}(x_{i}^{\lambda_{i}-1},\gamma)\leq 2\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}$. Additionally, by definition
of $B_{\gamma}$ we know that $\operatorname{dist}(\gamma,x_{\gamma})\leq
2^{-\operatorname{level}(x_{\gamma})}/2\leq
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}/4$. Combining these three
inequalities, and using the triangle inequality, we obtain

$\displaystyle\operatorname{dist}(x_{i}^{\lambda_{i}-1},x)$
$\displaystyle\leq\operatorname{dist}(x_{i}^{\lambda_{i}-1},\gamma)+\operatorname{dist}(\gamma,x_{\gamma})+\operatorname{dist}(x_{\gamma},x)$
$\displaystyle\leq(2+0.25+0.5)\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}$ $\displaystyle\leq 20\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}})}$ $\displaystyle\leq 10\cdot
2^{-\operatorname{level}(x_{i}^{\lambda_{i}-1})}.$

Therefore the ball $B(x,2^{-\operatorname{level}(x)})$ is a child of
$\sigma_{i}^{\lambda_{i}-1}$ and could have been chosen by the algorithm
instead of $\sigma_{i}^{\lambda_{i}}$. The algorithm selects a child of
$\sigma_{i}^{l}$ with the maximum value up to $\theta$. Hence
$\operatorname{Value}(\sigma_{i}^{\lambda_{i}})\geq\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))-\theta$.

To conclude the proof, it just remains to show that
$\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))\geq\operatorname{Value}(B_{\gamma})$.
We will show that for any $p\in P\cap B_{\gamma}$, the contribution of $p$ to
the value of $B_{\gamma}$ is lower than its contribution to the value of
$B(x,2^{-\operatorname{level}(x)})$. Let $p$ be a point of $P\cap B_{\gamma}$,
the contribution of $p$ to the value of $B_{\gamma}$ is
$(2^{-\operatorname{level}(x_{\gamma})}-\operatorname{dist}(p,x_{\gamma}))^{z}$.
We have established that
$\operatorname{level}(x_{\gamma})\geq\operatorname{level}(x_{i}^{\lambda_{i}-1})+2=\operatorname{level}(x)+1$.
Therefore we can bound $2^{-\operatorname{level}(x_{\gamma})}\leq
2^{-\operatorname{level}(x)}/2$. Moreover, $x_{\gamma}$ is by construction in
$B(x,2^{-\operatorname{level}(x)}/2)$, hence using the triangle inequality we
get
$\operatorname{dist}(p,x_{\gamma})\geq\operatorname{dist}(p,x)-\operatorname{dist}(x,x_{\gamma})\geq\operatorname{dist}(p,x)-2^{-\operatorname{level}(x)}/2$.
We can now bound the contribution of $p$ to the value of $B_{\gamma}$

$\displaystyle(2^{-\operatorname{level}(x_{\gamma})}-\operatorname{dist}(p,x_{\gamma}))^{z}$
$\displaystyle\leq(2^{-\operatorname{level}(x)}/2-(\operatorname{dist}(p,x)-2^{-\operatorname{level}(x)}/2))^{z}$
$\displaystyle\leq(2^{-\operatorname{level}(x)}-\operatorname{dist}(p,x))^{z}.$

This is precisely the contribution of $p$ to the value of
$B(x,2^{-\operatorname{level}(x)})$. Summing this inequality for all $p\in
P\cap B_{\gamma}$, we obtain
$\operatorname{Value}(B(x,2^{-\operatorname{level}(x)}))\geq\operatorname{Value}(B_{\gamma})$,
concluding the proof.

∎

##  Appendix E Missing Proofs of Section 4

###  E.1 Direct application to centralized DP

As an illustration, we sketch an application of previous results to the
centralized DP setting. A more formal and general argument will be given later
in Theorem 4.3. In centralized DP, when each element is part of at most $b$
sets, standard result show the existence of generalized histograms with
additive error
$O\left(\sqrt{bD}\cdot\log(m/(\delta\beta))/\varepsilon\right)$. To compute
the values of each cell, $D=1$, there are $m=n^{O(d)}$ many cells, and
$b=2^{O(d)}\log n$. Therefore, those results and Theorem 3.4 yield an
$(\varepsilon,\delta)$-DP algorithm $\mathcal{A}$ for $(k,z)$-clustering with
multiplicative approximation $O(1)$ and additive error
$O\left(k2^{O(d)}\cdot\log(n/(\beta\delta))\log^{1/2}(n)/\varepsilon\right)$,
with probability $1-\beta$.

This can be combined with the results of Section 2 to get multiplicative
approximation $w^{*}(1+\alpha)$ and additive error
$k^{O(1)}\log^{3/2}(n)/\varepsilon+O\left(k\sqrt{d}\log(k)/\varepsilon\right)$
as follows: first reduce the dimension to $O\left(\log(k)/\alpha^{2}\right)$,
then use algorithm $\mathcal{A}$ and the Laplace mechanism to apply Lemma 2.4.
To lift the result back up to the original space, estimate the mean of each
cluster as follow: simply estimate the size of each cluster ($D=1,b=1,m=k$)
and $\sum_{p\in P_{i}}p$ with a Laplace mechanism (the $\ell_{1}$ sensitivity
is $1$ in the first case, $\sqrt{d}$ in the second): 2.1 is satisfied with
$e=\sqrt{d}/\varepsilon$. Lemma 2.2 shows that this gives a solution with the
desired cost. Finally, repeat $\log(1/\beta)$ times to boost the probability,
which increases the additive error by $\log(1/\beta)$.

For $(k,z)$-clustering, instead of lifting the clustering using the average of
each cluster, we can solve the $(1,z)$-clustering problem on each, which can
be done efficiently with additive error
$\sqrt{d}\operatorname{polylog}(n/\delta)$ (see [GKM20]). This therefore
reduces the multiplicative approximation to $w^{*}(1+\alpha)$, as in the
$k$-means case.

###  E.2 Structured Clusters

We start by providing a formal statement for Lemma 4.2:

######  Lemma E.1.

There exists a family of set $\mathcal{G}=\left\\{G_{1},...,G_{m}\right\\}$
efficiently computable, with $m=n^{O(d)}$, and with the following properties.
First, any point from $B_{d}(0,1)$ is part of at most $O(\log n)$ sets
$G_{i}$. Second, each cluster can be transformed to consist of the union of
few $G_{i}$. Formally, fix any $1>\alpha>0$, 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 multiset $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}.$

###### Proof.

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 defined as
$\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$.

Such a recursive decomposition can be computed using e.g. the net tree of
[HM06]. This construction ensures $|\mathcal{G}_{i}|=2^{-O(id)}$. We let
$\mathcal{G}=\cup\mathcal{G}_{i}$: this has size $n^{O(d)}$, as desired. For
the first property, since the depth of the decomposition is
$\lceil\log(n)\rceil+1$ and each level is a partition, each point from
$B_{d}(0,1)$ appears in exactly $\lceil\log(n)\rceil+1$ many $G_{i}$.

We now show the second property. Fix a set of centers
$\mathcal{C}=\left\\{c_{1},...,c_{k}\right\\}$. We show how to construct a
partition $\mathcal{A}$ of $B_{d}(0,1)$ and assign each part to a center as in
the lemma.

For a cell $A$ of level $i+1$, we denote by $\textsc{Parent}(A)$ the unique
cell of level $i$ containing $A$. 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 verify now that $\mathcal{A}$ has the desired
properties: first, that its size is bounded; second, it is a partition; and
finally, that each cell can be fully assigned to a center while preserving the
cost.

Size of $\mathcal{A}$. 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. The product
of those two quantities is an upper bound on $|\mathcal{A}|$. 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
Lemma A.1:

$\displaystyle\operatorname{dist}(p,a(A))^{2}$
$\displaystyle\leq(\operatorname{dist}(p,v_{A})+\operatorname{dist}(v_{A},a(A)))^{2}\leq(2\operatorname{dist}(p,v_{A})+\operatorname{dist}(p,\mathcal{C}))^{2}$
$\displaystyle\leq(1+\alpha/2)\operatorname{dist}(p,\mathcal{C})^{2}+(1+\frac{2}{\alpha})\cdot
4\operatorname{dist}(p,v_{A})^{2}$
$\displaystyle\leq(1+\alpha/2)\operatorname{dist}(p,\mathcal{C})^{2}+\frac{9}{\alpha}\cdot\frac{1}{n}.$

Therefore, summing all points in cells at level $\log(n)$ gives an additive
error at most $\frac{9}{\alpha}$.

Now, fix a cell $A\in\mathcal{A}$ at level $>\log(n)$, and a point $p\in A$.
Since, by construction of $\mathcal{A}$, the $\ell$-neighborhood of $A$
contains at most one center from $\mathcal{C}$, it holds that:

  * •

either $p$ is already assigned to $a(A)$, and then
$\operatorname{dist}(p,a(A))=\operatorname{dist}(p,\mathcal{C})$,

  * •

or the center serving $p$ in $\mathcal{C}$ is outside of the
$\ell$-neighborhood of $A$: in particular,
$\operatorname{dist}(p,\mathcal{C})\geq\ell\cdot\operatorname{dist}(p,v_{A})$.
In that case, we use the modified triangle inequality from Lemma A.1. This
yields similarly as above:

$\displaystyle\operatorname{dist}(p,a(A))^{2}$
$\displaystyle\leq(\operatorname{dist}(p,v_{A})+\operatorname{dist}(v_{A},a(A)))^{2}\leq(2\operatorname{dist}(p,v_{A})+\operatorname{dist}(p,\mathcal{C}))^{2}$
$\displaystyle\leq(1+\alpha/2)\operatorname{dist}(p,\mathcal{C})^{2}+(1+\frac{2}{\alpha})\cdot
4\operatorname{dist}(p,v_{A})^{2}$
$\displaystyle\leq(1+\alpha/2)\operatorname{dist}(p,\mathcal{C})^{2}+(1+\frac{2}{\alpha})\cdot
4\cdot\frac{1}{\ell^{2}}\operatorname{dist}(p,\mathcal{C})^{2}$
$\displaystyle=(1+\alpha/2)\operatorname{dist}(p,\mathcal{C})^{2}+(4+\frac{8}{\alpha})\cdot\frac{\alpha^{2}}{100}\cdot\operatorname{dist}(p,\mathcal{C})^{2}$
$\displaystyle\leq(1+\alpha)\operatorname{dist}(p,\mathcal{C})^{2}.$

Summing over all $p\in P$ and combining with the cells at level $\log(n)$, we
conclude that:

$\displaystyle\sum_{A\in\mathcal{A}}\sum_{p\in P\cap
A}\operatorname{dist}(p,a(A))^{2}\leq(1+\alpha)\operatorname{cost}(P,\mathcal{C})+\frac{9}{\alpha}.$

The other direction is straightforward: since $a(A)\in\mathcal{C}$, we have by
definition for any $p\in A$
$\operatorname{dist}(p,\mathcal{C})\leq\operatorname{dist}(p,a(A))$, and
therefore
$\operatorname{cost}(P,\mathcal{C})\leq\sum_{A\in\mathcal{A}}\sum_{p\in P\cap
A}\operatorname{dist}(p,a(A))^{2}$. ∎

###  E.3 Main Approximation Result

######  Lemma E.2.

Fix a privacy model where there exist private generalized bucketized vector
summation such that with probability $2/3$ the additive error is $A(m,b,D)$,
where $m$ is the number of sets, $b$ the maximal number of set containing any
given element, and $D$ the dimension of the image of the $f_{i}$. Assume that
the error $A$ is non-decreasing.

Then, there is a private algorithm for $k$-means of points in $\mathbb{R}^{d}$
that, with probability $1-\beta$, computes a solution with multiplicative
approximation $w^{*}(1+\alpha)$ and additive error
$\left(A(m,k^{O_{\alpha}(1)}b,1)+A(m,b,d)\right)\cdot
k^{O_{\alpha}(1)}\operatorname{polylog}(n)\log(1/\beta)$, with
$m=n^{O_{\alpha}(\log(k))}$ and $b=\log(n)$.

There is also a private algorithm for $(k,z)$-clustering of points in
$\mathbb{R}^{d}$ that, with probability $2/3$, computes a solution with
multiplicative approximation $w^{*}(2^{z}+\alpha)$ and additive error
$\left(A(m,k^{O_{\alpha}(1)}b,1)+A(m,b,d)\right)\cdot
k^{O_{\alpha}(1)}\operatorname{polylog}(n)$.

###### Proof.

This theorem combines all previous results. We first describe and analyze our
private algorithm designed for low-dimensions $\hat{d}=O_{\alpha}(\log k)$. To
use Algorithm 1, one needs to estimate the value of each balls. There are at
most $m_{1}=n^{O(\hat{d})}$ of them, and each input point is in
$b_{1}=2^{O(\hat{d})}\log n$ many balls. This can be done with a summation
algorithm, with additive error $A(m_{1},b_{1},1)$ on the values. Therefore,
Theorem 3.2 shows that this implementation of Algorithm 1 computes a solution
with multiplicative approximation $O(1)$ and additive error
$kA(m_{1},b_{1},1)$.

Then, one can apply Lemma 4.2 to get structured cluster, with same
multiplicative approximation, and additive error increased by $O(1/\alpha)$.
We have the following guarantee: each cluster is described with
$k\alpha^{-\hat{d}}\log(n)$ many sets of $\mathcal{G}$, each element appears
in at most $\log n$ sets of $\mathcal{G}$, and
$|\mathcal{G}|=n^{O_{\alpha}(\log k)}$. Therefore, using the summation
algorithm, one can compute the size of each cluster up to an additive error
$e_{1}=A(|\mathcal{G}|,\log n,1)\cdot\alpha^{-\hat{d}}\log(n)$. Similarly, one
can compute $\textsc{Sum}_{i}$ for each cluster $i$ up to an additive error
$A(|\mathcal{G}|,\log n,d)$. Therefore, 2.1 is satisfied with an error
$e=A(|\mathcal{G}|,\log n,d)$.

This is enough to boost the approximation ratio using Lemma 2.4, and get a
multiplicative approximation $w^{*}$ in the space $\mathbb{R}^{\hat{d}}$. The
additive error increases to $k^{\prime}A(m_{1},b_{1},1)+ke_{1}$, for
$k^{\prime}=k^{O(1)}\log(n)$.

Now, we show how to use this algorithm as a subroutine, to solve the problem
in large dimension $d$. The algorithm starts by applying the dimension
reduction of Lemma 2.2, to reduce the dimension to $\hat{d}=O_{\alpha}(\log
k)$. Then, it computes a clustering using the previous argument, and turns the
result into a structured partition using Lemma E.1. Using generalized
summation algorithms, the algorithm computes $n_{i},\textsc{Sum}_{i}$ and
$\textsc{SumNorm}_{i}$ that satisfy 2.1. The additive error in the estimation
is $e:=A(|\mathcal{G}|,\log
n,1)\cdot\alpha^{-\hat{d}}\operatorname{polylog}(n)$ (note crucially that the
exponent of $\alpha$ is still $\hat{d}$, as the clusters are structured in
$\mathbb{R}^{\hat{d}}$).

We conclude the theorem for $k$-means by plugging those estimations in Lemma
2.2 for dimension reduction and Corollary 2.6 to boost the probabilities: with
probability $1-\beta$, the total additive error is

$\displaystyle\underbrace{k^{\prime}A(m_{1},b_{1},1)}_{\text{Compute initial
solution}}+\underbrace{A(|\mathcal{G}|,\log n,1)\cdot
k\cdot\alpha^{-\hat{d}}\log(n)}_{\text{Boost
approx.}}+\underbrace{A(|\mathcal{G}|,\log
n,d)\cdot\alpha^{-\hat{d}}\operatorname{polylog}(n)}_{\text{Lift up the
results and boost proba.}}$ $\displaystyle\leq\left(A(n^{O_{\alpha}(\log
k)},k^{O_{\alpha}(1)}\log(n),1)+A(n^{O_{\alpha}(\log k)},\log
n,1)+A(n^{O_{\alpha}(\log k)},\log n,d)\right)\cdot
k^{O_{\alpha}(1)}\operatorname{polylog}(n)$
$\displaystyle\leq\left(A(n^{O_{\alpha}(\log k)},k^{O_{\alpha}(1)}\log
n,1)+A(n^{O_{\alpha}(\log k)},\log n,d)\right)\cdot
k^{O_{\alpha}(1)}\operatorname{polylog}(n).$

For $(k,z)$-clustering, the same holds, although we cannot boost the success
probability, and the multiplicative approximation is $(2^{z}+\alpha)w^{*}$. ∎

See 4.4

###### Proof.

The guarantee for the local model stem from Lemma 28 in [CGKM21] combined with
Lemma B.2, which gives a generalized bucketized summation algorithm with
desired guarantee (even for $\delta=0$): the additive error is with
probability $2/3$ $A(m,b,D)=\frac{b\sqrt{nD\log(m)}}{\varepsilon}$. For the
$(\varepsilon,\delta)$-shuffle model, this is Theorem 33 of [CGKM21]: the
additive error is with probability $2/3$
$A(m,b,D)=\frac{b\sqrt{D}}{\varepsilon}\cdot\operatorname{polylog}(\frac{mD}{\delta})$
(with an unspecified $\operatorname{polylog}$).

Under continual observation, we give in Lemma B.3 a generalized counting
mechanism that has with probability $2/3$, at all time step simultaneously, an
additive error
$O\left(b\sqrt{D}\cdot\varepsilon^{-1}\log(DT)\sqrt{\log(mDT/\beta)\log(b\log(T)/\delta)}\right)$.
Plugging in the values of $b,m$ and using Theorem 4.3 concludes. ∎

##  Appendix F Missing Proofs of Section 5

###  F.1 Centralized DP

######  Lemma F.1.

Algorithm 1 implemented with the exponential mechanism computes a solution to
$(k,z)$-clustering with multiplicative approximation $O(1)$ and additive error
$\frac{k\sqrt{d}\operatorname{polylog}(n/\delta)}{\varepsilon^{\prime}}$.
Furthermore, the running time is $k^{O(1)}\cdot n\log^{2}n$.

###### Proof.

For the initial choice of the sequence (line 4 of Algorithm 1), the
exponential mechanism takes a decision out of $n^{O(d)}$ many balls:
therefore, the value of the chosen ball deviates from the optimum by an
additive error $O\left(\frac{d\log(n/\beta)}{\varepsilon^{\prime}}\right)$,
with probability $1-\beta$. Each choice made in the while loop line 5 takes a
decision out of the children of the current ball, and there are at most
$2^{O(d)}$ of them: therefore, the additive error is
$O\left(\frac{d\log(1/\beta)}{\varepsilon^{\prime}}\right)$, with probability
$1-\beta$.

In total, $k\log n$ choices are made: therefore, taking $\beta=1/(3k\log n)$
ensures that all errors are bounded by
$O\left(\frac{d\log(n/\beta)}{\varepsilon^{\prime}}\right)$ with probability
$2/3$. Combined with Theorem 3.4, this shows that the additive error of
Algorithm 1 is $O\left(\frac{kd\log(n/\beta)}{\varepsilon^{\prime}}\right)$.

Dimension reduction reduces $d$ to $\hat{d}=O(\log(k))$ while preserving a
multiplicative approximation $O(1)$, and the additive error induced by lifting
the clustering up in the original space with Lemma 2.2 is
$O\left(\frac{\operatorname{polylog}(n)k\sqrt{d}}{\varepsilon^{\prime}}\right)$.
Indeed, one can estimate the size of each cluster and $\sum_{p\in P_{i}}p$
with the Gaussian mechanism: in the both cases, the $\ell_{2}$ sensitivity is
$O(1)$. The Gaussian mechanism ensures that, for each of those estimates, the
additive error is bounded by $\sqrt{d}/\varepsilon^{\prime}\log(1/\beta)$ with
probability $1-\beta$. Therefore, a union-bound over all $2k$ estimates shows
that 2.1 is satisfied with $e=\sqrt{d}\log(k)/\varepsilon^{\prime}$. This
concludes the approximation guarantee.

The running time of a naive implementation of this algorithm is $n^{\hat{d}}$,
to run the exponential mechanism. However, note that only $2^{\hat{d}}n\log n$
balls are non-empty (since at each level, each point is in at most
$2^{\hat{d}}$ many balls). All empty balls have same value, equal to $0$.
Therefore, the exponential mechanism can be implemented in time
$2^{\hat{d}}n\log n=k^{O(1)}n\log n$. As the algorithm makes $O(k\log n)$
calls to the exponential mechanism, this concludes the complexity analysis. ∎

To show that the procedure is $(\varepsilon,\delta)$-DP, we follow the
analysis of [GLM+10] for weighted set cover (adapted by [CNX21] for
$k$-means): in our language, they analyzed the exponential mechanism for a
process that selects iteratively balls with largest value, and then remove all
points of the selected ball. Our process is more intricate, as it combines
selecting the heads with constructing the sequence. We manage nonetheless to
adapt their proof in the following lemma:

######  Lemma F.2.

Algorithm 1 when implemented using the exponential mechanism with parameter
$\varepsilon^{\prime}=\frac{\varepsilon}{4\log(n/\delta)}$, is
$(\varepsilon,\delta)$-DP.

###### Proof.

We follow the proof of [GLM+10] for set cover. Our two step process incurs
some complication: analyzing the selection of the first ball of each sequence
$\sigma_{i}$ is similar to [GLM+10], but in our case it is interlaced with the
recursive greedy choices, which makes thing more technical.

We consider the outcome of the algorithm to be the $k$ sequences of balls
$\sigma_{1},...,\sigma_{k}$ (instead of merely the $k$ centers), and we will
show that this is $(\varepsilon,\delta)$-DP. For this, we will fix a given set
of sequences $C=(\sigma_{1},...,\sigma_{k})$ and will compare the probability
that the outcome of $\mathcal{A}$ is $C$ on two neighboring inputs $X$ and
$X^{\prime}$. Note that fixing a sequence $C$ also fixes the center chosen by
the algorithm: the $i$-th center is the (geometric) center of the last ball in
$\sigma_{i}$.

We start with some notations. We write $\mathcal{A}(X)_{i}^{j}$ to be the
$j$-th choice made by the algorithm in the $i$-th sequence, on input $X$. We
denote $\\{\sigma,<i,<j\\}$ the event
$\mathcal{A}(X)_{i^{\prime}}^{j^{\prime}}=\sigma_{i}^{j}$ for all
$i^{\prime},j^{\prime}$ such that either $i^{\prime}<i$ or $i^{\prime}=i$ and
$j^{\prime}<j$. We write $\\{\sigma,\leq i\\}$ for $\\{\sigma,<i,<\infty\\}$.
Furthermore, for a ball $B$, we write $C(B)$ the children of $B$ (see Section
3 for the definition of children, forbidden and available)

For any ball $B\in\mathcal{B}$ and dataset $X$, we write
$\operatorname{Value}_{i}(B,X)=-\infty$ when $B$ is forbidden by some center
among the first $i-1$ of $C$; and
$\operatorname{Value}_{i}(B,X):=\operatorname{Value}(B,X)$ otherwise (when $B$
is still available after choosing the first $i-1$ centers from $C$).

Let $X$ and $X^{\prime}$ be two neighboring datasets, with symmetric
difference $X\Delta X^{\prime}=\\{p\\}$. We aim at bounding
$\frac{\Pr[\mathcal{A}(X)=C]}{\Pr[\mathcal{A}(X^{\prime})=C]}$.

There are two different choices in the algorithm: the choice of the first
elements of each sequence, and then the recursive construction of the
sequences themselves.

$\displaystyle\Pr\left[\mathcal{A}(X)_{i}^{1}=\sigma_{i}^{1}~{}|~{}\\{\sigma,\leq
i\\}\right]=\frac{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{1},X))}{\sum_{B\in\mathcal{B}}\exp(\varepsilon^{\prime}\operatorname{Value}_{i}(B,X))},$
$\displaystyle\Pr\left[\mathcal{A}(X)_{i}^{j}=\sigma_{i}^{j}~{}|~{}\\{\sigma,<i,<j\\}\right]=\frac{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{j},X))}{\sum_{c\in
C(\sigma_{i}^{j-1})}\exp(\varepsilon^{\prime}\operatorname{Value}(c,X))}.$

Note that, if there is $i$ such that $\sigma_{i}^{1}$ is not available at the
$i$-th step, then $\Pr[\mathcal{A}(X)=C]=\Pr[\mathcal{A}(X^{\prime})=C]=0$;
and similarly if there are some $i,j$ such that $\sigma_{i}^{j}$ is not a
children of $\sigma_{i}^{j-1}$, namely $\sigma_{i}^{j}\notin
C(\sigma_{i}^{j-1})$. Therefore, we only need to focus on admissible
sequences, where the previous cases cannot happen. This ensures that one input
point $p$ can appear only in $\log n$ many $\sigma_{i}^{j}$ and
$C(\sigma_{i}^{j})$, one per level of the ball hierarchy. Indeed, if
$p\in\sigma_{i}^{j}$, then all balls containing $p$ at the level of
$\sigma_{i}^{j}$ and the level below are forbidden by the algorithm, and thus
in any subsequent admissible sequence $p$ cannot appear in another ball at
those levels; since there are $\log n$ levels, $p$ appears in at most $\log n$
balls or children of balls in an admissible sequence of balls.

We now analyse the ratio of the probabilities. We write:

$\displaystyle\frac{\Pr[\mathcal{A}(X)=C]}{\Pr[\mathcal{A}(X^{\prime})=C]}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{k}\frac{\exp(\varepsilon^{\prime}\operatorname{Value}_{i}(\sigma_{i}^{1},X))}{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{1},X^{\prime}))}$
(9)
$\displaystyle\cdot\prod_{i=1}^{k}\frac{\sum_{B}\exp(\varepsilon\operatorname{Value}_{i}(B,X^{\prime}))}{\sum_{B}\exp(\varepsilon\operatorname{Value}_{i}(B,X))}$
(10)
$\displaystyle\cdot\prod_{i=1}^{k}\prod_{j=1}^{\operatorname{len}(\sigma_{i})}\frac{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{j},X))}{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{j},X^{\prime}))}$
(11)
$\displaystyle\cdot\prod_{i=1}^{k}\prod_{j=1}^{\operatorname{len}(\sigma_{i})}\frac{\sum_{B\in
C(\sigma_{i}^{j-1})}\exp(\varepsilon^{\prime}\operatorname{Value}(B,X^{\prime}))}{\sum_{B\in
C(\sigma_{i}^{j-1})}\exp(\varepsilon^{\prime}\operatorname{Value}(B,X))}$ (12)

We start by bounding the two easier Equation 11 and Equation 12. Those are the
standard terms from the exponential mechanism: for twe neighboring dataset
differing on a single point $p$, the value of any ball changes by at most
$\Delta$, and does so only when $p$ is part of the ball. So, when $p$ is part
of the ball $\sigma_{i}^{j}$, we have:
$\frac{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{j},X))}{\exp(\varepsilon^{\prime}\operatorname{Value}(\sigma_{i}^{j},X^{\prime}))}\leq\exp(\varepsilon^{\prime}\Delta)$,
and when $p$ is part of a ball among $C(\sigma_{i}^{j})$, we have:
$\frac{\sum_{B\in
C(\sigma_{i}^{j-1})}\exp(\varepsilon^{\prime}\operatorname{Value}(B,X^{\prime}))}{\sum_{B\in
C(\sigma_{i}^{j-1})}\exp(\varepsilon^{\prime}\operatorname{Value}(B,X))}\leq\exp(\varepsilon^{\prime}\Delta)$.

As mentioned before, is an admissible sequence $p$ is part of at most $\log n$
$\sigma_{i}^{j}$, and $\log n$ $C(\sigma_{i}^{j})$: therefore, the products of
Equation 11 and Equation 12 is bounded by $\exp(2\log
n\cdot\varepsilon^{\prime}\Delta)$.

We can now focus on the two more intricate terms, Equation 9 and Equation 10.
In the case where $X=X^{\prime}\cup\\{p\\}$, then for any ball $B$ and any
$i$,
$\operatorname{Value}_{i}(B,X^{\prime})\leq\operatorname{Value}_{i}(B,X)$, and
therefore term in Equation 10 is at most one. On the other hand,
$\operatorname{Value}(B,X)\leq\operatorname{Value}_{i}(B,X^{\prime})+\Delta$
when $B$ contains the point $p$, and
$\operatorname{Value}_{i}(B,X)=\operatorname{Value}(B,X^{\prime})$ if $B$
doesn’t contain $p$. Since at most $\log n$ of the $\sigma_{i}^{1}$ contain
$p$, the term in Equation 9 is at most $\exp(\log n\cdot\varepsilon)$.
Therefore,

$\Pr[\mathcal{A}(X)=C]\leq\exp(\log
n\cdot\varepsilon)\Pr[\mathcal{A}(X^{\prime})=C].$

The second case, where $X^{\prime}=X\cup\\{p\\}$, is more intricate. There,
Equation 9 is at most one, and we bound Equation 10 as follows: first, we
write for simplicity
$\pi_{i}(B):=\Pr[\mathcal{A}(X)_{i}^{j}=x~{}|~{}\\{\sigma,<i,<j\\}]=\frac{\exp(\varepsilon^{\prime}\operatorname{Value}_{i}(B,X))}{\sum_{B^{\prime}}\exp(\varepsilon^{\prime}\operatorname{Value}_{i}(B^{\prime},X^{\prime}))}$.

$\displaystyle\frac{\sum_{B^{\prime}}\exp(\varepsilon\operatorname{Value}_{i}(B^{\prime},X^{\prime}))}{\sum_{B^{\prime}}\exp(\varepsilon^{\prime}\operatorname{Value}_{i}(B^{\prime},X))}$
$\displaystyle=$
$\displaystyle\sum_{B^{\prime}}\pi_{i}(B^{\prime})\exp\left(\varepsilon^{\prime}(\operatorname{Value}_{i}(B^{\prime},X^{\prime})-\operatorname{Value}_{i}(B^{\prime},X))\right)$
$\displaystyle\leq$
$\displaystyle\sum_{B^{\prime}}\pi_{i}(B^{\prime})(1+2\varepsilon^{\prime}(\operatorname{Value}_{i}(B^{\prime},X^{\prime})-\operatorname{Value}_{i}(B^{\prime},X))/\Delta)$
$\displaystyle\leq$ $\displaystyle
1+2\varepsilon^{\prime}\sum_{B^{\prime}}\pi_{i}(B^{\prime})(\operatorname{Value}_{i}(B^{\prime},X^{\prime})-\operatorname{Value}_{i}(B^{\prime},X))$
$\displaystyle\leq$
$\displaystyle\exp\left(2\varepsilon^{\prime}\sum_{B^{\prime}}\pi_{i}(B^{\prime})(\operatorname{Value}_{i}(B^{\prime},X^{\prime})-\operatorname{Value}_{i}(B^{\prime},X))\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(2\varepsilon^{\prime}\Delta\sum_{B^{\prime}\text{ s.t.
}p\in B^{\prime}}\pi_{i}(B^{\prime})\right).$

The sum in the exponent corresponds to the probability to chose a ball
$B^{\prime}$ that contains $p$, after having made the choices
$\\{\sigma,<i,<j\\}$. We write $\pi_{i}$ this probability.

Therefore, combining with the bounds on Equation 11 and Equation 12, we have:

$\displaystyle\frac{\Pr[\mathcal{A}(x)=C]}{\Pr[\mathcal{A}(X^{\prime})=C]}\leq\exp\left(2\varepsilon^{\prime}\Delta\sum_{i=1}^{k}\pi_{i}\right)\cdot\exp\left(2\log
n\cdot\varepsilon^{\prime}\Delta\right).$

The analysis of [GLM+10] works black box from this point. They show that the
above equations implies that, for any set of possible outcomes $\mathcal{C}$,
it holds that

$\displaystyle\Pr[\mathcal{A}(x)\in\mathcal{C}]$
$\displaystyle\leq\exp(2\varepsilon^{\prime}\Delta\log(1/\delta)+2\log
n\cdot\varepsilon^{\prime}\Delta)\Pr[\mathcal{A}(X^{\prime})=\mathcal{C}]+\delta,$

which, with our choice of $\varepsilon^{\prime}$, concludes the proof.

∎

###  F.2 Parallel algorithm for MPC

See 5.1

###### Proof.

The proof of this lemma is grounded in the analysis of Algorithm 1, which we
conducted in Appendix D. We define
$\mathcal{A}(c_{\mathcal{A}},C)$,$\Gamma,\Gamma_{0}$, $\Gamma_{1}$, and the
$B_{\gamma}$’s for $\gamma\in\Gamma_{1}$ as detailed in Appendix D. Note that
$\mathcal{A}(c_{\mathcal{A}},C)$ is the set of balls of $\mathcal{B}$
available at scale $c_{\mathcal{A}}$ from $C$. Using Lemma D.2 and Equation 8,
we can reduce the task of proving Lemma 5.1 to bounding
$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}{B_{\gamma}}$. Note that the
constants appearing in Lemma D.2 depend on $c_{\mathcal{A}}$, but we consider
$c_{\mathcal{A}}$ as a fixed constant that does not appear in the $O(\cdot)$
notation.

In the proof of Theorem 3.4, to
$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}{B_{\gamma}}$, the proof
defines a function $\phi$ that maps the center of $\Gamma_{1}$ to balls of
$\mathcal{B}$ such that for all $\gamma\in\Gamma_{1}$:

  1. 1.

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

  2. 2.

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

  3. 3.

The value of $B_{\gamma}$ is less than
$\operatorname{Value}(\phi(\gamma))+\theta$.

Given such a mapping, the proof of Theorem 3.4 shows
$\sum_{\gamma\in\Gamma_{1}}\operatorname{Value}{B_{\gamma}}\leq\operatorname{cost}(P,\Gamma)$.
The same proof can be applied here: therefore, it is enough to construct the
mapping $\phi$. For this, we use the following procedure.

At the beginning of the procedure, the set $\Phi$ consists of all balls that
can be matched to a $\gamma$: this is all the balls of the form
$B(c,2^{-\ell})$ with $c\in C_{\ell}$, for all $\ell$. Until all
$\gamma\in\Gamma_{1}$ have been matched, repeat the following process. Let
$\gamma\in\Gamma_{1}$ be such that the radius of $B_{\gamma}$ is minimal,
among the centers of $\Gamma_{1}$ that have not yet been matched. $\gamma$ is
matched to an arbitrary ball $B(c,2^{-\ell})\in\Phi$ (ensuring that the radius
of $B_{\gamma}$ is also $2^{-\ell}$ and $c\in C_{\ell}$). All balls
intersecting $B(c,2^{-\ell})$ or containing $\gamma$ are removed from $\Phi$;
repeat the procedure for the next $\gamma$.

We begin by demonstrating that this procedure is well defined, namely that
there is always a ball $B(c,2^{-\ell})$ in $\Phi$. Once a ball
$B(c,2^{-\ell})$ is selected, at most $2$ balls per level
$\ell^{\prime}\leq\ell$ are eliminated. This is due to condition (1) of the
lemma, which ensures that the distance between two distinct centers of
$C_{\ell^{\prime}}$ is greater than $3\cdot 2^{-\ell^{\prime}}$. This
condition has two implications: first, the balls
$B(c^{\prime},2^{-\ell^{\prime}})$ with $c^{\prime}\in C_{\ell^{\prime}}$ are
disjoint, and therefore at most one contains $\gamma$. Second, a single ball
$B(c^{\prime},2^{-\ell^{\prime}})$ at level $\ell^{\prime}$ can intersect
$B(c,2^{-\ell})$. Indeed, assuming by contradiction that two balls
$B(c^{\prime}_{1},2^{-\ell^{\prime}})$ and
$B(c^{\prime}_{2},2^{-\ell^{\prime}})$ intersect $B(c,2^{-\ell})$, we have, by
the triangle inequality,
$\operatorname{dist}(c^{\prime}_{1},c^{\prime}_{2})\leq 2\cdot
2^{-\ell^{\prime}}+2^{-\ell}\leq 3\cdot 2^{-\ell^{\prime}}$ because we assumed
$\ell^{\prime}\leq\ell$.

The procedure defines $\phi$ by increasing order of the radii of the
$B_{\gamma}$’s. Therefore, when the center $\gamma^{\prime}$ with
$B_{\gamma^{\prime}}=B(c^{\prime},2^{-\ell^{\prime}})$ is considered in the
procedure, all centers $\gamma$ previously matched had
$B_{\gamma}=B(c,2^{-\ell})$ with $\ell^{\prime}\leq\ell$: the previous
discussion implies that each of those removed at most two balls with radius
$2^{-\ell^{\prime}}$ from $\Phi$.

By construction of our algorithm, each $C_{\ell}$ contains $2k$ centers: since
there are $k$ centers in $\Gamma$, the matching $\phi$ is well defined. We can
now verify that this matching satisfies the three desired properties.

  1. 1.

The procedure guarantees that for all $\gamma,\gamma^{\prime}\in\Gamma_{1}$,
$\phi(\gamma)\cap\phi(\gamma^{\prime})=\emptyset$ because when a ball is
selected, any ball intersecting it is removed from $\Phi$.

  2. 2.

Let $\gamma\in\Gamma$. Assume by contradiction that there exists
$\gamma^{\prime}\in\Gamma$ covering $\phi(\gamma)$, and let
$B_{\gamma}=B(z,2^{-\ell})$, $\phi(\gamma)=B(c,2^{-\ell})$ (the procedure
ensures that $\phi(\gamma)$ has same radius as $B_{\gamma}$), and
$B_{\gamma^{\prime}}=B(z^{\prime},2^{-\ell^{\prime}})$. By definition of
covering, $\gamma^{\prime}\in\phi(\gamma)$. First, in the case where
$\ell^{\prime}>\ell$, $\gamma^{\prime}$ is processed before $\gamma$ in the
procedure: all the balls containing $\gamma^{\prime}$ have been removed from
$\Phi$ when $\phi(\gamma^{\prime})$ is defined, and in particular
$\phi(\gamma)$. This yields to a contradiction. In the other case, when
$\ell^{\prime}\leq\ell$, we note the following inequality:
$\operatorname{dist}(c,\gamma^{\prime})\leq 2^{-\ell}\leq 2^{-\ell^{\prime}}$.
Moreover by definition of $B_{\gamma^{\prime}}$,
$\operatorname{dist}(\gamma^{\prime},z^{\prime})\leq 2^{-\ell^{\prime}}/2$.
Using the triangle inequality we obtain $\operatorname{dist}(c,z^{\prime})\leq
1.5\cdot 2^{-\ell^{\prime}}\leq c_{\mathcal{A}}\cdot 2^{-\ell^{\prime}}$, this
implies that $B_{\gamma^{\prime}}$ is not available at scale $c_{\mathcal{A}}$
from $C$, which contradicts the definition of $B_{\gamma^{\prime}}$. Those two
cases concludes that there is no $\gamma^{\prime}$ covering $\phi(\gamma)$.

  3. 3.

By definition, $B_{\gamma}$ is in $\mathcal{A}(c_{\mathcal{A}},C)$, and the
condition $3.$ of the lemma states that the value of the ball
$\phi(\gamma)=B(c,2^{-\ell})$ is greater (up to an additive error $\theta$)
than the value of any ball of $\mathcal{B}_{\ell}$ available at scale
$c_{\mathcal{A}}$ from $C_{\ell}$: this set contains
$\mathcal{A}(c_{\mathcal{A}},C)$, and therefore it contains $B_{\gamma}$, and
the third condition holds.

This conclude the proof of Lemma 5.1. ∎

We describe more formally the greedy algorithm described in the main body. We
suppose that machines are organized in a tree structure, where the degree of
every node is $n^{\kappa}$ – so that the depth of the tree is $1/\kappa$. We
also suppose the dimension is reduced to $\hat{d}=O(\log(k))$. The algorithm
works as in the centralized case: first solve $(k,z)$-clustering in this
projected space, then lift-up the centers in $\mathbb{R}^{d}$.

Initially, each possible ball is assigned randomly to one of the leaf (this
can be implemented with a simple hash-function). Using standard MPC procedure,
each machine can compute the value of each non-empty ball assigned to it.

For a leaf $M$, let $B(M)$ be the set of non-empty balls assigned to $M$. For
each round $i=0,\ldots,1/\kappa$, the following process happens. First, each
machine $M$ at height $i$ in the tree runs the greedy algorithm with distance
parameter $D_{i}:=2^{-i}\cdot 32^{1/\kappa}$. Let $S_{M}$ be the $2k$ balls
selected by $M$: $M$ sends $S_{M}$ to its parent. For each machine at height
$i+1$, let $B(M)$ be the set of balls received by $M$. This marks the end of
the round.

First, the privacy of this algorithm follows directly from composition: at
each level of the tree, properties of the exponential mechanism (or, more
precisely, the proof of Lemma F.2) ensure that process is
$(\varepsilon,\delta)$-DP, and there are $1/\kappa=O(1)$ many levels.

We verify that this algorithm can indeed be implemented in MPC when machines
have memory $k^{O(1)}n^{\kappa}$. Note there are at most
$2^{\hat{d}}n=k^{O(1)}n$ non-empty balls at each level: therefore it is
possible to represent all non-empty balls in the memory: each of the
$n^{1-\kappa}$ machine has memory
$k^{O(1)}n^{\kappa}\operatorname{polylog}(n)$. Assigning uniformly at random
the balls to leafs ensures that with high probability they are assigned in a
balanced way, and that they fit in memory.

To implement the exponential mechanism, the algorithm do not actually have
access to all balls assigned to the machine $M$ – only the non-empty ones.
Instead, the algorithm uses the exponential mechanism on the following set:
all possible balls, with value $0$, and all non-empty balls assigned to $M$,
with their true value. This can be efficiently implemented in time
$k^{O(1)}n^{\kappa}\operatorname{polylog}(n)$, and ensures that with
probability $1-\beta^{\prime}$, the ball selected by one exponential mechanism
have maximum value up to
$\theta=O\left(\frac{\hat{d}\log(n/\beta^{\prime})}{\varepsilon}\right)$.

The exponential mechanism is used $2k$ times on each machine: choosing
$\beta^{\prime}=\frac{\beta}{2kn^{1-\kappa}}$ allows to do a union bound, and
shows that all ball selected have maximum value up to
$\theta=O\left(\frac{\hat{d}\log(n/\beta)}{\varepsilon}\right)$.

We will condition all our analysis on the fact that the exponential mechanism
selects ball with maximal value, up to an additive error $\theta$. To compute
$\theta$, note that the exponential mechanism is used $2k$ times in each
machine, each time to select one ball out of $n^{\hat{d}}$ many balls. in
total it is used $2kn^{1-\kappa}$ times To analyse this greedy algorithm, we
note the following crucial claims:

######  Claim F.3.

Let $M$ be a machine and $M^{\prime}$ be its parent. Then, the smallest value
in $S_{M^{\prime}}$ is larger (up to $\theta$) than the smallest value in
$S_{M}$.

###### Proof.

The greedy process ensures all balls in $S_{M}$ are at distance at least
$2^{-h(M)}c_{\mathcal{A}}\cdot 2^{-\ell}$ of each other, where $h(M)$ is the
height of $M$ in the tree. Therefore, by triangle inequality every ball
selected in $S_{M^{\prime}}$ forbids at most one ball of $S_{M}$ (due to the
exponential decrease of the distance parameter): as a consequence, at any
choice made by the greedy on $M^{\prime}$, at least a ball of $S_{M}$ is still
available. Therefore, the value of selected balls in $S_{M^{\prime}}$ are only
larger than the ones in $S_{M}$ (up to an additive error $\theta$ due to the
exponential mechanism). ∎

######  Claim F.4.

Let $B$ be a ball in $\mathcal{B}(M)$ forbidden by some $B^{\prime}\in S_{M}$
at scale $\sum_{i\leq h(M)}D_{i}$. Then,
$\operatorname{Value}(B)\leq\operatorname{Value}(B^{\prime})+h(M)\theta$.

###### Proof.

Let $M_{i}$ be the machine at height $i$ such that $B\in\mathcal{B}(M_{i})$.
Define $B_{i}$ as follows:

  1. 1.

if $B_{i-1}\in S_{M_{i}}$, $B_{i}=B_{i-1}$

  2. 2.

if $B_{i-1}$ is available at scale $D_{i}$ from $S_{M_{i}}$: let $B_{i}$ be an
arbitrary ball in $S_{M_{i}}$

  3. 3.

otherwise, $B_{i-1}$ is forbidden by some ball in $S_{M_{i}}$. Let $B_{i}$ be
the first ball in the greedy process to forbid $B_{i-1}$.

Now, we claim that
$\operatorname{Value}(B_{i})\geq\operatorname{Value}(B)-i\theta$. This is
obvious in the first case. In the second case, this is directly due to the
greedy procedure: for each choice of the greedy on $M_{i}$, the ball $B_{i-1}$
is available, and therefore the ball selected has value at least
$\operatorname{Value}(B_{i-1})-\theta$. In the third case, at the moment
$B_{i}$ is chosen by the greedy procedure on $M_{i}$, $B_{i-1}$ is still
available and therefore
$\operatorname{Value}(B_{i})\geq\operatorname{Value}(B_{i-1})-\theta$.

Since $B^{\prime}=B_{h(m)}$, this concludes the claim. ∎

we can now show this implementation of the greedy achieve the guarantees
required by Lemma 5.1.

######  Lemma F.5.

Let $C_{\ell}$ be the set of balls selected by the merge-and-reduce process
described above after $1/\kappa$ rounds. The balls of $C_{\ell}$ are at
distance at least $3\cdot 2^{-\ell}$ from each other, and the value of any
ball in $C_{\ell}$ is larger (up to $\theta/\kappa$) than the value of any
ball available at scale $2^{1/\kappa+1}\cdot 3$.

###### Proof.

The first part of the statement follows directly from the greedy merging: at
the root of the tree, the ball selected are at distance $3\cdot 2^{-\ell}$
from each other. For the second, we proceed by induction.

We start with few notations: for a machine $M$, we let $h(M)$ be the height of
$M$ in the tree, and $c(M)$ be the set of children of $M$. We define
inductively $\mathcal{B}_{M}:=\cup_{M^{\prime}\in
c(M)}\mathcal{B}_{M^{\prime}}$ to be the set of balls covered by machine $M$
(for a leaf $M$ $\mathcal{B}_{M}$ be the balls assigned to the leaf $M$ by the
random assignment). We define $S_{M}$ be the set of balls selected by the
greedy procedure run on $M$.

Our inductive claim is that the balls selected in $S_{M}$ have larger values,
up to an additive error $\theta h(M)$, than the balls in $\mathcal{B}_{M}$
available at scale $\sum_{i\leq h(M)}D_{i}\cdot 2^{-\ell}$ from $S_{M}$. When
$h(M)=0$, this property stems directly from the greedy algorithm.

For $h(M)\geq 1$, we proceed as follows: let $B$ be a ball available at scale
$\sum_{i\leq h(M)}D_{i}\cdot 2^{-\ell}$ from $S_{M}$. Let $M^{\prime}$ be the
children of $M$ such that $B\in\mathcal{B}_{M^{\prime}}$. First, in the case
where $B\in S_{M^{\prime}}$, $B$ is part of the greedy process on machine $M$:
since it is available and not selected, it has smaller value than any ball
selected in $S_{M}$ up to an additive error $\theta$.² Second, in the case
where $B\notin S_{M^{\prime}}$: either $B$ is forbidden at scale
$D_{h(M^{\prime})}$ by some ball $B^{\prime}\in S_{M^{\prime}}$, or $B$ is
available at scale $D_{h(M^{\prime})}$ from $S_{M^{\prime}}$.

  * •

First, suppose $B$ is forbidden by some $B^{\prime}\in S_{M^{\prime}}$ at
scale $\sum_{i\leq h(M^{\prime})}D_{i}$. It cannot be that $B^{\prime}\in
S_{M}$, as otherwise $B$ would be forbidden at scale $\sum_{i\leq h(M)}D_{i}$
from $S_{M}$. Therefore, either $B^{\prime}$ is forbidden at scale $D_{h(M)}$
from $S_{M}$, or it is still available at the end of the greedy on $M$. In the
first case, triangle inequality shows that $B$ is at distance at most
$\sum_{i\leq h(M)}D_{i}$ of $S_{M}$, which contradicts the initial condition
on $B$. On the second case, if $B^{\prime}$ is still available at scale
$D_{h(M)}$ from $S_{M}$, then the greedy ensures that its value is smaller
than that of any ball selected in $S_{M}$, up to an additive error $\theta$.
Hence, combined with F.4, this shows that the value of $B$ is smaller than any
ball of $S_{M}$, up to an additive error $h(M)\theta$.

  * •

In the case $B$ is available at scale $\sum_{i\leq h(M^{\prime})}D_{i}$ from
$S_{M^{\prime}}$, then we know by induction that its value is less than any
selected ball in $S_{M^{\prime}}$, up to an additive $h(M^{\prime})\theta$. As
shown in F.3, this implies its value is less than any selected ball in $S_{M}$
as well, up to an additive error $h(M^{\prime})\theta+\theta=h(M)\theta$,
which concludes the inductive claim.

Therefore, at height $2^{1/\kappa}$ (i.e., the root of the merge-and-reduce
tree), the balls selected have higher values than the one available at scale
$\sum_{i\leq 2^{1/\kappa}}D_{i}2^{-\ell}$. As $D_{i}=2^{1/\kappa-i}$, this is
at most $2^{1/\kappa+1}\cdot 2^{-\ell}$, which concludes the lemma. ∎

Combining those lemmas proves Theorem 5.2:

###### Proof of Theorem 5.2.

Lemma F.5 shows that, at each level, the set $C_{\ell}$ computed by the
algorithm satisfies the conditions of Lemma 5.1 (with
$c_{\mathcal{A}}=2^{1/\kappa+1}\cdot 3$ and
$\theta=O\left(\frac{\hat{d}\log(n/\beta)}{\varepsilon}\right)$): therefore,
$C=\cup C_{\ell}$ verifies $\operatorname{cost}(P,C)\leq
O(1)\textsc{opt}_{k,z}+O\left(k\cdot\frac{\hat{d}\log(n/\beta)}{\varepsilon}\right))$.

Furthermore, $C$ has size $O(k\log n)$: it can be aggregated in a single
machine. The techniques from Section C.1 allows then to reduce the number of
centers selected to $k$, without increasing the error.

Finally, to lift-up the solution in the original space, we use Lemma 2.2:
using noisy average, we can estimate the mean of each cluster up to an
additive error $O\left(\sqrt{d}/\varepsilon\right)$, which yields a solution
with cost
$O(1)\textsc{opt}_{k,z}+O\left(\operatorname{polylog}(n)\cdot\frac{k\sqrt{d}}{\varepsilon}\right)$.

For the second part of the lemma, we need to boost the approximation ratio
using Section 2.2. For this, Lemma 2.4 directly applies, if we can lift up the
solution to the original space. For $k$-means, we can simply compute the noisy
average of each cluster – which gives an extra additive error
$O(k\sqrt{d}\log(1/\delta)/\varepsilon)$, as in the proof of Lemma F.1.

Recovering the optimal $(1,z)$-clustering in each cluster, using low memory,
is more intricate. For this, we apply the techniques presented in Theorem E.6
of [CEM+22], to get an additive error
$(2^{\hat{d}}+k\sqrt{d})\operatorname{polylog}(n/\delta)/\varepsilon$.

In both cases, this provides a solution with cost
$(1+\alpha)w^{*}\textsc{opt}_{k,z}+(k^{O_{\alpha}(1)}+k\sqrt{d})\operatorname{polylog}(n/\delta)/\varepsilon$.
∎

##  Appendix G A note on $\varepsilon$-Differential Privacy

Our results partially extend to pure-DP, i.e. when $\delta=0$. In that case,
we can adapt our algorithm for the optimal multiplicative approximation : in
most models, there is a general summation algorithm with additive error
essentially worsen by a $\sqrt{b}$ factor, compared to
$(\varepsilon,\delta)$-DP. For centralized DP, the additive error is
$b\sqrt{D}\log(m/\beta)/\varepsilon$ – this is a direct extension of
histograms. In local DP, the additive error we presented already worked in the
case $\delta=0$ – as the summation result of [CGKM21] that we used readily
works in this case.

For $\varepsilon$-DP under continual observation, we can apply the second part
of our Lemma B.3 to get that an additive error worsen by a $\sqrt{d\log(T)}$ –
leading to a $(k,z)$-clustering with additive error
$dk^{O_{\alpha}(1)}\log^{3}(n)\log^{2}(T)\log(1/\beta)$.