Random Cuts are Optimal for Explainable k-Medians
Authors: Konstantin Makarychev
Liren Shan
Venue: NeurIPS 2023 oral (2023)
Keywords: Clustering
k-medians
Decision Tree
Explainability
TL;DR: We provide the optimal competitive ratio for explainable k-medians.

Abstract: We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable $k$-medians in $\ell_1$. The problem of explainable $k$-medians was introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian in 2020. Several groups of authors independently proposed a simple polynomial-time randomized algorithm for the problem and showed that this algorithm is $O(\log k \log\log k)$ competitive.  We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by $2\ln k+2$. This bound matches the $\Omega(\log k)$ lower bound by Dasgupta et al (2020).

Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev Northwestern University
Liren Shan" TTIC
Abstract
We show that the RANDOMCOORDINATTECTT algorithm gives the optimal compet- itive ratio for explainable k-medians f, The problem of explainable k-medians was introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian in 2020. Several groups of authors independently proposed a simple polynomial-tine algorithm for the problem and showed that this algorithm is O & log log k) competitive. We provide tight analysis of the algorithm and prove that its compet- itive ratio is upper bounded by 2 In k + 2. This bound matches the Stoo k) lower bound by Dasgupta et al (2020).
randomized
Introduction
Machine learning is being increasingly used to make decisions for critical applications, such as healthcare, finance, and public policy. Considering the profound impact of algorithmic decisions on individuals and society, it is essential to understand the underlying logic behind these decisions. In this paper, we explore an explainable k-medians clustering algorithm (called RANDOMCOORDINATE. CUT). The algorithm's 's aim is to cluster data sets and present results in manner easily understood and visualized by humans.
Clustering is fundamental task in unsupervised learning, Among many clustering methods, k- k-means, k-medians, and k d-medoids are particularly popular. These are centroid- based methods that choose centers and assign each data point to the center nearest to it. As result, each cluster is a Voronoi cell in the Voronoi partition of the space. Since these cells may have complicated boundary (see Figure for an example of k-medians), it is not always easy for humans to comprehend and visualize such clustering.
To address this problem, Dasgupta, Frost, Moshkovitz, and Rashtchian [2020] introduced explainable k-means and k-medians clustering. They argued that decision trees easy understand and interpret. Therefore, in order to make clustering more explainable, we need to use threshold decision trees to define clusters. A threshold decision Each internal node of the threshold decision tree splits the data into two groups using threshold cut (j, (): on the one side the cut, we have points æ with 2j S and, on the other side, points x with rectangular region of the space. A decision tree with leaves partitions data set X into clusters, Pı...., Pt. See Figure for an example. Dasgupta et al. [2020] suggested that we use the standard k-medians and k-means objectives to measure the cost of the threshold decision tree. For k-medians, the cost of a threshold decision tree equals
is binary space partitioning tree with l leaves.
Ty >> 0. Thus, every node of the tree corresponds
cost (X, = Σ Σ
-
i= xIE.
where Pj.... Pt is the partitioning of X produced by T: and غt ....,. a are the medians of clusters PI..... Pt. We denote the l fnmm by || 1/1. Note that each P, is a rectangular region of the space. Thus, generally speaking, every x is not assigned to the closest center č² ,....." zk like in unconstrained k-medians k-means.
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

20.0
200
y S 8.6
17.5
175-
150
100
3,00
x S -1.9
75
75
50
1100 -7.
-5.0
-25
0.0
2.5
5.0
10.0
0.
-30.0
-7.5
-5.0
-2.5
0.0
2.5
5.0
7.5
16.0
Figure 1: The unconstrained k-medians clustering and explainable k-medians clustering. The left diagram shows the Voronoi partition of the plane w.r.t three centers in & distance. The Voronoi cell for each center consists of all points that are closer (in l distance) to this center than any other center (the boundaries between cells are not straight lines because we use the & distance). The middle diagram shows explainable partition. The right diagram shows the corresponding decision tree for explainable clustering.
Dasgupta, Frost, Moshkovitz, and Rashtchian [2020] defined the price of explainability as the ratio of the k-medians cost of explainable clustering to the optimal cost of unconstrained k-medians clustering. They showed that the cost of explainability for k-means and k-medians (somewhat surprisingly) does not depend on the number of points in the data set X and only depends on k. Specifically, they provided greedy algorithm that given reference centers c' .c² ..... c of any unconstrained k-medians as input, outputs threshold decision tree of cost at most O(k) times the cost of original
unconstrained k-medians with centers c², c², ...... . We call such an algorithm ((k) competitive. To get an explainable k-medians clustering, we first obtain reference centers c¹ c',?? ..... c² using an off-the-shelf approximation algorithm for k-medians and then run a-competitive algorithm for explainable k-medians with centers c¹ c,, .... c² given as input. This algorithm produces the desired threshold decision tree. Dasgupta et al. [2020] also gave O(k2) competitive algorithm for k-means and showed 2(log k) lower bounds on the price of explainability for both k-medians and k-means.
The notion of explainable clustering immediately got a lot of attention the field (Laber and Murtinho [2021], Makarychev and Shan [2021], Gamlath et al. [2021], Charikar and Hu [2022], Esfandiari et al. [2022]). Particularly, Makarychev and Shan 2, Esfandiari, Mirrokni, and Narayanan [2022] provided almost optimal algorithms for explainable k-medians, and Makarychev and Shan [2021], Esfandiari, Mirrokni, and Narayanan [2022], Gamlath, Jia, Polak, and Svensson [2021] 1] provided
almost optimal algorithms for k-means. The competitive ratios these algorithms are Ó k) for k-medians and ((k) for k-means.
The algorithms for explainable k-medians by Makarychev and Shan [2021], Esfandiari, Mirrokni, and Narayanan [2022], Gamlath, Jia, Polak, and Svensson [2021] are variants of the same simple This algorithm receives set of k reference
algorithm, which we call RANDOMCOORDINATTEC centers .'...., c as input and then builds a threshold decision tree with & leaves. It works as follows. It recursively partitions d-dimensional space until every cell contains exactly ct. The algorithm starts with a tree consisting of one node, the root. Initially, all A: reference centers assigned that root. At every step, the algorithm picks random threshold cut (j. 0) and splits centers in every cell using this cut. If this cut does not separate any centers a cell u (i.e., all centers in are located one side of the cut), then the algorithm does not split into two regions this step. Finally, for every leaf u of the constructed tree, the unique center that belongs to the cell corresponding to u is assigned u. We provide pseudo-code for this algorithm in Figure 2.
reference center
Makarychev and Shan 1, Esfandiari et al. [2022] showed that the competitive ratio of RAN- DOMCOORDINATECUT is at most Olog & log log k). That is, for every data set X and set of centers c². cl.....ch
E Bcoost X, (XT))= < O(log & log log k)
Σ min ||0 - cll2-
oE(c cElce.....ee .....kk
xEX
Note that the running time of this algorithm is Ökd)). Gamlath, Jia, Polak, and Svensson [2021] provided slightly worse bound of Ollog" k) on the competitive ratio of this algorithm. They also

---

Input: a data set X C Rd and set of centers = {cl, ,r, c CR
Output: threshold tree T
Create tree To containing a root node Assign C, = [ct, c², 22,... , to the root. Let / 0.
Let maxij le)l-
while Tn contains a leaf with at least two distinct centers do
Pick coordinate j and threshold E (-M, .M) uniformly at random. Let wn (i,
For every leaf node u in Tas split the set C₂ into two sets:
Left fc E C : Cj S 0}
and
Right = {c Cv : > 0).
If both not empty, then create children of a in tree Tr. The left child corresponds to the subregion of u with x., S 0, and the right child corresponds to the subregion of with z; 0. Assign sets Left and Right to the left and right child, respectively.
Denote the updated tree by T1+1-
Update = +
end while
Figure 2: RANDOMCOORDINATECCUT algorithm
conjectured that this algorithm is optimal and its competitive ratio is Ollog k), more specifically, Ha-1 + 1, where HE is the k-th harmonic number. They provided some justification for their conjecture by proving this bound for very special set of centers and data points (corresponding to the case of completely disjoint sets in our Set Elimination Game).
Our Results. In this work, we show that indeed the competitive ratio of CANDOMCOORDINATICO most In k 2, and, therefore, this algorithm has the optimal competitive ratio which matches the lower bound of Dasgupta, Frost, Moshkovitz, and Rashtchian [2020]. Our analysis is not only tight but also fairly simple. To get our result we define a game, the Set Elimination Game, which was also implicitly analyzed in previous works on this topic. We show that the cost of this game is at most Iu k 2.
The unconstrained k-medians clustering has been extensively studied. Charikar, Guha, Tardos, and Shmoys [1999] gave the first constant factor approximation algorithm for the problem in general metric spaces. Li and Svensson [2013] provided 1 v3 + approximation algorithm. Byrka, Pensyl, Rybicki, Srinivasan, and Trinh [2017] improved the approximation factor to 2.675 Cohen-Addad, Esfandiari, Mirrokni, and Narayanan [2022] recently improved the approximation factor to 2.406 for Euclidean k-medians. Megiddo and Supowit [1984] showed that the k-medians in problem is NP-hard. Cohen-Addar and Lee [2022] showed that is also NP-hard to approximate k-medians in L within factor of 1.06.
Related Work.
As discuss above, Gamlath, Jia, Polak, and Svensson [2021], Esfandiari, Mirrokni, and Narayanan [2022], Makarychev and Shan [2021], independently proposed the WOANDOMCOORDDAAAATT algorithm. They also gave an (k) algorithm for explainable k-means and showed lower bound of Ộ(k) for the problem. Charikar and Hu [2022] provided an O(K1-2/d poly(d, log k)) competitive algorithm for explainable k-means, whose competitive ratio depends the dimension d of the instance. For small d < log k/ log log k, their bound is better than (k)). They showed an almost matching 22k222/d/pll /ploy log k) lower bound for explainable k-means. Esfandiari et al. [2022] gave an upper bound of Odd dl) on the competitive ratio of RANDOMCOORDINATECU for explainable k-medians. This bound better than Ollog k) for small & log k/ log log k. Laber and Murtinho [2021] gave (dd log k) and Oddk log k) competitive algorithms for explainable k- medians and k-means, respectively. Frost, Moshkovitz, and Rashtchian [2020] provided some empirical evidence that bi-criteria algorithms for explainable k-means (that partition the data set into (1 + 5)k clusters) can give a much better competitive ratio than Okk). Then, Makarychev and Shan [2022] gave a Ö(} log² k) competitive bi-criteria algorithm for explainable k- k-means. Bandyapadhyay, Fomin, Golovach, Lochet, Purohit, and Simonov [2022] provided an algorithm
3

---

that computes the optimal explainable k-medians and k-means clustering in time n n22+0(1) and (And)*+0(1) respectively. Laber, Murtinho, and Oliveira [2023] proposed to use shallow decision trees for explainable clustering.
Independently and concurrently with our work, Gupta, Pittu, Svensson, and Yuan [2023] proved a Ollog k) bound on the price of explainability for k-medians. They showed that the competitive ratio of MRANDOMCOORDINATEECCC answers the open question raised by Gamlath, Jia, Polak, and Svensson [2021]. They also proved hardness of approximation result for explainable k-medians clustering and improved the competitive ratio for explainable k-means from O( log k) to O(k log log
is + H where Hş is the k-th harmonic number. Their work
2 Set Elimination Game
In this section, we define the set elimination game. Consider discrete finite measure space (S,, p)). In this space, each element E Ω has measure of p(w), and the measure of every set S C S equals [s( = Ewes ((w)). Let S1, Sg..................... .................. Sy C f2 be & distinct sets which may overlap with each other. The set climination game proceeds in series of rounds. Initially, all sets Si,... Sy enter the competition. Formally, they belong to the set of remaining sets Rg = {S Sk J. At every round n, the host picks random Wn, E S with probability Pr(w,, = w) = p(w)/ (f)).. Then, all sets S; that contain wn are eliminated from the game unless all remaining sets contain wns in which case, no set gets eliminated. That is, for n 2 1,
Rn-1 \ {S: E Rn-1 : Wp E S if for some S, E Rn-1, Wn. $ Sy:
R₂,
R
otherwise.
The last remaining set is declared the winner. We denote that winner by winner. We say that the cost of the game the measure of the winning set, (wwinner).
We remark that R. cannot get empty (in which case, the winner would not be defined) because of the "otherwise" clause in the definition (1). We shall always assume that all sets Si..... Sx are not only distinct and non-empty but also (a) for every i, p(S)) > O, and (b) for all and j. ((S,4S,)) > 0 (here, S,A,, denotes the symmetric difference of sets S, and S,). Then, in every game, there is unique winner with probability 1.
We similarly define the set elimination game for arbitrary finite measure spaces: For an arbitrary finite measure space (S2, (t), element wn chosen with probability function Pr(w., E S) = (())
Our main result is the following theorem, which, as we discuss later in Section 2.1, implies that the competitive ratio of the explainable clustering algorithm is In k + 2.
Theorem 2.1. Consider a set elimination game with the finite measure space (2, p)) and k distinct , Sy (as above). The expected cost of the game is at most sets S -..
E [[u(winner)] < (2lnk + 2) -iin ((S.).
sE(K)
To simplify the exposition, we will prove this theorem for discrete finite measure sets. If S2 is not a discrete measure space, we first replace it with quotient space: We say that w' 52 and w" E Ω are equivalent (w' ~ w") if they are contained in exactly the same set of sets SI,..., Sz. This equivalence relation partitions into most 2* different equivalence classes. We replace Ω with the quotient space 9/~~ whose elements are equivalence classes. In other words, we merge all equivalent w's. The measure of a new element ä equals to the measure of the corresponding equivalence class.
Organization. In Section 2.1, we discuss the connection between explainable k-medians and set elimination games. We define set elimination game in set system 1 C (S1, ... S. in Section 2.2. Then, we define the hitting and elimination time in Section 2.3. In Section 3, we first illustrate our proof strategy by showing Theorem 2.1 for the case when the smallest set S₁ does not overlap with S Sg. An important ingredient of our proof is the notion of surprise sets, which we discuss in Section 1. Finally, we complete the proof of Theorem 2.1 in Section 3.2.
2.1 Explainable k-Medians via Set Elimination Game
In this section, we show how to use Theorem 2.1 to obtain a bound of 2 In + 2 on the competitive ratio of the RANDOMCOORDIATTECUT algorithm.

---

Theorem 2.2. The competitive ratio of the RANDOMCOORDINATECCUT algorithu for Explainable k-Medians at most 2 l 22 That for every set of centers C {c', ...,,.""" and data set X, the algorithm finds random decision tree T such that
Elcost X, T) (2lnk +
Σ
min
|| cll2.
2EX selchinnee
The pseudo-code for the RANDOMCOORDIAATECII algorithm is provided in Figure 2.
Theorem 2.2 shows that given any k centers C = {ct,..... )* RANDOMCOORDNATTCUT finds decision tree ' with cost at most 2 k + 2 times the cost of unconstrained k-medians with centers C' {d', .......cce. c²} By using k centers given by any constant approximation algorithm for k-medians, KANDOMCOORDINATECUU finds a decision tree with cost most Olog k) times the optimal unconstrained k-medians cost. This implies an O(log k) upper bound on the price of explainability.
Proof of Theorem 2.2. Consider an arbitrary data set X C Rd and set of l centers C C Rdd We assume that all points in X and all centers in C' are in the cube [-M, M] The threshold decision tree obtained by the R MANDOMCOORDDNNTTCC. contains single reference center e'. The center ct is not necessarily optimal for cluster P. (cluster P. is the intersection of the data set X and i-th cell). However, we will use it as proxy for the optimal center. In other words, we will upper bound the cost of the threshold decision tree as follows:
algorithm partitions the space into & cells. Each cell
cost(X,
min
Σ
I 2'1l2
S
1
c'111.
==1 ZEP;
1=1
zER;
Let Q be the set of all coordinate cuts: 12 (). jE
M]}. We define measure j
on Ω as follows. For every subset S C 52, we set
d u(S) = Σ (1.0) S}).
#=1
where frr. is the Lebesgue measure on IR. Thus, we have p(?t= 2/M, which implies (2, 11) is finite measure space.
Consider any data point E X. Define is sets S1, S Sp for the set elimination game. For every E (I, let S, be the set of all threshold cuts that separate I and center c², i.e.,
S 0) E Ω sign(a, 0) + sign(c) -0)].
Note that the l distance from x to center cf equals the measure S; ||e - dell ((S)). We now examine the set elimination game with sets SI,..., Ss. measure space (Ω, 11), and random sequence of draws w 42,... ... (each Wn E Ω is the threshold cut chosen by the RANDOMCOODINATTCCTT algorithm at step n). We claim that S; belongs to R, if and only if center c' lies in the same cell as since Ry contains all sets S1...., Sy
point after step of the algorithm. This is the case for n and the root of the threshold tree contains all centers cl ..... c Then, whenever we pick cut wn. all centers separated from I by Wn are removed from the cell of z. The only exception from this rule occurs when all centers in that cell lie on the same side of the cut wn. That is exactly the same rule as we have for the set elimination game (note that center et separated from x by Wn if and only wn. E S,). Therefore, the same sets S, remain in the game center ct in the cell of x (namely, sets S, and centers cf have the same indices).
The MANDOMCOORDINATEUUT algorithm stops when all leaves of the decision tree contain exactly one center. At this step, the set elimination game contains one set, S,. This set corresponds the center c¹ assigned to point z. The cost of the game ((S,) equals the distance from x to cf. By Theorem 2.1, we have
Elcost (x, 7) = Elu(winner)] < (2 k - 2) min p (S,) = (2 + +2) min ||x - c'll
We sum this bound over all data points x in X and get the desired result.
5

---

2.2 Local Competitions
We now revisit the definition of the set elimination game and define competitions in subsets of {Si...., ..). For the rest of the proof, we assume (S2, (4) is a discrete finite measure space. We remind the reader that every set elimination game is determined by an infinite sequence of i.i.d. random variables wi, .2..... In each round n, we sample an element win from Ω with probability Pr(w., = w) = pl)).
Definition 2.3. Consider a finite measure space (9, Let be set of subsets Q. We say that I a valid set system if (a) for every I, ((S) > O, and (b) for every S' S E 1(S' A.S") ) > O.
The reader may assume that uu)) > 0 for all w in Q. Then, the definition above says that in valid set system I, all sets non-empty and distinct.
Definition 2.4. Consider a finite measure space (St, 11). Let w1, w2, as described above and I be valid set system. We define a set elimination game in I. Initially, (I( = 1. Then, for every n. 2 1,
be i.i.d. ...
random variables
(R)-1(1) -1(1))((--11))) (8 Rn-1(1): Wn E S}, for some S' Rn-1(1), Wn & S': R. R,, ( (I))
(2)
otherwise.
The winner of the game in I, denoted by winner(I). is the only element remaining, or, formally, the unique element On20 (T). If (0, contains more than one element, then the winner is not defined. The cost of the game is the measure of the winner, j((wineer[)))
We remark that Nn20R (I) contains exactly one element with probability 1. Thus, the winner and cost of the game are defined with probability 1.
Consider sets , Sg from Theorem 2.1. Denote K = {S S The definition of the competition among sets Si,..., S₂ (given in the beginning of Section 2) is exactly the same as the definition of competition in K. Our goal is show that [[jinnee K))] S 2(I k: +1)- ming,eK (S:)). In the proof of Theorem 2.1, we will consider competitions in different set systems I ICK. We show the following key lemma. We defer the proof of Lemma 2.5 to Appendix A.
Lemma 2.5. Consider a partitioning of the set system K = {Si....,$4 into m sets Ti...., J Then, winner(K) E
2.3 Set Elimination with Exponential Clock
Consider a set elimination game on sets , i..d. draws W1, w2. .... Random variable wn is chosen round n. We assign every round a random time Ta- Let the time between two consecutive rounds be an exponential random variable with parameter p(2)). Specifically, let Ar1, Ar2, ... be a sequence of i.i.d. exponential random variables with parameter ((2t) and each Tn Tn-1 + Ar, = An + ... + AT.. Note that all AT, are positive and Tı, T2. ... an increasing sequence with probability 1. The number of draws that occur by time t (i.e., (2)) = In:
Sk. It is determined by the sequence of random
S +) is Poisson process with parameter f((2).. We now can think of the set elimination game as follows: The host the game observes Poisson process with parameter u()). Whenever the process jumps (at time T.). the host picks element wn. in Ω with probability Pr(w,, = w) = ((w)/ and eliminates some sets according to the rules of the game discussed above. Note that by assigning every round some time Tn. we do not change the game, the winner, and the cost of the game (because the sequence of random draws W1, W2,... remains the same as before). This interpretation of the game allows to introduce hitting time h(S) of every subset S C. Ω with the following properties: (a) each h(S) is an exponential random variable with rate u(S); (b) hitting times of disjoint sets are mutually independent random variables.
Definition 2.6. For every subser X C 9 the hitting time h(X) is the time Tn when the first Wn is drawn from X: h(X) min Wn X). When the set contains one element w, we will write h(W) instead of (((w))
We also define the elimination time of each set St.
Definition 2.7. Consider any set elimination game with the measure space (Q,, 1)) and sets S1. S2...., Sk in Ω. The elimination time e(St) of set S; is the time when set S is eliminated from the game, Le., e(S,) = min St & R, [)). If St is the winner, then we let e(S.) = oo (because the winner is never eliminated).

---

Note that e(S.) 2 h(S)). Sometimes, e(S)) may be equal to h(S)), but e(S,) and h(S,) are not always the same. We now prove that hitting times for disjoint sets are independent. To this end, we splür the Poisson process (2) = [ Tn S 4-1- Let N.(w)) In Tn I L and wn = w/l- It easy to see that (S2) = Σ Een (w: for every t. also true that each Ne(w) is Poisson process with parameter (lww) and all (w) (for W {2) are mutually independent. This fact follows from the Coloring Theorem (see e.g., Kingman [1992], Coloring Theorem, page 53).
Theorem 2.8 (Coloring Theorem). Let 1I, be a Poisson process on the real line with rate X. We color each event of the Poisson process randomly with one of M colors: The probability that a point receives the i-th color is Pt. The colors of different points are independent. Let I1((i) be the number of events of color in the interval (0,t), Then, (1)....... IIM(M) are independent Poisson processes. The rate of process (i) is Xp:-
Lemma 2.9. For every w E S2 h(w) is an exponential random variable with parameter p(w), and all random variables h(w) (for w E Q2) are mutually independent.
Proof. Observe that h(w) = min(t: Ni(w) 2 1}. Thus, h(w) is an exponential random variable (the time of the first jump of Poisson process) with rate n(w).. Also, since all (w(w)) (for Q)) are mutually independent, all h(w) are also mutually independent.
Note that the set climination game depends only on the hitting times for elements w in Q. This is the case because matters only when every w is drawn the first time. At that time - the hitting time of all sets that contain same w is drawn again, it does not eliminate any new sets. Also, note that for any set S C Ω the hitting time h(S)) minwes h(w). Thus, hSS) is an exponential random variable with parameter (SS)= = EEves ((w)).
eliminated unless all remaining sets contain this w. When the
3 Proof of Main Result
We now present the proof of our main result, Theorem 2.1. We assume without loss of generality that S is the smallest set i.e., p(S1) S ((S)) for all i. Then, the expected cost of the game is at most:
k
((S)) + Σ 2
Pr (S: = (iiner((K))
We first provide some intuition for the proof by considering the case when S does not intersect with sets S2 ................. ,, Sg. i.e. sets S₁ and S, are disjoint for all 2, 3,..... ,,, k. We split all sets into two groups S₁ and the rest of the sets S2....,Si St. We know from Lemma 2.5 that the winner among Denote I- {S Sk). Each set S, is eliminated time eSS)). The set S is eliminated at its hitting time h(S,) ) unless it is the only remaining set at time h(S)) (because we are considering the case when S₁ does not overlap with other sets). Thus,
all sets Si...., S& is either S₁ or winner (fS2....,,$.)
if ((S)) > e(winner (I-); )); winner(T-), if el e(winner(T-)) > h(S1). winner(K). =
{
S1,
(4)
When the winner among S1,..., Ss is not S1, we consider two cases of the winner S (1) St is surprise set; (2) St is a non-surprise set.
Definition 3.1. We say that S; is a surprise set efe()) Z M(S1) 2 L/N(S,), where L = In k.
We call S. a surprise set because the probability of the event e(S,) 2 h(S)) 2 L/u(S,) is small. We give bound on the probability of e(S,) 2 h(S))) 2 L/P(S,) in Lemma 3.3. Here, we provide some intuition. By Lemma 2.9, the hitting time h(S.) is an exponential random variable with parameter ((S)). Thus, the expected hitting time for S; is 1/))S.). Consider a set S; with a small measure (u(S,) is close to ((S)) )). If the hitting time h(S)) 2 L/p(SS). then h(S)) is much larger than its expected value 1/u(Si). which happens with small probability. Consider set S; with a large measure p(S)) >> p(Si). Then, the expected hitting time for S, is 1 1/p(S.), which is much smaller than the expected hitting time of Sj. Thus, the event e(S,) > h( ((S1) occurs with a small probability.
7

---

Let us examine bound (3). Let Surprise be the set of all surprise sets. Note that Surprise is random set. Then,
Pr (S: = winner((K))
Σ Pr (S. = winner(K), S & Surprise) ((()) (5)
2
i=2
Σ 2m
Pr (S, Surprise) ((S)).
We show in the next section (Lemmaa 3.3) that the second sum is upper bounded by f(S1). We now bound the first sum. For every winner S, which not surprise set, we have e(S.) h(1 (because S; is the winner) and h(S)) I L/p(S;) (because S; is not a surprise set). We also have S. winner(7-) thus
Pr (S: = winner(K), S, & Surprise) S Pr (h(()) S L/n(S.) and S; winner([-)).
By Lemma 2.9, all hitting times hSS)) = minwes; h(w) for 2 2 are independent from ((i)). Thus, winner( [-) is also independent of h(s)) (winner(T-) depends only the hitting times for sets S, E )- Therefore,
Pr (S; winner(K), S; & Surprise) S Pr (h(S)) S L/M(S.)) Pr (St winner(!-))
(1-e-L(Si/A(ss)) Pr (S: winner(T-))
SLp(St)/U(Sa)
< Pr (S; = winner(r-)) L. ((S:)//((.))
We combine all bounds on terms of (5) and get the following bound on the expected cost of the game:
k
(AS)) +
Σ PS winner(T-)) L. ((S)) + ((S1) = (L. + (((:)) = (In k: + 2) (((i)).
1=2
This concludes the proof of the theorem for the case when S1 does not overlap with S2, ... Sk. We now analyze surprise sets.
3.1 Surprise Sets
In this section, we prove a bound on the probability that a set S; is surprise set. We no longer assume that S₁ does not intersect with other sets S,. We first show a lemma about exponential random variables.
Lemma 3.2. Let X and Y be two independent exponential random variables with positive parameters Xx and Xy, respectively. Then, for every T 0, we have
Ax
Pr 2 x T)
Ax + Ay (Ax+AVIT
(6)
Proof. The desired probability can be casily found by computing JT (Fx - (((() where (L) 1 - - is the cumulative distribution function of X, and fv(1) Xy e Avt the probability density function of Y. Here, we give an alternative proof. Write,
Pr (Y x T) Pr (Y 2 X & min (X, (X,Y) 2 2)
Pr (x Y min (a,inn(XX)))) Y) 2 T) Pr (miim(XX)))21
We have Pr ( (mni(XXY) 2 7) - (Ax )T because the minimum of two independent exponen- tial random variables with parameters Ax and xy is an exponential random variable with parameter Ax + Ayy Then, Pr (X < Y min X, Y) 2 T) = Pr (X < Y) because the exponential distribution
memoryless; and Pr (X Y) = Ax / (Ax + Ay).
Lemma 3.3. For every set S,, we have
Pr(S, is surprise set) - (())
((S))
8

---

Proof. First, we show that min(e(()), h(S))) & h(S, \ S1). Claim 3,4. We always have min(e(S,), h(S:)) - h(s; \ S.)).
Proof. Consider an arbitrary realization of the game and the time t = h(S; \. Si) when S \ Si is hit. by this time, S1 has already been hit then h(ii) < t. Similarly, if by this time, St has already been eliminated then e(S)) < t. Otherwise, both S and S, are still remaining in the game time t. Therefore, when we pick w E S \ S1 at time t, set S; gets eliminated (since w E S w & S1; both S1 and S₃ are remaining in the game). Thus, in this case, e(S,) t. This concludes the proof. O
If Sg is surprise set, then min(c h(S,)) M(S)) L/)( By Claim 3.4, we have h(S, \ S1) 2 min ((S)) = ((S)) 2 L/
Thus, Pr(S; is surprise set) = Pr (h(S. S1) 2 b(S)) 2 L/p(S))) By Lemma 3.2 applied to the independent exponential random variables h(S1), h(S, S1). and time T = L/ we have
(((1))
Liafs 1(a(8 (8)))(11))
1 n(Si) < K u(S()
Pr(S; is surprise set) S M(S; \(1) ((S))
(9
L
3.2
General Case
Proof of Theorem 2.1. We upper bound the expected cost of the game for arbitrary sets Si...., .a.....,s, Sk- As before, we assume that S is the smallest We remind the reader that each hitting time (S,)) is an exponential random variable with parameter (=(S)). .. In the proof, we will use the definitions of surprise sets (see Definitions 3.1). We also set L = In k. We define all sets S for o that not surprise set to be non-surprise sets.
We separately upper bound the cost of the winner depending on whether the winner is (a) set Si, (b) surprise set, (c) non-surprise set. Write
E [[u(winner(K))) (K))
E [u( ((wwinee((K) (K)) 1 [winner(KK) =SHH]
(a)
+ p (winncr( K)) 1 (winner is surprise set}
(b)
+ E (winner(AN) K)) 1 (winner is non-surprise set}
(c)
Term (a) is upper bounded by ((S)). We bound term (b) using Lemma 3.3: The probability that set a surprise set is at most l/4 ((.))) Thus, the expected total measure of all sets (not only the surprise winner) is upper bounded by & E ((S)) ((S)) < ((S)).
((S1)
((S))
We now bound term (c). Define (S,),, where S; is the winner) if (1) the winner is a non-surprise set, and (2) w is the first element that chosen in St. We let cost (w) = 0, otherwise. If w is the first element that chosen in Si, then h(Si) =
random variable: Let cost(w) be the cost of the winner (i.e.,
h(w)). So, the definition of (wst can be written as follows:
cost (w) = ((winnor(K]) K)) 1 1(h(S)) = h(w)) 1 [winner((K) ()) & Surprise).
Since the hitting time h(S)) finite with probability 1, the term (c) equals
(c)
Σ
[w)).
WEST
Lemma 3.5, which we prove below, gives bound of (S)) on the expression above. Combining upper bounds on terms (a), (b), and (c), we get
E [[a[winnen K))] < (1 21+224+ 1)((S1) = (2 + 2) ((S)).
Lemma 3.5. For every St. we have E[coss(w)) < 2Lu(w).

---

Proof. We have
Elcost(w)] = (((inner((K) (K)) 1(h(51) = h(w)) [wwinner(( ( & Surprise
(7)
If S; is a non-surprise set, then h(S1) < [.,)(S:) or e(S.) < 1((S). If S: the winner, then e(S.) 2 h(S.). Thus, if S, is non-surprise winner, then h(S1) L/p(S,). This observations gives us the following upper bound on (7):
(rost(w) S Σ u(S)) Pr (s. winner(K) and h(w) M(S)) L/u(S.)).
(8)
Define two set systems L and I of sets S, containing and not containing wt:
[ (St & S and 2 2):
1 {S 8; and 2 2).
Note that K = = Sx) = (Si) U 15 U I. By Lemma 2.5,
winner(K) (Si, winner(T5), winner(I]) ).
Observe that if St with i is the winner, then winner(T5) S; winner((Tt) We replace the condition S. = winner(KK with S; E {winner(4[) winner [+)) in (8) and get bound:
((S)) Pr (S; (winner winner and h(w) < p(S.) ) 1=2
L
E cost(w))
S
The key observation now is that sets winner and winner (+ are independent of h(w). This is the case, because sets remaining the competitions (T,()))) and R, (T.) do not change when we select w. The set RR,, (Tw) does not change in the round n when w is chosen because all sets S; in R, (1 C 15 do not contain w. The set R2 (15) does not change this round because all sets S; in R., (1t) C It contain and consequently when is chosen, none of these sets is removed from R., Rn(1 (otherwise, R. would become empty). Thus,
&
L
E cost(ww)]
&
((S)) Pr (S; E {winner(45), ) vinner(I(t)) Pr (h(w) < 1=2
(sS:)
Using that h(ww) is an exponential random variable with parameter plw), we get (for every i)
L m(S.) Pr (h(w) S )(3))) ((S.)) (1 (1- - ((ot)
mسا
S ((S)) [k(W)
u(S)) p(w)L
Hence,
E cost(w)] S p(w) Σ Pr (S, E {winner([]) winner (1))
The sum on the right hand side is at most 2. Thus, E[cost(w)) S 2Lp(w).
Acknowledgments and Disclosure of Funding
The authors supported by NSF Awards
CCF-1934931, EECS-29 2216970.
References
Sayan Bandyapadhyay, Fedor Fomin, Petr A Golovach, William Lochet, Nidhi Purohit, and Kirill Simonov. How to find good explanation for clustering? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages
2022.
Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms (TALG), 111,
10

---

Moses Charikar and Lunjia Hu. Near-optimal explainable k-means for all dimensions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2580-2606. SIAM, 2022.
Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys. A constant-factor approximation algorithm for the k-median problem. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 1-10, 1999.
Vincent Cohen-Addad and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in lp-metrics. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1493-1530. SIAM, 2022.
Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1621- 1628, 2022.
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, pages 7055-7065, 2020.
Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Almost tight approximation algorithms for explainable clustering. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2641-2663 SIAM, 2022.
Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. Exkme: Expanding explainable k-means clustering. arXiv preprint arXiv:2006.022 02399, 2020.
Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson. Nearly-tight and oblivious algorithms for explainable clustering. Advances Neural Information Processing Systems, 34:28929-28939, 2021.
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and Rachel Yuan. The price of explain- ability for clustering. arXiv preprint SXKV::2304.097433 2023.
John Frank Charles Kingman. Poisson processes, volume Clarendon Press, 1992.
Eduardo Laber, Lucas Murtinho, and Felipe Oliveira. Shallow decision trees for explainable k-means clustering. Pattern Recognition, 137:109239, 2023.
Eduardo S Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In International Conference on Machine Learning, pages 5915-5925. PMLR, 2021.
Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation In proceedings of the forty-fifth anmual ACM symposium on theory of computing, pages 901-910, 2013.
Konstantin Makarychev and Liren Shan. Near-optimal algorithms for explainable k-medians and k-means. In International Conference on Machine Learning, pages 7358-7361 PMLR, 2021.
Konstantin Makarychev and Liren Shan. Explainable k-means: don't be greedy, plant bigger trees! In Proceedings of the 54th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1629-1642, 2022.
Nimrod Megiddo and Kenneth Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182-19) 1984.
11

---

A Proof of Lemma 2.5
Lemma 2.5. Consider partitioning of the set system (SI,..., Sk} into m sets 4...., Im Then,
winner(K) (winner(H)),.... wiinot))
The proof of Lemma 2.5 relies on the following observarion.
Lemma A.I. Let X and Y be two subsets of K. If X C Y, then every n, we always have R,(Y)nx= = R, or R,(Y)nx= Ø.
(9)
Initially, when O, have Ro(X) X and RY = Y. Therefore, RY) O n xny= (x(X). Suppose (9) holds for n, we prove that (9) also holds for n'
Proof. We prove that (9) holds by induction
1. If (.) n then (Y) n X remains empty for all n' 2 n. Therefore, (9) holds for n + So, let us assume that R, (Y) nx = (X). Consider three cases:
11 belongs to sets in R. (Y), then it also belongs to sets in (X) R, (Y) Thus, in this case, no set is eliminated in X Y. That is, Rx+1(() = R, (X) and Rx41(V) = (Y).
If w belongs to sets (X),), but not sets in R. (Y), then, at step n + 1, we remove all sets that contain wh+11 and, particularly, all sets in (X),), from (Y). Consequently, R.+1 (V)
If not all in R, and not all sets in R,, contain Wn+1, then we remove exactly the same sets from both (X) and R,,(Y, n X. Namely, we remove sets S, E RR, that contain wn+11
We conclude that (9) holds for = n
Proof of Lemma 2.5. Consider arbitrary realization of the game w1, .2,........... Let be the round when all sets but the winner are eliminated from the competition i.e., R. contains only one set, the winner. Since K is the union of Iı,...,A Ig. the winner must belong to some I,. Now, by Lemma A. for X = 1j and Y = K, we have (K) n I, R2 (1,) or R (K) n Ø. We know that (R( (winner(KK) (K)) and winner( (K) E Iy. Thus, R2 (K) nI, = (winner(K)) Ø, and
(I, R, (K) II (winncr(K)) (K)).
We conclude that at round n, (1,) contains only one set the winner in K. Consequently, it is also the winner in 1 i.e., winner [,) = winner( (K). This finishes the proof.
12


Reviews:
[{"review_id": "fCXjTQVwDT", "reviewer": "Reviewer_jrDD", "summary": "This paper considers the Explainable k-Medians problem, which is a more interpretable model for k-clustering than traditional models such as k-median. An explainable clustering partitions space based on coordinate threshold cuts, so that instead of a Voronoi diagram as in k-median / k-means, we end up with rectangular partitions. More specifically, the partitions are determined by a binary decision tree where each node contains a coordinate and a threshold, and the left child corresponds to points that fall below the threshold in that coordinate, and the right child corresponds to points that fall above the threshold in that coordinate. An algorithm is f(k)-competitive for explainable k-median if it produces an explainable clustering that has cost at most f(k) times the cost of the optimal (unconstrainted) k-median clustering. This paper shows that Random Coordinate Cut algorithm (studied by several authors before this paper) has the optimal competitive ratio: specifically, they prove it is (2 \\log k + 2)-competitive--improving on the previously best known bound of O(log log k)--and matching a previously known \\Omega(log k) lower bound. \n\nThe technique is to reduce the problem to a game which the authors call the Set Elimination Game, which is syntactically similar to the Random Coordinate Cut algorithm (and indeed, the authors note that other authors have implicitly analyzed this game). In it, there is some ground set \\Omega and an associated probability measure \\mu, along with a set of subsets. At each round, an element of \\Omega is chosen according to \\mu, and any remaining subset that contains this element is eliminated (unless all remaining subsets contain this element). The last remaining subset is the winner, and the cost of the game is \\mu(winner). The main result, which directly translates to the competitive ratio bound for explainable k-median, is that the expected cost of the game is at most (2 log k + 2) times the cost of any subset. \n\nThe idea behind the analysis is to associate each round with an arrival in a Poisson process, so that they may then view the times at which elements first are chosen in the game as hitting times with exponential distributions.  The hitting times have the nice property that they are independent for different elements. Notably, hitting times single-handedly determine the behavior of the game, so the analysis of the game can be reduced to the analysis of hitting times. ", "questions": "Can any of the methods in this paper potentially be adapted to explainable k-means?", "limitations": "Not applicable. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper resolves the question of whether the Random Coordinate Cut algorithm is optimal via a tight analysis. \n\n- The analysis of the Set Elimination Game using Poisson processes is creative and novel (based on my understanding from the related work section, other papers implicitly analyze this game, but the method here is new). It is also quite clean. \n\n- The formulation of the Set Elimination Game and the main result on its expected cost (Theorem 2.1) may be of independent interest. ", "weaknesses": "The result is slightly weaker (by a factor of 2) than a concurrent result of Gupta, Pittu, Svensson, and Yuan (2023), which gives a bound of 1+H_{k-1}. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Yes, our result can be used for explainable k-means. Makarychev and Shan (2021) provided a cut-preserving terminal embedding from $\\ell_2^2$ to $\\ell_1$ with distortion $O(k)$. Thus, we can first run the terminal embedding and then use the Random Coordinate Cut algorithm on the new instance. Our analysis and also the analysis by Gupta et al. (2023) show that this algorithm achieves $O(k\\log k)$ competitive ratio for explainable k-means. This ratio matches the previous best ratio given by Esfandiari, Mirrokni, and Narayanan (2022). Gupta et al. (2023) proposed a new algorithm that achieves the $O(k \\log\\log k)$ competitive ratio for k-means."}, {"review_id": "stoEYDcq3T", "reviewer": "Reviewer_9ZE5", "summary": "The paper considers the problem of explainable $k$-medians which was recently introduced by Dasgupta et al, and analyzes the RandomCoordinateCut algorithm. The paper proves an upper bound of $2\\ln k + 2$ on the competitive ratio of RandomCoordinateCut. This matches a previously known lower bound of $\\Omega(\\log k)$, and hence the paper proves that RandomCoordinateCut for explainable $k$-medians is optimal up to constant factors.\n\nEdit: I've read the authors' rebuttals. As I mentioned in my first review, I believe that this is a strong accept paper.", "questions": "- Can the authors comment about the proof of Gupta et al. (mentioned on page 4, line 105)? Is it very different from the approach that is presented in the current paper?", "limitations": "No concerns regarding potential societal impact of this work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper proves optimality of RandomCoordinateCut for $k$-medians with a remarkably simple and elegant proof. Furthermore, the paper is generally very well written and easy to follow.", "weaknesses": "I can't see any significant weakness in the paper.\n\nHere are few minor comments/typos:\n- Page 4, line 116: The equation $Pr(\\omega_n = \\omega) = \\mu(\\omega)/\\mu(\\Omega)$  is not strictly formal for spaces that are not discrete.\n- Page 5: In the displayed equation right after line 156, the summation should be over $j$.\n- Page 5, line 185: \"all sets are non-empty and disjoint\" -> \"all sets are non-empty and distinct\".\n- Page 8: In the displayed equation after line 296, I think that in (c) we should also specify that the winner is not $S_1$, because technically $S_1$ does not satisfy the definition of a surprise set.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "5NBvqJySjW", "reviewer": "Reviewer_uidA", "summary": "The paper provides a tight analysis of the random-coordinate-cut (RCC shortly) algorithm for explainable k-medians in the $ \\ell_1 $ metric. To be precise, the RCC algorithm was independently proposed  by several works, and for the explainable k-medians in $ \\ell_1 $ , the tightest proved competitive ratio is $ O(\\log k \\log\\log k) $, which has a small gap between its lower bound $ \\Omega(\\log k) $. This paper shows that the competitive ratio is no larger than $ 2\\ln k+2 $, thereby concluding that the RCC algorithm is optimal for explainable k-medians.", "questions": "- I have no questions but the independent work of this paper. I am interested in learning more about the comparison between these two works, particularly with regard to the differences in the techniques and high-level ideas underlying them.", "limitations": "None", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper completely answers the problem of whether there exists an algorithm with a competitive ratio that matches the lower bound $ \\Omega(\\log k) $ for the explainable k-medians problem.  Its contribution is significant and solid. The proofs are simple and elegant.\n- The idea behind the analysis method set elimination game is ingenious. Actually, it effectively summarizes a series of prior works in a concise and abstract manner.", "weaknesses": "i don’t find obvious weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "FIBPWQLGcX", "reviewer": "Reviewer_vAmy", "summary": "The paper studies the optimal upper bound of explainable k-median and shows a tight analysis for the random coordinate cut algorithm. The explainable k-clustering model was first introduced by Dasgupta et al. [ICML’20] and was followed by a flurry of work to understand the optimal approximation factor to achieve explainability. For the k-median task, previous work has shown that an $\\Omega(\\log k)$ factor is necessary, and algorithms that follow a random coordinate cut scheme can achieve $O(\\log k \\cdot \\log\\log k)$-approximation. This paper shows that by picking appropriate distributions, the random coordinate cut can achieve the asymptotically tight approximation of $O(\\log k)$.\n\nAt the heart of the analysis of the paper is a newly-defined *set elimination game* (SEG), where elements are split into multiple (potentially overlapping) sets, and the referee takes an element $e$ at random and eliminates all the sets that contain $e$ unless every remaining set contain $e$. The final value of the game is defined as the measure of the final surviving set. The paper establishes the upper bound for explainable k-median clustering by: 1). showing a ‘’reduction’’ from the cost of explainable k-median of a single point $x$ to the value of the SEG, 2). proving the expected value of the game as $O(\\log k)\\cdot \\mu(S^*)$, where $S^*$ is the set with the smallest measure.\n\nIn my opinion, the paper is generally well-written, and it settles an important question in explainable k-median clustering. The proof idea is novel, and it is presented in a clean manner (minus some minor exposition issues, see the weakness for details). Therefore, I believe the merits of the paper are sufficient for acceptance.", "questions": "- You never mentioned the initialization of the reference sets, but judging from the proof of Theorem 2.2, you’re assuming the optimal k-median centers as the reference centers, right? Something like this should be mentioned and discussed.\n- You never mentioned the *distribution* of the random coordinate cut in the paper; from the requirement of Theorem 2.1, it seems uniform at random works. Is this right? You should explicitly define the distribution, either way (‘’pick at random’’ $\\neq$ ‘’pick uniformly at random’’ – the former only means picking something from *a* distribution).\n- What is the intuition for the 'surprising sets'? I can read that the name 'surprising' may come from the fact that for $h(S_1) \\cdot \\mu(S_i) \\geq \\log k$, either $S_1$ should be hit very late or $S_i$ should have a high volume, which means it should have been hit/eliminated way earlier. If this is true, please also add a discussion about it, as it'll help readers understand your proof.\n- Do you see any other applications for the Set Elimination Game?\n", "limitations": "The work is of theoretical nature, so the (non-technical) limitations are on the model side, e.g., the explainable clustering model might not provide easy-to-understand explanations in real life. However, I do not think this affects the significance of the contribution.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Explainable clustering has been a popular topic in the recent few years, and the paper settles an open problem in the area. The idea of set elimination games is novel and interesting, and the paper is well-written. The organization helps the reader a lot in understanding the paper.\n", "weaknesses": "I do not see any major technical weaknesses in the paper. On the exposition part, I have some minor comments:\n- The paper is written in relatively advanced technical languages, and they might not be readily accessible to the broader NeurIPS audiences. To make the readers’ task easier, I think it makes sense to add some more intuitions on why using the set elimination game, why the value should be small, and the high-level intuitions for the analysis. \n- Conversely, the paper spent little effort discussing why explainability in k-clustering is important and why shaving off the exponentially-small $\\log\\log k$ factor is significant. I would recommend adding some discussion on this front for later versions.\n- Some notation problems. In the proof of Theorem 2.2, there is a slight overload of notation in the construction of $\\Omega$, and $S$: $S$ was used as a *variable* for the sets in the definition of the SEG, but in the proof it becomes the *realization*, i.e., fixed sets. I would recommend using a different notation instead. Also, $x_j$ (which I guess means the j-th coordinate of the point $x$) is used before it is defined.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for suggesting how we can improve the presentation. We will address all your comments in the final version of the paper.\n\n1. For Theorem 2.2, we do not assume the reference centers are optimal centers for k-medians. We show that for every set of k reference centers, the Random Coordinate Cut finds a threshold tree with the cost at most $2\\ln k+2$ times the unconstrained cost given by the input reference centers. We define the competitive ratio as the ratio between the cost of the decision tree and the cost of the input reference centers. The price of the explainability for k-medians is the ratio of the cost of the decision tree and the optimal unconstrained k-medians cost. To get an $O(\\log k)$ upper bound on the price of explainability, we need to use a constant factor approximation algorithm for k-medians to find the reference centers.\n\n2. Yes. Threshold cuts are sampled uniformly at random.\n\n3. Yes. We will add a discussion about the surprise sets.\n\n4. The Set Elimination Game can potentially be used to analyze other weighted sampling algorithms with non-independent events but we are not aware of any specific examples now.\n"}]

Author rebuttal:
First of all, we would like to thank all the reviewers for their valuable feedback. We will address
all their comments and implement all their suggestions in the final version of the paper. 

Several reviewers asked us to compare our proof and the proofs obtained independently by Gupta, Pittu, Svensson, and Yuan (2023). Gupta et al (2023) gave two different proofs. In the first, simpler proof, they also used the exponential clock technique. However, this proof is somewhat different from ours. First, it does not consider the set elimination game and instead works directly with cut metrics. Second, it keeps track of the elimination time of set $S_1$ (using our terminology) rather than its hitting time. This makes the technical details a bit different from ours. Their proof gives a slightly better bound than ours (their bound is $(1+o(1))\ln(k)$, our bound is $2\ln k +2$). The second more involved proof provided by Gupta, Pittu, Svensson, and Yuan (2023) gives a tight competitive ratio of $1+H_{k-1}$. This proof uses a different approach: It reduces an arbitrary instance of the problem to the “uniform” instance, in which all centers other than the closest center to point x are at the same distance from x.


Meta-review: The reviewers greatly appreciated the main contribution of the paper, and there was consensus that this a very strong submission.
Decision: Accept (oral)