# Towards Optimal Lower Bounds for $k$-median and $k$-means Coresets

Vincent Cohen-Addad Google Research, Zurich. Kasper Green Larsen Aarhus
University David Saulpic Sorbonne Université, Paris Chris Schwiegelshohn†

###### Abstract

Given a set of points in a metric space, the $(k,z)$-clustering problem
consists of finding a set of $k$ points called centers, such that the sum of
distances raised to the power of $z$ of every data point to its closest center
is minimized. Special cases include the famous $k$-median problem ($z=1$) and
$k$-means problem ($z=2$). The $k$-median and $k$-means problems are at the
heart of modern data analysis and massive data applications have given raise
to the notion of coreset: a small (weighted) subset of the input point set
preserving the cost of any solution to the problem up to a multiplicative
$(1\pm\varepsilon)$ factor, hence reducing from large to small scale the input
to the problem.

While there has been an intensive effort to understand what is the best
coreset size possible for both problems in various metric spaces, there is
still a significant gap between the state-of-the-art upper and lower bounds.
In this paper, we make progress on both upper and lower bounds, obtaining
tight bounds for several cases, namely:

  * •

In finite $n$ point general metrics, any coreset must consist of $\Omega(k\log
n/\varepsilon^{2})$ points. This improves on the $\Omega(k\log n/\varepsilon)$
lower bound of Braverman, Jiang, Krauthgamer, and Wu [ICML’19] and matches the
upper bounds proposed for $k$-median by Feldman and Langberg [STOC’11] and
$k$-means by Cohen-Addad, Saulpic, and Schwiegelshohn [STOC’21] up to polylog
factors.

  * •

For doubling metrics with doubling constant $D$, any coreset must consist of
$\Omega(kD/\varepsilon^{2})$ points. This matches the $k$-median and $k$-means
upper bounds by Cohen-Addad, Saulpic, and Schwiegelshohn [STOC’21] up to
polylog factors.

  * •

In $d$-dimensional Euclidean space, any coreset for $(k,z)$ clustering
requires $\Omega(k/\varepsilon^{2})$ points. This improves on the
$\Omega(k/\sqrt{\varepsilon})$ lower bound of Baker, Braverman, Huang, Jiang,
Krauthgamer, and Wu [ICML’20] for $k$-median and complements the
$\Omega(k\min(d,2^{z/20}))$ lower bound of Huang and Vishnoi [STOC’20].

We complement our lower bound for $d$-dimensional Euclidean space with the
construction of a coreset of size
$\tilde{O}(k/\varepsilon^{2}\cdot\min(\varepsilon^{-z},k))$. This improves
over the $\tilde{O}(k^{2}\varepsilon^{-4})$ upper bound for general power of
$z$ proposed by Braverman Jiang, Krauthgamer, and Wu [SODA’21] and over the
$\tilde{O}(k/\varepsilon^{4})$ upper bound for $k$-median by Huang and Vishnoi
[STOC’20]. In fact, ours is the first construction breaking through the
$\varepsilon^{-2}\cdot\min(d,\varepsilon^{-2})$ barrier inherent in all
previous coreset constructions. To do this, we employ a novel chaining based
analysis that may be of independent interest. Together our upper and lower
bounds for $k$-median in Euclidean spaces are tight up to a factor
$O(\varepsilon^{-1}\text{polylog }k/\epsilon)$.

##  1 Introduction

A clustering is a partition of a data set $P$ such that data points in the
same cluster are similar and points in different clusters are dissimilar.
Various clustering problems have become important cornerstones in
combinatorial optimization and machine learning problems. Among these, center-
based clustering problems are arguably the most widely studied and used. Here,
the data elements lie in a metric space, every cluster is associated with a
center point and the cost of a data point is some function of the distance
between data point and its assigned cluster. The $(k,z)$ problem captures this
and other important objectives via the cost function

$\text{cost}(P,\mathcal{S}):=\sum_{p\in
P}\underset{s\in\mathcal{S}}{~{}\min~{}}d(p,s)^{z},$

where $z$ is a positive integer, $|\mathcal{S}|=k$ and $d(~{},~{})$ denotes
the distance function. For $z=1$, this is $k$-median problem and for $z=2$,
this is the equally intensely studied $k$-means problem.

Datasets used in practice are often huge, containing hundred of millions of
points, distributed, or evolving over time. Hence, in these settings classical
heuristics (such as Lloyd or k-means++) are lapsed; the size of the dataset
forbids multiple passes over the input data and finding a “compact
representation” of the input data is of primary importance. This leads to a
tradeoff: the smaller the dataset, the less storage we need and the faster we
can run an algorithm on the data set, but conversely the smaller the data set
the more information about the orginal data will be lost. _Coresets_ formalize
and study this tradeoff. Specifically, given a precision parameter
$\varepsilon$, $k$ and $z$, an $(\varepsilon,k,z)$ coreset $\Omega$ is a
subset of $P$ with weights $w:\Omega\rightarrow\mathbb{R}$ that approximates
the cost of $P$ for any candidate solution $\mathcal{S}$ up to a
$(1\pm\varepsilon)$ factor, namely

$\forall\mathcal{S},~{}~{}~{}(1-\varepsilon)\text{cost}(P,\mathcal{S})\leq\sum_{p\in\Omega}w(p)\text{cost}(p,\mathcal{S})\leq(1+\varepsilon)\text{cost}(P,\mathcal{S}).$

A small $(\varepsilon,k,z)$ coreset is therefore a good compression of the
initial dataset, since it preserves the cost of any possible solution. Instead
of storing the full dataset, one can simply store the coreset, saving on
memory footprint and speeding up performances. We note that in some
definitions, an offset $\Delta$ is added to the coreset: in that case, the
coreset cost of solution $\mathcal{S}$ is
$(1\pm\varepsilon)\text{cost}(P,\mathcal{S})+\Delta$. In the case where the
input space is infinite (e.g., Euclidean space), the coreset points may be
chosen from the whole space, and are not restricted to be part of the input.

Although numerous great work focused on improving the size of coreset
constructions, our understanding of coreset lower bounds is comparatively
limited, and there is a significant gap between the best upper and lower
bounds on the possible coreset size. For example, even for Euclidean
$k$-means, nothing beyond the trivial $\Omega(k)$ lower bound is known. In
this work, we attempt to systematically obtain lower bounds for these
problems.

We pay a particular attention to Euclidean Spaces. For those, we complement
our lower bound with a new coreset construction that has an optimal dependency
in $1/\varepsilon$.

###  1.1 Our Results

Metric Space |  Best upper bound | Best lower bound |  Our result
---|---|---|---
Discrete Metrics |  $O(k\varepsilon^{-\max(2,z)}\log n)$ [35] |  $\Omega(k\varepsilon^{-1}\log n)$ [6] |  $\Omega(k\varepsilon^{-2}\log n)$*
with doubling dimension $D$ |  $O(k\varepsilon^{-\max(2,z)}D)$ [35] | - |  $\Omega(k\varepsilon^{-2}D)$*
Euclidean $k$-median |  $\widetilde{O}(k\varepsilon^{-4})$ [55] |  $\Omega(k\varepsilon^{-1/2})$ [6] |  $\widetilde{O}(k\varepsilon^{-3})$ $\Omega(k\varepsilon^{-2})$
Euclidean $k$-means |  $\widetilde{O}(k\varepsilon^{-4})$ [35] | - |  $\Omega(k\varepsilon^{-2})$
Euclidean |  $\widetilde{O}(k\varepsilon^{-2-\max(2,z)})$ [35] $\widetilde{O}(k^{2}\varepsilon^{-4})$ [17] |  $\Omega(k2^{z/100})$ [55] |  $\widetilde{O}_{z}(k\varepsilon^{-2}\cdot\min(\varepsilon^{-z},k))$ $\Omega(k\varepsilon^{-2})$
Figure 1: Comparison between the state-of-the-art bounds and our results.
Results marked with * are tight for $k$-median and $k$-means.

We settle the complexity of the problem for several cases. First, for finite
$n$-point metrics, we prove the following theorem.

######  Theorem 1.

For any $0<\varepsilon<1/2$, $k$ and $n\geq\varepsilon^{-5}$ such that $\log
k=O(\log n)$, there exists a finite $n$ point metric such that any
$(\varepsilon,k,z)$ coreset using offset $\Delta$ consists of at least
$\Omega\left(\frac{k}{\varepsilon^{2}}\log n\right)$ points.

Our result improves over the $\Omega(k\varepsilon^{-1}\log n)$ lower bound of
Baker, Braverman, Huang, Jiang, Krauthgamer, and Wu [6]. For the $k$-median
and $k$-means objective matches the upper bounds proposed in Feldman and
Langberg [41] and Cohen-Addad, Saulpic, and Schwiegelshohn [35] up to
polylog$(1/\varepsilon)$ factors.

For metric space with doubling dimension $D$, we present a lower bound similar
to that of Theorem 1:

######  Corollary 2.

For any $\varepsilon,k,D$ such that $D\geq 5\log 1/\varepsilon$ and $\log
k=O(D)$, there exists a graph with doubling dimension $D$ on which any
$(\varepsilon,k,z)$-coreset using offset $\Delta$ must have size
$\Omega\left(\frac{kD}{\varepsilon^{2}}\right)$.

This matches up to polylog$(1/\varepsilon)$ factors the upper bound from [35]
for $k$-median and $k$-means.

We also study Euclidean spaces more specifically. Here, the difficulty is that
centers can be placed arbitrarily in the space, and not only at input points.
Our main results for Euclidean spaces is the following.

######  Theorem 3 (See Theorem 11 for the exact statement).

For any $0<\varepsilon<1/2$ and any $k$, there exists a point set such that
any $(\varepsilon,k,z)$ coreset using offset $\Delta$ consists of at least
$\Omega\left(\frac{k}{\varepsilon^{2}\max\\{1,z^{4}\\}}\right)$ points.

This lower bound holds for any selection of points (i.e. the coreset may use
non-input points), and for any additive offset, which is a generalization
initially proposed by Feldman, Schmidt, and Sohler [43] and which has since
been used in a number of other papers, see Cohen, Elder, Musco, Musco, and
Persu [25], Sohler and Woodruff [86] and Cohen-Addad, Saulpic and
Schwiegelshohn [34]. The only previously known results are the
$\Omega(k/\sqrt{\varepsilon})$ bound for $k$-median by Baker, Braverman,
Jiang, Krauthgamer, and Wu [6], and the $\Omega(k\cdot\min(d,2^{z/20}))$ bound
by Huang and Vishnoi [55]. Thus, we obtain the first non-trivial lower bound
for Euclidean $k$-means.

We complement the lower bound with the following theorem.

######  Theorem 4.

Given a set of points $P$ in $d$-dimensional Euclidean space and any
$\varepsilon>0$, there exists an $(\varepsilon,k,z)$ coreset of size
$\tilde{O}(k\cdot\varepsilon^{-2}\cdot 2^{O(z\log
z)}\cdot\min(\varepsilon^{-z},k))$.

This is the first coreset construction with an optimal dependency on
$\varepsilon$, at the cost of a quadratic dependency on $k$. Previously, all
upper bounds either had a dependency of at least $\varepsilon^{-4}$ [18, 35,
55] or a dependency on $d$ [23, 41].

We note that for the special case of Euclidean $k$-median, we improve the best
coreset size from $O(k\cdot\varepsilon^{-4})$ to $O(k\cdot\varepsilon^{-3})$,
taking a step to reduce the gap with the lower bound.

A complete overview of previous coreset bounds for Euclidean spaces and finite
metrics is given in Table 1. For further related work, we refer to Section 2.

###  1.2 Overview of our Techniques

Our results for the Euclidean setting require several important new technical
insights and we thus review them first. We later review our approach for our
lower bound for general metrics.

#### Euclidean Lower Bounds

The lower bound proof consists of three separate steps which combined proves
that any coreset for the point set $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{d}$ (i.e., the standard basis of $\mathbb{R}^{d}$) must have size
$\Omega(k\cdot\varepsilon^{-2})$ (in this proof overview, we focus on $z=2$)
when $d=\Theta(k\cdot\varepsilon^{-2})$. The basic approach is to show that
any clustering of $P$ with $k$ centers has large cost, while at the same time,
for any coreset $\Omega$ using $o(d)$ weighted points, there is a low cost
clustering. Combining the two yields the lower bound. We carry out this proof
in three steps. In the first step, we show that any clustering of $P$ using
unit norm centers has cost at least $2d-O(\sqrt{dk})$. In the next step, we
show that for any coreset $\Omega$ consisting of $t$ points and a weighing
$w:\Omega\to\mathbb{R}^{+}$, there is a low-cost clustering using unit norm
centers that has cost
$2d-\Omega(\sqrt{k/t}\cdot\sum_{p\in\Omega}w(p)\|p\|_{2})$. Combining this
with step one implies $\sum_{p\in\Omega}w(p)\|p\|_{2}=O(\sqrt{td})$. In the
final step, we show that any coreset $\Omega$ must have
$\sum_{p\in\Omega}w(p)\|p\|_{2}=\Omega(d)$ when
$d=\Theta(k\cdot\varepsilon^{-2})$. Combining this with the previous two steps
finally yields $\sqrt{td}=\Omega(d)\Rightarrow t=\Omega(d)\Rightarrow
t=\Omega(k\cdot\varepsilon^{-2})$. In the following, we elaborate on the high
level ideas needed for each of the steps:

1\. First, we show that any clustering of $P$ using $k$ cluster centers
$c_{1},\dots,c_{k}$ of unit norm, must have cost at least $2d-O(\sqrt{dk})$.
To see this, notice that if $e_{i}$ is assigned to cluster center $c_{j}$,
then the cost of $e_{i}$ is
$\|e_{i}-c_{j}\|_{2}^{2}=\|e_{i}\|_{2}^{2}+\|c_{j}\|_{2}^{2}-2\langle
e_{i},c_{j}\rangle=2-2c_{j,i}$, where $c_{j,i}$ denotes the $i$’th coordinate
of $c_{j}$. Any cluster center $c_{j}$ can thus at most reduce the cost of the
clustering below $2d$ by an additive $2\sum_{i}c_{j,i}\leq 2\|c_{j}\|_{1}$.
Moreover, it is only “wasteful” to assign a value different from $0$ to
$c_{j,i}$ if $e_{i}$ is not assigned to center $c_{j}$ (wasteful since $c_{j}$
is required to have unit norm). Thus the $k$ centers can be thought of as
having disjoint supports. Thus on average, they only have $d/k$ coordinates
available. By Cauchy-Schwartz (i.e. the maximum ratio between $\|c_{j}\|_{1}$
and $\|c_{j}\|_{2}$), we can argue that
$\sum_{j}\|c_{j}\|_{1}\leq\sqrt{d/k}\sum_{j}\|c_{j}\|_{2}=\sqrt{dk}$ and the
conclusion follows.

2\. Next, we argue that for any coreset $\Omega$ consisting of $t$ points and
a weighing $w:\Omega\to\mathbb{R}^{+}$, we can find a low-cost clustering in
terms of $\sum_{p\in\Omega}w(p)\|p\|_{2}$ using unit norm centers. This is
achieved by partitioning the points of the coreset into $k$ groups of
$\ell=t/k$ points each and using one center for each group. For a group of
$\ell$ points $r_{1},\dots,r_{\ell}$, we choose the center as something that
resembles the mean scaled to have unit norm. More precisely, we consider a
random vector $u=\sum_{i=1}^{\ell}\sigma_{i}w(r_{i})r_{i}$ for uniform random
and independent signs $\sigma_{i}$. We can then argue that there is a fixing
of the signs, such that if $u$ is scaled to have unit norm and this is
repeated for all $k$ groups, the resulting cluster cost is at most
$2d-\Omega(\sqrt{k/t}\sum_{p\in\Omega}w(p)\|p\|_{2})$.

3\. In the last step, we need to argue that any coreset $\Omega$ and weighing
$w:\Omega\to\mathbb{R}^{+}$ must have
$\sum_{p\in\Omega}w(p)\|p\|_{2}=\Omega(d)$ when
$d=\Theta(k\cdot\varepsilon^{-2})$. This is the technically most challenging
part of the proof. The basic idea for arguing this, is to exploit that
$\Omega$ must be a coreset for many different clusterings of
$P=\\{e_{1},\dots,e_{d}\\}$. In particular, we consider the Hadamard basis
over $q=d/k$ coordinates. The Hadamard basis consists of $q$ orthogonal
vectors with coordinates in $\\{-1/\sqrt{q},1/\sqrt{q}\\}$, all having at
least half of the coordinates equal to $1/\sqrt{q}$. For each vector $v$ in
the basis, we consider a clustering where we use $k$ centers
$c_{1},\dots,c_{k}$ that are all copies of $v$ shifted to take up either the
first $q$ coordinates in $\mathbb{R}^{d}$, the next $q$ coordinates and so on.
Since half of the coordinates of any $v$ are $1/\sqrt{q}$, the cost of this
clustering on $P$ is $2d-\Omega(d/\sqrt{q})$ (if $e_{i}$ is assigned to a
center with the $i$’th coordinate is equal to $1/\sqrt{q}$ then the cost of
$e_{i}$ is $2-2/\sqrt{q}$). Thus intuitively, the points $r_{1},\dots,r_{t}$
in any coreset $\Omega$ also must have $\sum_{i=1}^{t}\max_{j=1}^{k}\langle
r_{i},c_{j}\rangle=\Omega(d/\sqrt{q})$. This means that on average over all
$r_{i}$, we have $\max_{k=1}^{k}w(r_{i})\langle
r_{i},c_{j}\rangle=\Omega(d/(t\sqrt{q}))$. The crucial observation is that we
can repeat this argument for every $v$ in the basis. There are $q$ such $v$’s.
Moreover, for any point $r_{i}$ in the coreset, the set of $q$ centers
$c_{i_{1}}^{1},\dots,c_{i_{q}}^{q}$ it is assigned to in these $q$ different
clusterings are all orthogonal vectors. Thus by Cauchy-Schwartz, we must have
$\sqrt{q}d/t\leq\sum_{j=1}^{q}\langle w(r_{i})r_{i},c_{i,j}^{j}\rangle=\langle
w(r_{i})r_{i},\sum_{j=1}^{q}c_{i_{j}}^{j}\rangle\leq\|w(r_{i})r_{i}\|_{2}\|\sum_{j=1}^{q}c_{i,j}^{j}\|_{2}=w(r_{i})\|r_{i}\|_{2}\sqrt{q}$.
That is, $w(r_{i})\|r_{i}\|_{2}=\Omega(d/t)$. Summing over all $r_{i}$
completes the proof. Finally, let us remark where the requirement
$d=\Theta(k\cdot\varepsilon^{-2})$ enters the picture. We argued that the cost
of clustering $P$ using the Hadamard basis was $2d-\Omega(d/\sqrt{q})$. In the
coreset, the clustering is allowed to be a factor $(1+\varepsilon)$ larger. We
thus require that $(2d-\Omega(d/\sqrt{q}))(1+\varepsilon)\leq
2d-\Omega(d/\sqrt{q})$, which is satisfied when
$d\varepsilon=O(d/\sqrt{q})\Leftrightarrow q=O(\varepsilon^{-2})$. But $q=d/k$
and thus this translates into $d=O(k\cdot\varepsilon^{-2})$.

#### Upper Bounds

Our main technical contribution is an application of chaining techniques used
to analyse Gaussian processes for coreset construction, see Talagrand for an
extensive introduction [87]. To the best of our knowledge, we are not aware of
any prior attempts of using chaining to improve coreset bounds directly.

For readers that may not be familiar with the technique, we now highlight how
it allows us to improve over previous constructions. For every candidate
solution $\mathcal{S}$, we say that $v^{\mathcal{S}}$ is the cost vector
associated with $\mathcal{S}$, where $v^{\mathcal{S}}_{p}$ is simply the cost
of point $p$ in $\mathcal{S}$. A sampling based coreset now picks rows of
$v^{\mathcal{S}}$ according to some distribution and approximates
$\|v^{\mathcal{S}}\|_{1}=\sum v^{\mathcal{S}}_{p}$ as the weighted average of
the costs of the picked points. To show that this weighted average is
concentrated, we require two ingredients. First, we bound the variance for
approximating any $\|v^{\mathcal{S}}\|_{1}$. Suppose we make the simplifying
assumption that all points less than 1 and that we are aiming for an additive
error of at most $\varepsilon\cdot n$. In this case, the variance is constant,
upon which applying a Chernoff bound requires only
$\textbf{Var}\cdot\varepsilon^{-2}$ samples to approximate any single
$\|v^{\mathcal{S}}\|_{1}$.

Second, we have to apply a union bound over all $v^{\mathcal{S}}$. In
Euclidean spaces, a naive union bound is useless, as there are infinitely many
candidate solutions. To discretize $\mathcal{S}$, previous work, either
implicitly or explicitly, showed that there exists a small set of vectors
$\mathbb{N}^{\varepsilon}$, henceforth called a net, such that for every
$v^{\mathcal{S}}$ there exists
$v^{\mathcal{S},\varepsilon}\in\mathbb{N}^{\varepsilon}$ with
$|v^{\mathcal{S},\varepsilon}_{p}-v^{\mathcal{S}}_{p}|\leq\varepsilon$. Thus,
an accurate estimation of $\|v\|_{1}$ for all $v\in\mathbb{N}^{\varepsilon}$
is sufficient to achieve an estimation for all $v^{\mathcal{S}}$.
Unfortunately, the only known bounds of $\mathbb{N}^{\varepsilon}$ are of the
order $\exp(k\min(d,\varepsilon^{-2}))$, which combined with bound of the
variance leads to
$\log|\mathbb{N}^{\varepsilon}|\cdot\textbf{Var}\cdot\varepsilon^{-2}=k\cdot\varepsilon^{-2}\cdot\min(\varepsilon^{-2},d)$
many samples.

To improve upon this idea, we use nets at different scales, i.e. we have nets
$\mathbb{N}^{1}$, $\mathbb{N}^{1/2}$, $\mathbb{N}^{1/4}$ and so on. These nets
allow us to write every $v^{\mathcal{S}}$ as a telescoping sum of net vectors
at different scales, that is

$v^{\mathcal{S}}=\sum_{h=0}^{\infty}v^{\mathcal{S},2^{-(h+1)}}-v^{\mathcal{S},2^{-h}},$

where $v^{\mathcal{S},2^{-h}}$ is an element of $\mathbb{N}^{2^{-h}}$. Instead
of applying the union bound for all vectors in $\mathbb{N}^{\varepsilon}$ at
once, we apply the union bound for all difference vectors at various scales,
i.e. we show that for all difference vectors
$v^{\mathcal{S},2^{-(h+1)}}-v^{\mathcal{S},2^{-h}}$

$\mathbb{P}\left[|v^{\mathcal{S},2^{-(h+1)}}-v^{\mathcal{S},2^{-h}}-\mathbb{E}[v^{\mathcal{S},2^{-(h+1)}}-v^{\mathcal{S},2^{-h}}|]\geq\varepsilon\cdot
n\right]$

is small.

The reason why this improves over the naive discretization is that as the nets
get finer, the difference also gets smaller, i.e.
$|v^{\mathcal{S},2^{-(h+1)}}_{p}-v^{\mathcal{S},2^{-h}}_{p}|\leq 2\cdot
2^{-h}$. This difference directly affects the bound on the variance, which
decreases from a constant to roughly $2^{-2h}\cdot O(1)$. Since there are only
$|\mathbb{N}^{2^{-(h+1)}}|\cdot|\mathbb{N}^{2^{-h}}|\in\exp(k\cdot
2^{-2h}\cdot O(1))$ many difference vectors, we can compensate the increase in
net size by a decrease in variance, i.e. we require only

$\log(|\mathbb{N}^{2^{-(h+1)}}|\cdot|\mathbb{N}^{2^{-h}}|)\cdot\textbf{Var}\cdot\varepsilon^{-2}\approx
k\cdot 2^{-2h}\cdot O(1)\cdot
2^{-2h}\cdot\varepsilon^{-2}=k\cdot\varepsilon^{-2}\cdot O(1)$

many samples. Applying this idea to every successive summand of the
telescoping sum (or rather to every link of the chain of net vectors), leads
to an overall number of samples of the order $k\cdot\varepsilon^{-2}$,
ignoring polylog factors.

Unfortunately, improving the analysis from an additive approximation to a
multiplicative approximation leads to several difficulties. Without using the
assumption that all points cost less than $1$, the variance increases. Indeed,
contrasting to the previous work [34] that used a chaining-based analysis to
obtain coreset bounds for a single center and previous work [35] that used a
chaining-inspired variance reduction technique, both of which managed to
obtain constant variance, bounding the variance in this setting is highly non-
trivial and requires a number of new ideas. The lowest variance we could show
for estimating $\|v^{\mathcal{S}}\|_{1}$ is only of the order
$\min(\varepsilon^{-z},k)$, leading to the (likely suboptimal) bound of
$\tilde{O}(k\cdot\varepsilon^{-2}\cdot\min(\varepsilon^{-z},k))$ and moreover
this bound on the variance is tight. Further ideas will be necessary to reach
the (conjectured) optimal bound of $\Theta(k\cdot\varepsilon^{-2})$.

#### Lower Bound for discrete metric spaces

The general idea behind our lower bound is to use the tight concentration and
anti-concentration bounds on the sum of random variables.

We first build an instance for $k=1$, and combines several copies of it to
obtain a lower bound for any arbitrary $k$. Our instance for $k=1$ is such
that: (1) when $|\Omega|\leq\varepsilon^{-2}\log|C|$ there exists a center
with $\text{cost}(\Omega,c)>(1+100\varepsilon)\text{cost}(c)$, and (2): for
any $|\Omega|>\varepsilon^{-2}\log|C|$ there exists a center $c$ with
$\text{cost}(\Omega,c)\in(1\pm\varepsilon)\text{cost}(c)$.

To show the existence of such an instance, we consider a complete bipartite
graph with nodes $P\cup C$ where there is an edge between each point of $P$
and each point of $C$, with length $1$ with probability $1/4$ and $2$
otherwise. The set of clients is $P$. For simplicity, we will assume here that
the coreset weights are uniform. Making the idea work for non-uniform weights
requires several other technical ingredients.

In that instance for $k=1$, the cost of a solution (with a single center, $c$)
is fully determined by $n_{1}(c)$, the number of length $1$ edges to $c$.
Indeed, $\text{cost}(c)=2(|P|-n_{1}(c))+n_{1}-c)=2|P|-n_{1}(c)$. Let us
further assume that $n_{1}(c)$ is equal to its expectation, $\delta|P|$. For a
fixed subset of points $\Omega$, the cost of the solution for $\Omega$ with
uniform weights $\frac{|P|}{|\Omega|}$ verifies the same equation: it is
$2|P|-n_{1}(\Omega,c)\cdot\frac{|P|}{|\Omega|}$, where $n_{1}(\Omega,c)$ the
number of length $1$ edges from $\Omega$ to $c$. Note that
$\mathbb{E}[n_{1}(\Omega,c)]=\delta|\Omega|$.

Using anti-concentration inequalities, we show that
$n_{1}(\Omega,c)>(1+200\varepsilon)\mathbb{E}[n_{1}(\Omega,c)]$ with
probability at least $\exp(-\alpha\varepsilon^{2}|\Omega|)$, for some constant
$\alpha$. When this event happens, then $\Omega$ does not preserve the cost of
solution $c$: indeed,

$\displaystyle 2|P|-n_{1}(\Omega,c)\cdot\frac{|P|}{|\Omega|}$
$\displaystyle>2|P|-(1+200\varepsilon)\delta|\Omega|\cdot\frac{|P|}{|\Omega|}$
$\displaystyle=2|P|-\delta|P|+200\varepsilon\delta|P|>(1+100\varepsilon)(2|P|-n_{1}(c)).$

Since the edges are drawn independently, the coreset cost for all possible
centers $c$ is independent. Hence, there exists one center with
$n_{1}(\Omega,c)>(1+200\varepsilon)\delta|\Omega|$ with probability at least
$1-(1-\exp(-\alpha\varepsilon^{2}|\Omega|))^{|C|}$. By doing a union-bound
over all possible subsets $\Omega$, one can show the following: with positive
(close to $1$) probability, for any $|\Omega|\leq\varepsilon^{-2}\log|C|$
there exists a center with
$\text{cost}(\Omega,c)>(1+100\varepsilon)\text{cost}(c)$.

Using standard concentration inequality, one can show that with probability
close to $1$, for any $|\Omega|>\varepsilon^{-2}\log|C|$, there exists a
center $c$ with $\text{cost}(\Omega,c)\in(1\pm\varepsilon)\text{cost}(c)$.
Since the probabilities are taken on the edges randomness, those two result
ensure the existence of a graph that verifies properties (1) and (2) desired
for the $k=1$ instance.

Now, the full instance is made of $k$ distinct copies $X_{1},...,X_{k}$ of the
$k=1$ instance, placed at infinite distance from each other. Let $P_{i}$ be
the set of clients of $X_{i}$: the clients for the full instance are $\cup
P_{i}$. Let $\Omega$ be a set of at most $1/100\cdot k\varepsilon^{-2}\log n$
points: we show that $\Omega$ cannot be a coreset. By Markov’s inequality,
there are at least $99/100k$ copies that contain less than
$\varepsilon^{-2}\log n$ points of $\Omega$. We say those copies are bad, the
others are good. Consider now the solution $\mathcal{S}$ defined as follows:
from each $X_{i}$, take the center such that $\text{cost}(\Omega\cap
P_{i},c)>(1+100\varepsilon)\text{cost}(P_{i},c)$ when $X_{i}$ is bad, and the
center such that $\text{cost}(\Omega\cap
P_{i},c)\in(1\pm\varepsilon)\text{cost}(P_{i},c)$ when $X_{i}$ is good.
Observe also that by construction of the instance for $k=1$, the cost in each
copy must lie in $[|P|,2|P|]$. For that solution, we have:

$\displaystyle\text{cost}(\Omega,\mathcal{S})$
$\displaystyle=\sum\text{cost}(\Omega\cap P_{i},s_{i})=\sum_{i\text{ bad
}}\text{cost}(\Omega\cap P_{i},s_{i})+\sum_{i\text{
good}}\text{cost}(\Omega\cap P_{i},s_{i})$ $\displaystyle>\sum_{i\text{ bad
}}(1+100\varepsilon)\text{cost}(P_{i},s_{i})+\sum_{i\text{
good}}(1-\varepsilon)\text{cost}(P_{i},s_{i})$
$\displaystyle>\text{cost}(\mathcal{S})+\frac{99k}{100}\cdot
100\varepsilon|P|-\frac{k}{100}\cdot\varepsilon
2|P|>\text{cost}(\mathcal{S})+98k\varepsilon|P|>(1+\varepsilon)\text{cost}(\mathcal{S}).$

Hence, any $\Omega$ with $|\Omega|\leq 1/100\cdot k\varepsilon^{-2}\log n$
cannot be a coreset for our instance, which concludes the proof.

##  2 Related Work

Reference | Size (Number of Points)
---|---
Coreset Bounds in Euclidean Spaces
Lower Bounds
Baker, Braverman, Huang, Jiang, | $\Omega(k\cdot\varepsilon^{-1/2})$
Krauthgamer, Wu (ICML’19) [15]
Huang, Vishnoi (STOC’20) [55] | $\Omega(k\cdot\min(d,2^{z/20}))$
This paper | $\Omega(k\cdot\varepsilon^{-2}/z^{4})$
Upper Bounds
Har-Peled, Mazumdar (STOC’04) [50] | $O(k\cdot\varepsilon^{-d}\cdot\log n)$
Har-Peled, Kushal (DCG’07) [49] | $O(k^{3}\cdot\varepsilon^{-(d+1)})$
Chen (Sicomp’09) [23] | $O(k^{2}\cdot d\cdot\varepsilon^{-2}\cdot\log n)$
Langberg, Schulman (SODA’10) [65] | $O(k^{3}\cdot d^{2}\cdot\varepsilon^{-2})$
Feldman, Langberg (STOC’11) [41] | $O(k\cdot d\cdot\varepsilon^{-2z})$
Feldman, Schmidt, Sohler (Sicomp’20) [43] | $O(k^{3}\cdot\varepsilon^{-4})$
Sohler, Woodruff (FOCS’18) [86] | $O(k^{2}\cdot\varepsilon^{-O(z)})$
Becchetti, Bury, Cohen-Addad, Grandoni, | $O(k\cdot\varepsilon^{-8})$
Schwiegelshohn (STOC’19) [8]
Huang, Vishnoi (STOC’20) [55] | $O(k\cdot\varepsilon^{-2-2z})$
Bravermann, Jiang, Krautgamer, Wu (SODA’21) [17] | $O(k^{2}\cdot\varepsilon^{-4})$
Cohen-Addad, Saulpic, Schwiegelshohn (STOC’21) [35] | $\tilde{O}(k\cdot\varepsilon^{-2-\max(2,z)})$
This paper | $\tilde{O}(k\cdot\varepsilon^{-2}\cdot\min(\varepsilon^{-z},k))$
General $n$-point metrics, $D$ denotes the doubling dimension
Lower Bounds
Braverman, Jiang, Krauthgamer, Wu (ICML’19) [16] | $\Omega(k\cdot\varepsilon^{-1}\cdot\log n)$
This paper | $\Omega(k\cdot\varepsilon^{-2}\cdot\log n)$
This paper | $\Omega(k\cdot\varepsilon^{-2}\cdot D)$
Upper Bounds
Chen (Sicomp’09) [23] | $O(k^{2}\cdot\varepsilon^{-2}\cdot\log^{2}n)$
Feldman, Langberg (STOC’11) [41] | $O(k\cdot\varepsilon^{-2z}\cdot\log n)$
Huang, Jiang, Li, Wu (FOCS’18) [51] | $O(k^{3}\cdot\varepsilon^{-2}\cdot D)$
Cohen-Addad, Saulpic, Schwiegelshohn (STOC’21) [35] | $\tilde{O}(k\cdot\varepsilon^{-\max(2,z)}\cdot D)$
Cohen-Addad, Saulpic, Schwiegelshohn (STOC’21) [35] | $\tilde{O}(k\cdot\varepsilon^{-\max(2,z)}\cdot\log n)$
Table 1: Comparison of coreset sizes for $(k,z)$-Clustering in Euclidean
spaces. [15] only applies to $k$-median, [49, 50] only applies to $k$-means
and $k$-median, and[8, 43] only applies to $k$-means. [86] runs in exponential
time, which has been addressed by Feng, Kacham, and Woodruff [44]. Aside from
[49, 50], the algorithms are randomized and succeed with constant probability.
Any dependency on $2^{O(z\log z)}$, as well as polylog factors have been
omitted in the upper bounds.

For the most part, related work on coresets for $k$ clustering in Euclidean
spaces are given in Table 1. A closely related line of research focusses on
dimension reduction for $k$-clustering objectives, particularly $k$-means.
Starting with [37], a series of results [8, 10, 11, 12, 25, 36, 43, 44, 64,
73, 86] explored the possibility of using dimension reduction methods for
$k$-clustering, with a particular focus on principal component analysis (PCA)
and random projections. The problem of dimension reduction, at least with
respect to these techniques has been mostly resolved by now: Cohen, Elder,
Musco, Musco, and Persu [25] proved tight bounds of $\lceil
k/\varepsilon\rceil$ for PCA and Makarychev, Makarychev and Razenshteyn [73]
gave a bound of $O(\varepsilon^{-2}\log k/\varepsilon)$ for random
projections, which nearly matches the lower bound by Larsen and Nelson [66].
The arguably most important technique for combining dimension reduction with
coresets is the recent work on terminal embeddings, see [24, 38, 72]. Notably,
Narayanan and Nelson [82] gave an optimal bound of $O(\varepsilon^{-2}\log
n)$. We will discuss specifics on terminal embeddings in Section 6.4.

While Euclidean spaces are doubtlessly the most intensively studied metric, a
number of further metrics have also been considered, including finite metrics
[23, 35, 41], doubling metrics [35, 51], and graph metrics [6, 18, 35].
Coresets also feature prominently in streaming literature, see [13, 14, 20,
45, 46] for results with a special focus on various streaming models. Other
related work considers generalizations of $k$-median and $k$-means by either
adding capacity constraints [7, 29, 52, 85], generalizing the notion of
centers to subspaces [19, 41, 42], time series [54] or sets [61] or
considering more general objective functions [5, 15]. Coresets have also been
studied for many other problems: we cite non-comprehensively decision trees
[60], kernel methods [59, 62, 83], determinant maximization [57], diversity
maximization [58], shape fitting problems [2, 22], linear regression [9, 53,
88], logistic regression [56, 81], Gaussian mixtures [70], dependency networks
[79], or low‐rank approximation [71]. The interested reader is referred to [3,
40, 80] and similar surveys for more pointers to coreset literature.

In terms of approximation guarantee, the best known approximation ratio for
general metrics is 2.67 due to Byrka et al. [21], improving over the result of
2.71 of Li and Svensson [69] while computing a better than
$1+2/e$-approximation has been shown to be NP-hard by Guha and Khuller [48].
In Euclidean spaces of arbitrary dimension, the best known approximation is
2.408 and 5.957 for $k$-median and $k$-means, respectively, due to a recent
result of Cohen-Addad et al. [1] who improved over the work of Grandoni et al.
[47] and Ahmadian et al. [4]. The best known hardness of approximation is 1.73
and 1.27 for $k$-means and $k$-median assuming the Johnson-Coverage Hypothesis
or 1.17 and 1.07 respectively assuming P $\neq$ NP [32] (see also [31, 33,
68]). For graphs excluding a fixed-minor, the problem is NP-Hard [75] and a
PTAS is known [28, 30]. For doubling metrics, the problem is NP-Hard (even in
the plane [77]) and a linear-time approximation scheme when the dimension is
considered constant is known [27, 26, 63].

###  2.1 Roadmap

The proof of the Euclidean lower bound for $k$-Means is given in Section 4.
The proof for general powers is given in Appendix A. The lower bounds for
finite metrics and doubling metrics are given in Section 5. The proof of the
upper bound is given in Section 6.

##  3 Preliminaries

#### General Preliminaries

Given two points $p$ and $c$ in some metric space with distance function dist,
the $(k,z)$-clustering cost of $p$ to $c$ is
$\text{cost}(p,c)=\text{dist}^{z}(p,c).$ The $\ell_{p}$ norm of a $d$
dimensional vector $x$ is defined as
$\|x\|_{p}:=\sqrt[p]{\sum_{i=1}^{d}|x|_{i}^{p}}$. If the value of $p$ is
unspecified, it is meant to be the Euclidean norm $p=2$. Given a set of point
$P$ with weights $w:P\rightarrow\mathbb{R}^{+}$ on a metric space $I$ and a
solution $\mathcal{S}$, we define $\text{cost}_{I}(P,\mathcal{S}):=\sum_{p\in
P}w(p)\text{cost}(p,\mathcal{S})$.

######  Definition 1.

Let $(X,\text{dist})$ be a metric space, let $P\subset X$ be a set of
_clients_ and let $\Omega$ be a set of points with weights
$w:\Omega\rightarrow\mathbb{R}^{+}$ and a constant $\Delta$. $\Omega$ is an
$(\varepsilon,k,z)$-coreset using offset $\Delta$ if for any set
$\mathcal{S}\subset X$, $|\mathcal{S}|=k$,

$\left|\sum_{p\in
P}\text{cost}(p,\mathcal{S})-\left(\Delta+\sum_{p\in\Omega}w(p)\text{cost}(p,\mathcal{S})\right)\right|\leq\varepsilon\sum_{p\in
P}\text{cost}(p,\mathcal{S})$

$\Omega$ is a $(\varepsilon,k,z)$-coreset using offset $\Delta$ with additive
error $E$ if for any set $\mathcal{S}\subset X$, $|\mathcal{S}|=k$,

$\left|\sum_{p\in
P}\text{cost}(p,\mathcal{S})-\left(\Delta+\sum_{p\in\Omega}w(p)\text{cost}(p,\mathcal{S})\right)\right|\leq\varepsilon\sum_{p\in
P}\text{cost}(p,\mathcal{S})+E.$

The offset $\Delta$ is often $0$ for most coreset constructions, with a few
exceptions [25, 43, 86]. In our algorithm, $\Delta=0$. The lower bounds hold
for any choice of $\Delta$.

##  4 Lower Bounds in Euclidean Spaces for $k$-Means

We first prove the bound for $k$-means, i.e. for $z=2$. The generalization to
arbitrary powers is made in appendix: the proof idea is exactly alike, but a
few new technicalities arise.

###  4.1 $k$-Means

As mentioned in the proof outline in Section 1.2, we proceed in three steps.
First we show that any clustering of $e_{1},\dots,e_{d}$ using $k$ cluster
centers of unit norm must have cost at least $2d-O(\sqrt{dk})$. Next, we show
that for any coreset $\Omega$ of $t$ points and weights
$w:\Omega\to\mathbb{R}^{+}$, there is a clustering that has cost at most
$2d-\Omega(\sqrt{k/t}\cdot\sum_{p\in\Omega}w(p)\|p\|_{2})$. Combined with step
one, this shows that
$\sum_{p\in\Omega}w(p)\|p\|_{2}=O(\sqrt{t/k}\sqrt{dk})=O(\sqrt{td})$. Finally
we show that $\Omega$ must satisfy $\sum_{p\in\Omega}w(p)\|p\|_{2}=\Omega(d)$
when $d=\Theta(k\cdot\varepsilon^{-2})$. Combining all of these implies
$\sqrt{td}=\Omega(d)\Rightarrow t=\Omega(d)=\Omega(k\cdot\varepsilon^{-2})$.

For technical reasons, we consider the point set $e_{1},\dots,e_{d}$ as
residing in $\mathbb{R}^{2d}$ and not $\mathbb{R}^{d}$. The reason for this,
is that we need to be able to find a vector that is orthogonal to all $e_{i}$
and all points in a coreset $\Omega$ (see proof of Lemma 4). If the size of
the coreset is $t<d$, then such a vector exists in $\mathbb{R}^{2d}$.

#### Step One.

We start by showing that any clustering of $e_{1},\dots,e_{d}$ using $k$
centers of unit norm must have large cost:

######  Lemma 1.

For any $d$, consider the point set $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{2d}$. For any set of $k$ centers
$c_{1},\dots,c_{k}\in\mathbb{R}^{2d}$ with unit norm, it holds that
$\sum_{i=1}^{d}\min_{j=1}^{k}\|e_{i}-c_{j}\|_{2}^{2}\geq 2d-2\sqrt{dk}$.

###### Proof.

We see that

$\displaystyle\sum_{i=1}^{d}\min_{j=1}^{k}\|e_{i}-c_{j}\|_{2}^{2}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{d}\min_{j=1}^{k}\|e_{i}\|_{2}^{2}+\|c_{j}\|_{2}^{2}-2\langle
e_{i},c_{j}\rangle$ $\displaystyle=$ $\displaystyle
2d-2\sum_{i=1}^{d}\max_{j=1}^{k}\langle e_{i},c_{j}\rangle$ $\displaystyle=$
$\displaystyle 2d-2\sum_{j=1}^{k}\sum_{i:j=\operatorname{argmax}_{h}\langle
e_{i},c_{h}\rangle}\langle e_{i},c_{j}\rangle.$

Now, for each $c_{j}$, define $\hat{c}_{j}$ to equal $c_{j}$, except that we
set the $i$’th coordinate to $0$ if $j\neq\operatorname{argmax}_{h}\langle
e_{i},c_{h}\rangle$. Then:

$\displaystyle 2d-2\sum_{j=1}^{k}\sum_{i:j=\operatorname{argmax}_{h}\langle
e_{i},c_{h}\rangle}\langle e_{i},c_{j}\rangle$ $\displaystyle=$ $\displaystyle
2d-2\sum_{i=1}^{d}\sum_{j=1}^{k}\langle e_{i},\hat{c}_{j}\rangle$
$\displaystyle=$ $\displaystyle 2d-2\sum_{i=1}^{d}\langle
e_{i},\sum_{j=1}^{k}\hat{c}_{j}\rangle$ $\displaystyle\geq$ $\displaystyle
2d-2\|\sum_{j=1}^{k}\hat{c}_{j}\|_{1}.$

By Cauchy-Schwartz, we have
$\|\sum_{j=1}^{k}\hat{c}_{j}\|_{1}\leq\|\sum_{j=1}^{k}\hat{c}_{j}\|_{2}\cdot\sqrt{d}$.
Since the $\hat{c}_{j}$’s are orthogonal and have norm at most $1$, we have
$\|\sum_{j=1}^{k}\hat{c}_{j}\|_{2}\leq\sqrt{k}$. Thus we conclude
$\sum_{i=1}^{d}\min_{j=1}^{k}\|e_{i}-c_{j}\|_{2}^{2}\geq 2d-2\sqrt{dk}$. ∎

#### Step Two.

Next, we show that for any coreset $\Omega$ of $t$ points and weights
$w:\Omega\to\mathbb{R}^{+}$, there is a clustering that has cost at most
$2d-\Omega(\sqrt{k/t}\cdot\sum_{p\in\Omega}w(p)\|p\|_{2})$. To prove this, we
start by considering the case of using a single cluster center to cluster
$\ell$ weighted points:

######  Lemma 2.

Let $r_{1},\dots,r_{\ell}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{\ell}\in\mathbb{R}^{+}$. There exists a unit vector $v$ such
that $\sum_{i=1}^{\ell}w_{i}|\langle
r_{i},v\rangle|\geq\frac{\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}}{\sqrt{\ell}}$.

###### Proof.

Consider the random vector $u=\sum_{i=1}^{\ell}w_{i}\sigma_{i}r_{i}$ where the
$\sigma_{i}$ are i.i.d. uniform Rademachers ($-1$ and $+1$ with probability
$1/2$). We see that

$\displaystyle\sum_{i=1}^{\ell}w_{i}|\langle r_{i},u\rangle|$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\ell}w_{i}\left|\sum_{j=1}^{\ell}w_{j}\sigma_{j}\langle
r_{i},r_{j}\rangle\right|$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\ell}w_{i}\left|\sum_{j=1}^{\ell}w_{j}\sigma_{i}\sigma_{j}\langle
r_{i},r_{j}\rangle\right|$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{\ell}w_{i}\sum_{j=1}^{\ell}w_{j}\sigma_{i}\sigma_{j}\langle
r_{i},r_{j}\rangle$ $\displaystyle=$ $\displaystyle\|u\|_{2}^{2}.$

We may then define the unit vector $v=u/\|u\|_{2}$ (with $v=0$ when $u=0$) and
conclude that

$\sum_{i=1}^{\ell}w_{i}|\langle r_{i},v\rangle|\geq\|u\|_{2}.$

Since $\mathbb{E}[\|u\|_{2}^{2}]=\sum_{i=1}^{\ell}w_{i}^{2}\|r_{i}\|_{2}^{2}$
we conclude that there must exist a unit vector $v$ with

$\sum_{i=1}^{\ell}w_{i}|\langle
r_{i},v\rangle|\geq\sqrt{\sum_{i=1}^{\ell}w_{i}^{2}\|r_{i}\|_{2}^{2}}.$

By Cauchy-Schwartz, we have:

$\sum_{i=1}^{\ell}|1\cdot
w_{i}\|r_{i}\|_{2}|\leq\sqrt{\sum_{i=1}^{\ell}w_{i}^{2}\|r_{i}\|_{2}^{2}}\cdot\sqrt{\sum_{i=1}^{\ell}1}=\sqrt{\sum_{i=1}^{\ell}w_{i}^{2}\|r_{i}\|_{2}^{2}}\cdot\sqrt{\ell}$

which finally implies

$\sum_{i=1}^{\ell}w_{i}|\langle
r_{i},v\rangle|\geq\frac{\sum_{i=1}^{\ell}w_{i}\|r_{i}\|_{2}}{\sqrt{\ell}}.$

∎

We can now extend this to using $k$ centers of unit norm to cluster $t$
weighted points:

######  Lemma 3.

Let $r_{1},\dots,r_{t}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{t}\in\mathbb{R}^{+}$. For any positive even integer $k$, there
exists a set of $k$ unit vectors $v_{1},\dots,v_{k}$ such that
$\sum_{i=1}^{t}-2w_{i}\max_{j=1}^{k}\langle
r_{i},v_{j}\rangle\leq-\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$ and
moreover, for all $i$ we have $\max_{j=1}^{k}\langle r_{i},v_{j}\rangle\geq
0$.

###### Proof.

Partition $r_{1},\dots,r_{t}$ arbitrarily into $k/2$ disjoint groups
$G_{1},\dots,G_{k/2}$ of at most $2t/k$ vectors each. For each group $G_{j}$,
apply Lemma 2 to find a unit vector $u_{j}$ with $\sum_{r_{i}\in
G_{j}}w_{i}|\langle r_{i},u_{j}\rangle|\geq\frac{\sum_{r_{i}\in
G_{j}}w_{i}\|r_{i}\|_{2}}{\sqrt{2t/k}}$. Let $v_{2j-1}=u_{j}$ and
$v_{2j}=-u_{j}$. Since we always add both $u_{j}$ and $-u_{j}$, it holds for
all $r_{i}$ that $\max_{j=1}^{k}\langle
r_{i},v_{j}\rangle=\max_{j=1}^{k}|\langle r_{i},v_{j}\rangle|$. We therefore
conclude (notice the $\leq$ rather than $\geq$ due to the negation):

$\displaystyle\sum_{i=1}^{t}-2w_{i}\max_{j=1}^{k}\langle r_{i},v_{j}\rangle$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{t}-2w_{i}\max_{j=1}^{k}|\langle
r_{i},v_{j}\rangle|$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{k/2}\sum_{r_{i}\in G_{j}}-2w_{i}|\langle
r_{i},u_{j}\rangle|$ $\displaystyle\leq$
$\displaystyle-2\sum_{j=1}^{k/2}\frac{\sum_{r_{i}\in
G_{j}}w_{i}\|r_{i}\|_{2}}{\sqrt{2t/k}}$ $\displaystyle=$
$\displaystyle-\frac{\sqrt{2}\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}}{\sqrt{t/k}}.$

∎

With this established, we now combine this with step one to show that for any
coreset $\Omega$ with $t$ points, we must have
$\sum_{p\in\Omega}w(p)\|p\|_{2}=O(\sqrt{t/k}\sqrt{dk})=O(\sqrt{td})$. This is
established in two smaller steps:

######  Lemma 4.

For any $d$, consider the point set $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{2d}$. Let $r_{1},\dots,r_{t}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{t}\in\mathbb{R}^{+}$ be an $\varepsilon$-coreset for $P$,
using offset $\Delta$ and with $t<d$. Then we must have
$\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+1)\in(1\pm\varepsilon)2d$.

###### Proof.

Since $t+d<2d$ there exists a unit vector $v$ that is orthogonal to all
$r_{i}$ and all $e_{j}$. Consider placing all $k$ centers at $v$. Then the
cost of clustering $P$ with these centers is $2d$. It therefore must hold that
$\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+\|v\|_{2}^{2}-2\langle
r_{i},v\rangle)=\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+1)\in(1\pm\varepsilon)2d$.
∎

######  Lemma 5.

For any $d$ and any $k>1$, let $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{2d}$. Let $r_{1},\dots,r_{t}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{t}\in\mathbb{R}^{+}$ be an $\varepsilon$-coreset for $P$ with
$t<d$, using offset $\Delta$. Then

$\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}\leq\frac{4\varepsilon
d+2\sqrt{dk}}{\sqrt{2k/t}}.$

###### Proof.

By Lemma 3, we can find $k$ unit vectors $v_{1},\dots,v_{k}$ such that
$\sum_{i=1}^{t}-2w_{i}\max_{j=1}^{k}\langle
r_{i},v_{j}\rangle\leq-\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$. By
Lemma 1, it holds that $\sum_{p\in P}\min_{j=1}^{k}\|p-v_{j}\|_{2}^{2}\geq
2d-2\sqrt{dk}$. Since points $r_{1},\dots,r_{t}$ with respective weights
$w_{1},\dots,w_{t}$ and offset $\Delta$ form an $\varepsilon$-coreset for $P$,
we must have

$\displaystyle(1-\varepsilon)(2d-2\sqrt{dk})$ $\displaystyle\leq$
$\displaystyle\Delta+\sum_{i=1}^{t}\min_{j=1}^{k}w_{i}\|r_{i}-v_{j}\|_{2}^{2}$
$\displaystyle=$
$\displaystyle\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+\|v_{j}\|_{2}^{2}-2\max_{j=1}^{k}\langle
r_{i},v_{j}\rangle)$ $\displaystyle=$
$\displaystyle\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+1)-2\sum_{i=1}^{t}w_{i}\max_{j=1}^{k}\langle
r_{i},v_{j}\rangle$ $\displaystyle\leq$
$\displaystyle\Delta+\sum_{i=1}^{t}w_{i}(\|r_{i}\|_{2}^{2}+1)-\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}.$

By Lemma 4, this is at most

$\displaystyle\leq$
$\displaystyle(1+\varepsilon)2d-\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}.$

We have therefore shown that

$\displaystyle(1-\varepsilon)(2d-2\sqrt{dk})$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon)2d-\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}\Rightarrow$
$\displaystyle\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$
$\displaystyle\leq$
$\displaystyle(1+\varepsilon)2d-(1-\varepsilon)(2d-2\sqrt{dk})\Rightarrow$
$\displaystyle\sqrt{2k/t}\cdot\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$
$\displaystyle\leq$ $\displaystyle 4\varepsilon
d+(1-\varepsilon)2\sqrt{dk}\Rightarrow$
$\displaystyle\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$ $\displaystyle\leq$
$\displaystyle\frac{4\varepsilon d+2\sqrt{dk}}{\sqrt{2k/t}}.$

∎

#### Step Three.

Finally we show that any coreset $\Omega$ must satisfy
$\sum_{p\in\Omega}w(p)\|p\|_{2}=\Omega(d)$ when
$d=\Theta(k\cdot\varepsilon^{-2})$:

######  Lemma 6.

For any $0<\varepsilon<1/2$ and any positive even integer $k$, let
$d=k/(36\varepsilon^{2})$ and let $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{2d}$. Let $r_{1},\dots,r_{t}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{t}\in\mathbb{R}^{+}$ be an $\varepsilon$-coreset for $P$ with
$t<d$, using offset $\Delta$. Then $\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}\geq d/6$.

###### Proof.

Consider the Hadamard basis $h_{1},\dots,h_{q}$ on $q=1/(36\varepsilon^{2})$
coordinates, i.e. the set of rows in the normalized Hadamard matrix. This is a
set of $q$ orthogonal unit vectors with all coordinates in
$\\{-1/\sqrt{q},1/\sqrt{q}\\}$. All $h_{i}$ except $h_{1}$ have equally many
coordinates that are $-1/\sqrt{q}$ and $1/\sqrt{q}$ and $h_{1}$ have all
coordinates $1/\sqrt{q}$. Now partition the first $d$ coordinates into $k$
groups $G_{1},\dots,G_{k}$ of $q$ coordinates each. For any $h_{i}$, consider
the $k$ centers $v^{i}_{1},\dots,v^{i}_{k}$ obtained as follows: For each
group $G_{j}$ of $q$ coordinates, copy $h_{i}$ into those coordinates to
obtain the vector $v^{i}_{j}$. We must have that
$\sum_{h=1}^{d}\min_{j=1}^{k}\|e_{h}-v^{i}_{j}\|_{2}^{2}=\sum_{h=1}^{d}\min_{j=1}^{k}\|e_{h}\|_{2}^{2}+\|v^{i}_{j}\|_{2}^{2}-2\langle
e_{h},v^{i}_{j}\rangle$. Since $k>1$, there is always a $j$ such that $\langle
e_{h},v^{i}_{j}\rangle=0$. Moreover, for $i=1$, we have $\max_{j=1}^{k}\langle
e_{h},v_{j}^{i}\rangle=1/\sqrt{q}$ and for $i\neq 1$, it holds that precisely
half of all $e_{h}$ have $\max_{j=1}^{k}\langle
e_{h},v_{j}^{i}\rangle=1/\sqrt{q}$. Thus we have
$\sum_{h=1}^{d}\min_{j=1}^{k}\|e_{h}-v^{i}_{j}\|_{2}^{2}\leq(d/2)2+(d/2)(2-2/\sqrt{q})=2d-d/\sqrt{q}$.
Thus:

$\displaystyle(1+\varepsilon)(2d-d/\sqrt{q})$ $\displaystyle\geq$
$\displaystyle\Delta+\sum_{h=1}^{t}w_{h}(\|r_{h}\|_{2}^{2}+1-2\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle)$

By Lemma 4, this is at least

$\displaystyle\geq$
$\displaystyle(1-\varepsilon)2d-2\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle.$

We have thus shown

$\displaystyle(1+\varepsilon)(2d-d/\sqrt{q})$ $\displaystyle\geq$
$\displaystyle(1-\varepsilon)2d-2\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle\Rightarrow$ $\displaystyle 4\varepsilon
d-(1+\varepsilon)d/\sqrt{q}$ $\displaystyle\geq$
$\displaystyle-2\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle\Rightarrow$
$\displaystyle\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle r_{h},v^{i}_{j}\rangle$
$\displaystyle\geq$ $\displaystyle(1+\varepsilon)d/(2\sqrt{q})-2\varepsilon
d\Rightarrow$ $\displaystyle\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle$ $\displaystyle\geq$ $\displaystyle
d/(2\sqrt{q})-2\varepsilon d.$

Now consider any $r_{h}$ with weight $w_{h}$. Collect the vectors $u^{i}_{h}$
such that $u^{i}_{h}=v^{i}_{j^{*}}$ with
$j^{*}=\operatorname{argmax}_{j}\langle r_{h},v^{i}_{j}\rangle$. By
construction, all these $q$ vectors are orthogonal (either disjoint support or
distinct vectors from the Hadamard basis). By Cauchy-Schwartz, we then have
$\langle w_{h}r_{h},\sum_{i=1}^{q}u^{i}_{h}\rangle\leq
w_{h}\|r_{h}\|_{2}\|\sum_{i=1}^{q}u^{i}_{h}\|_{2}=w_{h}\|r_{h}\|_{2}\sqrt{q}$.
We then see that

$\displaystyle dq/(2\sqrt{q})-2\varepsilon dq$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{q}\sum_{h=1}^{t}w_{h}\max_{j=1}^{k}\langle
r_{h},v^{i}_{j}\rangle$ $\displaystyle=$
$\displaystyle\sum_{h=1}^{t}\sum_{i=1}^{q}w_{h}\langle r_{h},u_{h}^{i}\rangle$
$\displaystyle=$ $\displaystyle\sum_{h=1}^{t}\langle
w_{h}r_{h},\sum_{i=1}^{q}u_{h}^{i}\rangle$ $\displaystyle\leq$
$\displaystyle\sum_{h=1}^{t}w_{h}\|r_{h}\|_{2}\sqrt{q}.$

We have thus shown $\sum_{h=1}^{t}w_{h}\|r_{h}\|_{2}\geq d/2-2\varepsilon
d\sqrt{q}=d/2-2\varepsilon d/(6\varepsilon)=d/2-d/3=d/6$. ∎

#### Combining it All.

######  Theorem 5.

For any $0<\varepsilon<1/2$ and any positive even integer $k$, let
$d=k/(36\varepsilon^{2})$ and let $P=\\{e_{1},\dots,e_{d}\\}$ in
$\mathbb{R}^{2d}$. Let $r_{1},\dots,r_{t}\in\mathbb{R}^{2d}$ and let
$w_{1},\dots,w_{t}\in\mathbb{R}^{+}$ be an $\varepsilon$-coreset for $P$,
using offset $\Delta$. Then $t\geq\varepsilon^{-2}k/180$.

###### Proof.

If $t\geq d$, then we are done. Otherwise, we combine Lemma 5 and Lemma 6, to
get:

$\displaystyle d/6$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t}w_{i}\|r_{i}\|_{2}$ $\displaystyle\leq$
$\displaystyle\frac{4\varepsilon d+2\sqrt{dk}}{\sqrt{2k/t}}$ $\displaystyle=$
$\displaystyle\frac{4\varepsilon d+6\varepsilon d}{\sqrt{2k/t}}$
$\displaystyle=$ $\displaystyle\frac{10\varepsilon d}{\sqrt{2k/t}}.$

This finally implies:

$t\geq\varepsilon^{-2}k/180.$

∎

##  5 Lower Bounds For Discrete Metrics

We show in this section Theorem 1, that we recall here for convenience: See 1

To prove the theorem, we create a _subinstance_ that implies a lower bound for
the case $k=1$. The general lower bound for arbitrary $k$ then naturally
combines several copies of the subinstance. The key technical part of our
proof is the use of some Azuma-Hoeffding type concentration inequality, but
where the concentration probability is lower bounded. The results we use are
developed in Section 5.1. We present the subinstance in Section 5.2, and the
general lower bound in Section 5.3.

###  5.1 Technical lemmas

Our proof relies on Lemma 8, which we prove using the following result from
[39].

######  Lemma 7 (Equation 2.11 in [39]).

Let $\xi_{1},...,\xi_{m}$ be independent centered random variables, and
$\tilde{\varepsilon}$ such that

$\forall i,k\geq
3~{}|\mathbb{E}[\xi_{i}^{k}]|\leq\frac{1}{2}k!\tilde{\varepsilon}^{k-2}\mathbb{E}[\xi_{i}^{2}].$

Let $\sigma^{2}=\sum\mathbb{E}[\xi_{i}^{2}]$, and
$S_{m}=\sum_{i=1}^{m}\xi_{i}$.

Then, for all $0\leq x\leq 0.1\frac{\sigma}{\tilde{\varepsilon}}$,

$\Pr[S_{m}\geq
x\sigma]\geq\left(1-\Phi\left(x(1-cx\frac{\tilde{\varepsilon}}{\sigma}\right)\right)\cdot\left(1-c(1+x)\frac{\tilde{\varepsilon}}{\sigma}\right),$

where $c$ is an absolute positive constant and $\Phi$ is the standard normal
distribution function.

######  Lemma 8.

Let $X_{1},...,X_{m}$ be independent Bernouilli random variables with
expectation $p\leq 1/4$, $\varepsilon>0$ and $w_{1},...,w_{m}$ be some
positive weights, such that $\max w_{i}\leq\gamma\cdot\frac{\sum
w_{i}}{\varepsilon m}$, for some $\gamma$. Let $\mu=p\cdot\sum w_{i}$. Then,
there exists a constant $\beta$ such that

$\Pr\left[\sum
w_{i}X_{i}-\mu>\varepsilon\mu\right]\geq\exp(-\frac{\beta}{\gamma^{2}}\varepsilon^{2}mp)$

###### Proof.

Define $\xi_{i}=w_{i}X_{i}-pw_{i}$. We show that the variables $\xi_{i}$
verify the conditions of Lemma 7. They are independent and centered, and:

$\displaystyle\mathbb{E}[\xi_{i}^{2}]$
$\displaystyle=p(w_{i}-pw_{i})^{2}+(1-p)(pw_{i})^{2})$
$\displaystyle=w_{i}^{2}\left(p-2p^{2}+p^{3}+p^{2}-2p^{3}+p^{4}\right)$
$\displaystyle=w_{i}^{2}(p-p^{2}-p^{3}+p^{4})\geq\frac{w_{i}^{2}p}{2},$

using $p\leq 1/4$. The $k$-th moment verifies:

$\displaystyle\left|\mathbb{E}[\xi_{i}^{k}]\right|$
$\displaystyle=w_{i}^{k}\cdot\left(p\cdot(1-p)^{k}+(1-p)\cdot(-p)^{k}\right)\leq
w_{i}^{k}p,$

hence $\xi_{i}$ verifies the condition of Lemma 7 with
$\tilde{\varepsilon}=\max_{i}w_{i}$. We want to apply that lemma to $x$ of the
order $\varepsilon\frac{\mu}{\sigma}$: therefore, we need to bound that
quantity. Note that

$\sigma^{2}\geq\frac{p}{2}\sum w_{i}^{2}\geq\frac{p}{2}\cdot\frac{(\sum
w_{i})^{2}}{m},$ (1)

and so by the assumptions of the lemma
$\frac{\sigma}{\tilde{\varepsilon}}\geq\frac{\varepsilon\sqrt{mp}}{\gamma\sqrt{2}}$.
Furthermore,

$\frac{\mu}{\sigma}\leq\frac{p\sum w_{i}}{\sqrt{\frac{p}{2m}}\sum
w_{i}}\leq\sqrt{2mp}$ (2)

Now, let $x:=\frac{\varepsilon}{10\gamma c\sqrt{2}}\cdot\frac{\mu}{\sigma}$.
Thus, $x$ verifies $x\leq\frac{\varepsilon}{10\gamma
c\sqrt{2}}\cdot\sqrt{2pm}\leq 0.1\frac{\sigma}{c\tilde{\varepsilon}}$ and so
applying Lemma 7 we obtain:

$\displaystyle\Pr\left[\sum w_{i}X_{i}-\mu>\varepsilon\mu\right]$
$\displaystyle\geq\left(1-\Phi\left(x(1-cx\frac{\tilde{\varepsilon}}{\sigma})\right)\right)\cdot\left(1-c(1+x)\frac{\tilde{\varepsilon}}{\sigma}\right)$
$\displaystyle\geq\left(1-\Phi\left(0.9x\right)\right)\cdot 0.9$
$\displaystyle=0.9\cdot\Pr[\mathcal{N}(0,1)\geq 0.9x]$ $\displaystyle\geq
0.9\cdot\frac{1}{2}\left(1-\sqrt{1-e^{-(0.9x)^{2}}}\right)$
$\displaystyle\geq\exp(-\frac{\beta}{\gamma^{2}}\varepsilon^{2}\frac{\mu^{2}}{\sigma^{2}})$
$\displaystyle\geq\exp(-\frac{\beta}{\gamma^{2}}\varepsilon^{2}mp),$

where $\beta$ is some absolute constant, and where the last line uses Eq. 2. ∎

###  5.2 A subinstance for the case $k=1$

We now turn to proving a lower bound for the case where $k=1$. This is going
to be our building block in the next subsection where we generalize the result
to arbitrary $k$. Let $\delta=1/4$ be a parameter.

######  Definition 2.

A subinstance $U_{\delta}$ is defined as follows. Let $C$ be a set of $n$
_candidate centers_ and $P$ a set of of $n_{U}$ _clients_. The metric on the
ground set $P\cup C$ is defined according to the following probability
distribution.

For each pair $(p,c)\in P\times C$,

$\text{dist}(p,c)=\begin{cases}1\text{ with probability }\delta\\\
2^{1/z}\text{ otherwise}\end{cases}$ (3)

Distances between any pair of points $p,p^{\prime}\in P$ or $c,c^{\prime}\in
C$ is set to $2^{1/z}$.

Fig. 2 illustrates the definition.

Figure 2: Illustration of an instance $U_{\delta}$. Dashed edges have length
$2^{1/z}$, black ones have length $1$.

Since any complete graph with edge length only $1$ or $\ell\leq 2$ defines a
metric space, it immediately follows that $(P\cup C,\text{dist})$ is a metric
space.

The important properties of the subinstance are summarized in the following
lemma. We say that a set of weights is _$\varepsilon$ -rounded_ if all weights
are multiples of $\varepsilon$.

######  Lemma 9.

There exists a constant $\eta$ and an instance $U_{\delta}=(P,C,\text{dist})$
with $|P|=n_{U}=\varepsilon^{-2}\log|C|$, $\delta\leq 1/4$ and
$|C|\geq\varepsilon^{-5}$, the following holds. For any subset
$\Omega\subseteq P$ with $\varepsilon/2$-rounded weights $w_{x}$ being such
that $\sum w_{x}\in(1\pm 1/2)n_{U}$, we have:

  1. 1.

If $|\Omega|<\varepsilon^{-2}\eta\log|C|$, there exists a center $\tilde{c}\in
C$ such that

$\sum_{x\in\Omega:\text{dist}(x,\tilde{c})=1}w_{x}>(1+200\varepsilon)\delta
n_{U}$

and $|x\in P:~{}\text{dist}(x,\tilde{c})=1|\geq\delta n_{U}$

  2. 2.

If $|\Omega|\geq\varepsilon^{-2}\eta\log|C|$, there exists a center $c^{*}\in
C$ such that

$\sum_{x\in\Omega:\text{dist}(x,c^{*})=1}w_{x}\geq(1-\varepsilon)\delta n_{U}$

and $|x\in P:~{}\text{dist}(x,c^{*})=1|\geq\delta n_{U}$.

###### Proof.

We use the probabilistic method: we will show that, when $U_{\delta}$ is
generated according to the process defined above, the two properties of the
lemma hold with some positive probability. This is enough to ensure the
existence of an instance $U_{\delta}$ verifying them.

We start by proving the first item. Fix some arbitrary subset of clients
$\Omega$ of size at most $\varepsilon^{-2}\eta\log|C|$, with weight
$w_{x},\forall x\in\Omega$ and a candidate center $c\in C$. Let
$w_{1}(c,\Omega):=\sum_{x\in\Omega:\text{dist}(x,c)=1}w_{x}$ denote the
(weighted) number of edges of length 1 from $\Omega$ to $c$. The expected
value of $w_{1}(c,\Omega)$ over the random choice of edges is $\delta\cdot
n_{U}$. We aim at applying Lemma 8 on the variable $w_{1}(c,\Omega)$. This
cannot be done directly, as we have no control on $\max w_{x}$. Hence, we
partition the points of $\Omega$ into five groups:

  * •

$\Omega_{1}:=\\{x\in\Omega:~{}w_{x}<\varepsilon\\}$

  * •

$\Omega_{2}:=\\{x\in\Omega:~{}w_{x}\in[\varepsilon,1)\\}$

  * •

$\Omega_{3}:=\\{x\in\Omega:~{}w_{x}\in[1,\varepsilon^{-1})\\}$

  * •

$\Omega_{4}:=\\{x\in\Omega:~{}w_{x}\in[\varepsilon^{-1},10\log(1/\delta)\cdot\varepsilon^{-2})\\}$

  * •

$\Omega_{5}:=\\{x\in\Omega:~{}w_{x}\geq
20\log(1/\delta)\cdot\varepsilon^{-2}\\}$

We will show that, $\forall i\in\\{2,...,5\\}$, $w_{1}(c,\Omega_{i})$ exceeds
its expectation by a factor $(1+205\varepsilon)$ with large probability, and
that $w_{1}(c,\Omega_{1})$ is negligible.

First, note that since
$\sum_{x\in\Omega}w_{x}\leq(1+1/2)n_{U}=\frac{3}{2}\varepsilon^{-2}\log|C|$,
it must be that

$|\Omega_{5}|\leq\frac{\log|C|}{10\log(1/\delta)}.$

Hence, $c$ is connected with length $1$ to all points of $\Omega_{5}$ with
probability
$\delta^{|\Omega_{5}|}\geq\exp\left(-\log|C|/10\right)=|C|^{-1/10}$.

Now, on each group $\Omega_{2},\Omega_{3},\Omega_{4}$, the maximum weight
cannot be more than $20\log(1/\delta)\cdot\varepsilon^{-1}$ times the average.

For $i\in\\{2,3,4\\}$, $w_{1}(c,\Omega_{i})$ is the sum of
$m=|\Omega_{i}|\leq\varepsilon^{-2}\eta\log|C|$ random variables $X_{x}$, for
$x\in\Omega_{i}$, with $X_{x}=0$ with probability $(1-\delta)$ and
$X_{x}=w_{x}$ with probability $\delta=1/4$. Hence, Lemma 8 gives that:

$\displaystyle\Pr\left[w_{1}(c,\Omega_{i})\geq(1+205\varepsilon)\cdot\mathbb{E}[w_{1}(c,\Omega_{i})]\right]$
$\displaystyle>\exp(-\frac{\beta}{\log(1/\delta)^{2}}\varepsilon^{2}\delta|\Omega_{i}|)$
$\displaystyle\geq\exp(-\log|C|/10),$

for some absolute constant $\beta$ given by Lemma 8 and
$\eta\leq\frac{\log(1/\delta)^{2}}{10\beta\delta}$.

Finally, to deal with $\Omega_{1}$, we note that
$\mathbb{E}[w_{1}(c,\Omega_{1})]\leq\varepsilon\delta n_{U}$. Hence,
$\sum_{i=2}^{5}\mathbb{E}[w_{1}(c,\Omega_{i})]\geq\mathbb{E}[w_{1}(c,\Omega)]-\varepsilon\delta
n_{U}$, and

$\displaystyle\sum_{i=2}^{5}w_{1}(c,\Omega_{i})\geq(1+205\varepsilon)\sum_{i=2}^{5}\mathbb{E}[w_{1}(c,\Omega_{i})]$
$\displaystyle\Rightarrow$ $\displaystyle
w_{1}(c,\Omega)\geq(1+200\varepsilon)\delta n_{U}.$

Since all groups are disjoint, the variables $w_{1}(c,\Omega_{i})$ are
independents and we can combine the previous equations to get:

$\displaystyle\Pr\left[\sum_{x\in\Omega:\text{dist}(x,\tilde{c})=1}w_{x}\geq(1+200\varepsilon)\cdot\delta
n_{U}\right]$ $\displaystyle>|C|^{-3/10}.$

Since the length of the edges are chosen independently, the probability that
there exists no center $\tilde{c}$ with
$\sum_{x\in\Omega:\text{dist}(x,\tilde{c})=1}w_{x}\geq(1+200\varepsilon)\cdot\delta
n_{U}$ is at most

$\displaystyle\left(1-|C|^{-3/10}\right)^{|C|}$
$\displaystyle=\exp\left(|C|\log(1-|C|^{-3/10})\right)$
$\displaystyle\leq\exp(-|C|^{7/10}).$

And hence with probability at least $1-\exp(-|C|^{7/10})$ there is a center
$\tilde{c}$ with
$\sum_{x\in\Omega:\text{dist}(x,\tilde{c})=1}w_{x}\geq(1+200\varepsilon)\cdot\delta
n_{U}$.

To conclude the proof of the first bullet, it remains to do a union-bound over
all possible weighted subset $\Omega$. Such an $\Omega$ consists of at most
$n_{U}$ different points, with $\varepsilon/2$-rounded weights in
$[0,(1+1/2)n_{U}]$. Hence, there are at most $\frac{4}{\varepsilon}n_{U}$ many
different weights.

Therefore, there are $\left(\frac{4n_{U}}{\varepsilon}\right)^{n_{U}}$ many
possible weighted subset $\Omega$ with $\varepsilon/2$-rounded weights, i.e.,

$\exp\left(\varepsilon^{-2}\log|C|\cdot\log\left(2\varepsilon^{-3}\log|C|\right)\right).$

We can conclude that there exists a center $\tilde{c}\in C$ with
$\sum_{x\in\Omega:\text{dist}(x,\tilde{c})=1}w_{x}\geq(1+200\varepsilon)\cdot\delta
n_{U}$ with probability at least

$\displaystyle
1-\exp\left(\varepsilon^{-2}\log|C|\cdot\log\left(2\varepsilon^{-3}\log|C|\right)\right)\cdot\exp(-|C|^{7/10})$
$\displaystyle\geq\frac{99}{100}$

by our choice of $|C|$. Furthermore, $\Pr[|x\in
P:~{}\text{dist}(x,\tilde{c})=1|\geq\delta n_{U}]\geq 1/2$, because $|x\in
P:~{}\text{dist}(x,\tilde{c})=1|$ follows a binomial law with mean $\delta
n_{U}$. This concludes the proof of the first bullet.

We now turn to the second bullet of the claim, for which the proof is a more
standard application of Azuma inequality. Fix some coreset $\Omega$ of size at
least $\varepsilon^{-2}\eta\log|C|$, and a center $c$. We have,

$\displaystyle\Pr\left[w_{1}(c,\Omega)\notin(1\pm\varepsilon)\cdot\delta
n_{U}\right]$
$\displaystyle\leq\exp(-2\varepsilon^{2}\delta^{2}\frac{n_{U}^{2}}{\sum
w_{i}^{2}})$ $\displaystyle\leq\exp(-2/4\cdot\delta^{2}\varepsilon^{2})$
$\displaystyle\leq\exp(-1/2\cdot\delta^{2}\varepsilon^{2}),$

where the second inequality uses $n_{U}^{2}\geq 1/4\left(\sum
w_{i}\right)^{2}\geq 1/4\cdot\sum w_{i}^{2}$.

Since those events are independent for different centers $c$, the probability
that there exists no center $c\in C$ with
$w_{1}(c,\Omega)\in(1\pm\varepsilon)\cdot\delta n_{U}$ is at most
$\exp(-1/2\cdot\delta^{2}\varepsilon^{2}|C|)$.

Hence, a union-bound over the
$\left(\frac{4n_{U}}{\varepsilon}\right)^{n_{U}}$ many possible weighted
subset $\Omega$ ensures that the following holds with probability at most
$1-\left(\frac{4n_{U}}{\varepsilon}\right)^{n_{U}}\cdot\exp(-1/2\cdot\delta^{2}\varepsilon^{2}|C|)\geq
99/100$: For any $\Omega$ there exists a center $c$ with
$w_{1}(c,\Omega)\in(1\pm\varepsilon)\cdot\delta|\Omega|$ as desired. ∎

###  5.3 Combining the subinstances

Figure 3: Illustration of a full instance, in the case $z=1$. The subinstance
are inside squares, and there is an edge from a node to a square when the node
is linked to every point of the subinstance, with the distance written on the
edge. $D_{\infty}$ is set to be $4^{i}\cdot\frac{n_{U}\cdot k}{\varepsilon}$.
The node $c^{4\cdot\infty}$ is not represented.

We now conclude the proof of the lower bound for the $(\varepsilon,k,z)$
coreset using offset $\Delta$. We consider $k$ copies of the subinstance given
by Lemma 9, $U_{\delta}^{1},\ldots,U_{\delta}^{k}$, where the set of clients
in each subinstance has size $n_{U}=10\varepsilon^{-2}\log n$, and the set of
candidate centers has size $|C|$ such that $|C|\geq\varepsilon^{-5}$ and
$\log\left(|C|\cdot k\right)=O(\log|C|)$. In total, there are $k|C|$ many
candidate centers, and $kn_{U}$ many different clients. The subinstances are
numbered from $1$ to $k$, and connected together in a star-graph metric
centered at an arbitrary point $c^{\infty}$, where all points are at distance
$\frac{n_{U}\cdot k}{\varepsilon}$ of $c^{\infty}$. There is some additional
candidate centers: $c^{4\cdot\infty}$, at distance $4\cdot\frac{n_{U}\cdot
k}{\varepsilon}$ of every client, and for subinstance $i$ there is a center
$c^{2}_{i}$, at distance $2^{1/z}$ from every client of the subinstance. Fig.
3 illustrates that construction.

We can now turn to the proof of the theorem. For this, we start with three
claims: The first one shows that the total weight of the coreset must be very
close to the number of point in the instance. The second shows that the offset
$\Delta$ must be negligible, and the third that the coreset weight in each
subinstance is close to $n_{U}$, the number of point in a subinstance.

######  Claim 6.

If $\Omega$ is an $\varepsilon$-coreset with offset $\Delta$ for the instance,
then the total weight verifies $w(\Omega)\in(1\pm 2\varepsilon)kn_{U}$.

###### Proof.

Consider the solution consisting only of one center placed at $c^{\infty}$.
Let $D_{\infty}=\frac{n_{U}\cdot k}{\varepsilon}$. This solution has cost
$\text{cost}(c^{\infty})=kn_{U}\cdot D_{\infty}^{z}$, and
$\text{cost}(\Omega,c^{\infty})=w(\Omega)\cdot D_{\infty}^{z}$. Hence,

$\Delta+w(\Omega)\cdot D_{\infty}^{z}\in(1\pm\varepsilon)kn_{U}\cdot
D_{\infty}^{z}.$

Similarly, considering the solution that places only one center at
$c^{4\cdot\infty}$ gives

$\Delta+w(\Omega)4^{z}D_{\infty}^{z}\in(1\pm\varepsilon)kn_{U}\cdot
4^{z}D_{\infty}^{z}.$

Substracting those two equations yields:

$\displaystyle(4^{z}-1)w(\Omega)\cdot
D_{\infty}^{z}\in((4^{z}-1)\pm(4^{z}+1)\varepsilon)kn_{U}\cdot
D_{\infty}^{z},$

and so $w(\Omega)\in(1\pm 2\varepsilon)kn_{U}$. ∎

######  Claim 7.

If $\Omega$ is an $\varepsilon$-coreset with offset $\Delta$ for the instance,
then $|\Delta|\leq 3\varepsilon k\cdot n_{U}$.

###### Proof.

Consider the solution $\mathcal{S}^{2}=\\{c^{2}_{i},~{}\forall i\\}$. We have
$\text{cost}(\mathcal{S}^{2})=2kn_{U}$ and
$\text{cost}(\Omega,\mathcal{S}^{2})=2w(\Omega)\in(1\pm
2\varepsilon)\text{cost}(\mathcal{S}^{2})$, using 6. Since
$|\Delta+\text{cost}(\Omega,\mathcal{S}^{2})-\text{cost}(\mathcal{S}^{2})|\leq\varepsilon\text{cost}(\mathcal{S}^{2})$,
it must be that $|\Delta|\leq
3\varepsilon\text{cost}(\mathcal{S}^{2})=3\varepsilon kn_{U}$. ∎

######  Claim 8.

If $\Omega$ is an $\varepsilon$-coreset with offset $\Delta$ for the instance,
then in every subinstance, the sum of the coreset weights is in $(1\pm
1/2)n_{U}$.

###### Proof.

Assume towards contradiction that, in some subinstance, say subinstance $i$,
the coreset mass is not in $(1\pm 1/2)n_{U}$, and consider a solution
$\mathcal{S}$ that places one center in each subinstance but subinstance $i$.
Suppose w.l.o.g. that the subinstance is overweighted: the coreset places a
total weight larger than $3/2\cdot n_{U}$ in it. The cost of the solution is a
most

$\displaystyle\text{cost}(\mathcal{S})$
$\displaystyle\leq\underbrace{2(k-1)n_{U}}_{\text{for subinstances that
contain a
center}}+\underbrace{n_{U}\cdot\left(kn_{U}\varepsilon^{-1}\right)^{z}}_{\text{for
the overweighted subinstance}}$ $\displaystyle\leq(1+\varepsilon)\left(k\cdot
n_{U}^{2}\varepsilon^{-1}\right)^{z},$

while the cost in the coreset verifies

$\displaystyle\Delta+\text{cost}(\Omega,\mathcal{S})$
$\displaystyle>-3\varepsilon kn_{U}+3/2\cdot
n_{U}\cdot\left(kn_{U}\varepsilon^{-1}\right)^{z}$ (using 7 and keeping only
the cost of the overweighted subinstance)
$\displaystyle>(1+\varepsilon)\cdot(1+\varepsilon)\left(k\cdot
n_{U}^{2}\varepsilon^{-1}\right)^{z}$
$\displaystyle>(1+\varepsilon)\text{cost}(\mathcal{S}),$

hence contradicting the fact that $\Omega$ is an $\varepsilon$-coreset with
offset $\Delta$.

The proof of the case where some subinstance is underweighted is done exactly
alike. ∎

We can now turn to the proof of the theorem.

###### Proof of Theorem 1.

Assume toward contradiction that there exists an $\varepsilon$-coreset with
offset $\Delta$ of size smaller than $\frac{\eta}{10}\cdot
k\varepsilon^{-2}\log|C|$, where $\eta$ is the constant of Lemma 9.

First, this implies the existence of an $2\varepsilon$-coreset with
$\varepsilon$-rounded weights, simply by rounding each weight to the closest
multiple of $\varepsilon$.

Using 8, we can apply Lemma 9 on each subinstance. The total coreset size is
$\frac{\eta}{10}\cdot k\varepsilon^{-2}\log|C|$: that means that there are at
least $k/10$ subinstances for which the coreset contains no more than
$\eta\varepsilon^{-2}\log|C|$ many different points. We refer to these
subinstances as the bad subinstances. Using Lemma 9, we construct a solution
$\mathcal{S}$ by taking the center given by bullet 1 for the bad subinstances,
i.e.: center $\hat{c}$ as per the notation of Lemma 9, and bullet 2 for the
others, i.e.: center $c^{*}$ as per the notation of Lemma 9. The cost of that
solution is $n_{1}+2(kn_{U}-n_{1})=2kn_{U}-n_{1}$, where $n_{1}$ the number of
edges of length $1$ from the clients to $\mathcal{S}$. Similarly, the cost of
$\mathcal{S}$ for the coreset is $2\cdot w(\Omega)-w_{1}(\mathcal{S},\Omega)$,
where $w(\Omega)$ is the total coreset weight and $w_{1}(\mathcal{S},\Omega)$
the weighted number of length 1 edges from $\Omega$ to $\mathcal{S}$. By
construction of $\mathcal{S}$, $w_{1}(\mathcal{S},\Omega)$ verifies

$\displaystyle w_{1}(\mathcal{S},\Omega)\geq k/10\cdot(1+200\varepsilon)\delta
n_{U}+9k/10\cdot(1-\varepsilon)\delta n_{U}>(1+19\varepsilon)\delta\cdot
kn_{U}$

Furthermore, using properties of Lemma 9, $n_{1}\leq\delta kn_{U}$. Hence, the
cost of $\mathcal{S}$ in the coreset satisfies

$\displaystyle\Delta+2\cdot w(\Omega)-w_{1}(\mathcal{S},\Omega)$
$\displaystyle<3\varepsilon
kn_{U}+2\cdot(1+2\varepsilon)kn_{U}-(1+19\varepsilon)\delta\cdot kn_{U}$
$\displaystyle\leq(2kn_{U}-n_{1})+\varepsilon
kn_{U}\cdot(7-38\delta)<(1-\varepsilon)(2k|P|-n_{1}),$

where the last inequality uses $\delta=1/4$, so that $(38\delta-7)kn_{U}\geq
2kn_{U}$. Therefore the cost of the coreset for $\mathcal{S}$ is smaller than
a $(1-\varepsilon)$ factor times the cost of $P$ for $\mathcal{S}$, a
contradiction that concludes the proof. ∎

A simple corollary of that proof is a lower bound for metric with bounded
doubling dimension. Since any $n$ points metric has doubling dimension $O(\log
n)$, the metric constructed has doubling dimension $D=O(\log n)=O(\log|C|)$,
which implies Corollary 2.

##  6 Algorithm

Throughout this section, we use the following notation. We use $\|P\|_{0}$ to
denote the distinct number of points in $P$. For a solution $\mathcal{S}$, we
define the $|P|$ dimensional cost vector $v^{\mathcal{S}}$ induced by
$\mathcal{S}$ as

$v^{\mathcal{S}}_{p}=\text{cost}(p,\mathcal{S}).$

Hence, $\|v^{\mathcal{S}}\|_{1}=\text{cost}(P,\mathcal{S})$.

We will also make use the following lemma to have a weaker version of the
triangle inequality for $k$-Means and more general powers of distances. See
Appendix A from Makarychev, Makarychev, and Razenshteyn [73] for a proof.

######  Lemma 10 (Triangle Inequality for Powers).

Let $a,b,c$ be an arbitrary set of points in a metric space with distance
function $d$ and let $z$ be a positive integer. Then for any $\varepsilon>0$

$\displaystyle d(a,b)^{z}$
$\displaystyle\leq(1+\varepsilon)^{z-1}d(a,c)^{z}+\left(\frac{1+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z}$
$\displaystyle\left|d(a,b)^{z}-d(a,c)^{z}\right|$
$\displaystyle\leq\varepsilon\cdot
d(a,c)^{z}+\left(\frac{z+\varepsilon}{\varepsilon}\right)^{z-1}d(b,c)^{z}.$

We also require Bernstein’s inequality:

######  Theorem 9 (Bernstein’s Inequality).

Let $X_{1},\ldots X_{\delta}$ be non-negative independent random variables.
Let $S=\sum_{i=1}^{\delta}X_{i}$. If there exists an almost-sure upper bound
$M\geq X_{i}$, then

$\mathbb{P}\left[\left|S-\mathbb{E}[S]\right|\geq
t\right]\leq\exp\left(-\frac{t^{2}}{2\sum_{i=1}^{\delta}\text{Var}[X_{i}]+\frac{2}{3}\cdot
M\cdot t}\right).$

###  6.1 Preprocessing and General Outline

We make the following three assumptions:

Assumption 1

The number of distinct points $\|P\|_{0}$ is in $\text{poly}(k/\varepsilon)$.

Assumption 2

The dimension $d$ of the points is in
$O(\varepsilon^{-2}\log\|P\|_{0})=O\left(\varepsilon^{-2}\log\frac{k}{\varepsilon}\cdot\text{poly
}z\right)$.

Assumption 3

The point set is unweighted.

Assuming these simplifies the presentation significantly. The first assumption
can be justified by computing a (potentially weighted) coreset in
preprocessing. Coresets of size $\tilde{O}(k^{2}\cdot\varepsilon^{-4}\cdot
2^{O(z)})$ are known to exists for all $(k,z)$ clustering objectives [35],
which is sufficient for our purposes.

The second assumption follows from a result on terminal embeddings due to
Narayanan and Nelson [82]. We will discuss this result in more detail in
Section 6.4. Suffice to say here is that there exists a coreset-preserving
embedding from an arbitrary dimension to the desired target dimension.

The final assumption follows by scaling the weights and rounding them to
integers. Each weight is then treated as a multiplicity of a point. Note that
this does not increase the distinct number of points. For a proof of the
validity of such an operation, we refer to Corollary 2.3 [35].

We now describe the algorithm. We first compute some constant factor
approximation $\mathcal{A}$ for the entire instance.111A bicriteria
approximation that uses $O(k)$ centers and yields a constant factor
approximation would also be possible. See [74] for state of the art bounds on
bicriteria approximations for $k$-median and $k$-means. For higher powers, see
Mettu and Plaxton [78] for a $2^{O(z)}$ approximation. Let $C_{i}$ be the
$i$th cluster induced by $\mathcal{A}$. The average cost of $C_{i}$ is
$\Delta_{C_{i}}=\frac{\text{cost}(C_{i},\mathcal{A})}{|C_{i}|}$. For all
$i,j$, the ring $R_{i,j}$ is the set of points $p\in C_{i}$ such that
$2^{j}\Delta_{C_{i}}\leq\text{cost}(p,\mathcal{A})\leq 2^{j+1}\Delta_{C_{i}}.$
The inner rings $R_{I}(C_{i}):=\cup_{j\leq z\log(\varepsilon/z)}R_{i,j}$
(resp. outer rings $R_{O}(C_{i}):=\cup_{j>2z\log(z/\varepsilon)}R_{i,j}$) of a
cluster $C_{i}$ consists of the points of $C_{i}$ with cost at most
$\left(\nicefrac{{\varepsilon}}{{z}}\right)^{z}\Delta_{C_{i}}$ and resp. at
least $\left(\nicefrac{{z}}{{\varepsilon}}\right)^{2z}\Delta_{C_{i}}$. The
main rings $R_{M}(C_{i})$ consists of all the other points of $C_{i}$. For
each $j$, $R_{j}$ is defined to be $\cup_{i=1}^{k}R_{i,j}$. We then partition
the input point set into the following groups.

  * •

For each $j$, the rings $R_{i,j}$ are gathered into groups $G^{M}_{j,b}$:

$\displaystyle G^{M}_{j,b}:=\Big{\\{}p~{}|~{}\exists i,~{}p\in R_{i,j}\text{
and }$
$\displaystyle\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\frac{\text{cost}(R_{j},\mathcal{A})}{k}\cdot
2^{b}$
$\displaystyle\leq\text{cost}(R_{i,j},\mathcal{A})\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot
2^{b+1}\cdot\frac{\text{cost}(R_{j},\mathcal{A})}{k}\Big{\\}}.$

  * •

For any $j$, let $G^{M}_{j,min}:=\cup_{b\leq 0}G^{M}_{j,b}$ be the union of
the cheapest groups, and $G^{M}_{j,max}:=\cup_{b\geq
z\log{\frac{4z}{\varepsilon}}}G^{M}_{j,b}$ be the union of the most expensive
ones. We define
$G^{M}:=\bigcup_{j}G^{M}_{j,max}\cup\bigcup_{b}G^{M}_{j,b}\setminus
G^{M}_{j,min}$.

  * •

The points in the outer rings are also partitioned into _outer groups_ :

$\displaystyle G^{O}_{b}=\Big{\\{}p~{}\mid~{}\exists i,~{}p\in C_{i}\text{ and
}$
$\displaystyle\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\frac{\text{cost}(R_{O}^{\mathcal{A}},\mathcal{A})}{k}\cdot
2^{b}$
$\displaystyle\leq\text{cost}(R_{O}(C_{i}),\mathcal{A})\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot
2^{b+1}\cdot\frac{\text{cost}(R_{O}^{\mathcal{A}},\mathcal{A})}{k}\Big{\\}}.$

We denote by $P^{G^{O}_{b}}:=\\{p\in P~{}|~{}p\in C\wedge C\cap
G^{O}_{b}\neq\emptyset\\}$ the set all points in clusters intersecting with
$G$.

  * •

We let as well $G^{O}_{min}=\cup_{b\leq 0}G^{O}_{b}$ and
$G^{O}_{max}=\cup_{b\geq z\log{\frac{4z}{\varepsilon}}}G^{O}_{b}$. We define
$G^{O}:=G^{O}_{max}\cup\bigcup_{b}G^{O}_{b}\setminus G^{O}_{min}$.

The set of all groups is denoted by $\mathcal{G}:=G^{M}\cup G^{O}$. We
sometimes abuse notation and also use $\mathcal{G}$ to denote the set of
points in the groups $G^{M}\cup G^{O}$, i.e. $P\cap\mathcal{G}=\\{p\in
P~{}|~{}p\in G\in\mathcal{G}\\}$ and $P\setminus\mathcal{G}=\\{p\in
P~{}|~{}p\in G\notin\mathcal{G}\\}$. We summarize the group partitioning
scheme with the following two facts.

######  Fact 1.

There exist at most $O(z^{2}\log^{2}z/\varepsilon)$ groups in $\mathcal{G}$.

######  Fact 2.

All groups are pairwise disjoint. Moreover, every cluster $C$ induced by
$\mathcal{A}$ intersects with at most one group $G\in G^{O}$.

The final algorithm now consists of sensitivity sampling for all groups
$G\in\mathcal{G}$. Specifically, we pick a point $p\in G$ with probability
$\frac{\text{cost}(p,\mathcal{A})}{\text{cost}(G,\mathcal{A})}$. We repeat
this $\delta$ times, where $\delta$ is the size of the desired coreset. For
each picked point $p$, we set the weight equal to
$w_{p}:=\frac{\text{cost}(G,\mathcal{A})}{\delta\cdot\text{cost}(p,\mathcal{A})}$.
For every cluster $C_{i}$, we weigh the center $c_{i}$ with the number of
points in $C_{i}\cap\left(\bigcup_{j}G_{j,\min}\cup G^{O}_{\min}\right)$. The
entire coreset construction then consists of steps required to satisfy the
three initial assumptions followed by the sampling procedure, see Algorithm 1.

Compute a $O(2^{z})$ approximation $\mathcal{A}$ to $P$.

Preprocess the instance such that Assumptions 1-3 hold.

Partition the points into groups
$\mathcal{G}=\left(\bigcup_{j}G_{j,\max}\cup\bigcup_{b}G(j,b)\setminus
G_{j,\min}\right)\cup\left(G^{O}_{\max}\cup\bigcup_{b}G^{O}_{b}\setminus
G^{O}_{\min}\right)$.

for all Groups $G\in\mathcal{G}$ do

Sample $\delta\in k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot
2^{O(z\log(1+z))}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k)$
points $\Omega_{G}$ proportionate to
$\frac{\text{cost}(p,\mathcal{A})}{\text{cost}(G,\mathcal{A})}$, and weighted
by $\frac{\text{cost}(G,\mathcal{A})}{\delta\cdot\text{cost}(p,\mathcal{A})}$.

end for

for all $c_{i}\in\mathcal{A}$ do

Weigh $c_{i}\in\mathcal{A}$ by the number of points not in $\mathcal{G}\cap
C_{i}$

end for

Output $\Omega=\mathcal{A}\cup\bigcup_{G}\Omega_{G}$.

Algorithm 1 Euclidean Coreset Construction

For every group $G\in\mathcal{G}$, we will prove that the sampling yields an
$(\varepsilon,E)$ coreset with $E=\varepsilon\cdot\text{cost}(G,\mathcal{A})$.

Given a solution $\mathcal{S}$, the basic estimator for the error is

$D^{\Omega}_{\mathcal{S}}(G):=\left|\sum_{p\in\Omega}w_{p}\cdot\text{cost}(p,\mathcal{S})-\text{cost}(G,\mathcal{S})\right|.$

If for all solutions $\mathcal{S}$ we have a coreset of group
$G\in\mathcal{G}$, we can compose the coresets of each group such that we have
a coreset for $P$. Specifically, we will prove Theorem 4 by proving the
following three lemmas.

The first lemma states that we can use the centers of $\mathcal{A}$ as proxies
for all points not in $\mathcal{G}$. The second and third lemmas informally
give the bounds such that sensitivity sampling for every group $G\in G^{M}$
and respectively $G\in G^{O}$ yield corsets.

######  Lemma 11.

Let $P$ be a set of points and let $\mathcal{S}$ be an arbitrary solution.
Then

$\left|\text{cost}(P\setminus\mathcal{G},\mathcal{S})-\sum_{C_{i}}|\mathcal{G}\cap
C_{i}|\cdot\text{cost}(c_{i},\mathcal{S})\right|\leq\varepsilon\cdot\left(\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})\right).$

######  Lemma 12.

Let $P$ be a set of points and let $G\subset G^{M}$ be a group. Then there
exist absolute constants $\gamma_{1}>0$ such that the sampling procedure of
Algorithm 1 with $\delta\geq
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot 2^{\gamma_{1}\cdot
z\log(1+z)}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k)$ yields

$\mathbb{E}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\cdot
D^{\Omega}_{\mathcal{S}}(G)\right]\leq\varepsilon.$

######  Lemma 13.

Let $P$ be a set of points and let $G\subset\mathcal{G}^{O}$ be a group. Then
there exist absolute constants $\gamma_{2}>0$ such that the sampling procedure
of Algorithm 1 with $\delta\geq
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot 2^{\gamma_{2}\cdot
z\log(1+z)}\cdot\log^{3}\varepsilon^{-1}$ yields

$\mathbb{E}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\cdot
D^{\Omega}_{\mathcal{S}}(G)\right]\leq\varepsilon.$

First, we show that this lemma implies our main theorem.

###### Proof of Theorem 4.

For every group $G\in\mathcal{G}$, let $\Omega_{G}$ be the set of points
returned by the sampling routine and let $\Omega_{\mathcal{G}}$ be the union
of the output of all sampling routines. We consider

$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\frac{1}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}D_{\mathcal{S}}^{\Omega_{\mathcal{G}}}(P\cap\mathcal{G})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\frac{1}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\left|\sum_{G\in\mathcal{G}}\sum_{p\in\Omega_{G}}w_{p}\cdot\text{cost}(p,\mathcal{S})-\text{cost}(G,\mathcal{S})\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\frac{1}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\sum_{G\in\mathcal{G}}D_{\mathcal{S}}^{\Omega_{G}}(G)\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\sum_{G\in
G^{M}}\frac{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\cdot\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\cdot
D_{\mathcal{S}}^{\Omega_{G}}(G)\right]\right.$ $\displaystyle\left.+\sum_{G\in
G^{O}}\frac{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\cdot\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\cdot
D_{\mathcal{S}}^{\Omega_{G}}(G)\right]\right]$
$\displaystyle(\lx@cref{creftype~refnum}{lem:coresetgroupmain})$
$\displaystyle\leq$
$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\sum_{G\in
G^{M}}\frac{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\cdot\varepsilon\right.$
$\displaystyle(\lx@cref{creftype~refnum}{lem:coresetgroupouter})$
$\displaystyle+\left.\sum_{G\in
G^{O}}\frac{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}{\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})}\cdot\varepsilon\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}~{}\underset{\mathcal{S}}{\sup}\left[\varepsilon+\varepsilon\right]=2\varepsilon$

Due to Markov’s inequality, we have with probability at least $3/4$ that
$D_{\mathcal{S}}^{\Omega}(P\cap\mathcal{G})\leq
8\cdot\varepsilon\cdot\left(\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})\right)$
for all $\mathcal{S}$. Combining this with Lemma 11, we then have for all
$\mathcal{S}$

$\displaystyle D_{\mathcal{S}}^{\Omega}(P)$ $\displaystyle\leq$ $\displaystyle
D_{\mathcal{S}}^{\Omega_{\mathcal{G}}}(P\cap\mathcal{G})+\left|\text{cost}(P\setminus\mathcal{G},\mathcal{S})-\sum_{C_{i}}|\mathcal{G}\cap
C_{i}|\cdot\text{cost}(c_{i},\mathcal{S})\right|$ $\displaystyle\leq$
$\displaystyle
9\cdot\varepsilon\cdot\left(\text{cost}(P,\mathcal{S})+\text{cost}(P,\mathcal{A})\right).$

Rescaling $\varepsilon$ by a factor
$9\cdot\left(1+\frac{\text{cost}(P,\mathcal{A})}{\text{OPT}}\right)\in
2^{O(z)}$ yields the desired accuracy. What is left is to prove the space
bound. The maximum number of samples in any group required by Lemma 12 and
Lemma 13 is in
$O(k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}\cdot
2^{O(z\log z)}\cdot\min(\varepsilon^{-z},k))$. Due to Fact 1, the overall
coreset therefore has size
$O(k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{5}\varepsilon^{-1}\cdot
2^{O(z\log z)})$. ∎

The remainder of this section will now focus on the proofs of Lemma 12 and
Lemma 13. Our main analysis tool will be a chaining argument. To do this, we
require two things: (i) a reduction to a Gaussian process and (ii) controlling
the variance of said Gaussian process. The proof of Lemma 11 is standard in
this line of research and included in the appendix for completeness sake.

###  6.2 Setting up a Gaussian process

The chaining arguments we use for proving Lemma 12 and Lemma 13, while
similar, are distinct enough that each lemma requires it’s own notation and
approach. We will focus on Lemma 12, as it arguably the more interesting and
important step. The differences for Lemma 13 are discussed at the end of this
section.

Unless mentioned otherwise, we let the group $G$ be in $G^{M}$. For proving
Lemma 12, we need to have a handle on $\sum_{p\in
G\cap\Omega}w_{p}\text{cost}(p,\mathcal{S})$, to show that
$D^{\Omega}_{\mathcal{S}}(G)$ is concentrated around zero. We will not try to
work directly with the basic cost estimator $\sum_{p\in
P\cap\Omega}v^{\mathcal{S}}_{p}\cdot w_{p}$, since it has a too large
variance. We denote the cost vector
$v^{G,\mathcal{S}}_{p}=\begin{cases}v^{\mathcal{S}}_{p}&\text{if }p\in G\\\
0&\text{else}\end{cases}.$ We will split the cost vector $v^{G,\mathcal{S}}$
into two vectors for which we have separate estimators, for which we will be
able show strong concentration.

To define those estimators, let us first characterize the clusters of the
initial solution $\mathcal{A}$ as follow.

  * •

We say that a cluster $C_{i}\cap G$ induced by $\mathcal{A}$ is _huge_ if
there exists a point $p\in C_{i}\cap G$ such that
$\text{cost}(p,\mathcal{S})\geq\left(\frac{4z}{\varepsilon}\right)^{z}\cdot\text{cost}(p,\mathcal{A})$.
The set of huge clusters induced by $\mathcal{S}$ in $G$ are denoted by
$H_{G,\mathcal{S}}$.

Instead of estimating $\|v^{G,\mathcal{S}}\|_{1}$ directly, we now split
$v^{G,\mathcal{S}}$ in two vectors for which we carry out the estimation
separately. We, define the $|P|$-dimensional vector $u^{G,\mathcal{S}}$ with
entries

$u^{G,\mathcal{S}}_{p}:=\begin{cases}\text{cost}(p,\mathcal{S})&\text{if }p\in
C\cap G\text{ and }C\in H_{G,\mathcal{S}}\\\ 0&\text{otherwise}\end{cases}.$
(4)

Clearly
$v^{G,\mathcal{S}}=v^{G,\mathcal{S}}-u^{G,\mathcal{S}}+u^{G,\mathcal{S}}$, but
even more importantly

$\|v^{G,\mathcal{S}}\|_{1}=\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}+\|u^{G,\mathcal{S}}\|_{1}$
(5)

as none of the entries of the considered vectors are negative.

For a group $G\in G^{O}$, we also characterize the clusters by a type.

  * •

We say that a cluster $C_{i}\cap G$ induced by $\mathcal{A}$ is _far_ if there
exists a point $p\in C_{i}\cap G$ such that $\text{cost}(p,\mathcal{S})\geq
4^{z}\cdot\text{cost}(p,\mathcal{A})$. The set of far clusters induced by
$\mathcal{S}$ in $G$ are denoted by $F_{G,\mathcal{S}}$.

Again, we split the cost vector $v^{G,\mathcal{S}}$ into two parts. Here we
define

$u^{G,\mathcal{S}}_{p}:=\begin{cases}\text{cost}(p,\mathcal{S})&\text{if }p\in
C\cap G\text{ and }C\in F_{G,\mathcal{S}}\\\ 0&\text{otherwise}\end{cases}.$
(6)

As above, Equation 5 holds for this definition of $u^{G,\mathcal{S}}$.

We will estimate $\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}$ in both cases
by means of controlling a Gaussian process. Estimating
$\|u^{G,\mathcal{S}}\|_{1}$ is done via more straightforward methods.

To show that
$\sum_{p\in\Omega}w_{p}\cdot\left(v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p}\right)$
is concentrated around its expectation
$\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}$, we introduce a notion of nets
for cost vectors defined as follows.

######  Definition 3.

Let $I$ be a metric space, $P$ a set of points and two positive integers $k$
and $z$, and let $\alpha>0$ be a precision parameter. Given some solution
$\mathcal{A}$, suppose that $G$ is a group of $P$. Let $\mathbb{C}\subset
I^{k}$ be a (potentially infinite) set of candidate $k$-clusterings. We say
that a set of cost vectors $\mathbb{N}\subset\mathbb{R}^{|P|}$ is an
$(\alpha,k,z)$-clustering net if for every $\mathcal{S}\in\mathbb{C}$ there
exists a vector $v\in\mathbb{N}$ such that the following condition holds.

For all $p\in C\cap G$ such that $C\cap G$ is not huge and not far,

$|\text{cost}(p,\mathcal{S})-v_{p}|\leq\alpha\cdot(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A})).$

For all $p\in C\cap G$ such that $C\cap G$ is either huge or far,

$v_{p}=0.$

The existence of small clustering nets is given by Lemma 21 and 22 in Section
6.4 further below. Before we prove these lemmas, we first describe how this
allows us to use a Gaussian process.

Consider a sequence of $|P|$ dimensional vectors
$v^{\mathcal{S},1},v^{\mathcal{S},2},\ldots$ such that $v^{\mathcal{S},h}$ is
the vector approximating the cost vector $v^{G,\mathcal{S}}-u^{G,\mathcal{S}}$
of $\mathcal{S}$ from a $(2^{-h},k,z)$ clustering net $\mathbb{N}_{h}$. Let us
now consider our estimator of $\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}$
defined as follows.

$\displaystyle Y_{G,p,\mathcal{S}}$ $\displaystyle:=$
$\displaystyle\left(\sum_{h=1}^{\infty}w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)\right)+w_{p}\cdot
v^{\mathcal{S},1}_{p}$ $\displaystyle Y_{G,\mathcal{S}}$ $\displaystyle:=$
$\displaystyle\sum_{p\in\Omega}Y_{G,p}$

The following fact shows that this sum telescopes, and that the expectation of
$Y_{G,\mathcal{S}}$ remains $\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}$.

######  Fact 3.

$\mathbb{E}_{\Omega}\left[Y_{G,\mathcal{S}}\right]=\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}.$

###### Proof.

For a fixed point $p$, it holds that
$\lim_{h\rightarrow\infty}v^{h}_{p}=v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p}$.
Hence, the infinite sum is well defined and we have:

$\displaystyle\sum_{h=1}^{\infty}w_{p}\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)+w_{p}\cdot
v^{\mathcal{S},1}_{p}$ $\displaystyle=~{}$ $\displaystyle
w_{p}v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}\text{ since the sum telescopes}$

Hence, summing over all points $p\in\Omega$ and taking the expecation
concludes the lemma. ∎

Using this fact, we can estimate $\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}$
by $Y_{G,\mathcal{S}}$.

To prove Lemma 12, we in particular wish to show for $G\in G^{M}$

$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left|\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\cdot(Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}])\right|\leq\varepsilon.$

Analogously, for Lemma 13, we wish to show for $G\in G^{O}$

$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left|\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\cdot(Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}])\right|\leq\varepsilon.$

Unfortunately, it is difficult to apply the chaining framework with weighted
Boolean variables. This is usually addressed using the following
symmetrization argument. We pick $\delta$ independent standard normal Gaussian
random variables $\xi_{1},\ldots,\xi_{\delta}\sim\mathcal{N}(0,1)$ and analyse
the following random variables for the respective cases $G\in G^{M}$ and $G\in
G^{O}$

$\displaystyle X_{G,\mathcal{S}}$ $\displaystyle:=$
$\displaystyle\frac{\sum_{p\in\Omega}\left(\sum_{h=1}^{\infty}\xi_{p}\cdot
w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)\right)+\xi_{p}\cdot
w_{p}\cdot
v^{\mathcal{S},1}(p)}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})},$
$\displaystyle X_{G,\mathcal{S}}$ $\displaystyle:=$
$\displaystyle\frac{\sum_{p\in\Omega}\left(\sum_{h=1}^{\infty}\xi_{p}\cdot
w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)\right)+\xi_{p}\cdot
w_{p}\cdot
v^{\mathcal{S},1}_{p}}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}.$

The following lemma is due to Rudra and Wootters [84], see also the book by
Ledoux and Talagrand [67] for more general statements.

######  Lemma 14 (Appendix B.3 of [84]).

Let $T=\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}$ or
$T=\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}$.
Then
$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left|\sum_{p\in\Omega}^{\delta}T\cdot(Y_{G,p,\mathcal{S}}-\mathbb{E}[Y_{G,p,\mathcal{S}}])\right|\leq\sqrt{2\pi}\cdot\mathbb{E}_{\Omega}\mathbb{E}_{\xi}\underset{\mathcal{S}}{\text{sup}}|X_{G,\mathcal{S}}|$.

With these, we now prove the following lemmas.

######  Lemma 15.

Let $G\in G^{M}$. Suppose $\delta=\gamma_{3}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}$ for some absolute
constant $\gamma_{5}$. Then

$\mathbb{E}_{\Omega}~{}\underset{\mathcal{S}}{\sup}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot
u^{G,\mathcal{S}}_{p}-\|u^{G,\mathcal{S}}\|_{1}}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right|\right]\leq\varepsilon.$

######  Lemma 16.

Let $G\in G^{M}$. Suppose $\delta=2^{\gamma_{4}\cdot z\log(1+z)}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k)$
for absolute constants $\gamma_{6}$ and $\gamma_{7}$. Then

$\mathbb{E}_{\Omega}~{}\mathbb{E}_{\xi}~{}\underset{\mathcal{S}}{\sup}~{}|X_{G,\mathcal{S}}|\leq\varepsilon.$

######  Lemma 17.

Let $G\in G^{O}$. Suppose $\delta=\gamma_{5}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}$ for some absolute
constant $\gamma_{9}$. Then

$\mathbb{E}_{\Omega}~{}\underset{\mathcal{S}}{\sup}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot
u^{G,\mathcal{S}}_{p}-\|u^{G,\mathcal{S}}\|_{1}}{\text{cost}(P^{G},\mathcal{A})+\text{cost}(P^{G},\mathcal{S})}\right|\right]\leq\varepsilon.$

######  Lemma 18.

Let $G\in G^{O}$. Suppose $\delta=2^{\gamma_{6}\cdot z\log(1+z)}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}$
for absolute constants $\gamma_{8}$ and $\gamma_{9}$. Then

$\mathbb{E}_{\Omega}~{}\mathbb{E}_{\xi}~{}\underset{\mathcal{S}}{\sup}~{}|X_{G,\mathcal{S}}|\leq\varepsilon.$

The proofs of Lemma 15 and Lemma 17 are in Section Section 6.6, the proofs of
Lemma 16 and Lemma 18 is split into proving the existence of sufficiently
small nets (Section 6.4) and analysing the variance of the Gaussian process.
For now, we show why these lemmas imply Lemma 12 and Lemma 13.

###### Proof of Lemma 12.

As mentioned in Equation 5, we have
$\text{cost}(G,\mathcal{S})=\|v^{G,\mathcal{S}}\|_{1}=\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}+\|u^{G,\mathcal{S}}\|_{1}$.
Due to Lemma 14, we have

$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\cdot|Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}]|\right]\leq\sqrt{2\pi}\cdot\mathbb{E}_{\Omega}~{}\mathbb{E}_{\xi}~{}\underset{\mathcal{S}}{\text{sup}}|X_{G,\mathcal{S}}|.$

Plugging in the bound from Lemma 16, we therefore have

$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\cdot|Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}]|\right]\leq\sqrt{2\pi}\varepsilon.$

Then

$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}D^{\Omega}_{\mathcal{S}}(G)]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}+\|u^{G,\mathcal{S}}\|_{1}-\sum_{p\in\Omega}\left(w_{p}\cdot\left(v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p}\right)+w_{p}\cdot
u^{G,\mathcal{S}}_{p}\right)}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot
u^{G,\mathcal{S}}_{p}-\|u^{G,\mathcal{S}}\|_{1}}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\right|\right]$
$\displaystyle+\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot(v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p})-\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\right|\right]$
$\displaystyle\leq\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot
u^{G,\mathcal{S}}_{p}-\|u^{G,\mathcal{S}}\|_{1}}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\right|\right]+\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left|\sum_{p\in\Omega}^{\delta}\frac{Y_{G,p,\mathcal{S}}-\mathbb{E}[Y_{G,p,\mathcal{S}}]}{\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})}\right|$
$\displaystyle(\lx@cref{creftype~refnum}{lem:q})$ $\displaystyle\leq$
$\displaystyle\varepsilon+\sqrt{2\pi}\varepsilon.$

Rescaling $\varepsilon$ yields the claim. ∎

The proof of Lemma 13 is completely analogous. For completeness sake, we
repeat the steps.

###### Proof of Lemma 13.

As mentioned in Equation 5, we have
$\text{cost}(G,\mathcal{S})=\|v^{G,\mathcal{S}}\|_{1}=\|v^{G,\mathcal{S}}-q^{G,\mathcal{S}}\|_{1}+\|u^{G,\mathcal{S}}\|_{1}$.
Due to Lemma 14, we have $\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\cdot|Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}]|\right]\leq\sqrt{2\pi}\cdot\mathbb{E}_{\Omega}~{}\mathbb{E}_{\xi}~{}\underset{\mathcal{S}}{\text{sup}}|X_{G,\mathcal{S}}|$.
Plugging in the bound from Lemma 18, we therefore have
$\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\cdot|Y_{G,\mathcal{S}}-\mathbb{E}[Y_{G,\mathcal{S}}]|\right]\leq\sqrt{2\pi}\varepsilon$.
Then

$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{ sup
}}\left[\frac{1}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}D^{\Omega}_{\mathcal{S}}(G)]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}+\|u^{G,\mathcal{S}}\|_{1}-\sum_{p\in\Omega}w_{p}\cdot\left(v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p}\right)+w_{p}\cdot
u^{G,\mathcal{S}}_{p}}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot
u^{G,\mathcal{S}}_{p}-\|u^{G,\mathcal{S}}\|_{1}}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\right|\right]$
$\displaystyle+\mathbb{E}_{\Omega}\underset{\mathcal{S}}{\text{sup}}\left[\left|\frac{\sum_{p\in\Omega}w_{p}\cdot(v^{G,\mathcal{S}}_{p}-u^{G,\mathcal{S}}_{p})-\|v^{G,\mathcal{S}}-u^{G,\mathcal{S}}\|_{1}}{\text{cost}(P^{G},\mathcal{S})+\text{cost}(P^{G},\mathcal{A})}\right|\right]$
Lemma 17 $\displaystyle\leq$
$\displaystyle\varepsilon+\sqrt{2\pi}\varepsilon.$

Rescaling $\varepsilon$ yields the claim. ∎

###  6.3 A Structural Lemma

We will use the property for $G^{M}$ that we have a good estimator for the
size of every cluster of $\mathcal{A}$. We will frequently use this property
in subsequent sections. By definition of groups, we have for every point $p$
of any cluster $C$ with a non-empty intersection with $G\in G^{M}$

$\text{cost}(G,\mathcal{A})\leq 2k\cdot\text{cost}(C\cap G,\mathcal{A})\leq
4k\cdot|C\cap G|\cdot\text{cost}(p,\mathcal{A}).$ (7)

We first show that, given we sampled enough points, $|C\cap G|$ is well
approximated for every cluster $C$. This lemma will also be used later for
bounding the supremum of $X_{G,\mathcal{S}}$ in the proof of Lemma 16. We
define event $\mathcal{E}_{G}$ to be for all clusters $C$,

$\sum_{p\in C\cap G\cap\Omega}w_{p}=\sum_{p\in C\cap
G\cap\Omega}\frac{\text{cost}(G,\mathcal{A})}{\delta\cdot\text{cost}(p,\mathcal{A})}=(1\pm\varepsilon)\cdot|C\cap
G|.$

######  Lemma 19.

Let $G\in G^{M}$. We have that with probability at least
$1-k\cdot\exp\left(-\frac{\varepsilon^{2}}{9\cdot k}\delta\right)$, event
$\mathcal{E}_{G}$ happens.

The proof is similar to the one used in Lemma 4.4 from [35]. The main
difference is, due to using a slightly different sampling distribution,
Hoeffding’s inequality is insufficient and we have to rely on Bernstein’s
inequality.

###### Proof of Lemma 19.

First, observe that $\mathbb{E}[\sum_{p\in C\cap G\cap\Omega}w_{p}]=|C\cap
G|$. We will bound both the variance as well as $M$ in order to apply
Bernstein’s inequality. Let $\Omega$ be the set of sampled points and let
$p_{j}$ be the $j$th point in the sample with respect to some arbitrary but
fixed ordering. Consider the random variable
$w_{p_{j},C}=\begin{cases}w_{p}&\text{if }p_{j}=p\in C\cap G\\\
0&\text{else}\end{cases}$. Then

$\displaystyle\text{Var}[w_{p_{j},C}]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}[w_{p_{j},C}^{2}]=\sum_{p\in C\cap
G}w_{p}^{2}\cdot\mathbb{P}[p\in\Omega]=\sum_{p\in C\cap
G}\frac{\text{cost}(G,\mathcal{A})}{\delta^{2}\cdot\text{cost}(p,\mathcal{A})}$
$\displaystyle(Eq.~{}\ref{eq:ksize1})$ $\displaystyle\leq$
$\displaystyle\sum_{p\in C\cap
G}\frac{2k\text{cost}(C,\mathcal{A})}{\delta^{2}\text{cost}(p,\mathcal{A})}\leq\sum_{p\in
C\cap G}\frac{4k\cdot|C\cap G|}{\delta^{2}}\leq\frac{4k\cdot|C\cap
G|^{2}}{\delta^{2}}$ (8)

For the maximum upper bound, we have again due to Equation 7

$w_{p_{j},C}=\frac{\text{cost}(P,\mathcal{A})}{\delta\cdot\text{cost}(p_{j},\mathcal{A})}\leq\frac{4k\cdot|C\cap
G|}{\delta}$ (9)

Thus, combining Equation 8 and 9 with Bernstein’s inequality, we have

$\displaystyle\mathbb{P}\left[\left|\sum_{p\in C_{i}\cap\Omega}w_{p}-|C\cap
G|\right|>\varepsilon\cdot|C\cap G|\right]$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\varepsilon^{2}\cdot|C\cap
G|^{2}}{2\delta\cdot\frac{4k\cdot|C\cap
G|^{2}}{\delta^{2}}+\frac{2}{3}\frac{4k\cdot|C\cap
G|}{\delta}\cdot\varepsilon\cdot|C\cap G|}\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\varepsilon^{2}}{9\cdot k}\cdot\delta\right).$

The lemma now follows by taking a union bound over all clusters in
$\mathcal{A}$. ∎

###  6.4 Existence of Small Clustering Nets

For a set of points $P$, a set of points $\mathcal{N}_{\varepsilon}$ is an
_$\varepsilon$ -net_ of $P$ if for every point $x\in P$ there exists some
point $y\in\mathcal{N}_{\varepsilon}$ with $\|x-y\|\leq\varepsilon$. The
existence of small nets in Euclidean spaces is given by the following
statement.

######  Lemma 20 (Lemma 5.2 of [89]).

For the unit $d$-dimensional Euclidean ball centered around the origin, there
exists an $\varepsilon$-net of cardinality $(1+2/\varepsilon)^{d}$.

We further will crucially rely on terminal embeddings defined as follows. A
terminal embedding of a set $P\in\mathbb{R}^{d}$ is a mapping
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ such that

$\forall x\in P,~{}\forall
y\in\mathbb{R}^{d},~{}(1-\varepsilon)\cdot\|x-y\|_{2}\leq\|f(x)-f(y)\|_{2}\leq(1+\varepsilon)\cdot\|x-y\|_{2}.$

The statement is closely related to the classic Johnson-Lindenstrauss lemma.
The crucial generalization is that the pairwise distances between any point of
$\mathbb{R}^{d}$ and any point of $P$, rather than just the pairwise distances
of points in $P$, are preserved.

######  Theorem 10 (Theorem 1.1 of [82]).

For any point set $P$ in $\mathbb{R}^{d}$, there exists a terminal embedding
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ with $m\in
O(\varepsilon^{2}\log\|P\|_{0})$.

The target dimension here is optimal for a wide range of parameters (see
Larsen and Nelson for a matching lower bound [66]). Using both of these
statements, we now show the existence of small clustering nets.

######  Lemma 21.

Let $k,z$ be two positive integers, $G$ be a group and $\mathcal{A}$ be a
solution to $(k,z)$-clustering. Define $\mathbb{C}$ to be the set of possible
candidate centers. For all $\alpha\leq 1/2$, there exists an
$(\alpha,k,z)$-clustering net $\mathbb{N}$ of $\mathbb{C}$ with

$|\mathbb{N}|\leq\exp\left(\gamma_{7}\cdot z^{2}\cdot
k\cdot\log\|P\|_{0}/\alpha^{2}\cdot\log\frac{1}{\alpha\cdot\varepsilon})\right),$

where $\gamma_{7}$ is an absolute constant.

###### Proof.

Let $f$ be a terminal embedding of $P$ into
$O(\left(\frac{z}{\alpha}\right)^{2}\log\|P\|_{0})$ dimensions given by
Theorem 10. Given a solution $\mathcal{S}$, we then have for any $p\in P$

$\text{cost}(p,f(\mathcal{S}))=\left(\min_{s\in\mathcal{S}}\|f(p)-f(s)\|\right)^{z}=\left((1\pm\alpha/O(z))\cdot\min_{s\in\mathcal{S}}\|p-s\|\right)^{z}=(1\pm\alpha)\cdot\text{cost}(p,\mathcal{S})$

Let $B$ be an arbitrary subset of the clusters induced by $\mathcal{A}$. Here
$B$ is meant to contain the clusters that are not in $H_{G,\mathcal{S}}$ for a
given candidate solution $\mathcal{S}$, but the exact interpretation of $B$ is
not important for the proof. We will show that for every $B$, there exists an
$(\alpha,k,z)$ clustering net $\mathbb{N}_{B}$ of size

$|\mathbb{N}_{B}|\in\exp\left(O\left(z^{2}/\alpha^{2}k\cdot\log\|P\|_{0}\cdot\log\left(\frac{z}{\alpha\cdot\varepsilon}\right)\right)\right).$
(10)

Since there are at most $2^{k}$ subsets $B$, the overall size of the
clustering net is then $\sum_{B}|\mathbb{N}_{B}|\leq
2^{k}\cdot\exp\left(O\left(z^{2}\cdot
k\cdot\log\|P\|_{0}/\alpha^{2}\cdot\log\left(\frac{z}{\alpha\cdot\varepsilon}\right)\right)\right)=\exp\left(O\left(z^{2}\cdot
k\cdot\log\|P\|_{0}/\alpha^{2}\cdot\log\left(\frac{z}{\alpha\cdot\varepsilon}\right)\right)\right).$

We now justify Equation 10. We take an
$\frac{\alpha}{z}\cdot\text{dist}(p,\mathcal{A})$-net of the Euclidean ball
centered around $p\in C\in B$ with radius
$8\cdot\left(\frac{4z}{\varepsilon}\right)\cdot\text{dist}(p,\mathcal{A})$.
Such a net has size at most

$\exp\left(O\left(z^{2}\log\|P\|_{0}/\alpha^{2}\cdot\log\left(\frac{z}{\alpha\cdot\varepsilon}\right)\right)\right)$

due to Lemma 20.

We now take the union of all
$\frac{\alpha}{z}\cdot\text{dist}(p,\mathcal{A})$-nets of all points $p\in
C\in B$. This yields a total number of
$\|P\|_{0}\cdot\exp\left(K_{z}\log\|P\|_{0}\cdot\alpha^{-2}\cdot\log\frac{1}{\alpha\cdot\varepsilon}\right)$
nets points. We set $\mathbb{N}_{B}$ to be set of all subsets of size $k$ of
the union of nets. Clearly, $|\mathbb{N}_{B}|=\exp\left(K_{z}\cdot
k\cdot\log\|P\|_{0}/\alpha^{2}\cdot\log\frac{1}{\alpha\cdot\varepsilon}\right)$
as desired in Equation 10. What is left to show is that $\mathbb{N}_{B}$ is an
$(O(\alpha),k,z)$ clustering net. The lemma then follows by rescaling
$\alpha$.

Let $\mathcal{S}\in\mathbb{C}$ be a set of $k$ centers. Consider the set $N$
of $k$ net points defined as follows :
$N:=\cup_{s\in\mathcal{S}}\\{n_{s}:n_{s}\text{ is the closest net point to
}f(s)\\}$. Define the cost vector $v^{N}$ such that
$v^{N}(p)~{}=~{}\begin{cases}\text{cost}(f(p),N)&\text{if }p\in C\notin
H_{G,\mathcal{S}}\\\ 0&\text{else}\end{cases}$. Let $p$ be a point from a
cluster $C\notin H_{G,\mathcal{S}}$. By definition of $H_{G,\mathcal{S}}$,
this implies

$\text{cost}(p,\mathcal{S})\leq\left(\frac{4z}{\varepsilon}\right)^{z}\text{cost}(p,\mathcal{A}).$
(11)

We need to show that
$|\text{cost}(p,\mathcal{S})-v_{N_{\mathcal{S}}}(p)|\leq\alpha\cdot(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A}))$.

Let $s$ be the center closest to $p$ in $\mathcal{S}$, and $c$ be $p$’s
closest center in $\mathcal{A}$. The terminal embedding ensures

$\|f(p)-f(s)\|_{2}\leq(1+\alpha/O(z))\|p-s\|_{2}\leq(1+\alpha/O(z))^{2}\cdot\|f(p)-f(s)\|_{2}.$

Then,

$\displaystyle\|f(c)-f(s)\|_{2}$
$\displaystyle\leq\|f(c)-f(p)\|_{2}+\|f(p)-f(s)\|_{2}$
$\displaystyle\leq(1+\alpha/z)\cdot\|c-p\|_{2}+(1+\alpha/z)\cdot\|p-s\|_{2}$
$\displaystyle\leq(1+\alpha/O(z))\left(1+\left(\frac{4z}{\varepsilon}\right)\right)\cdot\|p-c\|_{2}$
$\displaystyle\leq 4\cdot\left(\frac{4z}{\varepsilon}\right)\|p-c\|_{2}$

where third inequality holds due to Equation 11. Hence, $f(s)$ is in the ball
of radius $8\left(\frac{4z}{\varepsilon}\right)\text{dist}(p,c)$ centered
around $p$ which implies

$|\text{dist}(f(p),f(\mathcal{S}))-\text{dist}(f(p),n_{s})|\leq\left(\frac{2\alpha}{z}\right)\cdot\text{dist}(f(p),f(\mathcal{A})).$

We therefore have

$\displaystyle|\text{cost}(f(p),f(\mathcal{S}))-\text{cost}(f(p),n_{s})|$
$\displaystyle=$
$\displaystyle|\text{dist}(f(p),f(\mathcal{S}))-\text{dist}(f(p),n_{s})|\cdot\text{dist}(f(p),f(\mathcal{S}))^{z-1}\cdot\sum_{i=0}^{z-1}\left(\frac{\text{dist}(f(p),n_{s})}{\text{dist}(f(p),f(\mathcal{S}))}\right)^{i}$
$\displaystyle\leq$
$\displaystyle\left(\frac{2\alpha}{z}\right)\cdot\text{dist}(f(p),f(\mathcal{A}))\cdot\text{dist}(f(p),f(\mathcal{S}))^{z-1}\cdot
z\cdot\left(1+\left(\frac{2\alpha}{z}\right)\cdot\frac{\text{dist}(f(p),f(\mathcal{A}))}{\text{dist}(f(p),f(\mathcal{S}))}\right)^{z-1}$
$\displaystyle\leq$
$\displaystyle\left(\frac{2\alpha}{z}\right)\cdot\text{dist}(f(p),f(\mathcal{A}))\cdot
z\cdot\left(\text{dist}(f(p),f(\mathcal{S}))+\left(\frac{2\alpha}{z}\right)\text{dist}(f(p),f(\mathcal{A}))\right)^{z-1}$
$\displaystyle\leq$
$\displaystyle\left(\frac{2\alpha}{z}\right)\cdot\text{dist}(f(p),f(\mathcal{A}))\cdot
z\cdot\left(1+\left(\frac{2\alpha}{z}\right)\right)\cdot\max\left(\text{dist}(f(p),f(\mathcal{S})),\text{dist}(f(p),f(\mathcal{A}))\right)^{z-1}$
$\displaystyle\leq$ $\displaystyle
4\alpha\cdot\left(\text{cost}(f(p),f(\mathcal{A})+\text{cost}(f(p),f(\mathcal{S})\right).$
(12)

This implies that

$\displaystyle|\text{cost}(p,\mathcal{S})-v_{N}(p)|$
$\displaystyle\leq|\text{cost}(f(p),f(\mathcal{S}))-\text{cost}(f(p),n_{s})|+O(\alpha)\cdot\text{cost}(p,\mathcal{S})$
$\displaystyle(Eq.~{}\ref{eq:diffbound})$ $\displaystyle\leq
4\alpha\cdot\left(\text{cost}(f(p),f(\mathcal{A})+\text{cost}(f(p),f(\mathcal{S})\right)+O(\alpha)\cdot\text{cost}(p,\mathcal{S})$
$\displaystyle=O(\alpha)\cdot(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A})).$

Thus, up to a rescaling of $\alpha$ by constant factors, we have the desired
accuracy and thereby proving Equation 10. ∎

######  Lemma 22.

Let $k,z$ be two positive integers, $G$ be a group and $\mathcal{A}$ be a
solution to $(k,z)$-clustering. Suppose the points of $G$ lie in $d$
dimensional Euclidean space. Define $\mathbb{C}$ to be the set of possible
candidate centers. For all $\alpha\leq 1/2$, there exists an
$(\alpha,k,z)$-clustering net $\mathbb{N}$ of $\mathbb{C}$ with

$|\mathbb{N}|\leq\exp\left(\gamma_{8}\cdot k\cdot d\cdot
z\log(4z/(\alpha\cdot\varepsilon))\right),$

where $\gamma_{8}$ is an absolute constant.

###### Proof.

The construction is essentially identical to that of Lemma 21. The main
difference is that we now take nets of the $d$-dimensional Euclidean ball
centered around every point $p$. These nets has size at most

$\exp\left(O\left(d\cdot
z\log(4z/(\alpha\cdot\varepsilon))\right)\right)=\exp\left(\gamma_{11}\cdot
d\cdot z\log(4z/(\alpha\cdot\varepsilon))\right)$

due to Lemma 20.

The remaining arguments from Lemma 21 are not affected by this change. ∎

Recall that we assumed that $d\in O(\varepsilon^{-2}\log\|P\|_{0})$, which is
a consequence of Theorem 10. We will describe the chaining procedure in more
detail in Section 6.5. For those familiar with chaining: this assumption on
$d$, combined with the bound of Lemma 22 will ensure that the chain converges
after only a small number of steps.

###  6.5 Proofs of Lemma 16 and Lemma 18

We focus on the proof of Lemma 16. The proof of Lemma 18 follows along the
same lines, but is far simpler. For completeness, we repeat the arguments at
the end of the section.

###### Proof of Lemma 16.

In the following, let $G\in G^{M}$. We recall the random variable

$\displaystyle X_{G,\mathcal{S}}$ $\displaystyle:=$
$\displaystyle\frac{1}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\sum_{p\in\Omega}\left(\sum_{h=1}^{\infty}\xi_{p}\cdot
w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)\right)+\xi_{p}\cdot
w_{p}\cdot v^{\mathcal{S},1}_{p}.$

Define

$\displaystyle X_{G,\mathcal{S},0}$ $\displaystyle:=$
$\displaystyle\frac{1}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\sum_{p\in\Omega}\xi_{p}\cdot
w_{p}\cdot v^{\mathcal{S},1}_{p}$ $\displaystyle X_{G,\mathcal{S},h}$
$\displaystyle:=$
$\displaystyle\frac{1}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\sum_{p\in\Omega}\xi_{p}\cdot
w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right).$

We have $\mathbb{E}_{\Omega}\mathbb{E}_{\xi}\underset{\mathcal{S}}{\text{ sup
}}|X_{G,\mathcal{S}}|\leq\sum_{h=0}^{\infty}\mathbb{E}_{\Omega}\mathbb{E}_{\xi}\underset{\mathcal{S}}{\text{
sup }}|X_{G,\mathcal{S},h}|.$ The number of vectors $v^{\mathcal{S},h}$ are
bounded via Lemma 21 and 22. The primary remaining challenge is to control the
variance of $X_{G,\mathcal{S},h}$.

######  Lemma 23.

Let $G\in G^{M}$. Fix a solution $\mathcal{S}$ and let $\beta_{1},\beta_{2}>0$
be absolute constants. Then $X_{G,\mathcal{S},h}$ is Gaussian distributed with
mean $0$. The variance of $X_{G,\mathcal{S},h}$ is always at most

$\sum_{p\in\Omega}\left(\frac{w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}\in\delta^{-1}\cdot
2^{\beta_{1}z\log(1+z)}2^{-2h}\cdot\varepsilon^{-2z}.$

Furthermore, conditioned on event $\mathcal{E}_{G}$, the variance of
$X_{G,\mathcal{S},h}$ is at most

$\sum_{p\in\Omega}\left(\frac{w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}\in\delta^{-1}\cdot
2^{\beta_{2}z\log(1+z)}2^{-2h}\cdot\min(\varepsilon^{-z},k).$

###### Proof.

We recall the standard fact that if $\xi_{p}\sim\mathcal{N}(0,1)$, then
$\sum_{p}a_{p}\cdot\xi_{p}$ is Gaussian distributed with mean $0$ and variance
$\sum_{p}a_{p}^{2}$.

For any $p\in C\notin H_{G,\mathcal{S}}$, we have
$\text{cost}(p,\mathcal{S})\leq\left(\frac{4z}{\varepsilon}\right)^{z}\text{cost}(p,\mathcal{A})$.
A terminal embedding with target dimension $O(z^{2}2^{2h}\log\|P\|_{0})$
preserves the cost up to a factor $(1\pm 2^{-h})$, i.e. we have
$(1-2^{-h})\cdot\text{cost}(p,\mathcal{S})\leq
v^{\mathcal{S},h}_{p}\leq(1+2^{-h})\text{cost}(p,\mathcal{S})$. Therefore

$\displaystyle\sum_{p\in\Omega}\left(\frac{w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-v^{\mathcal{S},h}_{p}\right)}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}$
(13) $\displaystyle=$
$\displaystyle\sum_{p\in\Omega}\left(\frac{w_{p}\cdot\left(v^{\mathcal{S},h+1}_{p}-\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{S})-v^{\mathcal{S},h}_{p}\right)}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}$
$\displaystyle\leq$ $\displaystyle\sum_{p\in\Omega}\left(\frac{w_{p}\cdot
2^{-h-1}\cdot\text{cost}(p,\mathcal{S})}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{p\in\Omega}2^{-2h+2}\left(\frac{\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}\cdot\text{cost}(p,\mathcal{S})}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}.$

To prove the first bound, we now merely recall since $p\in C\notin
H_{G,\mathcal{S}}$, we have
$\frac{\text{cost}(p,\mathcal{S})}{\text{cost}(p,\mathcal{A})}\leq\left(\frac{4z}{\varepsilon}\right)^{z}$.

For the second bound, we first consider an arbitrary cluster $C$ and let
$q=\underset{p\in C}{~{}\operatorname{argmin}~{}}\text{cost}(p,\mathcal{S})$.
Then we have for any solution $\mathcal{S}$

$\text{cost}(p,\mathcal{S})\leq(\text{dist}(q,\mathcal{S})+\text{dist}(p,q))^{z}\leq\frac{2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})}{|C|}.$ (14)

We first focus on the case $\varepsilon^{z}<k$. Continuing from Equation 13
and combining with Equation 14, we have

$\displaystyle\sum_{p\in\Omega}2^{-2h+2}\left(\frac{\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}\cdot\text{cost}(p,\mathcal{S})}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{\text{cost}(G,\mathcal{A})}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot
2^{-2h+2}\cdot\sum_{p\in\Omega}\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}\cdot\text{cost}(p,\mathcal{S})\cdot\left(\frac{4z}{\varepsilon}\right)^{z}$
$\displaystyle\leq$ $\displaystyle\frac{\text{cost}(G,\mathcal{A})\cdot
2^{-2h+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\sum_{C}\frac{2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})}{|C|}\sum_{p\in
C\cap\Omega}\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}$
$\displaystyle\leq$ $\displaystyle\frac{\text{cost}(G,\mathcal{A})\cdot
2^{-2h+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\sum_{C}2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})$ $\displaystyle\leq$
$\displaystyle\frac{\text{cost}(G,\mathcal{A})\cdot
2^{-2h+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot
8^{z}\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))$
$\displaystyle\leq$
$\displaystyle\frac{2^{-2h+2}\cdot\left(\frac{4z}{\varepsilon}\right)^{z}\cdot
8^{z}}{\delta}$

where the third inequality uses event $\mathcal{E}_{G}$.

We now obtain a bound depending on $k$. Recall for any point $p\in C\cap G$,
we have

$\text{cost}(G,\mathcal{A})\leq 2k\cdot\text{cost}(C\cap G,\mathcal{A})\leq
4k\cdot\text{cost}(p,\mathcal{A})\cdot|C|$ (15)

by definition of the groups. Then

$\displaystyle\sum_{p\in\Omega}2^{-2h+2}\left(\frac{\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}\cdot\text{cost}(p,\mathcal{S})}{\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot
2^{-2h+2}\cdot\sum_{C}\sum_{p\in
C\cap\Omega}\frac{4\cdot\text{cost}(G,\mathcal{A})\cdot|C|\cdot
k}{\delta\cdot\text{cost}(p,\mathcal{A})}\cdot\text{cost}^{2}(p,\mathcal{S})$
$\displaystyle\leq$ $\displaystyle\frac{2^{-2h+4}\cdot
k}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\sum_{C}|C|\cdot\left(\frac{2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})}{|C|}\right)^{2}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\cdot\sum_{p\in
C\cap\Omega}\frac{\text{cost}(G,\mathcal{A})}{\delta\text{cost}(p,\mathcal{A})}$
$\displaystyle\leq$ $\displaystyle\frac{2^{-2h+4}\cdot
k}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\sum_{C}\left(2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})\right)^{2}$
$\displaystyle\leq$ $\displaystyle\frac{2^{-2h+4}\cdot
k}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\left(\sum_{C}2^{z}\cdot\text{cost}(C\cap
G,\mathcal{S})+4^{z}\cdot\text{cost}(C\cap G,\mathcal{A})\right)^{2}$
$\displaystyle\leq$ $\displaystyle\frac{2^{-2h+4}\cdot k\cdot
64^{z}}{\delta\cdot(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S}))^{2}}\cdot\left(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})\right)^{2}$
$\displaystyle\leq$ $\displaystyle\frac{2^{-2h+4}\cdot k\cdot 64^{z}}{\delta}$

where the first inequality uses Equation 15, the second inequality uses
Equation 14 and the third inequality uses Equation 13. ∎

We now combine the bound on the variance with union bounds for
$X_{G,\mathcal{S},h}$. Let $\delta$ be as given in the statement of Lemma 16.

We will use the following lemma for bounding the expected maximum of
independent Gaussians.

######  Lemma 24 (Lemma 2.3 of Massart [76]).

Let $g_{i}\thicksim\mathcal{N}(0,\sigma_{i}^{2})$, $i\in[n]$ be Gaussian
random variables and suppose $\sigma_{i}\leq\sigma$ for all $i$. Then

$\mathbb{E}[\underset{i\in[n]}{\max}|g_{i}|]\leq 2\sigma\cdot\sqrt{2\ln n}.$

We use the following fact:

######  Fact 4.

$\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}]=\mathbb{P}_{\Omega}[\mathcal{E}_{G}]\cdot\mathbb{E}_{\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]+\mathbb{P}_{\Omega}[\overline{\mathcal{E}_{G}}]\cdot\mathbb{E}_{\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\overline{\mathcal{E}_{G}}].$

$\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{\mathcal{S}}]=\mathbb{P}_{\Omega}[\mathcal{E}_{G}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]+\mathbb{P}_{\Omega}[\overline{\mathcal{E}_{G}}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\overline{\mathcal{E}_{G}}].$

###### Proof.

Since $\mathcal{E}_{G}$ is independent of $\xi$, the law of total expectation
gives

$\displaystyle\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}]$
$\displaystyle=\mathbb{P}_{\Omega,\xi}[\mathcal{E}_{G}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]+\mathbb{P}_{\Omega,\xi}[\overline{\mathcal{E}}_{G}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\overline{\mathcal{E}}_{G}]$
$\displaystyle=\mathbb{P}_{\Omega}[\mathcal{E}_{G}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]+\mathbb{P}_{\Omega}[\overline{\mathcal{E}}_{G}]\cdot\mathbb{E}_{\Omega,\xi}[\sup_{\mathcal{S}}X_{G,\mathcal{S},h}~{}|~{}\overline{\mathcal{E}}_{G}]$

∎

We will bound the expectation, first assuming the (more likely case) that
event $\mathcal{E}_{G}$ holds, then assuming the (more unlikely case) that
event $\mathcal{E}_{G}$ does not hold.

Condition on $\mathcal{E}_{G}$. We simply upper bound
$\mathbb{P}[\mathcal{E}_{G}]$ with $1$. Assume that the points lie in
dimension $\alpha\cdot\log\|P\|_{0}\cdot\varepsilon^{-2}$ and let $t\in
O(\log(\alpha\cdot\varepsilon^{-2}))$. We will show that the contribution of
the $X_{G,\mathcal{S},h}$ with $h\leq t$ to the expectation is at most
$\varepsilon/\log(1/\varepsilon)$, and then bound the expectation for all
remaining $h\geq t$.

First, we recall that, conditioned on event $\mathcal{E}_{G}$ and due to Lemma
23 and by our choice of $\delta$, we have

$\textbf{Var}[X_{h,\mathcal{S}}~{}|~{}\mathcal{E}_{G}]\leq\beta_{3}\cdot\delta^{-1}\cdot
2^{\beta_{4}z\log z}2^{-2h}\cdot\min(\varepsilon^{-z},k).$

for absolute constants $\beta_{3}$ and $\beta_{4}$.

For the number of distinct $X_{G,\mathcal{S},h}$, we have an upper bound of
$|\mathbb{N}_{h-1}|\cdot|\mathbb{N}_{h}|\leq|\mathbb{N}_{h}|^{2}$, where
$|\mathbb{N}_{h}|$ is the size of an $(2^{-h},k,z)$-clustering net. Due to
Lemma 21, this is at most $\exp(2\cdot\gamma_{7}\cdot z^{2}\cdot
k\cdot\log\|P\|_{0}\cdot 2^{2h}\cdot\log\frac{1}{2^{-h}\cdot\varepsilon})$,
which by the upper bound on $h$ is at most $\exp(2\cdot\gamma_{7}\cdot
z^{2}\cdot k\cdot\log\|P\|_{0}\cdot
2^{2h}\cdot\log\frac{\alpha}{\varepsilon^{-3}})$. Therefore, using Lemma 24

$\displaystyle\mathbb{E}[\sup_{\mathcal{S}}|X_{G,\mathcal{S},h}|~{}|~{}\mathcal{E}_{G}]$
(16) $\displaystyle\leq$ $\displaystyle
2\sqrt{\textbf{Var}[X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]}\sqrt{2\ln(|\mathbb{N}_{h-1}|\cdot|\mathbb{N}_{h}|)}$
$\displaystyle\leq$ $\displaystyle 2\sqrt{\delta^{-1}\cdot 2^{\beta_{1}z\log
z}2^{-2h}\cdot\min(\varepsilon^{-z},k)}\cdot\sqrt{2\cdot\gamma_{7}\cdot
z^{2}\cdot k\cdot\log\|P\|_{0}\cdot
2^{2h}\cdot\log\log\frac{\alpha}{\varepsilon^{-3}}}$ $\displaystyle=$
$\displaystyle 2\cdot\left(\frac{2\cdot\gamma_{7}\cdot z^{2}\cdot
k\cdot\log\|P\|_{0}\cdot 2^{2h}\cdot\log\frac{\alpha}{\varepsilon^{-3}}\cdot
2^{\beta_{1}z\log z}2^{-2h}\cdot\min(\varepsilon^{-z},k)}{2^{\gamma_{4}\cdot
z\log(1+z)}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k))}\right)^{1/2}$
$\displaystyle\leq$ $\displaystyle\beta\cdot\frac{\varepsilon}{\log
1/\varepsilon},$

where the final inequality holds for a sufficiently large choice of the
constants $\gamma_{4}$.

We now assume that $h\geq t$. This time, using Lemma 22, we have a net of size
at most $|\mathbb{N}_{h}|\leq\exp\left(\gamma_{8}\cdot k\cdot d\cdot
z\log(4z/(2^{-h}\varepsilon))\right)$. Furthermore, using the assumption that
the points lie in dimension $\log\|P\|_{0}\cdot\varepsilon^{-2}\in O(\log
k/\varepsilon)\cdot\varepsilon^{-2}$, we have

$\displaystyle\mathbb{E}[\sup_{\mathcal{S}}|X_{G,\mathcal{S},h}|~{}|~{}\mathcal{E}_{G}]$
(18) $\displaystyle\leq$ $\displaystyle
2\sqrt{\textbf{Var}[X_{G,\mathcal{S},h}~{}|~{}\mathcal{E}_{G}]}\sqrt{2\ln(|\mathbb{N}_{h-1}|\cdot|\mathbb{N}_{h}|)}$
$\displaystyle\leq$ $\displaystyle 2\cdot\left(\frac{2\cdot\gamma_{8}\cdot
k\cdot d\cdot z\log(4z/(2^{-h}\varepsilon))\cdot\beta_{3}\cdot
2^{\beta_{4}z\log z}2^{-2h}\cdot\min(\varepsilon^{-z},k)}{2^{\gamma_{4}\cdot
z\log(1+z)}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k))}\right)^{1/2}$
$\displaystyle\leq$ $\displaystyle 2\cdot\left(\frac{2\cdot\gamma_{8}\cdot
k\cdot\alpha\cdot\|P\|_{0}\varepsilon^{-2}\cdot
z\log(4z/(2^{-h}\varepsilon))\cdot
2^{\beta_{2}z\log(1+z)}2^{-2h}\cdot\min(\varepsilon^{-z},k)}{2^{\gamma_{4}\cdot
z\log(1+z)}\cdot
k\cdot\log\frac{k}{\varepsilon}\cdot\varepsilon^{-2}\cdot\log^{3}\varepsilon^{-1}\cdot\min(\varepsilon^{-z},k))}\right)^{1/2}$
$\displaystyle\leq$ $\displaystyle\beta\cdot\left(\frac{\log
h}{2^{2h}\log^{2}1/\varepsilon}\right)^{1/2},$

where again the final inequality holds for a sufficiently large choice of the
constant $\gamma_{4}$ and with the assumption
$\|P\|_{0}=\text{poly}(k/\varepsilon)$.

Summing up Equations 16 and 18 for all $h$, we then obtain

$\displaystyle\mathbb{E}[\sup_{\mathcal{S}}|X_{\mathcal{S}}|~{}|~{}\mathcal{E}_{G}]$
$\displaystyle\leq$
$\displaystyle\sum_{h=0}^{\infty}\mathbb{E}[\sup_{\mathcal{S}}|X_{h,\mathcal{S}}|~{}|~{}\mathcal{E}_{G}]$
$\displaystyle=$
$\displaystyle\sum_{h=0}^{t-1}\mathbb{E}[\sup_{\mathcal{S}}|X_{h,\mathcal{S}}|~{}|~{}\mathcal{E}_{G}]+\sum_{h=t}^{\infty}\mathbb{E}[\sup_{\mathcal{S}}|X_{h,\mathcal{S}}|~{}|~{}\mathcal{E}_{G}]$
$\displaystyle(\text{Eq. }\ref{eq:chainappl1}~{}\ref{eq:chainappl2})$
$\displaystyle\leq$
$\displaystyle\sum_{h=0}^{t-1}\beta\cdot\frac{\varepsilon}{\log
1/\varepsilon}+\sum_{h=t}^{\infty}\beta\cdot\left(\frac{\log
h}{2^{2h}\log^{2}1/\varepsilon}\right)^{1/2}$ (19)
$\displaystyle\overset{t=\log(\alpha/\varepsilon^{2})}{\leq}$
$\displaystyle\beta\cdot\varepsilon+\beta\cdot\varepsilon\sum_{h=0}^{\infty}\left(\frac{\log(h+t)}{\beta\cdot
2^{2h}\log^{2}1/\varepsilon}\right)^{1/2}\in O(\varepsilon).$

Now, we move onto the case $\overline{\mathcal{E}_{G}}$. Due to Lemma 19, we
have

$\mathbb{P}[\overline{\mathcal{E}_{G}}]\leq k\cdot
z^{2}\log^{2}(z/\varepsilon)\exp(-O(1)\cdot\frac{\varepsilon^{2}}{k}\delta)\leq\varepsilon^{2z},$
(20)

where the second upper bound follows from our choice of sufficiently large
constants in the definition of $\delta$222The bound is not close to tight and
can be any power of $\varepsilon$. The stated bound happens to be sufficient
here.

Using the worse variance bound from Lemma 23 for the variance in equations 16
and 18, we then have for $h\leq t$

$\displaystyle\mathbb{E}[\sup_{\mathcal{S}}|X_{h,\mathcal{S}}|~{}|~{}\overline{\mathcal{E}_{G}}]\leq\beta\frac{\varepsilon}{\log
1/\varepsilon}\cdot\varepsilon^{-z}.$ (21)

and for $h>t$

$\displaystyle\mathbb{E}[\sup_{\mathcal{S}}|X_{h,\mathcal{S}}|~{}|~{}\overline{\mathcal{E}_{G}}]\leq\beta\cdot\left(\frac{\log
h}{2^{2h}\log^{2}1/\varepsilon}\right)^{1/2}\cdot\varepsilon^{-z}.$ (22)

Using an analogous calculation to those in the derivation of Equation 19 using
Equations 21 and 22, we now obtain

$\mathbb{E}[\sup_{\mathcal{S}}|X_{\ell,\mathcal{S}}|~{}|~{}\overline{\mathcal{E}_{G}}]\in
O(\varepsilon^{-z}).$ (23)

Combining Equations 19, 20, and 23, we finally have

$\displaystyle\mathbb{P}_{\Omega}[\mathcal{E}_{G}]\cdot\mathbb{E}_{\xi}[\sup_{\mathcal{S}}X_{\ell,\mathcal{S}}~{}|~{}\mathcal{E}_{G}]+\mathbb{P}_{\Omega}[\overline{\mathcal{E}_{G}}]\cdot\mathbb{E}_{\xi}[\sup_{\mathcal{S}}X_{\ell,\mathcal{S}}~{}|~{}\overline{\mathcal{E}_{G}}]\in
O(\varepsilon+\varepsilon^{2z}\cdot\varepsilon^{-z})=O(\varepsilon).$

∎

We now repeat these calculations for Lemma 18. The main difference is the
variance bound, which improves over what we were able to prove for Lemma 16.
The remaining arguments differ only in the calculations and are omitted.

###### Proof of Lemma 18.

Let $G\in G^{O}$. As for Lemma 18, we bound the random variable

$\displaystyle X_{G,\mathcal{S}}$ $\displaystyle:=$