Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Authors: Buddhima Gamlath
Xinrui Jia
Adam Polak
Ola Svensson
Venue: NeurIPS 2021 Poster (2021)
Keywords: algorithms
clustering
combinatorial optimization
explainability

Abstract: We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A $k$-clustering is said to be 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 cluster. We give an algorithm that outputs an explainable clustering that loses at most a factor of $O(\log^2 k)$ compared to an optimal (not necessarily explainable) clustering for the $k$-medians objective, and a factor of $O(k \log^2 k)$ for the $k$-means objective. This improves over the previous best upper bounds of $O(k)$ and $O(k^2)$, respectively, and nearly matches the previous $\Omega(\log k)$ lower bound for $k$-medians and our new $\Omega(k)$ lower bound for $k$-means. The algorithm is remarkably simple. In particular, given an initial not necessarily explainable clustering in $\mathbb{R}^d$, it is oblivious to the data points and runs in time $O(dk \log^2 k)$, independent of the number of data points $n$. Our upper and lower bounds also generalize to objectives given by higher $\ell_p$-norms.

Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Buddhima Gamlath"
Xinrui Jia" EPFL Annui.jja@epfi
Adam Polak* EPFL
EPFL
buddhima.gammltthonnn ch
adam. odam.polakkepfl.coo
Ola Svensson"
EPFL
ola. svensson@epfl.ch
Abstract
We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A k-clustering is said to be explainable it is given by a decision tree where each internal node splits data points with threshold cut in single dimension (feature), and each of the k leaves corresponds cluster. give an algorithm that outputs an explainable clustering that loses most a factor of Ologg k) compared to an optimal (not necessarily explainable) clustering for the k-medians objective, and factor of Olllog' k)) for the k-means objective. This improves over the previous best upper bounds of (Ik) and O(k²). respectively, and nearly matches the previous 22 k) lower bound for k-medians and our new (2(k) lower bound for k-means. The al algorithm is remarkably simple.
particular, given an initial not necessarily explainable clustering in IRd, it is oblivious to the data points and runs in time Oddk log" k). independent of the number of data points n. Our upper and lower bounds also generalize objectives given by higher e--norms.
Introduction
An important topic in current machine learning research is understanding how models actually make their decisions. For a recent overview on the subject of explainability and interpretability, see,
e.g.. 13 14].
Many good methods exist (e.g. [15] for interpreting black-box models, so called
post-modeling explainability, but this approach has been criticized [16] for providing little insight into the data. Currently, there is a shift towards designing models that are interpretable by design.
Clustering is fundamental problem in unsupervised learning. A common approach clustering to minimize the k-medians or k-means objectives, e.g., with the celebrated Lloyd's [11] or k- means++ 2 algorithms. Both objectives also widely studied from theoretical perspective, and, in particular, they admit constant-factor approximation algorithms rumning in polynomial time [13 4 9).
In their recent paper (6). Dasgupta et al. were the first to study provable guarantees for explainable clustering. They define a k-clustering to be explainable if given by a decision tree, where each internal node splits data points with threshold cut in single dimension (feature), and each of the leaves corresponds to cluster (see Figure
"Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

21 < 0.4
.22 S 0.6
(a) Non-explainable clustering
(b) Explainable clustering
(c) Threshold tree
Figure I: Examples of an optimal non-explainable and costlier explainable clustering of the same set of points in IR?, together with the threshold tree defining the explainable clustering.
This definition is motivated by the desire to have concise and easy-to-explait reasoning behind how the model chooses data points that form a cluster. See the original paper (6) for an extensive discussion of motivations and a survey of previous (empirical) approaches to explainable clustering.
The central question study in this setting that of the price explainability: How much do have to lose in terms of a given objective, e.g., k-medians or k-means compared to an optimal unconstrained clustering, if insist on an explainable clustering, and can we efficiently construct such a clustering?
Dasgupta et al. 6 proposed algorithm that, given unconstrained (non-explainable) reference clustering produces an explainable clustering losing at most a multiplicative factor of O for the k-medians objective and (lk)) ) for k-means, compared the reference clustering. They also gave a lower bound showing that an (log k)) loss is unavoidable, both for the k-medians and k-means objective. Later, Laber and Murtinho (10) improved over the upper bounds in low-dimensional regime d < k/ log(k), giving an Od log -papproxiiitioon algorithm for explainable k-medians and an (dk log -pparoooxittaooon algorithm for explainable k-means.
1.1 Our contributions
Improved clustering cost. We present randomized algorithm that, given h centers defining reference clustering and number 1, constructs threshold tree that defines an explainable clus- tering that is, in expectation, worse than the reference clustering by most factor of O(k2-1 log" k) for the objective given by the fp-norm. That is (log² k-) for k-medians and O log² kc) for k k-means.
Simple and oblivious algorithm. Our algorithm is remarkably simple. It samples threshold cuts uniformly at random (for k-medians; k-means and higher f--norms need slightly fancier distributions) until all centers separated from each other. In particular, the input to the algorithm includes only the centers a reference clustering and not the data points.
As consequence, the algorithm cannot overfit the data (any more than the reference clustering possibly already does), and the same expected cost guarantees hold for any future data points not known at the time of the clustering construction. Besides, the algorithm is fast; its running time does not depend on the number data points n. A naive implementation runs time (dd??), and in Section 3.2] we show how to improve it to Oddk log" k) time, which is near-linear in the input size dk of the k reference centers.
Nearly-tight bounds. We complement results with lower bound. We show how construct instances of the clustering problem such that any explainable clustering must be at least 1(k--1) times worse than optimal clustering for the f--norm objective. In particular, this improves the previous 2(log k) lower bound for k-means (6) to ((k).
A reference clustering can be obtained, e.g., e.. by running a constant-factor approximation algorithm for a given objective function. Then, the asymptotic upper bounds of the explainable clustering cost compared to the reference clustering translate identically the bounds when compared to optimal clustering.

---

Table Algorithms and lower bounds for explainable k-clustering in R For a given objective function, how large multiplicative factor do have to lose, compared optimal unconstrained clustering, if we insist on an explainable clustering?
k-medians
k-means
4 ep-norm
O(k)
O(k2)
Dasgupta et
Algorithms
Od k)
O(kd logk)
Laber and Murtinho 10
Ologg* k)
O k))
This paper
(log & log log It)
O loo l log log
Makarychev and Shan
(log & log log k)
O log k)
Esfandiari et al.
Od d)
Esfandiari al.
O(k polylog
Charikar and Hu [
Lower bounds
((logk) k)
((log
Dasgupta et al.
((kk)
1(KP-1)
This paper
(2
Makarychev and Shan [2]
A(min(d, log k))
(2(A:)
Esfandiari et al.
22k42 2(4 polylog k)
Charikar and Hu
In consequence, we give a nearly-tight answer to the question of the price of explainability. We leave log(k) gap for k-medians, and a log" (k) gap for k-means and higher é, -n-mrrm objectives. See
Table for summary of the upper and lower bounds discussed above and recent independent works discussed in Section
1.2 Technical overview
The theoretical guarantees obtained by Dasgupta al. [6] depend on the number of clusters i and the height the threshold tree obtained H. Their algorithm loses, compared to the input reference clustering, O(H) factor for the k-medians cost and O for k-means. These approximations are achieved by selecting a threshold cut that separates some two centers and minimizes the number of points that get separated from their centers in the reference clustering. This creates two children of tree node, and the threshold tree is created by recursing on each of the children. The height of the tree H may need be vectors (see Figure 2. Laber and Murtinho (10) replace the dependence on H with d, the dimension of the data set, by first constructing optimal search trees for each dimension and then carefully using them to guide the construction of the threshold tree. In our work, we obtain improved guarantees by using randomized cuts that are oblivious to the data points and depend only on the reference centers, in contrast to the above-mente menee-ee two prior approaches,
For example, consider the data set in I consisting of the & standard basis
which selected cuts based on the data points.
31 0.5
There are two components to achieving our improved guar- antees that correspond with aspects of the minimum cut algorithm of [6]: the use of the minimum cut, and the height of the threshold tree produced. The first observa- tion is that, for the & -norm, we do not lose in the analysis by taking a cut uniformly random compared to always using the minimum cut. (The corresponding distribution for higher l -ormss proportional to the p-th power of the distance to the closest center.) Indeed, using random cut makes us robust against specifically engineered exam- ples, such as the one that fools the minimum cut algorithm of (6] (see Appendix in the supplementary material). that example we add dimensions in which cut is mini-
322
0.5
Th-1 5 0.5
Figure 2: An optimal threshold tree for the & standard basis vectors in R* Any optimal threshold tree on this data set has height k: 1.

---

mum, but these minimum cuts produce a tree of height ((k) whose cost is (k()) times larger than the optimum.
However, threshold trees of height 2 k+) are unavoidable in certain instances as seen in the example with A standard basis vectors (Figure 2 This leads our second observation that it is necessary to use tighter upper bound on the cost of reassigning point since any height k 1 threshold tree produced on this example is actually optimal. Using the diameter definition in [6] the cost of each cut is upper bounded by k while the actual distance between any two centers is at most 2, which is also valid upper bound for the reassignment cost. Hence, we use the maximum distance between any two centers to upper bound the cost of misclassifying a point.
Limitations and further work. We conjecture that our k-medians algorithm is asymptotically optimal. In particular, we believe the actual approximation ratio of our algorithm is 1 H where Hn is the n-th harmonic number (recall that In(n) < Hn S. 1 + In(n)). There are two potential barriers our current analysis that prevent us from demonstrating this optimality. The first that our upper bound on the cost increase of assigning a single point to a wrong center is not tight, and secondly, our analysis may include the cost of the same point multiple times. Despite the further developments mentioned in Section 1.3 it still remains to fully resolve the correct asymptotic price of explainability.
Some potential directions to expanding our work include parallelizations, generalizing the notion of explainability, and defining natural clusterability assumptions under which the price of explainability is reduced. Constructing a threshold tree seems inherently sequential; it would be interesting to explore parallelizations for faster implementation. Another direction would be allow each node to be a hyperplane in a chosen number of dimensions instead of only splitting along one feature. Finally, it seems a non-trivial question to find right clusterability assumption on the data points distribution that would allow us to overcome the existing lower bounds because these lower bounds are in fact very "clusterable" instances, in the traditional usage of this notion.
Societal impact. Our contributions theoretical in nature and thus not tailored any specific application. We show that a simple algorithm has good approximation guarantees while also having running time independent of the number of points in the data set. Moreover, this algorithm is oblivious to the data points, which avoids introducing biases. However, our algorithms rely on reference clustering and may show existing biases of the original clustering.
1.3 Independent work
We note independent further developments by Makarychev and Shan 12 Esfandiari, Mirrokni, and Narayanan 77: and Charikar and Hu (5).
Makarychev and Shan [2] showed Olog k log log k) and O log k log log k) upper bounds for k-medians and k-means, respectively, thus improving over our bounds by a factor of log k/1og log k. Their k-medians algorithm is essentially the same as our modified Algorithm| (see Section 3.1.I] ) but they provide tighter analysis. Their k-means upper bound follows from combining their k-medians algorithm with their insightful reduction from k-means to k-medians that loses a factor of Olk). However, the k-means algorithm resulting from that combination is essentially the same Algorithm 2 They also provide an 2(4/1og x) lower bound for k-means, which is slightly worse than ours. Finally, they study the explainable k-medoids problem (i.e., k-medians with & norm), and provide Ollog"/ 8/2 k) upper bound and an 2(log k) lower bound.
Esfandiari, Mirrokni, and Narayanan 77 also give an Olog log log k) upper bound for k-medians. Their algorithm is essentially the same our (unmodified) Algorithm and, again, they provide tighter analysis. They also give an (A: log k)) upper bound for k-means, improving over the result of Makarychev and Shan by a factor of log log k. Their k-means algorithm is similar to Algorithm but samples cuts from a different distribution. They also match our 22k) lower bound for k-means, and improve the k- t-medians lower bound of Dasgupta et al. (6) to ((min(d, logk)) k)).
Charikar and Hu focus on explainable k-means and present an O(k2-2/4 poly (d log k))- approximation algorithm, which better than any previous algorithm when d = O k/tog log k) (in particular, for any constant dimension d). Resorting to an O(k polylog k) aaprooximatoo algorithm

---

(e.g., (12) when this is not the case, they obtain O -//2 polylog k) upper bound. They match it with an (2(k' 4// polylog k) lower bound, which is tight up to polylogarithmic factors.
2 Preliminaries
Following the notation of (6). we use bold variables for vector values and corresponding non-bold indexed variables for scalar coordinates. Intuitively, a clustering is explainable because the inclusion of a data point a: [21, .......... Ird] particular cluster "easily explained" by whether or not a satisfies series of inequalities of the form 2; I 0. These inequalities are called threshold cuts, .d)) and a threshold E R. More precisely,
defined by a coordinate à [d] (denoting the set threshold free is binary tree where each non-leaf node is threshold cut (i, 0) which assigns
point æ that node into the left child x; and the right child otherwise. clustering is explainable if the clusters are in bijection to the leaves of threshold tree with exactly k leaves that started with all the data points at the root.
Given set of points X the k-medians cost of the clustering is defined in (6) as
(x', x², ..".....,""" } C Rd and its clustering (C",...,CC*) Uj CJ = XX,
4:
cost, c (Ct,,,."
min
x 1Il
Σ
Σ | median (C')
#EC
The k-means cost is defined analogousty with the square of the & distance of every point to mean(C").
For a set of centers U = "p=",..,,,x"" S Rd, non-explainable clustering (Č',...,CC of X is given by C (æc E x 1 = arg minmin |ær =l|1)), and we write cost (4) = cost, (Č¹ ).... Note that cost, (4)==2es minpeu x - pll11
Given a threshold tree T. the leaves of T induce explainable clustering "0.....,a and we write cost, (7) cost, (CI ..... Õk). In the analyses, however, often upper bound the cost of each explainable cluster O using the corresponding reference center μ²:
cost (T) S
Σ x
-'
j=1 wE
These may not optimal center locations, yet we are still able to obtain guarantees that are polylog away from being tight.
We generalize the above to higher E, -ormss, p 2 as follows
cost,(C"
C*
Σ
min
o - Hlp
cost, (T) -
Σ | j=1 Φ
MER
j=1
DEC1
3 Explainable k-medians clustering
In this section we present our algorithm for explainable k-medians and its analysis. Recall that algorithm is oblivious to the data points: It determines the threshold tree using only the center locations. The algorithm simply samples a sequence of cuts until defines a threshold tree with each center belonging to exactly one leaf. In what follows, elaborate this process in detail.
The algorithm's input a set of centers = {n² pe2.pp2.. .2...... .......,p
Rdd. We consider cuts that intersect the bounding box 24, Letting L, = [min u.. maxxe(a) [u]] be the interval between the minimum and maximum i-coordinate of centers, the set of all possible cuts that intersect the bounding box of L4 is AllCuts = {(i. 0) E [d]. E L.} Our algorithm uses a stream independent uniformly random cuts from AllCuts. In partieular, the probability density function of (i, 0) AllCuts is 1/L where L = Eie(4 [ is the sum of the side lengths of the bounding box U.
The algorithm simply takes cuts from this stream until produces a threshold tree. To this end, maintains tentative set of tree leaves, each identified by subset of centers, and continues until has
5

---

k leaves of singleton sets. We say cut splits leaf if the cut properly intersects with the bounding box of the corresponding subset of centers. In other words, cut (i,0) splits a leaf B and only the two sets B = (1 B μ4; S 0) and B+ (μ E B μ4i > 0} are both non-empty. At the beginning, the algorithm starts with a single leaf identified by M, the set of all centers. then samples a cut (i, () and checks if it splits any existing leaf. If so, it saves the cut, and for each leaf B that gets split by the cut into B and B+, adds and B as two new leaves rooted at B. These saved cuts define the output threshold tree. We present the pseudo-code of this algorithm in Algorithm
Algorithm I: Explainable k-medians algorithm.
Input: A collection of k centers U = {p², 2 Output: threshold tree with leaves.
) C Rd.
Leaves < {
4 while Leaves < k do Sample (i, () uniformly at random from AllCuts. for each E Leaves that are split by (i, 0) do
Split B into B and B+ and add them left and right children of B. Update Leaves.
return the threshold tree defined by all cuts that separated some B.
3.1 Cost analysis
We show that Algorithm
I satisfies the following guarantees.
Theorem 1. Given reference centers {ux', 12... ...., 1=²), Algorithm 7 outputs a threshold tree T whose expected cost satisfies
Bleost1 (T)s S (llo((k) (1 + log(( (umn))/ cost, (4),
where Cmax and Cuin denote the maximum and minimum pairwise distance between centers in U, respectively. Furthermore, with probability at least 1/k, Algorithm outputs a threshold tree T from a distribution with Elcost, (T)) S O(log* cosst, (24).
The (more involved) proof of the furthermore statement is discussed in Section 3. 1. and formally proved in Appendix B in the supplementary material. We remark that the success probability 1 1/k can be made larger by only slightly increasing the hidden constant in the cost guarantee. Furthermore, in Section 3.1. we give slight adaptation of the above algorithm that has expected cost bounded by Oloog" k) cost (44) The remaining part of this section is devoted to proving the upper bound on the expected cost of Algorithm
3.1.1
Proof outline. First, in Lemma we show that a random cut in expectation separates cost; (2) points from their closest centers. Indeed, note that the probability of separating a point x: from its center (xx) is at most I| (==)]l2 and on the other hand, cost (24) E.sx ||x <(x) l hence the bound follows from linearity of expectation. Each such separated point incurs a cost of at most Cmax- Next, in Lemma 2 we show that with good probability (llog(k) L//mmxx random cuts separate all pairs of centers that are at distance at least 2max/2 from each other. Morally, the cost of halving Cmax, which we will need perform log (Cmma// /Cmin) many times, therefore cost, (11)L. TT Cmax (log(k)) TL/Cmax) = O(lo(())) cost, (II), and the bound follows (see Lemma 3)
Formal analysis of the expected cost. We first bound the number of points that are separated from their closest center by a random cut. This quantity is important as it upper bounds the number of points whose cost is increased in the final tree due to the considered cut. Recall that L dd [ denotes the total side lengths of the bounding box of the input centers U. We also let (() be the number of points separated from their closest center by the cut (i,
Lemma 1. We have (f,,))((()) cost, ( L where the expectation is over uniformly random threshold cut (i, 0) AllCuts.

---

Proof. For a point a E X let ग (x) denote the closest center in 24 Then by definition,
cost, (U) = Σ - xEX
Σ
2 π (x))..
f=1
Moreover, we let (0) be the number of points separated from their closest center by the cut (i.
rewrite the cost of fixed dimension as follows:
1 between æ; and <<)))]] f f:(0)d0.
Σ I {<>);|= = Σ
xEX
We thus have cost, (2) -i f:0)dd
At the same time, if we let [a,, by] denote the interval I, then [2:] J., f() equals the number of points separated from their closest center by uniformly random threshold cut (i, 0) 0 E 1 along dimension Thus the expected number of points separated from their closest center by a uniformly random threshold cut in AllCuts is
Σ
I d(
1
1 I
Σ
f(())d S
f((0)d0 cost, (U)/
where we used fi(0) 2 0 for the incquality.
The above lemma upper bounds the expected number of points whose cost increases from uniformly random threshold cut. We proceed to analyze how much this increase is, in expectation. Let Leaves( t denote the state Leaves at the beginning let Cmnxx(1) (t) max BELeaves(1) max , B |/ fe²|| || denote the maximum distance between two centers that belong to the same leaf the beginning of the 1-th iteration. With this notation we have
the 1-th iteration the while loop of Algorithm [ and
that Leaves(1) () = {2} and that Cmax (1) equals the Cmax in the statement of Theorem [ Observe that Cmax(() (t) 2 Cmax (t + 1) and Cmax = if Leaves = & (i.c., when each leaf contains exactly one center). Understanding the rate which Cmax (t) decreases is crucial for our analysis because of the following observation: Consider a leaf E Leaves(t) and point æ E X' that has not yet been separated from its closest center i (2x) B. If the threshold cut selected in the t-th iteration separates x from π x)) then the cost of æ in the final threshold tree is upper bounded by max || pll11. which, by the triangle inequality, is most
max | T (=)]l + [|((x) pll1 s || (x))]l BEB
+ Cmax (t).
(1)
In other words, a point that first separated from its closest center by the threshold cut selected in the 1-th iteration has cost increase of most Cmaxx (t).
Lemma 2. Fix the the threshold cuty selected by Algorithml 7 [during the first iterations (this determines the random variable Leaves(t) (t) and thus Cmax (t)). Let M 3 In(k) / Then
Pr|Cmaxx + M) S Craax(t)
1/k:
where the probability is the random cuts selected in iterations t, t + 1, ,,...,, -
Proof. Consider two centers Ju and μ that belong to the same leaf in Leaves(!). (I). The probability that a uniformly random threshold cut from AllCuts separates these two centers equals || μ ///
Thus if the centers are at distance at least Craxx (1)/2, the probability that they are not separated by any of M independently chosen cuts is at most
(1 (1- Cinaxe (1)/2)
(1/22 M L
= -(1- Crnxx (t) 3
S (1/e)3lln()) 1/k3.
2L
There at most (t) pairs of centers in the leaves of Leaves(t) distance at least Crnax (t)/2. By the union bound, we thus have, with probability at least 1 - 1/k, that each of these pairs are separated by least one the cuts selected in iterations 1, 5,4+1. 1, ..... 1+ M In that case, any two centers the same leaf of Leaves(t + .M) are at distance most Cmax (t)/2 /2 and Cmax (t +M) Cmax (t) L
7

---

Equipped with the above lemmas we are ready to analyze the expected cost of the tree output by Algorithm [ Let (4,, 0r) denote the cut selected by Algorithm[]]] the t-th iteration. As argued above in (T), Cmaxx (t) upper bounds the cost increase of the points first separated from their closest center by the 1-th threshold cut. Hence,
E [cost] (T) S cost (Lf + E Σ Cmax (t))
where the sum is over the iterations of Algorithm [ (and recall that f((0) denotes the number of points separated from their closest center by the cut (7, 0)). We remark that the right-hand side is an upper bound (and not an exact formula of the cost) for two reasons: first, not every separated point may experience cost increase of Cmax (t), and second, the right-hand side adds cost increase every time a cut separates a point from its closest center and not only the first time. Nevertheless, we show that this upper bound yields the stated guarantee. We do so by analyzing the expected cost increase of the cuts until Cmax (t) has halved. Specifically, let
cost-increase(r)
Σ
Cmax (0,)
Crann (f) (cmmax /2 122+1 Comax (2")
be the random variable that upper bounds the cost increase caused by the cuts selected during the iterations & when Cmax/ / /2 Cmax (t) S Cmax/2
/2", /2". Then
E|cost [[)] S cost, (2t) + Σ Elcost-increess(())
where the sum is over r from 0 to 1 + [log (Cmax/ (Cmax/mmim) [mmn)] The bound on the expected cost therefore follows from the following lemma.
Lemma 3. For every r, E[cost-increase(()] S 12 lnk) cost (21).
Let M = 3 lm()) /e//maxx(t (t) as in Lemma 2 Using Lemma I one can upper bound the expected cost of M uniformly random cuts in iterations f, 1....,t t M 1 by 6 in(k) cost, (4) and M cuts is very likely to halve Cmax (4) as in Lemma 2 It is thus very likely that the cost of these M cuts upper bounds cost-increase(r). The additional constant factor of in the statement of the lemma arises by considering the small "failure" probability of such trial. The formal proof bounding the expected cost of this geometric series can be found in Appendix B.1 in the supplementary material.
3.1.1 Upper bounding cost by factor of Ologg k)
Observe that our analysis of Algorithm D immples that the expected cost of the output tree is at most Olog (log2(() (k) (24)) whenever Cmax and Cmin do not differ by more than a polynomial factor in k. However, our current techniques fail to upper bound this expectation by a factor (k) for general Gmax and Cmin- To illustrate this point, consider the k-dimensional instance with single point the origin and centers where the i-th center fa² is located at the i-th standard basis vector scaled by the factor 2'. In our analysis, we upper bound the cost of with its maximum distance those centers that remain in the same leaf whenever æ is separated from its closest center μ² This yields the following upper bound on the expected cost of æ in the final tree
h
2' Pr(æ is separated from 4u² and 4e is the farthest remaining center].
Due to the exponentially increasing distances, this is lower bounded by 2 Pr[æ is separated from je' and 2³ is remaining center). Now note that the probability in this last sum equals Pr[æ is separated from je' before is separated from μ¹ 2/(2 2¹). It follows that any analysis of Algorithm that simply upper bounds the reassignment cost of a point with the maximum distance to remaining center cannot do better than factor of ((kk).
We overcome this obstacle by analyzing slight modification of Algorithm T that avoids these problematic cuts that separate very close centers. Recall the notation used in the previous section: Leaves(() denotes the state of Leaves at the beginning of the (-th iteration of the while loop and Cmax(1 (1) = BELeveee))))( maxp', W/EB |||=² -1'll denotes the maximum distance between two centers that belong to the same leaf at the beginning of the 1-th iteration. We now modify Algarithm by replacing Line 5 "Sample (i, () uniformly random from AllCuts" by
8

---

Sample (i, 8) uniformly at random from those cuts in AllCuts that do not separate two centers that are within distance most Cmax (t)/k² /k+
This modification allows us to prove a nearly tight guarantee on the expected cost.
Theorem 2. Given reference centers U {u² p² ..... ,, ,,,,,,,,, modified Algorithm outputs threshold tree T whose expected cost satisfies E|cost (T) S O k) costt(2))
The above theorem implies the furthermore statement of Theorem This follows by observing that Algorithm selects the same cuts as the modified version with probability least 1 1/k: This etror probability can be made smaller by not allowing cuts that separate centers within distance Cmax (t)/kf for an larger than 4. Due to space limitations, we give a more formal explanation of this implication in Appendix B.2 and we prove Theorem 2 in Appendix [33 in the supplementary material.
3.2 Implementation details
Since we only use cuts that split at least one leaf, the algorithm in fact only needs to sample cuts conditioned on this event. Note that if we sample only the cuts that split at least one leaf, the while loop in I. Line 4 of Algorithm runs for at most 1 iterations. We now explain how to efficiently sample cuts (Line 5), find the leaves split by a given cut (Line 6 and implement the split operation (Lines
We first show how to efficiently implement the split operation. For a cut (i. 0) that splits given leaf B into B and B+, the split operation can be implemented in O(d min( I log [B) time as follows: In each leaf B, we maintain d binary search trees T ..... Tá where T. stores the i-th coordinate of the centers in B. Now, given a cut (i. 8) and leaf B that gets split by (i. 6). we can find the number of centers in B that have a smaller or equal i-th coordinate than @ using T." in Oloo B)) time. Let b" be this number, and let b+ [B] b Suppose that b S bt. For the other case, the implementation is analogous. In this case, we construct B by initializing it with d empty binary search trees and inserting the centers whose i-th coordinate is at most @ to each of them. This takes Odd b- log BB) time. For B=, we just reuse the binary search trees of B after removing the centers that belong to B= This also takes Odd 6- log Bl) time, Let r(k) denote the running time of all splitting operations performed by the algorithm when starting with single leaf with & leaves. Then, T
k') r(k) = 7(k- - k') + T(k)) + O(d min(k - k',') log k) and by induction, we conclude that r(k) = (dk log² k).
To find the leaves that get separated by cut, we employ the following data structure. For each dimension i, we maintain a balanced interval tree Tiint For each tentative leaf node with centers B, we store the interval indicating the range of the i-th coordinate of B in Time. We update the corresponding interval trees after each split operation, which amounts to removing at most one interval and adding at most two intervals per node that gets split. Note that the added and removed intervals for a single split operation for a fixed dimension can be computed in Ollog k) time using the previously described node binary search trees. Moreover, adding and removing intervals to and from an interval tree with at most intervals also takes Olog k) time. As we have Okk) split operations in total, the time to maintain the interval trees is O(kk log k). Now, given cut (i, 9). we can retrieve all the leaves that get separated by (i. 0) in (log((k)) (k)) + k2) time where kn is the number of tentative leaves and ko is the number of tentative leaves that get separated by the cut. To retrieve such leaves, we query the i-th interval tree to find all intervals that contain the value f. Since we sample at most k k-1 1 cuts from the conditioned distribution, the total time for this operation over all cuts and all dimensions is (dk log k))
What remains is to show that we can efficiently sample a uniform cut conditioned on the event that it splits at least one leaf. To this end, in the interval trees described above, we also maintain the lengths of the unions of intervals in each subtree. This length information can be updated in O(log k') time where < is the number of intervals in an interval tree. Then in (d)) time, one can sample a dimension and in Oloog k') time, sample suitable 0 value.
4 Explainable k-means and general 4--norm clustering
In this section, we generalize Theorem 2 to the explainable k-clustering problems with assignment cost defined in terms of the fy-norm, which includes the explainable k-means (p = 2) problem.

---

Recall that in Section we sample cuts from the uniform distribution over AllCuts, and consequently, the probability that point E X is separated from its closest center ((x) is proportional to the ( distance between æ and (1:). However, selecting cuts according to the uniform distribution can be arbitrarily bad for higher p-norms even in one-dimensional space. For example, consider the k-means (i.e. p 2) problem with d = where the cost of assigning point z: to center μa is defined as x 14 12. Suppose we have two centers μ³ -1 and μ² D > 1, and fix one data point æ = O. The closest center to ø is u and hence the original cost is 1. However, the expected cost of a uniformly random cut is ((D. 1 + D2) (1 + D) = D which can be arbitrarily large.
To avoid such drastic costs, we sample cuts from generalized distribution. Ideally, we would like to sample cuts analogously the case of k-medians so that the probability that we separate a point from its closest center π (xx) is proportional to || Txx) lg. However, sampling from such distribution seems very complicated if all possible. Instead, we sample from a slightly different distribution: Namely, for p-norm where the cost of assigning point x: to a center is || vily, we sample cuts (i, 8) from the distribution where the probability density function of (é, 0) is proportional
to minjels] |nr 0|p-1 the (p- 1)-th power of the minimum distance to center along the i-th dimension. We call this distribution Dp.
Using samples from D2 with modified version of Algorithm 1 yields Theorem 3 We defer the proof of Theorem to Appendix ii the supplementary material.
Theorem 3. For every p 2 1. there exists randomized algorithm that when given imput centers U = {M', ,y.....,'* outputs a threshold tree T whose expected cost satisfies
Elcost, (T) S &OOK--1 "oo"""oog'/ k)) -csstppp) (U).
Lower bound
In this section we show how to construct an instance of the clustering problem such that any explainable clustering has cost at least 10(k-11) times larger than the optimal non-explainable clustering for the objective function given by ép norm, for every p 2 1. In particular, for = 2, this entails an ((k) lower bound for (explainable) k-means.
Let m be a prime. Our hard instance is in Rd for d = m - (m - 1) and the set of dimensions corresponds the set of all linear functions over Z.m. with non-zero slope. That is, we associate the i-th dimension with the function fi + (a,æ + by) mod m, where
1 + [i/m] and b; = i mod m. Consider & = m centers J y.,..., 11* such that the i-th coordinate of the j-th center is given by 3 = fj)... For each center μe we create a set of 2d points By, each point differing from the center in exactly one dimension by either -1 or +1, i.c., B, = {يع + c e I E {-1, 1], E [d]] where et denotes the standard basis vector in the i-th dimension. Then, our hard instance just USe(N] B,
Since every point is at distance exactly from its closest center, the cost of the optimal clustering OPT equal to the total number of points n 2dk (regardless of the lp norm). We prove, in Appendix D in the supplementary material, that:
Claim 1. Any two centers are at the same distance 8 = (dd from each other.
Claim 2.
Any nontrivial threshold cut, i.e., one that separates some two centers, separates also some two points from the same By.
It follows that, in any explainable clustering, already the first threshold cut (from the decision tree's root) forces some two points from the same set B, to eventually end up in two different leaves, and hence at least one of the & leaves has to contain two points from two different B, ss. The distance between these two points, by the triangle inequality, is at least 2, and therefore the cost of the explainable clustering is at least 1(8%) M(dk"), which is 1(kp-1) OPT.
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Swiss National Science Foundation projects 200021-184633 "Randomness in Problem Instances and Randomized Algorithms" and 185030 "Lattice Algorithms and Integer Programming."
References
[1] Sara Ahmadian, Ashkan Norouzi-Fart Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal dual algorithms. SIAM Journal on Computing. 49(4). 2020.
[2] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithuss, SODA 2007, pages 1027-1035. SIAM, 2007.
[3] Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k- k-median and positive correlation in budgeted optimization. ACM Transactions Algorithms, (32)):3:1-23:311 2017.
[4] Moses Charikar, Sudipto Guha, Eva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median prohlem. Journal of Computer and System Sciences, 65( (5(1):129-149, 2002.
[5] Moses Charikar and Lunjia Hu, Near-optimal explainable k-means for all dimensions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM, 2022. To appear.
Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian Explainable k-means and k-medians clustering. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 7055-7066 7065. PMLR, 2020.
[7] Hossein Esfandiari. Vahab Mirrokni, and Shyam Narayanan. Almost tight approximation algorithms for explainable clustering. In Proceedings of 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM, 2022. To appear.
[8] Michael Fredman. János Komlós, and Endre Szemerédi. Storing sparse table with o(1) worst case access time. Journal of the ACM, 31(3):538 544, 1984.
[91 Tapas Kamunga, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geomerry: Theory and Applications, 28(2-3):89-111 2004.
[10] Eduardo Sany Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 5915-5925. PMLR, 2021.
[11] Stuart P. Llayd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129- 136, 1982.
[12] Konstantin Makarychev and Liren Shan. Near-optimal algorithms for explainable k-medians and k-means. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 7358-7367. PMLR, 2021.
[13] Christoph Molnar. Interpretable Machine Learning.
2019.
https://cchrsstoplm..e thw.ppp.mmm...uuu....oo.um..h.ee 1o/
interpretable sittrppretablemm--boole. mlobook/
[14] W. James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, 16(44))22071-220 -20000 2019.
[15] Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pages 1135-1144 144. ACM, 2016.
[16] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
11


Reviews:
[{"review_id": "lhqK3UzonF_", "reviewer": "Reviewer_tp15", "summary": "This work provides novel algorithms for explainable clustering, which achieve smaller approximation constants compared to the previous state of the art results. The approximation constants are measured relative to the unconstrained given clustering instance. The paper handles a wide set of cost functions, e.g., k-means, k-medians, and in general l_p norm objective functions.\nThe authors also improve the existing lower bound on the explainable clustering approximation factors. \nThe above results imply that the algorithms presented in the paper achieve nearly tight approximation constants.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The paper is very well written. It smoothly guides the reader through the results and claims.\n- I liked the given algorithms and their theoretical bounds, specially when accompanied by the new lower bound.\n- The overview of Algorithm 1 and the proof outline are very helpful.\n- The presented algorithm and its required modifications are generally very clear and easy to implement.\n\nCons:\n- Regarding the cost function definitions: The k-medians cost function handled in this paper is the sum of l_1 distances between every input point to its closest center. However, in many different papers that handle clustering, the k-medians cost function is defined as the sum of l_2 (Euclidean) distances between every point and its closest center (or generally, in the l_p clustering task, the cost is the sum of l_2 Euclidean distances to the power of p). See e.g.,\n(i) Arora, Sanjeev, Prabhakar Raghavan, and Satish Rao. \"Approximation schemes for Euclidean k-medians and related problems.\" Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. or\n(ii) Feldman, Dan, and Michael Langberg. \"A unified framework for approximating and clustering data.\" Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011.\nIs there a reason for this difference?\nIs it possible to generalize the given results to handle the k-medians cost function defined in the above papers? \n- All the results seem to hold only in expectation. Is there a hope to develop a bound on the worst case probability of success?\n- I am missing some simple experiments that test the empirical approximation constants, and compare the empirical results with previous algorithms, e.g., that of [9].\nFurthermore, as common in theory papers, the empirical approximation factor are usually smaller than predicted by the worst case theory. Has this been tested? Is this also the case here? \nAs the algorithms presented in the paper are very simple, I do not see why not to conduct such experiments.\n- The paper lacks a discussion / conclusion / future work section.\n\n\nMinor comments:\n- At Line 325, the authors claim that \"sampling from such a distribution seems very complicated if at all possible\". Can the authors elaborate more on why this might not be possible?\n- Line 350: \"We prove, Appendix D ..\" -> \"We prove, at Appendix D...\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ewQ116-2ji", "reviewer": "Reviewer_Hp5d", "summary": "Moshkovitz et al. recently propose a formal method to explain clustering algorithms: Build a decision tree where each internal node separates the points into two parts based on one dimension and a specific threshold.\n\nThe obvious question is price of explainability in this regime (with respect to the objective of k-means, k-median or some other \\ell_p norm). Prior to this work, the best upper bounds were k (for k-median) and k^2 (For k-means), and the lower bound was log k. For small dimension d, one factor k in the upper bounds could be swapped with d log k.\n\nThis work makes a serious attempt at closing the gap.\n1) They give k^{p-1} log^2 k upper bound (log^2 k for k-median and k log^2 k for k-means).\n2) They give a lower bound of k^{p-1} (which means k for k-means).\n\nThe new results have two main ingredients:\n1) Previous work did not use randomization. Given a non-explainable clustering, they would successively find a threshold cut (separating at least two clusters) that had the smallest \"error\" (in terms of assigning points to clusters). The new result uses randomization here.\n2) The straightforward analysis brings in the depth of the tree into the approximation factor, which can be as bad as k (think of basis vectors). The authors show how to better charge the final error to opt and bring down the approximation factor.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Important topic, significant contribution. As the bounds are still bad for k-means, we probably want to look at other ways to explain clusters.\n\nThe writeup is not difficult to read. Experimental study would be nice to have to establish the relevance of improved bounds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "I don't think so", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "PU9ViRsan7", "reviewer": "Reviewer_X5Zn", "summary": "A clustering is explainable if its cluster is partitioned by a decision tree whose internal nodes are axis-parallel lines. Given a reference clustering, usually a set of k centers, the goal is to transform it into an explainable clustering with a small factor increasing in the objective. \n\nThis paper provides new algorithms and improved analysis for explainable k-median and k-means clustering. For k-median, their analysis shows the algorithm achieves an O(log^2 k) *OPT objective when transforming an optimal clustering with objective value OPT. For k-means clustering, they achieve an O(k log^2 k) upper bound. A new lower bound for explainable k-means clustering is also provided in this paper.\n\nTheir results improve the original paper of Moshkovitz, Frost, Dasgupta, and Rashichian, which gives the upper bound of O(k) and O(k^2) for k-median and k-means.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I agree with the motivation of explainable clustering. To decide the cluster of a single point with a decision with the form I[x_i<=c] is a user-friendly structure. \nThis paper is an addition to this topic. For k-median clustering, their analysis shows we only need to afford a poly(log k) factor to transform a non-explainable solution to an explainable one. \nTheir algorithm is very simple. The analysis uses new observations and gets rid of the dependence on the height of the decision tree, which is Omega(k) in the worst case.\n\nSome comments/questions:\n1.  The authors conjecture their algorithms are tight but their analysis is not. I suggest such a statement should only appear in the Limitation paragraph. Currently, it is mentioned in multiple places in the main text, e.g. Line 246.\n2. As the algorithm is simple, and the k-median clustering only has a poly(log k) loss, it will be convinced to implement the algorithm and run experiments on real data. \n3. Is there any possible reason why there is a polynomial gap between the upper bounds of loss for explainable k-median and k-means? Why is explainable k-means inherently harder than k-median?\n\nEvaluation: I do think this paper has some interesting results. While these results look incremental upon Moshkovitz, Frost, Dasgupta, and Rashichian. The algorithm seems to be simpler than the previous work. Implementation of the algorithm will certainly earn more credits on novelty. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "KYvxODGvadz", "reviewer": "Reviewer_skXW", "summary": "This paper considers the explainable k-clustering problem with respect. Here we are given points in Euclidean spaces and seek to impose a decomposition of the space by orthogonal queries such that there exists a bijection between clusters and leaves of the decomposition. For this problem, the authors give a $\\log^2 k$ approximation for k-median and a $k\\cdot \\log^2 k$ approximation for $k$-means. Furthermore, the authors provide nearly matching lower bounds.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The algorithm proposed here is very simple  which is a good thing. Given a $k$-clustering that is not necessarily explainable, the authors give a black box transformation that makes the clustering explainable. What is nice about this is that, given the centers of the clustering, it is not necessary to scan the input again, i.e. the computational overhead is basically non-existent.  \n\nFor $k$-median, one merely samples cuts from the box bounding all the centers uniformly at random. The algorithm recurses on the set of non-separated clusters. For higher powers such as $k$-means, the authors prove a polynomial lower bound, separating k-median from k-means, along with a nearly matching upper bound. The algorithm for this case is similar; the main difference is that the cuts are only sampled among the cuts with enough separation.\n\nI like the algorithms, which are very simple, as well as the analysis which is elegant. The nearly matching lower bound constructions are also nice. The negatives, if any, are not really the author's fault: I think that explainable clustering is an artificial problem that has little to no bearing on the use cases of $k$-clustering. My opinion was only reinforced by the large separation between $k$-median and $k$-means. One could also take this complaint as an affirmation of these results, with the authors demonstrating that perhaps \"explainability\" as it has been defined is not a meaningful notion for higher powers (which also puts it into question for $k$-median). In any case, I think it is good that this problem has now been resolved.\n\nUnfortunately, the authors have been scooped by two recent ICML papers from Makarychev and Shan and Laber and Murtinho. The second paper by Laber and Murtinho has generally weaker (though not completely comparable) results and a more expensive algorithm with not the clean analysis presented here. The first paper by Makarychev and Shan has very similar results, both in terms of bounds as well as algorithms compared to this submission. I believe that the authors were not aware of these prior results, but the question is what to do about this paper (as well as at least 2 other papers in a similar situation -- if these papers are not known to the PC then I can provide arxiv links). Once the ICML proceedings are out, barring an improved analysis with not \"essentially matching\" bounds, but actually tight bounds, I believe that the 3 papers on explainable clustering will become unpublishable, or only publishable at smaller, less prestigious venues. What improvement there is in terms of bounds is only in terms of $\\text{polylog } k$ factors for both the submission under review here and the other two papers that I believe have also been sent to NeurIPS, along with minor improvements in the low-dimensional regime.\n\nJudging this paper in isolation, as I believe one should, it would have been a clear accept. The unfortunate circumstances that this papers finds itself in does not change my impression of the paper, which is positive, so my rating reflects that. Ultimately the question of acceptance is not on a scientific basis but on a policy basis.\n\nHowever the PC decides on this paper, fairness dictates that all 3 explainable papers submitted to this NeurIPS should either be accepted or rejected (I am not affiliated with the authors of any of these submissions). In terms of merit, there is no reason to favor one over the other, in my opinion, and while all bounds and algorithms are similar, I think that every analysis is unique enough (in my current understanding) to merit acceptance. I therefore encourage the chairs that are responsible for the other papers to reach a consensus for all of the papers, given the rather unique situation. While I believe that it would be deserving if this paper and its competitors gets accepted, if everyone gets rejected then it will be disappointing but nevertheless fair and understandable for all parties.\n\nFinally, as a side-issue: I believe that this should trigger an open discussion on what NeurIPS policy is on multiple submissions with similar results (including submissions to other conferences overlapping with the NeurIPS submission cycle). To the best of my knowledge there is no policy here, but I think having a unified guideline would make both reviewing and coordination simpler and more predictable. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not necessary for this paper", "review_text": "", "extra_scores": {"ethical_concerns": "Not necessary for this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 (including checking the other papers)"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Considering that the ICML papers are concurrent works, the results in the paper are substantial improvement over previous works in several interesting problems. In the camera-ready version, please include a comparison with the concurrent works and highlight the unique insights and techniques developed in this paper.
Decision: Accept (Poster)