# The Price of Explainability for Clustering††thanks: Part of this work was
done while visiting the _Data-Driven Decision Processes_ semester program at
the Simons Institute for the Theory of Computing.

Anupam Gupta Carnegie Mellon University<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Madhusudhan Reddy
Pittu22footnotemark: 2 Ola Svensson EPFL, Lausanne<EMAIL_ADDRESS>Rachel Yuan22footnotemark: 2

###### Abstract

Given a set of points in $d$-dimensional space, an explainable clustering is
one where the clusters are specified by a tree of axis-aligned threshold cuts.
Dasgupta et al. (ICML 2020) posed the question of the _price of
explainability_ : the worst-case ratio between the cost of the best
explainable clusterings to that of the best clusterings.

We show that the price of explainability for $k$-medians is at most
$1+H_{k-1}$; in fact, we show that the popular Random Thresholds algorithm has
_exactly_ this price of explainability, matching the known lower bound
constructions. We complement our tight analysis of this particular algorithm
by constructing instances where the price of explainability (using _any_
algorithm) is at least $(1-o(1))\ln k$, showing that our result is best
possible, up to lower-order terms. We also improve the price of explainability
for the $k$-means problem to $O(k\ln\ln k)$ from the previous $O(k\ln k)$,
considerably closing the gap to the lower bounds of $\Omega(k)$.

Finally, we study the algorithmic question of finding the best explainable
clustering: We show that explainable $k$-medians and $k$-means cannot be
approximated better than $O(\ln k)$, under standard complexity-theoretic
conjectures. This essentially settles the approximability of explainable
$k$-medians and leaves open the intriguing possibility to get significantly
better approximation algorithms for $k$-means than its price of
explainability.

##  1 Introduction

Clustering is a central topic in optimization, machine learning, and algorithm
design, with $k$-medians and $k$-means being two of the most prominent
examples. In recent years, mainly motivated by the impressive but still
mysterious advances in machine learning, there has been an increased interest
in the transparency and in the explainability of solutions. In the context of
clustering, this was formalized in a highly influential paper by Dasgupta et
al. [DFMR20].

To motivate the concept of explainability, consider the task of clustering $n$
points in $\mathbb{R}^{d}$ into $k$ clusters. If we solve $k$-means, the
clusters are in general given by a Voronoi diagram where each cluster/cell is
defined by the intersection of hyperplanes. Each cluster may be defined using
up to $k-1$ hyperplanes, each one of them possibly depending on all $d$
dimensions with arbitrary coefficients. Since the dimensions typically
correspond to features (e.g., “age”, “weight”, and “height” are natural
features in a dataset of people), arbitrary linear combinations of these
features may be difficult to interpret. To achieve more explainable solutions,
we may need to restrict our algorithms to find clusters with simpler
descriptions.

The model in [DFMR20] achieves explainability in an elegant way resembling the
classical notion of decision trees in theoretical computer science.
Specifically, a clustering is called _explainable_ if it is given by a
decision tree, where each internal node splits data points with a _threshold
cut_ in a single dimension (feature), and each of the $k$ leaves corresponds
to a unique cluster. This leads to more explainable solutions already in two
dimensions (see, e.g., Figure 1); the benefit is even more clear in higher
dimensions. Indeed, the binary tree structure gives an easy sequential
procedure for classifying points, and since each threshold cut is axis-
aligned, there is no linear combinations of features. Moreover, the total
number of dimensions/features used to describe the clustering is at most
$k-1$, independent of $d$, which is attractive for high-dimensional data111We
remark that dimensionality reduction for $k$-median and $k$-means show that
one can reduce the dimension of the data points to $O(\log(k)/\epsilon^{2})$
[BBC+19, MMR19]. However, those techniques take arbitrary linear combinations
of the original dimensions and therefore destroy explainability..

(a)

(b)

pt$x\leq 4.5$pt$y\leq-4$pt$x\leq-3.5$pt3pt0pt$y\leq 4$pt4pt1pt2

(c)

Figure 1:  Example from [DFMR20]. The optimal $5$-means clustering (left) uses
combinations of both features. The explainable clustering (middle) uses axis-
aligned rectangles summarized by the threshold tree (right).

Explainability is thus a very desirable and appealing property, but the best
explainable clustering may have cost much higher than the cost of the best
unrestricted clusterings. This tradeoff is captured by the _price of
explainability_ : the loss in cost/quality if we restrict ourselves to
explainable clusterings.

In their original paper, Dasgupta et al. [DFMR20] gave a greedy algorithm
which takes an arbitrary “reference” clustering and produces an explainable
clustering from it. It repeatedly adds threshold cuts which separate the
centers of the reference clustering until the threshold tree has one leaf for
each center of the reference clustering. Since only the points separated in
the threshold tree from their closest reference center suffer an increase in
cost, their algorithm repeatedly selects a threshold cut that separates the
fewest points from their closest reference center. They proved that it outputs
an explainable clustering with cost $O(k)$ times higher for the case of
$k$-medians, and $O(k^{2})$ times higher for the case of $k$-means. They also
show a lower bound of $\Omega(\ln k)$ for both of these problems.

Since the greedy algorithm’s analysis is tight, an alternative strategy was
independently proposed by [GJPS21, MS21, EMN22]: take random cuts instead! The
strategy is especially elegant in the case of $k$-medians (the distribution of
cuts is more complex than uniform in the case of $k$-means):

> Repeatedly select threshold cuts _uniformly at random_ among those that
> separate centers of the reference clustering.

We refer to this as the Random Thresholds algorithm (see §2.1 for a formal
description). While the algorithm is easy to describe, its performance
guarantee has remained an intriguing question. There are simple instances in
which it increases the cost by a factor of $1+H_{k-1}$, where
$H_{k-1}=\nicefrac{{1}}{{1}}+\nicefrac{{1}}{{2}}+\nicefrac{{1}}{{3}}+\ldots+\nicefrac{{1}}{{(k-1)}}$
is the $(k-1)^{th}$ harmonic number (see §5), and this was conjectured to be
the worst case for the Random Thresholds algorithm [GJPS21].

On a high level, a difficulty in analyzing the Random Thresholds algorithm is
that it may take prohibitively expensive cuts with a small probability. To
avoid this and other difficulties, the results in [GJPS21, MS21, EMN22]
considered more complex variants that intuitively forbid such expensive cuts.
Specifically, [GJPS21] gave a variant that outputs a threshold tree whose
expected cost increases by at most a $O(\ln^{2}k)$ factor, and both [MS21,
EMN22] obtain a better performance guarantee of $O(\ln k\ln\ln k)$ for their
variants of the Random Thresholds algorithm. These results give an exponential
improvement over that in [DFM22] but fail to settle the price of
explainability, and they leave open the conjectured performance of the natural
Random Thresholds algorithm.

Our main results on the price of explainability are (a) to settle this
conjecture in the affirmative (i.e., to give a _tight_ analysis of the Random
Thresholds algorithm), and (b) to show that its price of explainability of
$1+H_{k-1}=(1+o(1))\ln k$ is not only asymptotically correct, but also _tight
up to lower order terms_ : we cannot do much better regardless of the
algorithm.

######  Theorem 1 (Upper bound for $k$-medians).

The price of explainability for $k$-medians is at most $1+H_{k-1}$.
Specifically, given any reference $k$-medians clustering, the _Random
Thresholds_ algorithm outputs an explainable clustering with expected cost at
most $1+H_{k-1}$ times the cost of the reference clustering.

######  Theorem 2 (Lower Bound for $k$-medians).

There exist instances of $k$-medians for which any explainable clustering has
cost at least $(1-o(1))\ln k$ times the cost of the optimal $k$-medians
clustering.

These results resolve the performance of the Random Thresholds algorithm and
the price of explainability for $k$-medians.

For $k$-means, we are unable to settle the price of explainability completely,
but we make significant progress in closing the gap between known upper and
lower bounds. Here, the best upper bound before our work was $O(k\ln k)$
[EMN22] (see also [CH22] for better guarantees when the input is low-
dimensional). Moreover, we know instances where any single threshold cut
increases the cost of the clustering by a factor $\Omega(k)$ (see, e.g.,
[GJPS21]), and hence the price of explainability of $k$-means is at least
$\Omega(k)$.

It is tempting to guess that the $O(k\ln k)$ guarantee in [EMN22] is tight,
for the following reason. The first lower bound $\Omega(\ln k)$ for $k$-means
in [DFMR20] is obtained by arguing that (i) a single threshold cut increases
the cost by at least that of the reference clustering and (ii) a threshold
tree has height $\Omega(\ln k)$, and so the total cost increases by a constant
$\Omega(\ln k)$ times. Since we have examples where any single cut increases
the cost by $\Omega(k)$, it is reasonable to hope for more complex instances
to combine the two sources of hardness, and lose a $\Omega(k)\cdot\Omega(\ln
k)$ factor. However, we prove that this is _not_ the case and give an improved
upper bound:

######  Theorem 3 (Upper bound for $k$-means).

The price of explainability for $k$-means is at most $O(k\ln\ln k)$.
Specifically, given any reference $k$-means clustering, there exists an
algorithm that outputs an explainable clustering with expected cost at most
$O(k\ln\ln k)$ times the reference cost.

Hence the price of explainability for $k$-means lies between $\Omega(k)$ and
$O(k\ln\ln k)$. We leave the tight answer as an intriguing open problem. In
particular, we conjecture that the lower bound is tight and that it is
achieved by the $k$-means variant of the Random Thresholds algorithm. (The
ideas for $k$-means also extend to $\ell_{p}$ norms for $p\geq 2$; details
will appear in a forthcoming version.)

Our final contribution is to _study the approximability of explainable
clustering_. So far, the literature has mostly focused on settling the price
of explainability [DFMR20, LM21, GJPS21, MS21, EMN22, CH22] and its behavior
in a bi-criteria setting [MS22] where the explainable clustering is allowed to
form more than $k$ clusters. These algorithms give upper bounds on the
approximability of explainable clustering since they are all efficient, and
the cost of an optimal unconstrained clustering is a valid lower bound on the
best explainable one. Recent work of [BFG+22, Lab22] asked the question: _how
well can we approximate the best explainable clustering?_ They showed that the
problem is APX-hard, but left open the question of whether the problem can be
approximated better. Resolving this natural question positively would have the
advantage of finding good explainable clusterings for those instances that do
admit such clusterings, which is often the experience for more practical
instances. Our result shows a surprising hardness for the $k$-medians and
$k$-means problem.

######  Theorem 4 (Approximability).

The explainable $k$-medians and $k$-means problems are hard to approximate
better than $(\nicefrac{{1}}{{2}}-o(1))\ln k$, unless P=NP.

These results show that we cannot approximate $k$-medians much better than its
price of explainability (unless P=NP); the approximability for $k$-means
remains tantalizingly open.

###  1.1 Outline and Technical Overview

##### Upper bounding the performance of the Random Thresholds algorithm.

Our main result is the tight analysis (up to lower order terms) of the price
of explainability for $k$-medians. The upper bound of $1+H_{k-1}=(1+o(1))\ln
k$ is given by a tight analysis of the natural Random Thresholds algorithm. We
now sketch the main ingredients of this analysis. We start with two easy but
useful observations: (i) by linearity of expectations, it is sufficient to
bound the expected cost of a single point, and (ii) by translation, this point
can be assumed to be the origin. We thus reduce the problem to that of
analyzing the expected distance from the origin to the last remaining center
(i.e., the center in the same leaf of the threshold tree as the origin). We
call this process the _Closest Point Process_ and define it formally in §2.

##### Algorithm has no better guarantee than $1+H_{k-1}$.

For this discussion, let us make a simplifying assumption that is _not without
loss of generality_ : the $k$ centers are located on separate axes, so that
center $i$ is at ${\bm{e}}_{i}\cdot d_{i}$, with $d_{1}\leq
d_{2}\leq\ldots\leq d_{k}$, hence the closest center is at a distance $d_{1}$.
As cuts are selected uniformly at random, the first cut removes some center
$i_{1}$ with probability $\nicefrac{{d_{i_{1}}}}{{\sum_{j}d_{j}}}$.
Conditioned on that, the second cut removes center $i_{2}$ with probability
$\nicefrac{{d_{i_{2}}}}{{\sum_{j\neq i_{1}}d_{j}}}$, and so on. In other
words, at each step, a center $i$ is separated from the origin with
probability proportional to its distance $d_{i}$. For the further special case
when $d_{2}=d_{3}=\ldots=d_{k}=D$, the expected distance to the last remaining
center is:

$\displaystyle\Pr[1\mbox{ is last center}]$ $\displaystyle\cdot
d_{1}+\left(1-\Pr[1\mbox{ is last center}]\right)D\leq
d_{1}+\left(1-\Pr[1\mbox{ is last center}]\right)\cdot D$
$\displaystyle\textstyle=d_{1}+\big{(}1-\big{(}1-\frac{d_{1}}{(k-1)D+1}\big{)}\big{(}1-\frac{d_{1}}{(k-2)D+1}\big{)}\cdots\big{(}1-\frac{d_{1}}{D+1}\big{)}\big{)}\cdot
D\,.$

This is an increasing function of $D$ and tends to $(1+H_{k-1})\cdot d_{1}$
when $D/d_{1}\to\infty$, which shows that the Random Thresholds algorithm
cannot be better than the conjectured factor of $1+H_{k-1}$ (see also §5.1 for
a formal description).

##### Inductive argument and reduction to worst-case instances.

But can this special setting really be the worst-case? Perhaps surprisingly,
we prove that this is the case. An inductive argument can help remove the
assumption that $d_{2}=d_{3}=\ldots=d_{k}$: Since $(1+H_{k-1})\cdot d_{1}$ is
the right answer for $k\leq 2$, we can try to proceed inductively on the
number of centers to analyze

$\sum_{i=1}^{k}\Pr[\mbox{first cut removes center
$i$}]\cdot\mathbb{E}[\mbox{expected cost of process with centers
$[k]\setminus\\{i\\}$}]\,.$

Since each sub-instance in the sum has $k-1$ centers, we can use the induction
hypothesis to bound every term except $i=1$ in the sum by $(1+H_{k-2})\cdot
d_{1}$. To bound the cost of the instance with centers $[k]\setminus\\{1\\}$,
we could proceed based on the following natural observation: the farther away
a center is, the smaller probability it has to be the last remaining center,
since it is more likely to be cut/removed at each step). This would mean that
the expected cost of the process with centers $[k]\setminus\\{1\\}$ is at most
$\frac{d_{2}+d_{3}+\ldots+d_{k}}{k-1}$. And substituting, we get that the
expected distance to the last center is at most

$\Pr[\mbox{first cut removes center
$1$}]\cdot\frac{d_{2}+d_{3}+\ldots+d_{k}}{k-1}+\left(1-\Pr[\mbox{first cut
removes center $1$}]\right)(1+H_{k-2})\cdot d_{1}\,,$

which is at most $(1+H_{k-1})\cdot d_{1}$ using that $\Pr[\mbox{first cut
removes center $1$}]=\frac{d_{1}}{d_{1}+d_{2}+\ldots+d_{k}}$.

Several research groups found the above inductive proof for the separate-axis
special case, and it was one of the main motivations for the conjectured
performance of the Random Thresholds algorithm. To prove it for the general
case, it “only” remains to remove the assumption that each center is located
on a separate axis. This assumption, however, turns out to be highly non-
trivial to overcome. One indication of this difficulty is that, in the general
case, there are arbitrary correlations between centers: whether center $i$ is
removed impacts the probability that $j$ is removed. This causes most natural
monotonicity conditions not to hold anymore. For example, when centers are
arbitrarily located, a far center can be more likely to be the last one than a
closer one. We overcome these difficulties in a technical proof that manages
to show that the worst-case is as above. In this proof, we write the points as
a conic combination of cuts, view the cost as a function of this embedding,
and naturally try to bound its derivative. This is where the technical
challenges appear: since the derivative is also not “well-behaved” we define a
better-behaved upper bound called the “pseudo-derivative”, and show that this
pseudo-derivative is maximized when all points are at the same distance $D$
from the origin (even when they are not along separate axes). We then bound
the pseudo-derivative for the non-separate-axis uniform case. This is the
technically most challenging part of the paper, and we present it in §5.

##### A Simpler proof via Competing Exponential Clocks.

Interestingly, we can present not just one but two proofs of the correct
$(1+o(1))\ln k$ bound: we give an alternative simpler proof which takes the
viewpoint of _competing exponential clocks_ (previously used, e.g., for the
multiway cut problem [GHYZ11, BNS18, SV14]). In the separate-axis case, it
boils down to sampling an exponential random variable $Z_{i}$ with rate
$d_{i}$ for each center $i$. Two well-known properties of the exponential
distribution are that (i) the probability that $i$ “rings first” is
proportional to its rate, i.e., $\Pr[Z_{i}\leq\min_{j\neq
i}Z_{j}]=d_{i}/\sum_{j}d_{j}$ and that (ii) the distribution is memoryless
$\Pr[Z_{i}\geq s+t\mid Z_{i}\geq t]=\Pr[Z_{i}\geq s]$. This implies that
taking cuts in the order of the random variables $\\{Z_{i}\\}_{i\in[k]}$
(until one center remains) is identical to the Closest Point Process. We now
analyze the competing exponential clocks as follows. For a center $i\in[k]$
with $i\geq 2$, let $Q_{i}$ be the probability that $i$ is the last center
among the faraway centers $[k]\setminus\\{1\\}$. Conditioning on this, $i$ is
the last center and we pay a distance of $d_{i}$ instead of $d_{1}$ if
$Z_{1}\leq Z_{i}$. Now for the probability of $Z_{1}\leq Z_{i}$ to be
maximized, $Z_{i}$ should be as large as possible _in the event when $i$ is
last among $[k]\setminus\\{1\\}$_. So we can upper bound the contribution of
center $i$ by considering the upper quantile of the exponential distribution
of $Z_{i}$ with total probability mass $Q_{i}$. Now standard calculations show
that the total contribution of center $i$ to the cost is
$d_{1}\left(Q_{i}-Q_{i}\ln(Q_{i})\right)$. We thus get the upper bound

$\underbrace{d_{1}}_{\text{contribution of close center
$1$}}+\underbrace{d_{1}\sum_{i=2}^{k}\left(Q_{i}-Q_{i}\ln(Q_{i})\right)}_{\text{contribution
of far centers}}=d_{1}(2+\ln(k-1))\,,$

where used that the entropy $\sum_{i=2}^{k}-Q_{i}\ln(Q_{i})$ is at most
$\ln(k-1)$. What is particularly nice about this viewpoint is that the
analysis does not use the assumption of centers being on separate axes.
Indeed, we can define exponential random variables for each cut (as we did in
our first proof), and the whole machinery goes through. A small complication
arises due to cuts that separate the closest center $1$ along with other
points from the origin, but we can give a less precise but still tight (up to
lower order terms) bound. Apart from achieving the factor $(1+o(1))\ln k$, the
arguments are also arguably cleaner and easier than even the prior non-tight
analyses of the Random Thresholds algorithm. We present these arguments in §2.

##### Lower-Bounding the Price of Explainability.

Recall that the $\Omega(\ln k)$ on the price of explainability for $k$-medians
[DFMR20] is based on the following idea

  1. 1.

Select $k$ centers uniformly at random from a hypercube $\\{0,1\\}^{d}$, and

  2. 2.

Add a $1$-ball around each center with $d$ points, one per dimension, giving
$dk$ points..

The optimal unconstrained clustering has cost $dk$, so how expensive is the
best explainable clustering? Any pair of centers expect to differ in
$\nicefrac{{d}}{{2}}$ coordinates, and so by concentration, their distance
$\approx d/2$ whp. Furthermore, in a sub-instance with $k^{\prime}$ centers,
any cut separates $k^{\prime}$ points from their closest center, and these
incur cost $\approx d/2$. As the threshold tree has a height of at least
$\log_{2}k$, the total cost of any explainable clustering can now be seen to
be at least $\approx(dk/2)\log_{2}k$. While asymptotically tight, the above
symmetric construction does not lead to stronger lower bounds than
$\frac{1}{2}\log_{2}k$. We instead use an asymmetric construction to achieve
our tight lower bound of $(1-o(1))\ln k$, and it gives us hardness of
approximability too!

  1. 1.

Place a special center at the origin, and take a $1$-ball around it giving $d$
points.

  2. 2.

The remaining centers are located at the characteristic vectors of some
carefully chosen subsets of $\\{1,\ldots,d\\}$, and

  3. 3.

Finally, add many points colocated with the centers which force any good
threshold tree to have one leaf per center.

Now the only way to separate a center from the origin is to employ a threshold
cut along a dimension, which corresponds to an element in the set
corresponding to that center. Our threshold cuts must thus form a _hitting
set_ of the set system corresponding to the non-special centers. Furthermore,
the number of points separated from their closest center is equal to the size
of this hitting set. This tight connection allows us to apply the known
results for the hitting set problem, and we get a $(1-o(1))\ln k$ lower bound
on the price of explainability for $k$-medians. In addition, the connection
together with Feige’s landmark paper [Fei98] implies our hardness of
approximation results. (Interestingly enough, [BFG+22] give a very similar
construction, but with different parameters, which only gives them NP-
hardness.) We remark that the hardness result for $k$-means follows from that
of $k$-medians since all points and centers are located on the hypercube, and
thus the $\ell_{1}$-distances equal the squared $\ell_{2}$-distances. We
present the reduction from hitting set and its implications in §3.

##### Improvements for $k$-means.

Our final result is an $O(k\ln\ln k)$ price of explainability for $k$-means.
We observe that there are two ways to achieve the weaker $O(k\ln k)$ bound.
The first transforms the $k$-means instance into $k$-medians, but this
distorts distances by at most $k$ using the Cauchy-Schwarz inequality; then we
lose another $O(\ln k)$ using our analyses above. Another follows the approach
of [EMN22], of finding cuts that have a good cost-to-balance ratio. Both these
approaches are tight, but we show that they cannot be tight at the same time!
I.e., if we lose a factor of $\Omega(k)$ due to Cauchy-Schwarz, then the cuts
partition the instance into parts that are a constant factor smaller, and the
loss becomes a geometric sum that sums to $O(k)$. A quantitative version of
this tradeoff gives our result; the details appear in §4.

##### Outline.

We present the simpler exponential clocks-based proof for $k$-medians in §2,
followed by the matching hardness in §3. The result for $k$-means is in §4,
followed by the tight $1+H_{k-1}$ bound for $k$-medians in §5.

###  1.2 Further Related Work

We now discuss some of the related results beyond those mentioned above. Some
works consider the effect of the dimension $d$ of the price of explainability.
Laber and Murtinho [LM21] showed an $O(d\ln k)$ price of explainability for
$k$-medians, which was improved by Esfandiari et al. [EMN22] to
$O(\min\\{d\ln^{2}d,\ln k\ln\ln k\\})$. Charikar and Hu [CH22] showed that the
price of explainability is at most $k^{1-2/d}\operatorname{poly}\log k$ for
$k$-means, and a lower bound tight up to poly-logarithmic terms. Esfandiari et
al. [EMN22] also gave a lower bound of $\Omega(d)$ for $k$-medians. Frost et
al. [FMR20] posed the question of getting better guarantees using more than
$k$ clusters; Makarychev and Shan [MS22] showed how to open $(1+\delta)k$
centers and get a guarantee of $O(\nicefrac{{1}}{{\delta}}\cdot\ln^{2}k\ln\ln
k)$ for $k$-means.

The algorithmic problem has received much less attention. Bandyapadhyay et al.
[BFG+22] gave algorithms that find the best $k$-medians and $k$-means
clusterings in time $n^{2d}\cdot(dn)^{O(1)}$. They also showed NP-hardness,
and $W[2]$-hardness of finding the best explainable clustering; interestingly,
their hardness construction is also based on the hitting set problem and is
very similar to ours, but they use a different setting of parameters and hence
only infer an NP-hardness. Laber [Lab22] gave an APX-hardness based on a
reduction from finding vertex covers in triangle-free graphs. Our result
showing a logarithmic hardness essentially settles the question for
$k$-medians.

Both the $k$-medians and $k$-means problems have been studied extensively in
the unconstrained setting (i.e., without the explainability requirement), both
for geometric spaces (see, e.g., [CKM16, FRS16, CEMN22, CKL22]) and general
metric spaces (see, e.g., [CGLS23, BPR+17]). The techniques and algorithms for
those settings seem orthogonal to those used for our problems.

###  1.3 Preliminaries and Notation

Given points
$\mathcal{X}=\\{\bm{x}^{1},\dots,\bm{x}^{n}\\}\subseteq\mathbb{R}^{d}$, a
_clustering_ $\mathcal{C}$ of $\mathcal{X}$ is a partition of $\mathcal{X}$
into _clusters_ $\\{C^{1},\dots,C^{k}\\}$. Each cluster $C^{i}$ is assigned a
center $\boldsymbol{\mu}^{i}$ (giving _distinct_ centers
$\mathcal{U}=\\{\bm{\mu}^{1},\dots,\bm{\mu}^{k}\\}\subseteq\mathbb{R}^{d}$).
Let $\pi(\bm{x})$ be the center $\bm{\mu}^{j}\in\mathcal{U}$ corresponding to
the cluster $C^{j}$ containing $x$, and define the $q$-norm cost of a
clustering $\mathcal{C}$ with centers $\mathcal{U}$ as

$\displaystyle\operatorname{cost}_{q}\left(\pi,\mathcal{U}\right)=\sum_{\bm{x}\in\mathcal{X}}\|\bm{x}-\pi(\bm{x})\|_{q}^{q}.$
(1)

The $k$-medians and $k$-means costs of a clustering are simply the minimum
values for the parameters $q=1$ and $2$, minimized over all possible centers
$\mathcal{U}$.

_Threshold Cuts and Trees._ We call a hyperplane of the form $x_{i}\leq\theta$
a _threshold cut_ , and represent it as $(i,\theta)$. A _threshold tree_ $T$
is a binary tree with each non-leaf node $u$ corresponding to a threshold cut
$(i_{u},\theta_{u})$. Define $B_{u}\subseteq\mathbb{R}^{d}$ as the region
corresponding to node $u\in T$, where $B_{r}:=\mathbb{R}^{d}$ for $r$ being
the root of $T$; if nodes $l(u)$ and $r(u)$ are the left and right children of
node $u$, then

$\displaystyle B_{l(u)}:=B_{u}\cap\\{\bm{x}\mid
x_{i_{u}}\leq\theta_{u}\\}\qquad\text{and}\qquad
B_{r(u)}:=B_{u}\cap\\{\bm{x}\mid x_{i_{u}}>\theta_{u}\\}.$

_Explainable Clusterings._ Given points $\mathcal{X}$ and a threshold tree
$T$, the clustering $\mathcal{C}_{T}$ of $\mathcal{X}$ _explainable_ by the
threshold tree $T$ is the partition of $\mathcal{X}$ induced by the regions
corresponding to leaves in $T$, i.e., each leaf $\ell$ of $T$ generates a
cluster $C^{\ell}:=\mathcal{X}\cap B_{\ell}$ of $\mathcal{C}_{T}$. A
clustering $\mathcal{C}$ of $\mathcal{X}$ is said to be an _explainable
clustering_ if there exists a threshold tree $T$ such that
$\mathcal{C}=\mathcal{C}_{T}$.

For a set of centers $\mathcal{U}$, a threshold tree $T$ _separates_
$\mathcal{U}$ if each of the regions corresponding to leaves in $T$ contains
exactly one center in $\mathcal{U}$. Let $\mu^{\ell}$ denote the unique center
in the singleton set $\mathcal{U}\cap\cal B_{\ell}$ for leaf $\ell$ in $T$.
For any set of points $\mathcal{X}$, centers $\mathcal{U}$, and a threshold
tree $T$ that separates $\mathcal{U}$, each leaf in $T$ corresponds to a
cluster $C^{\ell}$ in the clustering $\mathcal{C}_{T}$, and also to a center
$\mu^{\ell}$. Such a tree induces an assignment
$\pi_{T}:\mathcal{X}\to\mathcal{U}$ from points to centers. With this, we can
define

$\displaystyle\operatorname{cost}_{q}\left(T\right)=\operatorname{cost}_{q}(\pi_{T},\mathcal{U})=\sum_{\bm{x}\in\mathcal{X}}\|\bm{x}-\pi_{T}(\bm{x})\|_{q}^{q}.$
(2)

##  2 Explainable $k$-medians via Exponential Clocks

We now give a bound of $(1+o(1))\,\ln k$ on the price of explainability for
$k$-medians. This is slightly weaker than the bound of $1+H_{k-1}\approx\ln
k+O(1)$ promised in Theorem 1, but the proof is simpler and more illuminating.
(We give the proof of the tight bound in §5.)

###  2.1 The Random Threshold Algorithm and the Closest Point Process

Let us first formalize the Random Thresholds algorithm: given a reference
clustering for point set $\mathcal{X}$ which opens centers $\mathcal{U}$ and
maps the data points to centers using $\pi:\mathcal{X}\to\mathcal{U}$, we
construct a threshold tree $T$ randomly as follows. For simplicity, let
$\mathcal{X}\subseteq[a,b]^{d}$ for some $a,b\in\mathbb{R}$. We start with the
trivial threshold tree with the root corresponding to all of $\mathbb{R}^{d}$.
Now while the leaves of $T$ do not give us a separating partition for
$\mathcal{U}$, we pick a dimension $i\in[d]$ and a value $\theta\in[a,b]$
independently and uniformly at random. For each leaf $u$ of $T$, if this
threshold cut separates at least one pair of centers which share the region
$B_{u}$, partition the leaf using the threshold cut. It is easy to see that as
long as all the centers in $\mathcal{U}$ are distinct, this process outputs a
threshold tree that separates $\mathcal{U}$. The main question is: what is the
cost of the resulting explainable clustering $\mathcal{C}_{T}$, in
expectation?

Since the algorithm does not depend on the data points $\mathcal{X}$, and it
is invariant under translations and scaling, we can use linearity of
expectations and focus on the following simpler problem:

######  Definition 5 (Closest Point Process).

Given a set of $k$ points $U\subseteq\mathbb{R}^{d}$, let
$\bm{p}^{*}:=\arg\min_{\bm{p}\in U}\|\bm{p}\|_{1}$ be the point in $U$ closest
to the origin. Assume $\|\bm{p}^{*}\|_{1}=1$. Run the Random Thresholds
algorithm to create a random threshold tree $T$ that separates this point set
$U$. Consider leaf node $u\in T$ whose corresponding region
$B_{u}\subseteq\mathbb{R}^{d}$ contains the origin, and let $\widehat{\bm{p}}$
be the unique point of $U$ in this region $B_{u}$. Define

$\displaystyle f(U):=\mathbb{E}[\;\|\widehat{\bm{p}}\|_{1}\;].$ (3)

Finally, define $\alpha(k):=\max_{U:|U|=k}f(U)$.

######  Lemma 6 (Focus on Closest Point).

Given a reference clustering $\pi:\mathcal{X}\to\mathcal{U}$, the expected
cost of the explainable clustering produced by the Random Thresholds algorithm
is

$\mathbb{E}[\operatorname{cost}(\pi_{T},\mathcal{U})]\leq\alpha(|\mathcal{U}|)\cdot\operatorname{cost}(\pi,\mathcal{U})\,.$

Therefore, the price of explainability is at most $\alpha(k)$.

Given this reduction (which we prove in Appendix A), the main result of this
section is:

######  Theorem 7 (Exponential Clocks).

For any set $U$ with $k$ points, $f(U)\leq(1+o(1))\,\ln k$.

###  2.2 The Exponential Clocks Viewpoint: the Last Point

We now focus on bounding the value $f(U)$ for any point set
$U\in\mathbb{R}^{d}$. We first impose some structure, just for the sake of
analysis. Since $\ell_{1}$ metrics can be written as a non-negative sum of cut
metrics (see, e.g., [DL97]), again using the data-obliviousness and
translation-invariance of the algorithm we can assume the following without
loss of generality (see Section A.1).

  1. 1.

there are $d=2^{k}$ dimensions (one for each subset $S\subseteq U$ of the
points), and

  2. 2.

the instance is specified by non-negative values $\\{z_{S}\\}_{S\subseteq U}$
such that for each point $\bm{p}\in U$, it lies at location

$\bm{p}_{S}:=z_{S}\mathbf{1}(\bm{p}\in S).$

Hence the distance of a point $\bm{p}$ is
$\|\bm{p}\|_{1}=\sum_{S}z_{S}\mathbf{1}(\bm{p}\in S)=\sum_{S:\bm{p}\in
S}z_{S}$.

Given this structure and the focus on $f(U)$, we need to analyze the following
process:

> _The Last Point Process._ Start with some set $V\subseteq U$, and empty
> sequence $\mathcal{S}\leftarrow\langle\rangle$. At each step, pick a set
> $S\not\in\mathcal{S}$ with probability
> $\frac{z_{S}}{\sum_{T\not\in\mathcal{S}}z_{T}}$ and add it to the end of
> $\mathcal{S}$. If $|V\setminus S|\neq\emptyset$, set $V\leftarrow V\setminus
> S$. When all remaining sets $S\not\in\mathcal{S}$ have $z_{S}=0$, stop and
> output the current $V$, a singleton set we call $V_{\text{final}}$.

An inductive argument shows that if we start with $V=U$, the final set
$V_{\text{final}}$ has the same distribution as the set of points in the
region containing the origin in the Random Thresholds algorithm. Specifically,
the first cut is taken with probability
$\frac{z_{S}}{\sum_{T\not\in\mathcal{S}}z_{T}}$ and the process inductively
proceeds; the process is thus identical to the Closest Point Process, and so
$V_{\text{final}}$ contains a single point $\widehat{\bm{p}}\in U$ when the
process stops with $f(U)=\mathbb{E}[\|\widehat{\bm{p}}\|_{1}]$.

To analyze this, we change the perspective slightly further, and recast the
process in terms of “exponential clocks”. Define independent exponential
random variables $X_{S}\sim\exp(z_{S})$ for each set $S\subseteq 2^{U}$ such
that $z_{S}>0$. Since exponential random variables
$\\{Y_{i}\sim\exp(r_{i})\\}$ have the memorylessness property, and the
property that $\Pr[Y_{j}=\min_{i}\\{Y_{i}\\}]=\frac{r_{j}}{\sum_{i}r_{i}}$, we
see the sets in the same order $\mathcal{S}$ as in the last-center process
above. Moreover, this order depends only on the set $U$, and is independent of
the starting set $V\subseteq U$.

Now consider the Last Point Process starting with different sets $V\subseteq
U$ (and not just the entire point set $U$): naturally, the identity of the
final point $\widehat{\bm{p}}$ changes. However, it turns out we can make the
following claim. Define the event _point $\bm{p}\in U$ is last in $V$_ if
starting with the set $V$ results in $V_{\text{final}}=\\{\bm{p}\\}$. It turns
out that being last in this process has a nice “monotone” property. (We defer
the proof to Section A.2.)

######  Lemma 8 (Monotonicity).

For any sets $T,V$ such that $T\subseteq V$, and any point $\bm{p}\in
V\setminus T$, we have

$\displaystyle\textnormal{``$\bm{p}$ is last in
$V$''}\Rightarrow\textnormal{``$\bm{p}$ is last in $V\backslash T$''}.$

###  2.3 Bounding the Expected Cost

By the definition of our process, we know that

$\displaystyle f(U)$ $\displaystyle=\sum_{\bm{p}\in
U}\|\bm{p}\|_{1}\cdot\Pr[\textnormal{$\bm{p}$ is last in
$U$}]\leq\gamma+\sum_{\bm{p}:\|\bm{p}\|_{1}>\gamma}\|\bm{p}\|_{1}\cdot\Pr[\textnormal{$\bm{p}$
is last in $U$}]$ (4)

for any $\gamma$. (We choose $\gamma>1$, which ensures that
$\bm{p}\neq\bm{p}^{*}$.) We now bound (4) as follows. Observe that whenever
$\bm{p}$ is last in $U$, the following is true. There must exist a cut $T$
that removes the closest point $\bm{p}^{*}$ before any cut removes $\bm{p}$,
i.e., $\bm{p}^{*}\in T,\bm{p}\notin T$. This implies $X_{T}\leq X_{S}$ for all
sets $S$ such that $\bm{p}\in S,\bm{p}^{*}\notin S$, which can be written as

$X_{T}\leq X_{\bm{p}}\mbox{, where }X_{\bm{p}}:=\min_{S:\bm{p}\in
S,\bm{p}^{*}\notin S}X_{S}\,.$

Second, by the Monotonicity Lemma 8, we have that $\bm{p}$ is last in $U$
implies that $\bm{p}$ is last in $U\backslash T$. Defining
$\mathcal{F}_{\bm{p}}:=\\{T\mid\bm{p}^{*}\in T,\bm{p}\not\in T\\}$ to be all
those cuts that could remove $\bm{p}^{*}$ before $\bm{p}$, therefore yields
the upper bound

$\displaystyle f(U)$
$\displaystyle\leq\gamma+\sum_{\bm{p}:\|\bm{p}\|_{1}>\gamma}\|\bm{p}\|_{1}\cdot\Pr[\exists
T\in\mathcal{F}_{\bm{p}}\textnormal{ such that }X_{T}\leq
X_{\bm{p}}\bigwedge\bm{p}\textnormal{ is last in }U\backslash T]$
$\displaystyle\leq\gamma+\sum_{\bm{p}:\|\bm{p}\|_{1}>\gamma}\|\bm{p}\|_{1}\sum_{T\in\mathcal{F}_{\bm{p}}}\Pr[X_{T}\leq
X_{\bm{p}}\bigwedge\bm{p}\textnormal{ is last in }U\backslash T]\,.$ (union
bound)

We upper bound the contribution of a fixed point $\bm{p}$ to the above
expression. By the law of total probability, $\Pr[X_{T}\leq
X_{\bm{p}}\bigwedge\bm{p}\textnormal{ is last in }U\backslash T]$ equals

$\displaystyle\int_{-\infty}^{\infty}\Pr[X_{T}\leq
t\bigwedge\bm{p}\textnormal{ is last in }U\backslash T\mid
X_{p}=t]f_{X_{p}}(t)dt\,,$ (5)

where $f_{X_{p}}(t)$ denotes the probability density function of $X_{p}$. The
event $X_{T}\leq t$ is independent from the event “$\bm{p}$ is last in
$U\backslash T$” because, $T$ does not cut any points in $U\backslash T$ and
hence the value of $X_{T}$ is irrelevant to the process restricted to points
in $U\backslash T$. We also know that $X_{T}$ and $X_{\bm{p}}$ are
independent. These observations can be used to rewrite the above expression as

$\displaystyle\int_{-\infty}^{\infty}\Pr[X_{T}\leq
t]\cdot\Pr[\bm{p}\textnormal{ is last in }U\backslash T\mid
X_{p}=t]f_{X_{p}}(t)dt\,.$ (6)

As $\Pr[X_{T}\leq t]$ is an increasing function of $t$, the above expression
is maximized if the probability mass of the event “$\bm{p}$ is last in
$U\backslash T$” is on large values of $t$. Formally, if we select
$\boldsymbol{\tau}$ to be threshold so that

$\displaystyle\int_{-\infty}^{\infty}\Pr[\bm{p}\textnormal{ is last in
}U\backslash T\mid
X_{p}=t]f_{X_{p}}(t)dt=\int_{-\infty}^{\infty}\mathbf{1}[t\geq\boldsymbol{\tau}]f_{X_{p}}(t)dt=\int_{\boldsymbol{\tau}}^{\infty}f_{X_{p}}(t)dt$
(7)

then (6) is upper bounded by

$\displaystyle\int_{\boldsymbol{\tau}}^{\infty}\Pr[X_{T}\leq
t]f_{X_{p}}(t)dt\,.$ (8)

To understand this expression, recall that $X_{T}$ is an exponential random
variable with rate $z_{T}$. Further, the random variable $X_{p}$ is the
minimum of exponentials, and hence is itself exponentially distributed with
rate ${\ell}(\bm{p})=\sum_{S:\bm{p}\in S,\bm{p}^{*}\not\in S}z_{S}$. In other
words, $\Pr[X_{T}\leq t]=1-e^{-z_{T}\cdot t}$ and
$f_{X_{p}}(t)={\ell}(\bm{p})e^{-{\ell}(\bm{p})t}$ for $t\geq 0$. This gives us
that the choice of $\boldsymbol{\tau}$ that satisfies the identity (7) is

$\boldsymbol{\tau}=\frac{-\ln Q_{T}(\bm{p})}{{\ell}(\bm{p})},\mbox{ where
$Q_{T}(\bm{p})$ is the probability that $\bm{p}$ is last in $U\backslash T$.}$

The integral (8) can be upper-bounded by standard calculations:

$\displaystyle\int_{\boldsymbol{\tau}}^{\infty}\Pr[X_{T}\leq t]f_{X_{p}}(t)dt$
$\displaystyle=\int_{\boldsymbol{\tau}}^{\infty}(1-e^{-z_{T}t})\cdot{\ell}(\bm{p})\cdot
e^{-{\ell}(\bm{p})t}dt$
$\displaystyle=Q_{T}(\bm{p})-\frac{{\ell}(\bm{p})}{{\ell}(\bm{p})+z_{T}}e^{-({\ell}(\bm{p})+z_{T})\cdot\boldsymbol{\tau}}$
$\displaystyle\leq
Q_{T}(\bm{p})\left(1-\frac{{\ell}(\bm{p})}{{\ell}(\bm{p})+z_{T}}\cdot\left(1+\frac{z_{T}\ln
Q_{T}(\bm{p})}{{\ell}(\bm{p})}\right)\right)$
$\displaystyle=Q_{T}(\bm{p})\cdot z_{T}\left(\frac{1-\ln
Q_{T}(\bm{p})}{{\ell}(\bm{p})+z_{T}}\right).$

Substituting in this upper bound, we have

$\displaystyle f(U)$
$\displaystyle\leq\gamma+\sum_{\bm{p}:\|\bm{p}\|_{1}>\gamma}\|\bm{p}\|_{1}\sum_{T\in\mathcal{F}_{\bm{p}}}Q_{T}(\bm{p})\cdot
z_{T}\left(\frac{1-\ln Q_{T}(\bm{p})}{{\ell}(\bm{p})+z_{T}}\right)$
$\displaystyle\leq\gamma+\sum_{\bm{p}:\|\bm{p}\|_{1}>\gamma}\frac{\|\bm{p}\|_{1}}{\|\bm{p}\|_{1}-1}\sum_{T\in\mathcal{F}_{\bm{p}}}Q_{T}(\bm{p})\cdot
z_{T}\left({1-\ln Q_{T}(\bm{p})}\right),$ where we use that
${\ell}(\bm{p})+z_{T}\geq\|\bm{p}\|_{1}-1$. Indeed
${\ell}(\bm{p})=\sum_{S:\bm{p}\in S,\bm{p}^{*}\not\in
S}z_{S}\geq\|\bm{p}\|_{1}-\|\bm{p}^{*}\|_{1}\geq\|\bm{p}\|_{1}-1$. Using the
fact that $\nicefrac{{x}}{{x-1}}$ is a decreasing function and then replacing
the summation over all $\bm{p}:\|\bm{p}\|_{1}>\gamma$ to all
$\bm{p}\neq\bm{p}^{*}$, and exchanging the summations gives
$\displaystyle\leq\gamma+\frac{\gamma}{\gamma-1}\sum_{T\ni\bm{p}^{*}}z_{T}\sum_{\bm{p}\in
U\backslash T}Q_{T}(\bm{p})(1-\ln Q_{T}(\bm{p})).$

Observe that for any cut $T$, we have $\sum_{\bm{p}\in U\setminus
T}Q_{T}(\bm{p})=1$, and the sum is over at most $k-1$ points. As the entropy
$\sum_{\bm{p}\in U\backslash T}Q_{T}(\bm{p})(-\ln Q_{T}(\bm{p}))$ of
$|U\backslash T|\leq k-1$ outcomes is at most $\ln(k-1)$, the inner sum is at
most $1+\ln(k-1)$. Finally, using that
$\sum_{T\ni\bm{p}^{*}}z_{T}=\|\bm{p}^{*}\|_{1}=1$, we get

$\displaystyle f(U)$
$\displaystyle\leq\gamma+\frac{\gamma}{\gamma-1}(1+\ln(k-1))\leq\ln(k-1)+2\sqrt{1+\ln(k-1)}+2$

by optimizing over $\gamma$. This proves Theorem 7, and gives us an
asymptotically optimal bound on the price of explainability. In the next
section we show that the bound is, in fact, tight up to lower-order terms.

##  3 Lower Bounds on the Price of Explainability

In this section, we prove a tight lower bound on the price of explainability
(up to lower order terms), and a lower bound on the approximability of
explainable clustering. Both results are obtained via a reduction from the
classic _hitting set problem_ : given a set system $([d],\mathcal{S})$, where
$[d]=\\{1,\ldots,d\\}$ denotes the ground set and
$\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{k}\\}$ is a family of $k$ subsets of
$[d]$, the task is to find the smallest subset $H\subseteq[d]$ that hits every
subset in $\mathcal{S}$, i.e., $H\cap S_{i}\neq\emptyset$ for all
$S_{i}\in\mathcal{S}$. We further say that a hitting set instance
$([d],\mathcal{S})$ is _$s$ -uniform if all subsets of $\mathcal{S}$ are of
the same size $s$_. We now first present the reduction from $s$-uniform
hitting set instances to explainable clustering, and we then analyze its
implications.

##### Reducing hitting set to explainable clustering.

Given an $s$-uniform hitting set instance
$([d],\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{k}\\})$, define the following data
set $\mathcal{X}$ in $\\{0,1\\}^{d}$ and reference solution $\mathcal{U}$:

  1. 1.

The reference clustering has $k+1$ centers
$\mathcal{U}:=\\{\boldsymbol{\mu}_{0},\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{k}\\}$,
where $\boldsymbol{\mu}_{0}$ is at the origin, and each other
$\boldsymbol{\mu}_{i}\in\\{0,1\\}^{d}$ is the characteristic vector of the set
$S_{i}$.

  2. 2.

The data set $\mathcal{X}$ consists of one point at each of the locations
$\\{\mathbf{e}_{i}\\}_{i\in[d]}$, and
$M=\operatorname{poly}(d,k)\gg\max\\{d,k\\}$ “colocated” points at each of the
$k+1$ locations in $\mathcal{U}$, giving $|\mathcal{X}|=d+M\cdot(k+1)$.

The cost of this reference clustering $\mathcal{U}$ with $k+1$ centers is at
most $d$, since all the $d$ non-colocated points can be assigned to the center
$\boldsymbol{\mu}_{0}$. We proceed to analyze the cost of an optimal
_explainable_ clustering with $k+1$ centers.

######  Lemma 9.

Let $h$ be the size of an optimal solution to the hitting set instance
$([d],\mathcal{S})$ and let OPT be the cost of an optimal $(k+1)$-median
explainable clustering of the data set $\mathcal{X}$. Then

$d+h(s-2-o(1))\leq\text{OPT}\leq d+h(s-2)\,.$

Moreover, the same bounds hold for the optimal $(k+1)$-means explainable
clustering.

###### Proof.

We present the proof for $(k+1)$-median and then observe that all the distance
calculations also hold for $(k+1)$-means since all the points of $\mathcal{X}$
have binary coordinates and, as we will show, the centers will be (arbitrarily
close) to such coordinates as well. Note that
$\|\mathbf{p}-\mathbf{q}\|_{1}=\|\mathbf{p}-\mathbf{q}\|_{2}^{2}$ if
$\mathbf{p},\mathbf{q}\in\\{0,1\\}^{d}$. We now proceed with the analysis for
$(k+1)$-median.

The $M$ points colocated with each of the reference centers
$\boldsymbol{\mu}_{i}$ ensure that the best explainable clustering separates
each of the centers $\boldsymbol{\mu}_{i}$. Separating a center
$\boldsymbol{\mu}_{i}$ from $\boldsymbol{\mu}_{0}$ using a threshold cut means
choosing some dimension $j\in S_{i}$ and a value $\theta\in(0,1)$, which in
turn also separates the data point ${\bm{e}}_{j}$ from $\boldsymbol{\mu}_{0}$.
Since $M\gg k$, the center for the final cluster containing ${\bm{e}}_{j}$ is
located at some location very close the reference center in it, and hence this
data point now incurs cost $s-(1+o(1)))$ instead of $1$. Here we used the fact
that each set has size $s$ and the term $o(1)$ accounts for the potential
small difference in the locations of the centers in the explainable clustering
compared to those in the reference clustering. The above observations imply
that

  * •

the collection of threshold cuts that separate $\boldsymbol{\mu}_{0}$ from
other centers must form a hitting set for the set system $([k],\mathcal{S})$;
and

  * •

if this hitting set has size $h^{\prime}$, the cost of the explainable
clustering is at least
$h^{\prime}(s-(1+o(1))+(d-h^{\prime})=d+h^{\prime}(s-2-o(1))$.

We thus have $\text{OPT}\geq d+h(s-2-o(1))$ since $h$ is the smallest size of
a hitting set.

For the upper bound $\text{OPT}\leq d+h(s-2)$, let
$H=\\{i_{1},i_{2},\ldots,i_{h}\\}\subseteq[d]$ be an optimal hitting set of
size $h$. Starting with the reference clustering $\mathcal{U}$, build a
threshold tree by adding the threshold cuts along dimensions
$i_{1},i_{2},\ldots,i_{h}$ with thresholds $1/2$. Specifically, the cut along
dimension $i_{1}$ is at the root of the tree and the remaining cuts are
recursively added to the subinstance that contain the reference center
$\boldsymbol{\mu}_{0}$. After adding these cuts we have separated
$\boldsymbol{\mu}_{0}$ from all other centers, since $H$ is a hitting set.
Furthermore, the only points in $\mathcal{X}$ that are separated from their
closest center in $\mathcal{U}$ are
${\bm{e}}_{i_{1}},{\bm{e}}_{i_{2}},\ldots,{\bm{e}}_{i_{h}}$. Note that the
tree may still contain centers $\boldsymbol{\mu}_{i},\boldsymbol{\mu}_{j}$
with $i,j\geq 1$ that are yet not separated. But they can be separated without
incurring any additional cost since, in their subinstance, all points of
$\mathcal{X}$ are colocated with the centers (or have already been separated
from their closest center $\boldsymbol{\mu}_{0}$). Hence, we can build a
threshold tree that has one leaf per center in $\mathcal{U}$ and the only
points of $\mathcal{X}$ that are separated from their closest center are
${\bm{e}}_{i_{1}},{\bm{e}}_{i_{2}},\ldots,{\bm{e}}_{i_{h}}$. Each of these
separated points ${\bm{e}}_{i_{j}}$ has cost at most $s-1$ instead of $1$
since the hitting set instance was $s$-uniform and the final center
$\boldsymbol{\mu}_{q}$ that ${\bm{e}}_{i_{j}}$ is assigned to correspond to a
set $S_{q}$ that contains $i_{j}$, and so
$\|{\bm{e}}_{i_{j}}-\boldsymbol{\mu}_{q}\|_{1}=s-1$. Hence, the total cost of
the clustering is at most $h\cdot(s-1)+d-h=d+h(s-2)$, which completes the
proof of the lemma. ∎

Having described our reduction, we now proceed to its implications.

##### Price of explainability for $k$-median.

As aforementioned, the cost of the reference clustering $\mathcal{U}$ is at
most $d$. Furthermore, Lemma 9 says that the optimal $(k+1)$-median
explainable clustering costs at least $h(s-2-o(1))+d$, where $h$ is the size
of an optimal hitting set of $([d],\mathcal{S})$. It thus suffices to
construct a set system $\mathcal{S}$ having large $h(s-2-o(1))\approx hs$. For
example, letting $d=|\mathcal{S}|=k$ and defining $\mathcal{S}$ based on the
Hadamard code would give us $s=k/2$ and a hitting set of size $\log_{2}k$, and
hence a lower bound of $\approx\frac{1}{2}\log_{2}k$. A better guarantee
follows using a probabilistic construction (selecting uniformly at random
sets), whose proof we defer to the appendix.

######  Lemma 10 (Hitting Set Lemma).

For large enough $k$, there exist set systems $([k],\mathcal{S})$ with $k$
sets of size $s$ each, such that the minimum hitting set satisfies
$h(s-2-o(1))/k\geq\ln k-O(\ln\ln k)$.

Combining the above lemma with our reduction shows that the price of
explainability is at least $(1-o(1))\ln k$, giving the proof of Theorem 2. See
2

##### Hardness of approximation

Our reduction from the hitting set problem to explainable clustering
immediately leads to a hardness result as well. Feige, in his landmark paper
[Fei98], proved that it is hard to distinguish whether an $s$-uniform hitting
set instance $([d],\mathcal{S})$ 222We remark that the result in [Fei98] is
stated in the terminology of set cover. The instances constructed there has a
ground set of size $n$ and a family of $m$ subsets. Furthermore, they can be
assumed to be regular: each element is contained in $s$ subsets and each
subset is of size $\ell$. Now in the yes case, there is a set cover so that
each element is covered by exactly one set. By the regularity, this implies
that the set cover has size $n/\ell=m/s$ in the yes case. Here we used that
$n\cdot s=m\cdot\ell$. In the no case however, any set cover is at least a
factor $(1-o(1))\ln n$ larger. Now in the terminology of hitting set, this is
an hitting set instance with $d=m$ elements and a family $\mathcal{S}$ of
$k=n$ many sets, each of size $s$, with the stated yes case and no case.

  * •

_(yes case:)_ has a hitting set of $d/s$ elements; or

  * •

_(no case:)_ any hitting set has size at least $(1-o(1))\ln(k)\cdot d/s$,
where $k=|\mathcal{S}|$.

Here, “hard” means that there is no polynomial-time algorithm can distinguish
between these two cases unless $P=NP$; it was under the stronger assumption in
Feige’s original paper [Fei98] and then subsequently improved to hold under
the weakest possible assumption $P\neq NP$ [DS14, Mos15].

Our reduction runs in polynomial time so the above hardness together with
Lemma 9 implies the following. Assuming $P\neq NP$, there is no polynomial-
time algorithm that, given a data set $\mathcal{X}\subseteq\mathbb{R}^{d}$,
distinguishes whether

  * •

_(yes case:)_ there is an explainable clustering with $k+1$ clusters of cost
at most $2d$; or

  * •

_(no case:)_ any such clustering has cost at least $(1-o(1))\ln(k)d$.

As any approximation algorithm with better guarantee than
$(\nicefrac{{1}}{{2}}-o(1))\ln(k)$ would allow us to distinguish between the
two cases, we have the following hardness of approximation result for
explainable clustering. See 4

The above hardness result settles the approximability of explainable
$k$-medians up to small constants: it is the same as its price of
explainability! For $k$-means, the situation is different. Our hardness of
approximation result is far from the lower bound $\Omega(k$) on its price of
explainability. We conjecture that there is no such hardness result matching
$\Omega(k)$ and, in contrast to $k$-medians, that there are significantly
better approximation algorithms for explainable $k$-means than its price of
explainability.

##  4 Explainable $k$-means clustering

We now prove our improved bound on the price of explainability of the
$k$-means problem, which improves on the previous bound of $O(k\ln k)$. Our
main result is the following:

######  Theorem 11.

Given a data set $\mathcal{X}$ and a base clustering with centers
$\mathcal{U}$ and map $\pi$, we can output a random threshold tree $T$
separating $\mathcal{U}$ such that

$\displaystyle\mathbb{E}[\operatorname{cost}_{2}(T)]\leq O(k\ln\ln
k)\cdot\operatorname{cost}_{2}(\pi,\mathcal{U}).$

At a high level, the approach is similar to that for $k$-medians: we give an
algorithm to separate a given set of centers, but since we are dealing with
squared Euclidean distances, we choose cuts from a non-uniform distribution
over dimensions and coordinate values. However, since a single cut can
increase the cost by a factor of $\Omega(k)$ we have to be careful not to lose
another factor of $\Omega(\ln k)$ due to the recursion. Here we use a win-win
analysis: we define a quantity called the _stretch_ of a pair of points and
argue that the loss due to a single cut is just the stretch: moreover, we show
that if stretch is large, the recursive problems are relatively balanced and
the loss in the recursion is a geometric sum, adding up to $\approx O(k)$. On
the other hand, if the stretch is low, we lose less-than-the-worst-case in
each round (although we now need to take a collection of “bulk” cuts).

###  4.1 The Closest Point Process Again

Recall that we proved the performance of the Random Thresholds algorithm for
$k$-medians by reducing to the perspective of a single data point and
analyzing the expected increase in its cost. We can also define the closest
point process for any $\ell_{q}$ norm and for any algorithm $\mathcal{A}$
separating point sets $U$ that is invariant under translations and scaling, as
follows:

######  Definition 12 ($\ell_{q}$-Norm Closest Point Process).

Given a set of $k$ points $U\subseteq\mathbb{R}^{d}$, let
${\bm{p}}^{*}:=\arg\min_{\bm{p}\in U}\|\bm{p}\|_{q}$ be the point in $U$
closest to the origin according to the $\ell_{q}$ metric. Assume
$\|\bm{p}^{*}\|_{q}=1$. Run the algorithm $\mathcal{A}$ to create a random
threshold tree $T$ that separates this point set $U$. Consider leaf node $u\in
T$ whose corresponding region $B_{u}\subseteq\mathbb{R}^{d}$ contains the
origin, and let $\widehat{\bm{p}}$ be the unique point of $U$ in this region
$B_{u}$. Define

$\displaystyle
f_{q,\mathcal{A}}(U):=\mathbb{E}[\;\|\widehat{\bm{p}}\|_{q}^{q}\;].$ (9)

Finally, define
$\alpha_{q,\mathcal{A}}(k):=\max\limits_{U:|U|=k}f_{q,\mathcal{A}}(U)$.

A proof identical to that of Lemma 6 shows that the price of explainability
for $\ell_{q}$-norm clustering is at most $\alpha_{q,\mathcal{A}}(k)$. In the
rest of this section, we give some terminology and then an algorithm
$\mathcal{A}$ which separates the input point set $U\subseteq\mathbb{R}^{d}$;
we then bound the resulting value of $f_{q,\mathcal{A}}(U)$.

###  4.2 Terminology

21$x$$y$$v^{4}_{1}$$v^{2}_{1}$$v^{1}_{1}$$v^{3}_{1}$$v^{1}$$v^{4}$$v^{2}$$v^{3}$
Figure 2: Intervals defined by projections.

We use similar terminology as in [GJPS21]. Given a set
$U\subseteq\mathbb{R}^{d}$ of points, and a dimension $i\in[d]$, let
$\ell_{i}:=\min_{v\in U}v_{i}$ and $u_{i}:=\max_{v\in U}v_{i}$ be the leftmost
and rightmost coordinates of points. Given two values $x,y\in\mathbb{R}$, let
$\mathcal{I}_{i}(x,y)$ be the set of consecutive intervals along the $i$-th
dimension delimited by the coordinates $x$ and $y$ themselves and the
projections of points in $U$ that lie between $x$ and $y$. For example,
consider the $2$-dimensional point set $U$ shown in Figure 2 (the same example
was given in [GJPS21]). On the horizontal axis, two coordinate values $x$ and
$y$ are marked along with the projections of the points:
$\mathcal{I}_{1}(x,y)$ consists of the three consecutive intervals
$[x,v^{4}_{1}],[v^{4}_{1},v^{2}_{1}]$, and $[v^{2}_{1},y]$.

By the definition of $\mathcal{I}_{i}(x,y)$, we have
$|x-y|=\sum_{[a,b]\in\mathcal{I}_{i}(x,y)}|b-a|$. Let

$\mathcal{I}_{\operatorname{all}}:=\cup_{i\in[d]}\left\\{(i,[a,b])\mid[a,b]\in\mathcal{I}_{i}(\ell_{i},u_{i})\right\\}$

denote the collection of all dimension-interval pairs which are delimited by
the projections of the points onto the respective dimensions; for brevity,
define $\mathcal{I}_{i}:=\mathcal{I}_{i}(\ell_{i},u_{i})$. Define

$L_{2}:=\sum_{(i,[a,b])\in\mathcal{I}_{\operatorname{all}}}|b-a|^{2}.$

A key definition is that of the _pseudo-distance_ : for points
$\bm{x},\bm{y}\in\mathbb{R}^{d}$, let

$\mathcal{I}(\bm{x},\bm{y})=\bigcup_{i\in[d]}\\{(i,[a,b])\mid[a,b]\in\mathcal{I}_{i}(x_{i},y_{i})\\}.$

We then define the pseudo-distance between $\bm{x}$ and $\bm{y}$ as

$d_{2}(\bm{x},\bm{y})=\sum_{(i,[a,b])\in\mathcal{I}(x,y)}|b-a|^{2}.$

It follows that $\|\bm{x}-\bm{y}\|^{2}_{2}\geq
d_{2}(\bm{x},\bm{y})\geq\frac{1}{|U\cup\\{\bm{x},\bm{y}\\}|-1}\cdot\|\bm{x}-\bm{y}\|_{2}^{2}$.

We define a distribution $D_{2}$ as follows: first select a dimension–interval
pair $(i,[a,b])\in\mathcal{I}_{\operatorname{all}}$ with probability
$|b-a|^{2}/L_{2}$, and then pick $\theta\in[a,b]$ randomly such that the
p.d.f. is

$\displaystyle
P_{a,b}(\theta):=\frac{4}{(b-a)^{2}}\min(\theta-a,b-\theta)\quad=\quad\frac{4}{(b-a)^{2}}\min_{\bm{v}\in
U}\\{|\theta-v_{i}|\\}.$ (10)

Often we refer to the above concepts not for the entire point set $U$ but for
some subset $V\subseteq U$; in those cases we refer to the partition
$\mathcal{I}_{\text{all}}(V)$, the sum $L_{2}(V)$, or the distribution
$D_{2}(V)$, etc. Finally, for subset $V\subseteq U$ of points we define:

  1. (i)

Let $\Delta(V):=\max_{\bm{x},\bm{y}\in V}\|{\bm{x}}-{\bm{y}}\|^{2}$ be the
squared diameter of point set $V$.

  2. (ii)

Call a pair of points $\bm{x},\bm{y}\in V$ _far_ if
$\|\bm{x}-\bm{y}\|_{2}^{2}\geq\Delta(V)/2$, and _close_ if
$\|{\bm{x}}-{\bm{y}}\|_{2}^{2}<\Delta(V)/k^{4}$.

  3. (iii)

Define the _stretch_ of a pair ${\bm{x}},{\bm{y}}\in V$ to be
$s_{{\bm{x}}{\bm{y}}}(V):=\|{\bm{x}}-{\bm{y}}\|_{2}^{2}/d_{2}({\bm{x}},{\bm{y}})$.
Define the _stretch of the set_ $s(V)$ to be the maximum stretch of any _far
pair_ in $V$.

###  4.3 The Algorithm

The process to construct the threshold tree $T$ for $k$-means is slightly more
complex than for $k$-medians: as before we start off with the root
representing the entire point set $\mathbb{R}^{d}$. Now, given a node $v$
representing some box $B_{v}$ (giving us a subset $U_{v}:=U\cap B_{v}$),
define the distribution $D_{2}(v):=D_{2}(U_{v})$. Now consider the stretch
$s(v):=s(U_{v})$ of the set of points.

  1. 1.

_(Solo Cuts)_ If $s(v)\geq\smash{\frac{|U_{v}|}{\ln^{2}|U_{v}|}}$, let
$\bm{p}^{*},\bm{q}^{*}$ be a pair of far points in $U_{v}$ of stretch $s(v)$,
and pick a threshold cut $(i,\theta)\sim D_{2}(v)$, conditioned on separating
the pair $\bm{p}^{*},\bm{q}^{*}$. This partitions the box $B_{v}$ into two
boxes, and recurse on both.

  2. 2.

_(Bulk Cuts)_ Else if $s(v)$ is smaller than the quantity above. In this case,
repeatedly sample cuts from $D_{2}(v)$ conditioned on not separating any close
pairs of points in $U_{v}$, until all pairs of far points in $U_{v}$ are
separated. Apply all these cuts in sequence, partitioning $B_{v}$ into
potentially multiple pieces; recurse on each of them.

The process stops when each leaf of $T$ contains a single point from $U$. For
the analysis below, we consider a _compressed threshold tree_ $T^{\prime}$
which is a tree with branching at least two: if we perform a solo cut at node
$v$, we call it a _solo node_ , and it has two children corresponding to the
two parts obtained by this cut. If we perform bulk cuts at node $v$, it has
potentially multiple children (one for each smaller box obtained by applying
these cuts), and we call it a _bulk node_.

In the following, let $S(T^{\prime})$ and $B(T^{\prime})$ denote the solo and
bulk nodes in $T^{\prime}$. For any node $v\in T^{\prime}$, let
$L_{2}(v):=L_{2}(U_{v})$, and similarly for other parameters defined above.

###  4.4 The Expected Cost Increase

We will bound the cost for the solo cuts and bulk cuts separately. First we
give some preliminary lemmas, then we bound the cost due to bulk cuts, and
finally the cost for solo cuts.

######  Lemma 13 (Separation Probability).

For any subset of points $V\subseteq U$ and a point $\bm{p}\in V$,

$\Pr_{(i,\theta)\sim D_{2}(V)}[(i,\theta)\text{ separates the origin from
}\bm{p}]\leq\frac{2\|\bm{p}\|_{2}^{2}}{L_{2}(V)}\,.$

###### Proof.

The probability that a random cut sampled from $D_{2}(V)$ separates the origin
$\bm{0}$ and $\bm{p}$ is:

$\displaystyle\sum_{i\in[d]}\sum_{[a,b]\in\mathcal{I}_{i}}\frac{(a-b)^{2}}{L_{2}(V)}\int_{a}^{b}P_{a,b}(\theta)\cdot\mathbbm{1}[\theta\text{
is between }0\text{ and }p_{i}]\,d\theta$
$\displaystyle=\frac{4}{L_{2}(V)}\sum_{i\in[d]}\sum_{[a,b]\in\mathcal{I}_{i}}\int_{a}^{b}\min(\theta-a,b-\theta)\cdot\mathbbm{1}[\theta\text{
is between }0\text{ and }p_{i}]\,d\theta$ (11)
$\displaystyle\leq\frac{4}{L_{2}(V)}\sum_{i\in[d]}\sum_{[a,b]\in\mathcal{I}_{i}}\int_{a}^{b}|\theta-
p_{i}|\cdot\mathbbm{1}[\theta\text{ is between }0\text{ and }p_{i}]d\theta$
(12)
$\displaystyle=\frac{4}{L_{2}(V)}\sum_{i\in[d]}\int_{-\infty}^{\infty}|\theta-
p_{i}|\cdot\mathbbm{1}[\theta\text{ is between }0\text{ and
}p_{i}]\,d\theta=\frac{4}{L_{2}(V)}\sum_{i\in[d]}(p_{i})^{2}/2=\frac{2\|\bm{p}\|_{2}^{2}}{L_{2}(V)}.$

Equality (11) and inequality (12) use the expressions for $P_{a,b}(\theta)$
given in (10). ∎

Given a set $V$, suppose we sample cuts from distribution $D_{2}(V)$ with an
added rejection step if the cut separates some pair of points in $V$ whose
distance is at most $\Delta(V)/k^{4}$. Formally, let
$R(V)\subseteq\mathcal{I}_{\text{all}}(V)$ be the subset of intervals which
are contained in projections of close centers in $V$ onto the coordinate axis.
Let

$L_{2}^{\prime}(V):=\sum_{(i,[a,b])\in\mathcal{I}_{\text{all}}(V)\backslash
R(V)}|b-a|^{2}.$

The distribution $D_{2}^{\prime}(V)$ picks an interval $[a,b]$ in
$\mathcal{I}_{\text{all}}^{\prime}(V):=\mathcal{I}_{\text{all}}(V)\backslash
R(V)$ with probability $\frac{(b-a)^{2}}{L_{2}^{\prime}(V)}$ and then a cut is
chosen from this interval with the same distribution as $P_{a,b}(\theta)$.

######  Proposition 14.

For any subset of points $V$, we have $L_{2}^{\prime}(V)\geq L_{2}(V)/2$.

###### Proof.

The sum of squared length of intervals in $R(V)$ is at most the total sum of
squared distance between all pairs of close centers, which is at most

$\displaystyle\binom{|V|}{2}\cdot\frac{\Delta(V)}{k^{4}}\leq\frac{\Delta(V)}{2k^{2}}\leq\frac{L_{2}(V)}{2k}.$

This implies that $L_{2}^{\prime}(V)\geq L_{2}(V)(1-1/2k)\geq\frac{1}{2}\cdot
L_{2}(V)$. ∎

######  Lemma 15 (Expected Number of Cuts).

For any node $V$, the expected number of cuts from $D_{2}^{\prime}(V)$ until
all far pairs in $V$ are separated is at most $24\ln|V|\cdot
s(V)\cdot\frac{L_{2}(V)}{\Delta(V)}$.

###### Proof.

Consider a collection of $M:=3\ln|V|\cdot\frac{4s(V)\cdot
L_{2}(V)}{\Delta(V)}$ cuts sampled from $D_{2}^{\prime}(V)$, and consider two
“far” points $\bm{p},\bm{q}$, i.e., such that
$\|\bm{p}-\bm{q}\|_{2}^{2}>\nicefrac{{\Delta(V)}}{{2}}$. Then, the probability
that any one cut separates the two is at least

$\displaystyle\Pr_{(i,\theta)\sim D^{\prime}_{2}(V)}[\mbox{$(i,\theta)$
separates
$\bm{p},\bm{q}$}]\geq\frac{d_{2}(\bm{p},\bm{q})-\binom{k}{2}\frac{\Delta(V)}{k^{4}}}{L_{2}(V)}$
$\displaystyle\geq\frac{\|\bm{p}-\bm{q}\|_{2}^{2}}{s(V)\cdot
L_{2}(V)}-\frac{\Delta(V)}{2k^{2}\cdot L_{2}(V)}$
$\displaystyle\geq\frac{\Delta(V)}{2s(V)\cdot
L_{2}(V)}-\frac{\Delta(V)}{2k^{2}\cdot L_{2}(V)}$
$\displaystyle\geq\frac{\Delta(V)}{4s(V)\cdot L_{2}(V)}\,.$

The last inequality in the above equation follows using $s(V)\leq k$ and
$k\geq 2$. Hence the probability that the $M$ cuts do not separate some pair
at distance at least $\Delta(V)/2$ can be upper-bound using a union bound by

$\displaystyle{{|V|}\choose 2}\cdot\left(1-\frac{\Delta(V)}{4\cdot s(V)\cdot
L_{2}(V)}\right)^{M}\leq|V|^{2}\left(\frac{1}{e}\right)^{(3\ln|V|)}=1/|V|\,.$

Hence, these $M$ cuts separate all pairs that have squared distance at least
$\Delta(V)/2$ with probability at least $1-1/|V|\geq\nicefrac{{1}}{{2}}$. In
turn, the expected number of cuts is at most $2M$. ∎

We can now start to bound the cost incurred due to bulk cuts.

######  Lemma 16 (Logarithmic Number of Relevant Levels).

For any cut $(i,\theta)$, we have

$\sum_{v\in B(T^{\prime})}\mathbbm{1}_{[\bm{0}\in
B_{v}]}\cdot\mathbbm{1}_{[(i,\theta)\in\operatorname{supp}(D_{2}^{\prime}(v))]}\leq
4\ln k.$

###### Proof.

The bulk nodes in the compressed tree $T^{\prime}$ that correspond to the part
containing the origin $\bm{0}$ lie on a root-leaf path; call these
$v_{1},v_{2},\ldots,v_{\ell}$, with $v_{1}$ closest to the root. Our algorithm
ensures that $\Delta(v_{j})\leq\Delta(v_{j-1})/2$. Consider the lowest integer
$j$ such that $(i,\theta)$ belongs to the support of $D_{2}^{\prime}(v_{j})$,
and let $\bm{p},\bm{q}\in U\cap B_{v_{j}}$ be the closest pair of points in
$B_{v_{j}}$ separated by $(i,\theta)$. The definition of the probability
distribution $D_{2}^{\prime}(v_{j})$ ensures that
$\|\bm{p}-\bm{q}\|_{2}^{2}\geq\Delta(v_{j})/k^{4}$. For $j^{\prime}=j+4\ln
k+1$ we have that $\Delta(v_{j^{\prime}})<\Delta(v_{j})/k^{4}$, and so there
are no pairs of points separated by $(i,\theta)$—implying that this cut will
no longer be in the support of $D_{2}(v_{j^{\prime\prime}})$ for
$j^{\prime\prime}\geq j^{\prime}$. ∎

######  Lemma 17 (Cost for Bulk Cuts).

The expected cost increase due to bulk cuts is at most
$O(k)\cdot\|p^{*}\|_{2}^{2}$.

###### Proof.

Consider a bulk node $v$ in the decision tree created by the algorithm: we
generate a random number of bulk cuts $\mathcal{K}_{v}$ at this node, and each
of these can cause an increase in cost. Let $Y_{t}$ be the following upper
bound on the increase in cost due to the $t^{\text{th}}$ such cut
$(i,\theta)$:

$Y_{t}:=\Delta(v)\cdot\mathbbm{1}_{[(i,\theta)\text{ seps
}\bm{0},\bm{p}^{*}]}\cdot\mathbbm{1}_{[\\{\bm{0},{\bm{p}}^{*}\\}\subseteq
B_{v}]}.$

Moreover, let $N$ be the number of such cuts, then the total expected cost is
$\mathbb{E}[\sum_{t=1}^{N}Y_{t}]$. Since the $Y_{t}$ variables are independent
and $N$ is a stopping time, we can use Wald’s equation to infer that the total
expected cost due to these cuts is $\mathbb{E}[N]\cdot\mathbb{E}[Y_{t}]$.
Taking expectations of the expression for $Y_{t}$ above (with respect to the
distribution $D_{2}^{\prime}(v)$), and using Lemma 15 to bound
$\mathbb{E}[N]$, this is at most

$\bigg{(}O(s(v)\ln|U_{v}|)\cdot\frac{L_{2}(v)}{\Delta(v)}\bigg{)}\cdot\Delta(v)\cdot\sum_{(i,[a,b])\in\mathcal{I}_{\operatorname{all}}^{\prime}(v)}\frac{(b-a)^{2}}{L_{2}^{\prime}(v)}\int_{a}^{b}P_{a,b}(\theta)\cdot\mathbbm{1}_{[(i,\theta)\text{
seps }\bm{0},\bm{p}^{*}]}\cdot\mathbbm{1}_{[\\{\bm{0},\bm{p}^{*}\\}\subseteq
B_{v}]}\,d\theta.$

Using 14, we know that $L_{2}^{\prime}(v)\geq L_{2}(v)/2$, so the above
expression is at most

$O(s(v)\ln|U_{v}|)\cdot\sum_{(i,[a,b])\in\mathcal{I}_{\operatorname{all}}(v)}(b-a)^{2}\int_{a}^{b}P_{a,b}(\theta)\cdot\mathbbm{1}_{[(i,\theta)\text{
seps }\bm{0},\bm{p}^{*}]}\cdot\mathbbm{1}_{[\\{\bm{0},\bm{p}^{*}\\}\subseteq
B_{v}]}\cdot\mathbbm{1}_{[(i,\theta)\in\operatorname{supp}(D_{2}^{\prime}(v))]}\,d\theta.$

Next, we observe that for any dimension $i$, we have

$(b-a)^{2}\cdot P_{a,b}(\theta)\cdot\mathbbm{1}_{[\bm{p}^{*}\in B_{v}]}\leq
4|\theta-\bm{p}_{i}^{*}|.$

Moreover, for each bulk node we have $s(v)\ln|U_{v}|\leq|U_{v}|/\ln|U_{v}|$.
This in turn is at most $k/\ln k$, since the function $\frac{x}{\ln x}$ is
monotone and $|U_{v}|\leq k$. Substituting both these facts, we get

$O(\nicefrac{{k}}{{\ln
k}})\cdot\sum_{i}\int_{-\infty}^{\infty}|\theta-\bm{p}_{i}^{*}|\cdot\mathbbm{1}_{[(i,\theta)\text{
seps }\bm{0},\bm{p}^{*}]}\cdot\mathbbm{1}_{[\bm{0}\in
B_{v}]}\cdot\mathbbm{1}_{[(i,\theta)\in\operatorname{supp}(D_{2}^{\prime}(v))]}\,d\theta.$

Next, we use Lemma 16 to get:

$\sum_{v\in B(T^{\prime})}\mathbbm{1}_{[\bm{0}\in
B_{v}]}\cdot\mathbbm{1}_{[(i,\theta)\in\operatorname{supp}(D_{2}^{\prime}(v))]}\leq
O(\ln k).$

Now summing over all $v$, we get

$O(k)\cdot\sum_{i}\int_{-\infty}^{\infty}|\theta-\bm{p}_{i}^{*}|\cdot\mathbbm{1}_{[(i,\theta)\text{
seps }\bm{0},\bm{p}^{*}]}\,d\theta=O(k)\cdot\|\bm{p}^{*}\|_{2}^{2}.$

This completes the proof. ∎

Finally, we turn our attention to solo cuts. For solo node $v$ let
$\bm{p}_{v},\bm{q}_{v}$ be the two far nodes such that their stretch is at
least $\frac{|U_{v}|}{(\ln|U_{v}|)^{2}}$, and define the distribution
$D_{2}^{\prime\prime}(v)$ to be the distribution $D_{2}(v)$ conditioned on
separating this far pair.

######  Lemma 18 (Ratio for Solo Cuts).

For any solo node $v\in T^{\prime}$,

$\frac{\mathbb{E}_{(i,\theta)\sim D_{2}^{\prime\prime}(v)}[\text{ cost
increase at node $v$ }]}{\mathbb{E}_{(i,\theta)\sim
D_{2}^{\prime\prime}(v)}[\text{ size of smaller child of node $v$ }]}\leq
32\|\bm{p}^{*}\|_{2}^{2}\cdot\left(1+\ln\left(\frac{|U_{v}|}{s(v)}\right)\right).$

###### Proof.

Lemma 13 implies that

$\mathbb{E}_{(i,\theta)\sim D_{2}(v)}[\text{ cost increase
}]\leq\Delta(v)\cdot\frac{2\|\bm{p}^{*}\|_{2}^{2}}{L_{2}(v)}.$

Moreover, the probability of separating $\bm{p}_{v},\bm{q}_{v}$ is at least

$\frac{d_{2}(\bm{p}_{v},\bm{q}_{v}\mid
U_{v})}{L_{2}(v)}\geq\frac{\|\bm{p}-\bm{q}\|_{2}^{2}}{s(v)\cdot
L_{2}(v)}\geq\frac{\Delta(v)}{2\cdot s(v)\cdot L_{2}(v)}\,.$

Since the cost increase is non-negative, we get that

$\displaystyle\mathbb{E}_{(i,\theta)\sim D_{2}^{\prime\prime}(v)}[\text{ cost
increase
}]\leq\Delta(v)\cdot\frac{2\|p^{*}\|_{2}^{2}}{L_{2}(v)}\cdot\frac{2\cdot
s(v)\cdot L_{2}(v)}{\Delta(v)}\leq 4s(v)\cdot\|\bm{p}^{*}\|_{2}^{2}.$ (13)

This bounds the numerator of the desired quantity; for the denominator, we
prove the following claim in Section C.1:

######  Claim 19.

If for a cut $(i,\theta)$, we define $H^{+}:=\\{x\mid x_{i}\geq\theta\\}$ and
$H^{-}=\mathbb{R}^{d}\setminus H^{+}$, then

$\mathbb{E}_{(i,\theta)\sim
D_{2}^{\prime\prime}(v)}\bigg{[}\min\big{(}|U_{v}\cap H^{+}|,|U_{v}\cap
H^{-}|\big{)}\bigg{]}\geq\frac{s(v)}{8(1+\ln(\nicefrac{{|U_{v}|}}{{s(v)}}))}\leavevmode\nobreak\
.$

Using Claim 19 with (13) finishes the proof. ∎

######  Lemma 20 (Cost for Solo Cuts).

For any internal solo node $v\in T^{\prime}$, the expected cost increase due
to solo cuts made in the subtree $T^{\prime}_{v}$ is at most

$32|U_{v}|(1+2\ln\ln|U_{v}|)\cdot\mathbbm{1}_{[\bm{0}\in
B_{v}]}\cdot\|\bm{p}^{*}\|_{2}^{2}.$

###### Proof.

The proof is by induction. The base cases are when node $v$ has $|U_{v}|\leq
3$. For $v$ to be an internal node, $|U_{v}|\in\\{2,3\\}$. If it has two
nodes, then $s(v)=1<\frac{2}{\ln^{2}2}$, and hence $u$ cannot be a solo node.
If we have $3$ points, then the only solo node in the subtree $T^{\prime}_{v}$
is $u$ itself, so it suffices to argue that the expected cost increase due to
this solo cut is at most
$32|U_{v}|(1+2\ln\ln|U_{v}|)\cdot\|\bm{p}^{*}\|_{2}^{2}$. From (13) we know
that the expected cost increase is at most $4s(u)\cdot\|\bm{p}^{*}\|_{2}^{2}$.
Now using $s(u)\leq|U_{v}|$ and $|U_{v}|\leq 3$, we obtain the required bound.

Else consider some node $v$ with $|U_{v}|\geq 4$, and let $\chi(v)$ be the set
of solo nodes whose closest solo ancestor is $v$: it follows that
$\sum_{w\in\chi(v)}|U_{w}|\leq|U_{v}|$. Moreover, suppose the random solo cut
$(i_{v},\theta_{v})\sim D_{2}^{\prime\prime}(v)$ partitions $U_{v}$ into parts
of size at least $\sigma(v)$, then each $|U_{v}|-|U_{w}|\geq\sigma(v)$. Using
the induction hypothesis on each $w\in\chi(v)$, the total expected cost
increase is at most

$\displaystyle\mathbb{E}[\text{ cost increase at $v$
}]+\sum_{w\in\chi(v)}32|U_{w}|(1+2\ln\ln|U_{w}|)\cdot\mathbbm{1}_{[\bm{0}\in
B_{w}]}\cdot\|\bm{p}^{*}\|_{2}^{2}.$ (14)

Since the origin belongs to at most one of the sets $B_{w^{*}}$, the sum
contributes at most

$\displaystyle 32|U_{w^{*}}|(1+2\ln\ln|U_{v}|)\cdot\|\bm{p}^{*}\|_{2}^{2}\leq
32(|U_{v}|-\mathbb{E}[\sigma(v)])(1+2\ln\ln|U_{v}|)\cdot\|\bm{p}^{*}\|_{2}^{2}.$
(15)

(The RHS is non-negative, since $\sigma(v)\leq|U_{v}|$, so the bound holds
even when $\chi(v)=\emptyset$.) Now Lemma 18 implies that the cost at $v$ is
at most

$\mathbb{E}[\sigma(v)]\cdot
32(1+\ln(\nicefrac{{|U_{v}|}}{{s(v)}}))\cdot\|\bm{p}^{*}\|_{2}^{2}.$

Finally, using that $s(v)\geq|U_{v}|/(\ln|U_{v}|)^{2}$ for a solo node, and
summing the two terms, completes the proof. ∎

We can wrap up: Using Lemma 17 and Lemma 20, we know that the expected cost
increase due to all the cuts used to separate the points in $U$ is at most
$O(k\ln\ln k)\cdot\|\bm{p}^{*}\|_{2}^{2}$. If $\widehat{\bm{p}}$ is the unique
point in $U$ in the region $B_{u}$ corresponding to the leaf node $u$ such
that $\bm{0}\in B_{u}$, then the cost is upper bounded by

$\displaystyle\|\widehat{\bm{p}}\|_{2}^{2}\leq
2\cdot\|\widehat{\bm{p}}-\bm{p}^{*}\|_{2}^{2}+2\cdot\|\bm{p}^{*}\|_{2}^{2}$
(16)

using the generalized triangle inequality. Taking expectation on both sides of
Equation 16 and plugging in $\|\bm{p}^{*}\|_{2}^{2}=1$ gives $f_{2}(U)\leq
O(k\ln\ln k)$.

##  5 Tight Bounds for the Random Threshold Algorithm

We now improve the bound of $(1+o(1))\ln k$ from §2.1 to give an exact bound
of $1+H_{k-1}$ for the Random Thresholds algorithm; we first show an example
which achieves this bound, and then give our precise analysis of the
algorithm.

###  5.1 A Lower Bound

Consider an instance in $\mathbb{R}^{k}$ given by a reference clustering
having one “close” center $\boldsymbol{\mu}^{1}=e_{1}$, and $k-1$ “far”
centers $\boldsymbol{\mu}^{i}=M\,e_{i}$ for each $i\in\\{2,\ldots,k\\}$, where
scalar $M\gg 1$. We consider a single data point at the origin. (As always, we
can imagine there being many points colocated with each of the centers.) Let
the expected assignment cost due to the algorithm for the point at the origin
on an instance with $j$ far points be denoted by $g(j)$. Then we get a
recurrence:

$\textstyle g(k)=\frac{1}{M(k-1)+1}\cdot M+\frac{M(k-1)}{M(k-1)+1}\cdot
g(k-1),$

and $g(\bm{0})=1$. As $M\to\infty$, this gives us $g(k)\to 1+H_{k-1}$, as
claimed. In the next section, we will prove a matching upper bound of
$1+H_{k-1}$.

###  5.2 Towards a Matching Upper Bound

Our proof for this case is technical, so the reader may want to keep three
special cases in mind:

  1. 1.

The “axis-aligned” case, inspired by the bad example: the points in $U$ are
$\\{{\bm{p}}_{i}:=d_{i}\bm{e}_{i}\\}$, where $1=d_{1}\leq d_{2}\leq\ldots\leq
d_{k}$,

  2. 2.

the “orthogonal closest-point” case, where the closest point is $\bm{e}_{1}$,
and all other points lie in the orthogonal subspace to it, and

  3. 3.

the “uniform” case, where all points other than the closest are at the same
distance $d\geq 1$.

Many of our proofs become simpler in these special cases, and thinking about
these cases will give us crucial intuition.

We start with a set of points $U\subseteq\mathbb{R}^{d}$, recall that $f(U)$
was defined to be $\mathbb{E}[\|\bf\widehat{p}\|_{1}]$, where $\bf\widehat{p}$
is the unique point in the box containing the origin in the Random Thresholds
algorithm. As in §2.3, assume we have a dimension for each cut $S\subseteq U$,
and point ${\bm{p}}\in U$ has value $z_{S}\mathbbm{1}[{\bm{p}}\in S]\geq 0$ in
this coordinate. Finally defining $\mathcal{C}_{S}$ to be the collection of
sets that cross $S\subseteq U$, we get that for any $S\subseteq U$,

$\displaystyle f(S)=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot f(S\setminus
E)}{\sum_{E\in\mathcal{C}_{S}}z_{E}},\qquad\text{and}\qquad
f(\\{{\bm{p}}\\})=\|{\bm{p}}\|_{1}.$ (17)

Moreover, when $\sum_{E\in\mathcal{C}_{S}}z_{E}=0$, the value of $f(S)=0$. Let
us denote by $\ell({\bm{p}}):=\|{\bm{p}}\|_{1}$ and $\beta_{k-1}:=1+H_{k-1}$.
Using Equation 17, we think of the function $f(U)$ purely as an algebraic
function of the $z_{S}$ values, and our central goal in this section to prove
the following:

######  Theorem 21 (Main Goal).

For any point ${\bm{p}}\in U$, the value
$f(U)\leq\beta_{k-1}\cdot\ell({\bm{p}})$.

Since the ratio $f(U)/\ell({\bm{p}})$ is difficult to argue about, we instead
focus on bounding the derivative $\frac{\partial f(U)}{\partial z_{E}}$ by
$\beta_{k-1}$. The following lemma shows that, by integrating along a path
from the origin to the point ${\bm{p}}$, such a bound on the derivative
suffices: (a formal proof appears in §D)

######  Lemma 22.

For any ${\bm{p}}\in U$, if $\frac{\partial f(U)}{\partial
z_{E}}\leq\beta_{k-1}$ for all $E\subseteq U$ with ${\bm{p}}\in E$, then
$f(U)\leq\beta_{k-1}\cdot\ell({\bm{p}})$.

###  5.3 Bounding the Derivative

We start by taking definition (17) and calculating the derivative
$\frac{\partial f(S)}{\partial z_{T}}$ for the case $|S|\geq 2$:

$\displaystyle\frac{\partial f(S)}{\partial
z_{T}}=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\partial f(S\setminus
E)}{\partial z_{T}}+\mathbbm{1}[T\in\mathcal{C}_{S}]\cdot\big{(}f(S\setminus
T)-f(S)\big{)}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (18)

When $|S|=1$, if $S=\\{r\\}$, then $f(S)=\ell(r)$ by definition, and so
$\frac{\partial f(S)}{\partial z_{T}}=\frac{\partial\ell(r)}{\partial z_{T}}$.
Henceforth, let us fix a set $S\subseteq U$ and some subset $T$. The next
lemma (in §D) follows by direct calculations:

######  Lemma 23.

The partial derivatives satisfy:

  1. (i)

If $T\supseteq S$, then $\frac{\partial f(S)}{\partial z_{T}}=1$.

  2. (ii)

If $T\cap S=\emptyset$, then $\frac{\partial f(S)}{\partial z_{T}}=0$.

  3. (iii)

We have $f(S)\geq\sum_{E\supseteq S}z_{E}$.

The partial derivative $\frac{\partial f(S)}{\partial z_{T}}$ is not very
well-behaved: e.g., it is not guaranteed to be non-negative (which turns out
to make an inductive proof difficult). To address this issue, we define a
surrogate _pseudo-derivative_ operator, and use bounds on this pseudo-
derivative to bound the derivative.

######  Definition 24 (Pseudo-Derivative).

The pseudo-derivative of $f(S)$ with respect to the variable $z_{T}$ such that
$T$ crosses $S$ (i.e., $T\in\mathcal{C}_{S}$) is:

$\displaystyle\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}$
$\displaystyle=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\frac{\widehat{\partial}f(S\setminus
E)}{\widehat{\partial}z_{T}}}+f(S\setminus
T)-{{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\sum_{E\supseteq
S}z_{E}}}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (19)

It is defined to be $1$ if $T\supseteq S$, and $0$ if $T\cap S=\emptyset$.

Observe the differences with (18), which are marked in red: when
$T\in\mathcal{C}_{S}$, each smaller derivative term $\frac{\partial
f(S\setminus E)}{\partial z_{T}}$ in the numerator of the derivative is
naturally replaced with the corresponding pseudo-derivative term
$\frac{\smash{\widehat{\partial}f(S\setminus E)}}{\widehat{\partial}z_{T}}$,
but crucially, the term $f(S)$ is replaced with $\sum_{E\supseteq S}z_{E}$.
These are the terms corresponding to the “shift” of the set $S$—i.e., the cuts
that separate all points in $S$ from the origin—and hence they form a lower
bound on $f(S)$, the expected distance to the closest point in $S$. This
latter change makes the following arguments easier (and indeed, possible), but
still maintains the intuition of the derivative being invariant under
translations. In §D, we prove the following lemma, showing it is indeed an
upper bound.

######  Lemma 25.

The pseudo-derivative is non-negative, and bounds the derivative from above.
I.e.,

$\displaystyle\max\left(\frac{\partial f(S)}{\partial
z_{T}},0\right)\leq\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}.$

Given Lemma 25, it suffices to upper bound the pseudo-derivative by
$\beta_{k-1}$, which we do next.

######  Theorem 26.

For any $S\subseteq U$ and any $T\neq\emptyset$, we have
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}\leq\beta_{|S\setminus
T|}.$

Theorem 26 implies our desired bound on the derivative, because $|S\setminus
T|\leq k-1$ for any $S\subseteq U,T\neq\emptyset$. To prove Theorem 26, we
first prove it for the special case when all points in $S\setminus T$ have the
same norm (the _uniform_ case), and then reduce the general case to this
uniform case.

####  5.3.1 Proof of Theorem 26: the Uniform Case

The main reason that it is easier to prove Theorem 26 for the uniform case is
because we know the value of $f(S\setminus T)$ exactly which will be equal to
the norm of all the points in $S\setminus T$. Otherwise, it is hard to obtain
any upper bound to $f(S\setminus T)$ in the general case. Moreover, we know
that the uniform property holds true for all subsets of $S$. This enables us
to use the upper bound of Theorem 26 to derivative terms
$\frac{\widehat{\partial}f(S\setminus E)}{\widehat{\partial}z_{T}}$ by
$\beta_{|S\setminus(E\cup T)|}$.

######  Lemma 27.

If all points in $S\setminus T$ have the same norm, then
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}\leq\beta_{|S\setminus
T|}$.

###### Proof.

The proof is by induction on $|S|$. If $T\notin\mathcal{C}_{S}$, we know that
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}$ is either $0$ or $1$.
But $\beta_{|S\setminus T|}\geq 1$ as $\beta_{m}\geq 1$ for any $m\geq 0$
which implies that we are done. Hence, for $|S|=1$, we know that
$T\notin\mathcal{C}_{S}$ and we are done. From now on, we can assume $|S|\geq
2$ and $T\in\mathcal{C}_{S}$. So we use the definition of the pseudo-
derivative from (19) and use the upper bound of the lemma inductively for the
recursive terms $\frac{\widehat{\partial}f(S\setminus
E)}{\widehat{\partial}z_{T}}$ to get:

$\displaystyle\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}\leq\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\beta_{|S\setminus(E\cup
T)|}+f(S\setminus T)-\sum_{E\supseteq
S}z_{E}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (20)

In order to show that
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}\leq\beta_{|S\setminus
T|}$, it is sufficient to upper bound the RHS of Equation 20 by
$\beta_{|S\setminus T|}$. Simplifying gives the following sufficient condition

$\displaystyle f(S\setminus T)\leq\sum_{E\supseteq
S}z_{E}+\sum_{E\in\mathcal{C}_{S}}z_{E}\left(\beta_{|S\setminus
T|}-\beta_{|S\setminus(T\cup E)|}\right).$ (21)

From here on, we will prove Equation 21. Since $T\in\mathcal{C}_{S}$, we know
that $|S\setminus T|\geq 1$. All points in $S\setminus T$ have the same norm,
so we can write

$\displaystyle f(S\setminus T)$ $\displaystyle=\frac{1}{|S\setminus
T|}\sum_{r\in S\setminus T}\ell(r)$ (22)
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn:norm_expansion}}}{{=}}\frac{1}{|S\setminus
T|}\sum_{r\in S\setminus T}\sum_{E:r\in E}z_{E}$ (23)
$\displaystyle=\sum_{E}z_{E}\cdot\frac{|(S\setminus T)\cap E|}{|S\setminus
T|}.$ (24)

When $E\supseteq S$, the coefficient of $z_{E}$ in Equation 21 is $1$. The
coefficient of $z_{E}$ in Equation 24 is also $1$ because in this case,
$S\subseteq E$ and hence $|(S\setminus T)\cap E|=|S\setminus T|$. Otherwise,
the coefficients of $z_{E}$ in Equation 21 and Equation 24 are
$\beta_{|S\setminus T|}-\beta_{|S\setminus(T\cup E)|}$ and $|(S\setminus
T)\cap E|/|S\setminus T|$ respectively. It remains to show

$\displaystyle\frac{|(S\setminus T)\cap E|}{|S\setminus
T|}\leq\beta_{|S\setminus T|}-\beta_{|S\setminus(T\cup E)|}.$ (25)

We can justify Equation 25 because the left hand side is sum of $|(S\setminus
T)\cap E|$ copies of $\frac{1}{|S\setminus T|}$, whereas the right hand side
is the sum of $|(S\setminus T)\cap E|$ terms, the smallest of them equal to
$\frac{1}{|S\setminus T|}$. ∎

######  Corollary 28.

If $T\in\mathcal{C}_{S}$ and $|S\setminus T|=1$, we have
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}\leq\beta_{1}=2$.

###### Proof.

Follows from Lemma 27 because when there is only one point in $S\setminus T$,
we can say that all points in $S\setminus T$ have the same norm. ∎

###  5.4 Proof of Theorem 26: Reducing to the Uniform Case

The case for points in $U\backslash T$ have different norms is the technical
heart of the proof. In this case, we “lift” the points in such a way that the
value of the pseudo-derivative
$\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}$ is monotonically increasing,
thereby reducing to the uniform case of Section 5.3.1. To begin, we give a few
supporting lemmas.

####  5.4.1 Supporting lemmas

######  Observation 29.

$\max\limits_{b\in S}(\ell(b))\geq f(S)\geq\min\limits_{a\in S}(\ell(a))$

###### Proof.

The proof follows from the fact that $f(S)$ is an expectation of norms of
points in $S$. ∎

Let us denote $S\backslash\\{{\bm{p}}\\}$ simply as $S-{\bm{p}}$.

######  Observation 30.

For any point ${\bm{p}}\in S$ such that $|S|\geq 2$, if $E\in\mathcal{C}_{S}$
and $E\notin\mathcal{C}_{S-{\bm{p}}}$, then $E\cap S$ is equal to either
$\\{{\bm{p}}\\}$ or $S-{\bm{p}}$.

######  Observation 31.

Let $A=\sum_{j=1}^{m}w_{j}\cdot v_{j}/\sum_{j=1}^{m}w_{j}$ be a weighted
average of $m$ items $t_{1},\dots,t_{m}$ with values $v_{1},\dots,v_{m}$
weighted by respective weights $w_{1},\dots,w_{m}$. Adding any number
$m^{\prime}-m$ items of value $A$ (with any weights) does not change the
weighted average. I.e., the new weighted average is

$\displaystyle A^{\prime}$ $\displaystyle=\frac{\sum_{j=1}^{m}w_{j}\cdot
v_{j}+\sum_{j=m+1}^{m^{\prime}}w_{j}\cdot
A}{\sum_{j=1}^{m}w_{j}+\sum_{j=m+1}^{m^{\prime}}w_{j}}=A$

31 is simple but powerful.

######  Lemma 32.

Let ${\bm{p}}$ be a point in $S$ having the minimum $\ell_{1}$ norm. If
$S-{\bm{p}}\neq\emptyset$, then

$\displaystyle f(S-{\bm{p}})\geq f(S)\geq f(\\{{\bm{p}}\\})$ (26)

###### Proof.

The lower bound follows from 29. Let us prove the upper bound by induction in
$|S|$. If $|S|=2$, then $f(S-{\bm{p}})$ is the norm of the maximum norm point
in $S$ which is more than $f(S)$ by 30. If $|S|\geq 3$, then $|S-{\bm{p}}|\geq
2$ so we will use Equation 17 to expand both $f(S)$ and $f(S-{\bm{p}})$ as

$\displaystyle
f(S-{\bm{p}})=\frac{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\cdot
f((S-{\bm{p}})\backslash
E)}{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}},\,f(S)=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot
f(S\backslash E)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (27)

Using 31 and 30, we can re-write $f(S-{\bm{p}})$ as

$\displaystyle
f(S-{\bm{p}})=\frac{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\cdot
f((S-{\bm{p}})\backslash E)+z_{\\{{\bm{p}}\\}}\cdot
f(S-{\bm{p}})+z_{S-{\bm{p}}}\cdot
f(S-{\bm{p}})}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (28)

In the numerators of $f(S-{\bm{p}})$ and $f(S)$, the coefficient of $z_{E}$ in
$f(S-{\bm{p}})$ is more than that of $f(S)$ either by induction on $|S|$
($S\leftarrow S\backslash E$) or using the fact that $f(S-{\bm{p}})\geq
f(\\{{\bm{p}}\\})$ from 29. ∎

From now, many other lemmas will have their proofs very similar to that of
Lemma 32 where we compare the function values of two different sets by
expanding the functions and using 31 to normalize the denominators and then
use induction and other arguments to conclude.

####  5.4.2 The lifting operation

Now let us define the lift operation. For a set
$S^{\prime}=\\{{\bm{p}}_{1},\dots,{\bm{p}}_{k^{\prime}}\\}\subseteq U$,
consider the following trajectory for the $\bm{z}$ vector

$\displaystyle z_{E}(t):=\begin{cases}z_{E}+t&E=\\{{\bm{p}}\\},\,{\bm{p}}\in
S^{\prime}\\\ z_{E}&\text{ otherwise }.\end{cases}$ (29)

Given this trajectory for the embedding, we are interested in how this changes
the function value. Let us define

$\frac{\partial f(S)}{\partial
S^{\prime}}:=\frac{\mathrm{d}f_{t}(S)}{\mathrm{d}t}\bigg{|}_{t=0}\,.$

######  Lemma 33.

Let $S^{\prime}$ be a subset of $U$. Then,

  1. 1.

If $S\cap S^{\prime}=\emptyset,\frac{\partial f(S)}{\partial S^{\prime}}=0$.

  2. 2.

If $|S|=1$, $S\subseteq S^{\prime},\frac{\partial f(S)}{\partial
S^{\prime}}=1$.

  3. 3.

If $|S|\geq 2$,

$\displaystyle\frac{\partial f(S)}{\partial
S^{\prime}}=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\partial
f(S\backslash E)}{\partial S^{\prime}}+\sum_{{\bm{p}}_{i}\in S\cap
S^{\prime}}\left(f(S-\\{{\bm{p}}_{i}\\})-f(S)\right)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$
(30)

Moreover, if points in $S^{\prime}\cap S$ if any, have the least norm out of
points in $S$, then $\frac{\partial f(S)}{\partial S^{\prime}}\geq 0.$

###### Proof.

Since $f(S)$ is purely a function of points in $S$, and hence only depends on
variables $z_{E}$ such that ${\bm{p}}\in E$ for some ${\bm{p}}\in S$. But the
only variables that change with $t$ are
$z_{\\{{\bm{p}}^{\prime}\\}},{\bm{p}}^{\prime}\in S^{\prime}$. Since
$S^{\prime}\cap S=\emptyset$, we can conclude statement 1. When
$S=\\{{\bm{p}}\\}$ and ${\bm{p}}\in S^{\prime}$,
$f_{t}(S)=\ell_{t}({\bm{p}})$. Since $z_{\\{{\bm{p}}\\}}$ is the only variable
that is changing and $\ell({\bm{p}})$ contains this, we can conclude statement
2. Once we know that $|S|=2$, using Equation 17 and applying the
$\frac{\partial}{\partial S^{\prime}}$ operator on both sides gives

$\displaystyle\frac{\partial f(S)}{\partial
S^{\prime}}=\frac{\sum_{E\in\mathcal{C}_{S}}\left(z_{E}\cdot\frac{\partial
f(S\backslash E)}{\partial s^{\prime}}+\frac{\partial z_{E}}{\partial
S^{\prime}}\cdot f(S\backslash
E)\right)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}-\frac{f(S)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}\cdot\frac{\partial\sum_{E\in\mathcal{C}_{S}}z_{E}}{\partial
S^{\prime}}.$ (31)

Using the fact that the only variables that are changing with $t$ are
$z_{\\{{\bm{p}}\\}}$ for ${\bm{p}}\in S^{\prime}$ in Equation 31 gives
Equation 30. Let us argue that $\frac{\partial f(S)}{\partial S^{\prime}}\geq
0$ when points in $S\cap S^{\prime}$ have the least norm of points in $S$
using induction on $|S|$. For $|S|=1$, using statement 2 or statement 1, we
are done. Otherwise, using Equation 30, we have that the recursive derivative
terms $\frac{\partial f(S\backslash E)}{\partial S^{\prime}}$ in the numerator
of Equation 30 are non-negative by inductive hypothesis. From Lemma 32, we
know that $f(S-{\bm{p}}_{i})-f(S)\geq 0$ for every ${\bm{p}}_{i}\in S\cap
S^{\prime}$. Combining both these observations, we can conclude statement 3
and hence the lemma. ∎

######  Lemma 34.

If $S^{\prime}$ is the set of points in $U\backslash T$ of minimum norm, then

$\displaystyle\frac{\partial}{\partial
S^{\prime}}\left(\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\right)\geq 0.$

###### Proof.

The proof is by induction on $|S|$. If $T\notin\mathcal{C}_{S}$, this is
trivially true because $\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}$ is
either $0$ or $1$. So for $|S|=1$, we are done. Otherwise, we have $|S|\geq 2$
and $T\in\mathcal{C}_{S}$. Recall from Equation 19 that

$\displaystyle\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}+f(S\backslash T)-\sum_{E\supseteq
S}z_{E}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$

Applying the operator $\frac{\partial}{\partial S^{\prime}}$ on both sides
gives

$\displaystyle\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\partial}{\partial
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)+\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}-\frac{\partial}{\partial S^{\prime}}\left(\sum_{E\supseteq
S}z_{E}\right)+\sum_{{\bm{p}}\in S^{\prime}\cap
S}\left(\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\right)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$

Since $|S|\geq 2$, the term $\frac{\partial}{\partial
S^{\prime}}\left(\sum_{E\supseteq S}z_{E}\right)$ is zero. Using this, what
remains is

$\displaystyle\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\partial}{\partial
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)+\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\right)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$

This means, it is sufficient to show that when $T\in\mathcal{C}_{S}$,

$\displaystyle\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\right)\geq
0.$ (32)

Because, the recursive derivatives $\frac{\partial}{\partial
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)$ are at least zero by induction on $|S|$. The
proof of Equation 32 is now given in Lemma 35. ∎

######  Lemma 35.

Let $S^{\prime}=\\{{\bm{p}}_{1},\dots,{\bm{p}}_{k^{\prime}}\\}$ be the set of
points in $U\backslash T$ of minimum norm. For $T\in\mathcal{C}_{S}$,

$\displaystyle\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\right)\geq
0.$

###### Proof.

The proof is by induction on $|S|$. Let us work out boundary cases first. If
$S\cap S^{\prime}=(S\backslash T)\cap S^{\prime}=\emptyset$, then
$\frac{\partial f(S\backslash T)}{\partial S^{\prime}}=0$ and the summation is
empty which makes the entire expression equal to $0$ in which case, we are
fine. So from now, we can assume $S\cap S^{\prime}\neq\emptyset$. If
$|S\backslash T|=1$, then $S\backslash T=\\{{\bm{p}}^{*}\\}\subseteq
S^{\prime}$, which implies $\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}=1$. The expression in this case is simply

$\displaystyle
1+\frac{\hat{\partial}f(S-{\bm{p}}^{*})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}=2-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}$

because $S-{\bm{p}}^{*}\in T$. For this boundary case, it remains to prove
that $\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}\leq 2$. This is taken
care of 28. For the base case $|S|=2$, we have $|S\backslash T|=1$ in which
case, we are done from the preceding arguments. Otherwise, if $|S\backslash
T|\geq 2$ we can expand all the derivative terms. But before we do that, we
need 31 so that we have the same denominator for all the three derivatives.
Now using Equation 30 and the fact that $(S\backslash T)\cap S^{\prime}=S\cap
S^{\prime}$,

$\displaystyle\frac{\partial f(S\backslash T)}{\partial S^{\prime}}$
$\displaystyle=\frac{\sum_{E\in\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(f(S\backslash(T\cup\\{{\bm{p}}\\}))-f(S\backslash
T)\right)}{\sum_{E\in\mathcal{C}_{S\backslash T}}z_{E}}$
$\displaystyle=\frac{\sum_{E\in\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(f(S\backslash(T\cup\\{{\bm{p}}\\}))-f(S\backslash
T)\right)}{\sum_{E\in\mathcal{C}_{S}}z_{E}}$
$\displaystyle\geq\frac{\sum_{E\in\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (33)

Using Equation 19 and the fact that $T\in\mathcal{C}_{S-{\bm{p}}}$ for any
${\bm{p}}\in S\cap S^{\prime}$,

$\displaystyle\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}$
$\displaystyle=\frac{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\cdot\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}+f(S\backslash(T\cup\\{{\bm{p}}\\}))-\sum_{E\supseteq
S-{\bm{p}}}z_{E}}{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}}$
$\displaystyle=\frac{\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\cdot\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S-{\bm{p}}}}z_{E}\cdot\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}+f(S\backslash(T\cup\\{{\bm{p}}\\}))-\sum_{E\supseteq
S-{\bm{p}}}z_{E}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$

Using Equation 19,

$\displaystyle\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}+f(S\backslash T)-\sum_{E\supseteq
S}z_{E}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$

The numerator of
$\frac{\hat{\partial}f(S-{\bm{p}})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S)}{\hat{\partial}z_{T}}$
is

$\displaystyle\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S-{\bm{p}}}}z_{E}\left(\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)$ $\displaystyle-\sum_{E:S\backslash
E=\\{{\bm{p}}\\}}z_{E}+\left(f(S\backslash(T\cup\\{{\bm{p}}\\}))-f(S\backslash
T)\right)$
$\displaystyle\geq\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S-{\bm{p}}}}z_{E}\left(\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)$ $\displaystyle-\sum_{E:S\backslash
E=\\{{\bm{p}}\\}}z_{E}.$ (34)

Note that the condition
$E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S-{\bm{p}}}$ holds only when
${\bm{p}}\in S$ and $E\cap S$ is either $S\backslash\\{{\bm{p}}\\}$ or
$\\{{\bm{p}}\\}$ from 30. When $E\cap S=\\{{\bm{p}}\\}$, the second derivative
term in Section 5.4.2 is zero. Otherwise, it is
$\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}=\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}$.
Using these observations, Section 5.4.2 can be simplified and can be re-
written as

$\displaystyle\sum_{E\in\mathcal{C}_{S-{\bm{p}}}}z_{E}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)+\sum_{E:S\backslash
E=\\{{\bm{p}}\\}}z_{E}\left(\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-1\right).$
(35)

The remaining numerator of $\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}$ from Equation 33 is

$\displaystyle\sum_{E\in\mathcal{C}_{S\backslash T}}z_{E}\cdot\frac{\partial
f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S\backslash
T}}z_{E}\cdot\frac{\partial f(S\backslash T)}{\partial S^{\prime}}.$ (36)

It remains to prove that the sum of Equation 36, and Equation 35 summed over
all ${\bm{p}}\in S\cap S^{\prime}$ is non-negative. Let us do that by
carefully partitioning all the $E$ into groups and do a case analysis.

Case 1: ($E\in\mathcal{C}_{S}\backslash\mathcal{C}_{S\backslash T}$)

First, observe that this happens only when either $\emptyset\neq S\cap
E\subseteq S\cap T$ or $\emptyset\neq S\backslash E\subseteq S\cap T$ as shown
in figures Figure 3(a) and Figure 3(b) respectively.

(a) Case 1a

(b) Case 1b

Figure 3: Case 1

Observe that in either case, for that $E$, we have
$E\in\mathcal{C}_{S-{\bm{p}}}$ for any ${\bm{p}}\in S\cap S^{\prime}$.

Case 1a: ($\emptyset\neq S\cap E\subseteq S\cap T$ )

In this case, the coefficient of $z_{E}$ in the sum of Equation 36 and,
Equation 35 summed over all ${\bm{p}}\in S\cap S^{\prime}$ is

$\displaystyle\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right).$ (37)

Which we can re-write as

$\displaystyle\frac{\partial f((S\backslash E)\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}_{r}\in(S\backslash E)\cap
S^{\prime}}\left(\frac{\hat{\partial}f((S\backslash
E)\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right).$

This, we can argue is non-negative by induction on $|S|$ by setting
$S\leftarrow S\backslash E$. But note that before using inductive hypothesis,
we need $T\in\mathcal{C}_{S\backslash E}$ which is not guaranteed when
$E=S\cap T$. But in that case, the terms inside the summation of Equation 37
are zero because $T\cap(S\backslash E)=\emptyset$ which implies that the
coefficient is $\frac{\partial f(S\backslash T)}{\partial
S^{\prime}}=\frac{\partial f(S\backslash(T\cup E))}{\partial S^{\prime}}\geq
0$ from Lemma 33.

Case 1b: ($\emptyset\neq S\backslash E\subseteq S\cap T$)

In this case, the coefficient of $z_{E}$ is the same expression as Equation 37
but observe that $S\backslash(E\cup\\{{\bm{p}}\\})=S\backslash E$ which
implies that the coefficient is simply $\frac{\partial f(S\backslash
T)}{\partial S^{\prime}}$ which we know is non-negative from Lemma 33.

Case 2: ($E\in\mathcal{C}_{S\backslash T}$)

Let us branch based on whether there exists ${\bm{p}}\in S\cap S^{\prime}$
such that $E\notin\mathcal{C}_{S-{\bm{p}}}$. This can happen in two ways.
First, there exists a point ${\bm{p}}^{*}\in S\cap S^{\prime}$ such that
$S\backslash E=\\{{\bm{p}}^{*}\\}$. Second, there exists a point point
${\bm{p}}^{*}\in S\cap S^{\prime}$ such that $S\backslash
E=S\backslash\\{{\bm{p}}^{*}\\}$

(a) Case 2a

(b) Case 2b

Figure 4: Case 2

Case 2a: ($\exists{\bm{p}}^{*}\in S\cap S^{\prime},S\backslash
E=\\{{\bm{p}}^{*}\\}$)

First, note that $E\in\mathcal{C}_{S\backslash T}$ for such a cut (see Figure
4(a)). Observe that for any ${\bm{p}}\neq{\bm{p}}^{*}\in S\cap S^{\prime}$, we
have $S\backslash(E\cup\\{{\bm{p}}\\})=S\backslash E$ and there cannot be a
different ${\bm{p}}$ such that $S\backslash E=\\{{\bm{p}}\\}$ for the same
$E$. This implies that the coefficient of $z_{E}$ in the sum of Equation 36
and, Equation 35 summed over all ${\bm{p}}\in S\cap S^{\prime}$ is

$\displaystyle\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}^{*}\\})}{\hat{\partial}z_{T}}-1$
$\displaystyle=\frac{\partial f(\\{{\bm{p}}^{*}\\})}{\partial
S^{\prime}}+\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}^{*}\\})}{\hat{\partial}z_{T}}-1$
$\displaystyle=\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}^{*}\\})}{\hat{\partial}z_{T}}\geq
0$

Case 2b: ($\exists{\bm{p}}^{*}\in S\cap S^{\prime},S\backslash
E=S\backslash\\{{\bm{p}}^{*}\\}$)

First, note that $E\in\mathcal{C}_{S\backslash T}$ for such a cut (see Figure
4(b)). Observe that for any ${\bm{p}}\neq{\bm{p}}^{*}\in S\cap S^{\prime}$, we
have $E\in\mathcal{C}_{S-{\bm{p}}}$. This implies that the coefficient of
$z_{E}$ in the sum of Equation 36 and, Equation 35 summed over all
${\bm{p}}\in S\cap S^{\prime}$ is

$\displaystyle\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{{\bm{p}}\neq{\bm{p}}^{*}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)$ $\displaystyle=\frac{\partial
f((S\backslash\\{{\bm{p}}^{*}\\})\backslash T)}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in(S\backslash{\bm{p}}^{*})\cap
S^{\prime}}\left(\frac{\hat{\partial}f((S\backslash\\{{\bm{p}}^{*}\\})\backslash\\{{\bm{p}}\\})}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash\\{{\bm{p}}^{*}\\})}{\hat{\partial}z_{T}}\right).$

This, we can argue is non-negative by induction on $|S|$ ($S\leftarrow
S\backslash\\{{\bm{p}}^{*}\\}$). Note that $T\in\mathcal{C}_{S-{\bm{p}}^{*}}$
holds so we can use induction hypothesis.

Case 2c: ($E\in\mathcal{C}_{S-{\bm{p}}},\forall{\bm{p}}\in S\cap S^{\prime}$ )

In this case, the coefficient of $z_{E}$ is simply,

$\displaystyle\frac{\partial f(S\backslash(T\cup E))}{\partial
S^{\prime}}+\sum_{{\bm{p}}\in S\cap
S^{\prime}}\left(\frac{\hat{\partial}f(S\backslash(E\cup\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right)$ $\displaystyle=\frac{\partial f((S\backslash
E)\backslash T)}{\partial S^{\prime}}+\sum_{{\bm{p}}\in(S\backslash E)\cap
S^{\prime}}\left(\frac{\hat{\partial}f((S\backslash
E)\backslash\\{{\bm{p}}\\}))}{\hat{\partial}z_{T}}-\frac{\hat{\partial}f(S\backslash
E)}{\hat{\partial}z_{T}}\right).$

This, we can again argue is non-negative by induction on $|S|$ ($S\leftarrow
E$). Note that if $T\notin\mathcal{C}_{S\backslash E}$, then $E\supseteq S\cap
T$ in which case, the terms in the summation are zero and we are done directly
without induction.

This completes the proof of Lemma 35. ∎

We can now wrap up: Lemma 35 was the missing piece in the proof of Lemma 34.
In turn, because of Lemma 34 we can assume all points in $S\backslash T$ to
have the same norm. Lemma 27 shows the desired bound of Theorem 26 for this
uniform case, completing the proof.

##  Appendix A Proofs from Section 2

###### Proof of Lemma 6.

For any client $\bm{x}\in\bm{X}$. Since the Random Thresholds algorithm is
translation and scaling invariant, we imagine that $\bm{x}=\bm{0}$. Now the
expected cost incurred by this client is at most the distance to the unique
center in its leaf region in the tree produced by the Random Thresholds
algorithm, which is at most $\alpha(|\mathcal{U}|)$. The claim now follows by
scaling by the true distance to the closest center $\|\bm{x}-\pi(\bm{x})\|$,
summing over all $\bm{x}\in\bm{X}$, and using linearity of expectations. ∎

###  A.1 Going from $\ell_{1}$ Metrics to Cut Metrics

It is known that point set in $\ell_{1}$ can be written as a non-negative sum
of cut metrics [DL97]; we give the details here for completeness. Given a
point set $V\in\mathbb{R}^{d}$, define $\ell_{i}:=\min_{\bm{v}\in V}v_{i}$ and
$u_{i}=\max_{\bm{v}\in V}v_{i}$. Then
$L_{1}(V):=\sum_{i=1}^{d}(u_{i}-\ell_{i})$, and $D_{1}(V)$ is the uniform
distribution over $\\{(i,\theta)\mid\theta\in[\ell_{i},u_{i}]\\}$. Define for
any $S\subseteq V$ the non-negative quantity

$z_{S}=L_{1}(V)\cdot\Pr_{(i,\theta)\sim
D_{1}(V)}[(V\cap\\{\bm{x}\mid\text{sign}(\theta)\cdot x_{i}\geq\theta\\})=S].$

This is a scaled version of the probability that for a random threshold cut,
the points of $V$ in the halfspace not containing the origin equals $S$. A
direct calculation shows that for all $\bm{p},{\bm{q}}\in V$, we have

$\|\bm{p}-\bm{q}\|_{1}=\sum_{S}z_{S}\mathbbm{1}_{(|S\cap\\{\bm{p},\bm{q}\\}|=1)}.$

Now define an $\ell_{1}$-embedding $\varphi:V\to\mathbb{R}^{2^{|V|}}_{\geq 0}$
by setting, for any $S\subseteq V$,

$\varphi(\bm{p})_{S}=\sum_{S}z_{S}\mathbbm{1}_{(\bm{p}\in S)}.$

Again, $\|\bm{p}-\bm{q}\|_{1}=\|\varphi(\bm{p})-\varphi(\bm{q})\|_{1}$.
Moreover, if the origin belongs to $V$, we get $\varphi(\bm{0})=\bm{0}$.

###  A.2 Proof of Lemma 8

Let $\mathcal{S}=\langle S_{1},\dots,S_{2^{k}}\rangle$ be the sequence of cuts
in increasing order of their sample values $X_{S}$. (We add the subsets with
$z_{S}=0$ at the end of the sequence in some fixed but arbitrary order.)
However, it is not true that we remove points from $U$ in this order: we need
to reject cuts that do not cross the remaining set $U$. (We say a set $A$
_crosses_ $B$ if $B\cap A$ is a non-empty proper subset of $B$: i.e., if both
$B\setminus A$ and $B\cap A$ are non-empty.) Hence, we recast the “last-point”
process again as follows. Given any subset of points $U\subseteq V$:

  1. 1.

Define $U^{0}:=U$ and $\mathcal{S}^{0}=\langle\rangle$. In general, $U^{r}$ is
the set of points remaining after considering sets $S_{1},\dots,S_{r}$, and
let $\mathcal{S}^{r}$ is a sequence of cuts selected until this point from the
sequence $\mathcal{S}$.

  2. 2.

We define $\mathcal{S}^{r+1}\leftarrow\mathcal{S}^{r}\circ\langle
S_{r+1}\rangle$ if $S_{r+1}$ crosses $U^{r}$, else we define
$\mathcal{S}^{r+1}\leftarrow\mathcal{S}^{r}$. Either way,
$U^{r+1}=U\backslash\bigcup_{S\in\mathcal{S}^{r+1}}S$.

Note that $U^{r}$ and $\mathcal{S}^{r}$ are both functions of
$(U,\mathcal{S})$. Call the cuts in $\mathcal{S}^{2^{k}}$ to be the _valid_
cuts for set $U$. Given the same sequence of cuts $\mathcal{S}$ we may get
different subsequences for each subset $U$ of $V$. So it is not necessarily
true that $(U\backslash T)^{r}=U^{r}\backslash T$, because the set of valid
cuts can differ when considering point sets $U$ and $U\backslash T$. But it
turns out that we can still relate $(U\backslash T)^{r}$ and $U^{r}\backslash
T$ in some settings.

######  Lemma 36.

Given sequence $\mathcal{S}$ and index $0\leq r\leq 2^{k}$ such that
$U^{r}\backslash T\neq\emptyset$, we have $(U\backslash T)^{r}=U^{r}\backslash
T$.

###### Proof of Lemma 36.

We prove this by induction on $r$. For $r=0$, we know that $U^{0}\backslash
T=U\backslash T=U^{0}\backslash T$. Suppose the claim holds for $r=t$, then we
want to show it holds for $r=t+1$. Suppose $U^{t+1}\backslash T\neq\emptyset$,
then since $U^{t+1}\subseteq U^{t}$ we have $U^{t}\backslash T\neq\emptyset$,
and by the inductive hypothesis we get that $(U\backslash
T)^{t}=U^{t}\backslash T$. In particular, we get that $(U\backslash
T)^{t}\subseteq U^{t}$. Hence if the new cut $S_{t+1}$ crosses $(U\backslash
T)^{t}$, then it also crosses $U^{t}$, and therefore

$(U\backslash T)^{t+1}=(U\backslash T)^{t}\setminus S_{t+1}=(U^{t}\backslash
T)\setminus S_{t+1}=(U^{t+1}\backslash T).$

So suppose the new cut $S_{t+1}$ does not cross $(U\backslash T)^{t}$, and
thus $(U\backslash T)^{t+1}=(U\backslash T)^{t}$. There are two cases: either
$(U\backslash T)^{t}\subseteq S_{t+1}$ or $(U\backslash T)^{t}\cap
S_{t+1}=\emptyset$. In the first case, if $S_{t+1}$ crosses $U^{t}$, then
$U^{t+1}\backslash T=(U^{t}\setminus S_{t+1})\setminus T=\emptyset$, and hence
there is nothing to prove. Else if $S_{t+1}$ does not cross $U^{t}$, then
$U^{t+1}=U^{t}$ and also $(U\backslash T)^{t+1}=(U\backslash T)^{t}$, so we
are done using the inductive hypothesis.

In the second case, $(U\backslash T)^{t}\cap S_{t+1}=(U^{t}\backslash T)\cap
S_{t+1}=\emptyset$, so we get that $(U^{t}\cap S_{t+1})\subseteq T$. This
means that $U^{t+1}\backslash T=U^{t}\backslash T$ regardless of whether
$S_{t+1}$ crosses $U^{t}$. Since $U^{t}\backslash T=(U\backslash
T)^{t}=(U\backslash T)^{t+1}$, we are done. ∎

As discussed above, $|U^{2^{k}}|=1$, and we define this unique point $p\in
U^{2^{k}}$ to be the “last” point in $U$, and we call this event “$p$ is last
in $U$”.

See 8

###### Proof.

Using the definition of the event “$p$ is last in $U$”, we know that
$U^{2^{k}}=\\{p\\}$ and since $p\notin T$, we have $U^{2^{k}}\backslash
T\neq\emptyset$. Using Lemma 36, we can say that $(U\backslash
T)^{2^{k}}=\\{p\\}$. ∎

##  Appendix B Proofs from Section 3

See 10

###### Proof of Lemma 10.

For some parameter $p\in(0,\nicefrac{{1}}{{2}})$, consider $k$ independently
chosen sets, each obtained by adding in each element of $[k]$ independently
with probability $p$. The expected size of each such set is $\bar{s}:=pk$;
moreover, each element of $[k]$ should hit a $p$ fraction of the sets, so
hitting all the $k$ sets should require
$\bar{h}:=\ln_{1-p}(1/k)\approx(1/p)\ln k$ sets, giving $\bar{s}\bar{h}/k=\ln
k$. We now show that with non-zero probability, there does exist a set system
with parameters close to these.

Define $\mathcal{B}_{1}$ to be the bad event that some set $S_{i}$ has size
smaller than $s:=(1-\varepsilon)pk$, and $\mathcal{B}_{2}$ to be the bad event
that the hitting set has size at most some parameter $h$. We now show that for
suitable choices of $\varepsilon$ and $h$, we have
$\Pr[\mathcal{B}_{1}]<\nicefrac{{1}}{{2}}$ and
$\Pr[\mathcal{B}_{2}]\leq\nicefrac{{1}}{{2}}$, which completes the proof. We
consider the event $\mathcal{B}_{2}$ first: a union bound shows that

$\Pr[\mathcal{B}_{2}]\leq\sum_{H:|H|=h}\Pr\left[\forall i\in[k]:S_{i}\cap
H\neq\emptyset\right]={k\choose h}(1-(1-p)^{h})^{k}\leq\frac{(2k)^{h}}{2}\cdot
e^{-k(1-p)^{h}}.$

Setting this upper bound to equal $\nicefrac{{1}}{{2}}$, we get

$\displaystyle\ln h-h\ln(1-p)=\ln\left(\frac{k}{\ln 2k}\right).$ (38)

We now use that $-p-p^{2}\leq\ln(1-p)\leq-p$ for $p\in[0,\nicefrac{{1}}{{2}}]$
to get

$\displaystyle\ln h+hp\leq\ln\left(\frac{k}{\ln 2k}\right)\leq\ln h+hp(1+p).$
(39)

Since $h\geq 1$, the left-most inequality of (39) gives
$h\leq(1/p)\ln(\frac{k}{\ln 2k})$. However, we want a lower bound on $h$, so
we substitute this into the right-most inequality of (39) to get

$\displaystyle\frac{1}{1+p}\cdot\ln\underbrace{\left(\frac{k}{\ln
2k}-\frac{1}{p}\ln\bigg{(}\frac{k}{\ln 2k}\bigg{)}\right)}_{(\star)}\leq
p\,h=\frac{s\,h}{(1-\varepsilon)k}.$ (40)

We can now set $p:=\frac{2\ln 2k}{k^{1/3}}$ (which ensures that the second
term in $(\star)$ is at most half the first for a large enough $k$) and get

$sh/k\geq\frac{1-\varepsilon}{1+p}\cdot\ln\left(\frac{k}{2\ln 2k}\right).$

Now setting $\varepsilon:=1/k^{1/3}$ and using a Chernoff bound and a union
bound,

$\Pr[\mathcal{B}_{1}]<k\cdot e^{-\varepsilon^{2}pk/2}=\frac{1}{2}.$

Taking a union bound over the two bad events, we get that with non-zero
probability our sets in $\mathcal{S}$ are of size $\approx k^{2/3}\ln k$, the
hitting set is of size $\approx k^{1/3}$, and $hs/k\geq(1-\frac{2\ln
2k}{k^{2/3}})(\ln k-O(\ln\ln k))$. ∎

##  Appendix C Proofs from Section 4

###  C.1 Proof of the Stretch-vs.-Separation Claim 19

Figure 5: projection of points onto an axis

We prove a lemma about point sets that immediately implies Claim 19. Consider
a set $S\subseteq\mathbb{R}^{d}$ of points, and focus on $p,q\in S$. Consider
some dimension $i$, and consider the projection of the points onto that
dimension (as in the figure). Let $a_{1},\dots,a_{\ell}$ be the lengths of
intervals into which the line segment joining $p_{i}$ and $q_{i}$ is
partitioned by projections of other points in $S$ onto the $i^{th}$ dimension.
Any cut $(i,\theta)$ intersecting the $j^{th}$ interval splits the centers
into two groups with at least $\min(j,\ell+1-j)$ centers on either side.

Define the _stretch_ $s_{i}$ between $p$ and $q$ in the $i^{th}$ dimension,
and the _expected separation_ ${\text{sep}}_{i}$ after choosing a random cut
that cuts the $j^{th}$ interval with probability proportional to $a_{j}^{2}$
as

$\displaystyle
s_{i}:=\frac{\big{(}\sum_{j\in[\ell]}a_{j}\big{)}^{2}}{\sum_{j\in[\ell]}a_{j}^{2}}\qquad\text{and}\qquad\text{sep}_{i}:=\frac{\sum_{j\in[\ell]}a_{j}^{2}\cdot\min(j,\ell+1-j)}{\sum_{i\in[\ell]}a_{j}^{2}}.$

######  Lemma 37.

$\text{sep}_{i}\geq\frac{s_{i}}{8(1+\ln(\nicefrac{{(2|S|)}}{{s_{i}}}))}$.

Before we prove this, let us generalize this to higher dimensions:

######  Corollary 38.

Consider a set $S\subseteq\mathbb{R}^{d}$ and two points $p,q\in S$ having
stretch $s$. If we choose a threshold cut $(i,\theta)$ from the distribution
$D_{2}(S)$ and condition on separating $p,q$, the expected number of points in
each side of the cut decreases by at least
$\frac{s}{8(1+\ln(\nicefrac{{(2|S|)}}{{s}}))}$.

###### Proof.

The stretch between $p,q$, and the expected separation conditioned on
separating the two centers is

$\displaystyle\overline{s}:=\frac{\sum_{i\in[d]}\big{(}\sum_{j\in[\ell_{i}]}a_{i,j}\big{)}^{2}}{\sum_{i\in[d]}\sum_{j\in[\ell_{i}]}a_{i,j}^{2}}\qquad\text{and}\qquad\overline{sep}:=\frac{\sum_{i\in[d]}\big{(}\sum_{j\in[\ell_{i}]}a_{i,j}^{2}\cdot\min(j,\ell_{i}+1-j)\big{)}}{\sum_{i\in[d]}\sum_{j\in[\ell_{i}]}a_{i,j}^{2}},$

where $a_{i,j}$ is the width in the partition defined above along dimension
$i$. Define a random variable $I\in[d]$ on the dimensions, that takes on value
$i$ with probability

$\frac{\sum_{j\in[\ell_{i}]}a_{i,j}^{2}}{\sum_{i\in[d]}\sum_{j\in[\ell_{i}]}a_{i,j}^{2}}.$

Then we have $\overline{s}=\mathbb{E}_{I}[s_{I}]$ and
$\overline{\text{sep}}=\mathbb{E}_{I}[\text{sep}_{I}]$. Finally, the function
$h(x)=\frac{x}{1+\ln(\alpha/x))}$ being convex for $0\leq x\leq\alpha$, we can
use Jensen’s inequality to get

$\overline{\text{sep}}=\mathbb{E}_{I}[\text{sep}_{I}]\stackrel{{\scriptstyle(\text{Lem.\ref{lem:expected_separation}})}}{{\geq}}\mathbb{E}_{I}\left[\frac{s_{I}}{8\left(1+\ln\left(\frac{2|S|}{s_{I}}\right)\right)}\right]\geq\frac{\overline{s}}{8\left(1+\ln\left(\frac{|S|}{\overline{s}}\right)\right)}.\qed$

Finally, translating to the language of §4 shows that Claim 19 is just a
reformulation of 38. So it suffices to prove Lemma 37, which we do next.

###### Proof of Lemma 37.

Let us look at the following constrained minimization problem

$\displaystyle\min\text{sep}_{i}$
$\displaystyle=\textstyle\sum_{j}a_{j}^{2}\cdot\min(j,\ell+1-j)$ (41)
$\displaystyle s.t.\quad$ $\displaystyle\textstyle\sum_{j}a_{j}=\sqrt{s_{i}}$
$\displaystyle\textstyle\sum_{j}a_{j}^{2}=1.$

The Lagrangian dual of the above primal program is

$\displaystyle\mathcal{L}(a,\lambda,\gamma)=\sum_{j}a_{j}^{2}\cdot\min(j,\ell+1-j)-2\lambda\bigg{(}\sum_{j}a_{j}-\sqrt{s_{i}}\bigg{)}+\gamma\bigg{(}\sum_{j}a_{j}^{2}-1\bigg{)},$

and setting the gradient to zero means the minima for $a$ occur when
$a_{j}=\frac{\lambda}{\gamma+\min(j,\ell+1-j)}$. (We assume $\gamma\geq 0$.)
Substituting and simplifying gives

$\displaystyle
2\lambda\sqrt{s_{i}}-\sum_{j}\frac{\lambda^{2}}{\gamma+\min(j,\ell+1-j)}-\gamma.$

We can maximize over $\lambda$ which happens when
$\sum_{j}\frac{\lambda}{\gamma+\min(j,\ell+1-j)}=\sqrt{s_{i}}$; substituting
gives

$\displaystyle\frac{s_{i}}{\sum_{j}\frac{1}{\gamma+\min(j,\ell+1-j)}}-\gamma\geq\frac{s_{i}}{2\ln(1+\frac{\ell+1}{2\gamma})}-\gamma\geq\frac{1}{2}\bigg{(}\frac{s_{i}}{\ln(1+\frac{|S|}{2\gamma})}-2\gamma\bigg{)}.$

It remains to choose $\gamma$. For convenience, we set the above expression to
$\gamma$; this means

$\displaystyle\frac{s_{i}}{\ln(1+\frac{|S|}{2\gamma})}=4\gamma\qquad\iff\qquad\frac{2|S|}{s_{i}}=\frac{|S|/2\gamma}{\ln(1+\frac{|S|}{2\gamma})}.$

Using 39 below, we get
$\gamma\geq\frac{s_{i}}{8(1+\ln(\nicefrac{{(2|S|)}}{{s_{i}}}))}$. ∎

######  Observation 39.

For any $x\geq 0$ and $y\geq 1$ such that $y=\frac{x}{\ln(1+x)}$, we have
$x\leq 2y(1+\ln y)$.

###### Proof.

Since $x/\ln(1+x)$ is an increasing function, it is sufficient to prove that

$\displaystyle y\leq\frac{2y(1+\ln y)}{\ln(1+2y(1+\ln y))}.$

Finally, taking derivatives shows $\ln(1+2y(1+\ln y))\leq 2(1+\ln y)$ for
$y\geq 1$. ∎

##  Appendix D Proofs from Section 5

###### Proof of Lemma 22.

For a point ${\bm{p}}\in U$, define

$\displaystyle z_{E}(t):=\begin{cases}z_{E}\cdot t&{\bm{p}}\in E\\\
z_{E}&{\bm{p}}\notin E.\end{cases}$ (42)

Let $f_{t}(U)$ and $\ell_{t}({\bm{p}})$ be the function value of points in $U$
and norm of ${\bm{p}}$ at time $t$ when the embedding is changing according to
the trajectory given by Equation 42.

We first claim that $\ell_{0}({\bm{p}})=0$ and $f_{0}(U)=0$. Indeed, We know
that $\ell_{t}({\bm{p}})=\sum_{S:{\bm{p}}\in S}z_{S}(t)=\sum_{S:{\bm{p}}\in
S}z_{S}\cdot t=t\cdot\ell({\bm{p}})$, which implies that
$\ell_{0}({\bm{p}})=0$. The second part is proved by induction on $|U|$: If
$|U|=1$, then $f_{0}(U)=\ell_{0}({\bm{p}})=0$. If $|U|\geq 2$ and $z_{E}(0)=0$
for all $E\in\mathcal{C}_{U}$, then $f_{0}(U)=0$ by definition. Otherwise,
using Equation 17, we can write

$\displaystyle f_{0}(U)=\frac{\sum_{E\in\mathcal{C}_{U}}z_{E}(0)\cdot
f_{0}(U\backslash U_{E})}{\sum_{E\in\mathcal{C}_{U}}z_{E}(0)}.$

In the numerator of $f_{0}(U)$, either $z_{E}(0)=0$ when ${\bm{p}}\in E$, or
$f_{0}(U\backslash U_{E})=0$ when ${\bm{p}}\in U\backslash U_{E}$ by inductive
hypothesis which concludes the proof.

Now using the chain rule and the assumed bound on the derivative,

$\displaystyle\frac{\mathrm{d}f_{t}(U)}{\mathrm{d}t}=\sum_{E\subseteq[k]}\frac{\partial
f(U)}{\partial
z_{E}}\Big{|}_{\bm{z}=\bm{z}(t)}\cdot\frac{\mathrm{d}z_{E}(t)}{\mathrm{d}t}=$
$\displaystyle\sum_{E:{\bm{p}}\in E}z_{E}\cdot\frac{\partial f(U)}{\partial
z_{E}}\Big{|}_{\bm{z}=\bm{z}(t)}$ $\displaystyle\leq\sum_{E:{\bm{p}}\in
E}z_{E}\cdot\beta_{k-1}=\beta_{k-1}\cdot\ell({\bm{p}}).$

Integrating gives
$f_{1}(U)-f_{0}(U)=f(U)-f_{0}(U)=f(U)\leq\beta_{k-1}\cdot\ell({\bm{p}})$. ∎

###### Proof of Lemma 23.

The proof is by induction on $|S|$. The base case is when $|S|=1$. If
$S=\\{r\\}$, then we have $\frac{\partial f(S)}{\partial
z_{T}}=\frac{\partial\ell(r)}{\partial z_{T}}$. We know that $\ell(r)$ can be
written as

$\displaystyle\ell(r)=\sum_{E\ni r}z_{E}.$ (43)

The derivative $\frac{\partial\ell(r)}{\partial z_{T}}$ is equal to $1$ if
$z_{T}$ appears as a term in the expansion of $\ell(r)$ as in Equation 43 and
is equal to $0$ otherwise. In the case of statement (i), since
$T\in\mathcal{C}_{S}^{\ell}$, we have $S\subseteq T\implies r\in T$ this
concludes the base case for statement (i). Similarly, if statement (ii) holds,
$z_{T}$ does not appear as a term in the expansion of $\ell(r)$ and hence the
partial derivative of $f(S)=\ell(\mu_{r})$ with respect to $z_{T}$ is zero.

For $|S|\geq 2$, we have $\mathbbm{1}[T\in\mathcal{C}_{S}]=0$ in both the
cases of statements (i) and (ii). Using this in Equation 18 gives

$\displaystyle\frac{\partial f(S)}{\partial
z_{T}}=\frac{\sum_{E\in\mathcal{C}_{S}}z_{E}\cdot\frac{\partial f(S\backslash
E)}{\partial z_{T}}}{\sum_{E\in\mathcal{C}_{S}}z_{E}}.$ (44)

For the inductive step, since $S\subseteq T$ in statement (i), we have
$(S\backslash E)\subseteq T$. By the inductive hypothesis, the recursive
derivative terms $\frac{\partial f(S\backslash E)}{\partial z_{T}}$ are equal
to $1$. Using Equation 44, we are done. The inductive step for the case of
statement (ii) follows similarly where all terms $\frac{\partial f(S\backslash
E)}{\partial z_{T}}$ are equal to $0$. Finally, using the fact that $f(S)$ is
always non-negative for any $z$, and the fact that $\frac{\partial
f(S)}{\partial z_{E}}=1$ for any $S\subseteq E$, we have
$f(S)\geq\sum_{E\supseteq S}z_{E}$. ∎

###### Proof of Lemma 25.

The proof is by induction on $|S|$. Observe that for $T\notin\mathcal{C}_{S}$,
either $T\supseteq S$ or $T\cap S=\emptyset$, and then
$\frac{\widehat{\partial}f(S)}{\widehat{\partial}z_{T}}=\frac{\partial
f(S)}{\partial z_{T}}$ by 24 and Lemma 23. The fact that the pseudo-derivative
is non-negative in this case is immediate from the 24. For $|S|=1$, since
$T\notin\mathcal{C}_{S}$, we are done. If $|S|\geq 2$ and
$T\in\mathcal{C}_{S}$, the inductive hypothesis implies that
$\frac{\widehat{\partial}f(S\setminus
E)}{\widehat{\partial}z_{T}}\geq\max\left(\frac{\partial f(S\setminus
E)}{\partial z_{T}},0\right)$. It remains to prove that

$\displaystyle\max\left(f(S\setminus T)-f(S),0\right)\leq f(S\setminus
T)-\sum_{E\supseteq S}z_{E}.$

Using Lemma 23, we get $f(S\setminus T)-f(S)\leq f(S\setminus
T)-\sum_{E\supseteq S}z_{E}$. The other inequality $\sum_{E\supseteq
S}z_{E}\leq f(S\setminus T)$ follows from the below argument, again using
statement (iii) of Lemma 23:

$f(S\setminus T)\geq\sum_{E\supseteq S\setminus T}z_{E}\geq\sum_{E\supseteq
S}z_{E}$

This concludes the proof of the lemma. ∎

## References

  * [BBC+19] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for _k_ -means: beyond subspaces and the Johnson-Lindenstrauss lemma.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039–1050. ACM, 2019.
  * [BFG+22] Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, William Lochet, Nidhi Purohit, and Kirill Simonov.  How to find a good explanation for clustering?  In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 3904–3912. AAAI Press, 2022.
  * [BNS18] Niv Buchbinder, Joseph (Seffi) Naor, and Roy Schwartz.  Simplex partitioning via exponential clocks and the multiway-cut problem.  SIAM J. Comput., 47(4):1463–1482, 2018.
  * [BPR+17] Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh.  An improved approximation for _k_ -median and positive correlation in budgeted optimization.  ACM Trans. Algorithms, 13(2):23:1–23:31, 2017.
  * [CEMN22] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan.  Improved approximations for euclidean _k_ -means and _k_ -median, via nested quasi-independent sets.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1621–1628. ACM, 2022.
  * [CGLS23] Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn.  Breaching the 2 LMP approximation barrier for facility location with applications to _k_ -median.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 940–986. SIAM, 2023.
  * [CH22] Moses Charikar and Lunjia Hu.  Near-optimal explainable k-means for all dimensions.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2580–2606. SIAM, 2022.
  * [CKL22] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  Johnson coverage hypothesis: Inapproximability of k-means and k-median in $\ell_{p}$-metrics.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022.
  * [CKM16] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu.  Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 353–364. IEEE Computer Society, 2016.
  * [DFM22] Sanjoy Dasgupta, Nave Frost, and Michal Moshkovitz.  Framework for evaluating faithfulness of local explanations.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 4794–4815. PMLR, 2022.
  * [DFMR20] Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian.  Explainable k-means and k-medians clustering.  In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7055–7065. PMLR, 2020.
  * [DL97] Michel Marie Deza and Monique Laurent.  Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 1997.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624–633. ACM, 2014.
  * [EMN22] Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan.  Almost tight approximation algorithms for explainable clustering.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2641–2663. SIAM, 2022.
  * [Fei98] Uriel Feige.  A threshold of $\ln n$ for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * [FMR20] Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian.  Exkmc: Expanding explainable k-means clustering.  CoRR, abs/2006.02399, 2020.
  * [FRS16] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour.  Local search yields a PTAS for k-means in doubling metrics.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 365–374. IEEE Computer Society, 2016.
  * [GHYZ11] Dongdong Ge, Simai He, Yinyu Ye, and Jiawei Zhang.  Geometric rounding: a dependent randomized rounding scheme.  J. Comb. Optim., 22(4):699–725, 2011.
  * [GJPS21] Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson.  Nearly-tight and oblivious algorithms for explainable clustering.  pages 28929–28939, 2021.
  * [Lab22] Eduardo Sany Laber.  The computational complexity of some explainable clustering problems, 2022\.