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": "xJHDztv9_PX", "reviewer": "Reviewer_65No", "summary": "Given a set of points X in R^d, an explainable k-clustering of X is a partition of X in k sets that can be defined by a decision tree whose generic node has the form \"x_i > t_i ?\" where x_i is the i-th feature and t_i is a threshold value. The work studies the problem of computing explainable clusterings that are good in the sense of k-means and k-medians. The main results is a randomized algorithm that, given the centers of any k-clustering of X (not necessarily explainable), computes a novel k-clustering that is explainable and whose cost is only O(log^2 k) times worse that of the input in the case of k-medians, and O(k log^2 k) times worse in the case of k-means. The work gives near-matching lower bounds as well.\n", "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": "TLDR: I think this is a good paper with clear (and clean) results, and deserves acceptance.\n\nOriginality: good. The results, including the algorithm, are original work. The authors compare correctly against previous work. \n\nQuality: good. I read only some of the proofs, and they look ok to me. The authors point out both the strengths and the weaknesses of the work.\n\nClarity: good. The paper is clearly written and I found it very smooth to read. There are only a couple of points that perhaps could be improved, but these are minor concerns.\n\nSignificance: good. The paper advances the state of the art, in at least three ways: (1) it gives dimension-free bounds on the \"cost of explainability\" that are significantly better than the existing ones, (2) it shows that those bounds are almost optimal, (3) it shows that those bounds can be achieved by a very simple algorithm (I checked the previous work, and that algorithm is much more intricate).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are adequately discussed. There is no foreseeable societal impact.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "U9VhY814LRJ", "reviewer": "Reviewer_mWXa", "summary": "The paper improves the results of Dasgupta et al. for explainable clustering, under the $k$-median and $k$-means objectives (and also $\\ell_p$-norms). In this problem, clustering solutions are restricted to partitions achievable via a collection of single coordinate cuts (where the coordinates are assumed to be features that explain the resulting clustering). The cost of a resulting clustering is measured against a reference (non-explainable) clustering that the algorithm takes into account. The algorithms in this paper are remarkably simple (and I mean that in a good way), and involve iterating over selecting coordinate cuts at random, subject to the next cut refining the separation between the reference cluster centers.", "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 improvement is substantial (from $k$ to $\\log^2 k$ for $k$-median, and from $k^2$ to $k\\log^2 k$ for $k$-means), and nearly matches lower bounds (a previous one in the case of $k$-median and a new one from this paper in the case of $k$-means). The algorithm is simple and attractive. The paper is clearly written and easy to follow. Overall, this is a nice theoretical contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no immediate concrete applications, so societal impact is mostly irrelevant.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "GLwl0TYkaQ", "reviewer": "Reviewer_gBnK", "summary": "The paper suggests an algorithm that aims to understand how models make their decisions. In particular, the paper handles clustering approaches, including $k$-means and $k$-medians, and aims to explain their behavior by using the notion of \"explainability\" using a special instance of a decision tree, called threshold decision trees, where each edge in the tree is made with respect to a single dimension using a threshold on its value.\n\nI enjoyed reading the paper! However, please see my comments below.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In this paper, the author suggests two algorithms, one which is naive in nature with theoretical guarantees in obtaining an explainable clustering concerning the $k$-median and $k$-means problems.\nWhile the first algorithm is fairly simple, however, the approximation can be very large, especially when the diameter of the set of centers is very large (exponential in the number of points, for example), its modified version handles this case by discarding cuts that will separate between a pair of centers having \"small\" distance between them.\n\n I believe the theoretical results are correct. I have looked into most of the proofs though not all, due to time constraints.\n\nMinor Comments:\n- I think that the left side of Equation (1) is not correct! Did you mean to write $\\left\\lVert \\boldsymbol{x} - \\pi(\\boldsymbol{x}) + \\pi(\\boldsymbol{x}) - \\mu\\right\\rVert_1$?\n- Where there is $O$ notation in any of the inequalities/equalities you use, please use $\\in$ instead for mathematical correctness.\n\nComment:\n\n* I wonder whether it is better to apply importance sampling on the cuts than using uniform sampling. Coresets are known to approximate given loss functions concerning a set of queries (or all possible queries). In addition, they shine a light on the underlying structure of the data which in terms, aids in understanding the probability distribution from which the points were obtained. Since clustering aims in encapturing such hidden structures, the centers will encapture such hidden information within themselves (in the structure of their coordinates, for example, their distance from each other, etc.).  Using such information, one can sample better cuts with higher probability which will help in attaining tighter upper bounds than those achieved by uniform sampling. In light of this, why did you choose to go with uniform sampling? Can you give a brief explanation of whether importance sampling would be a better candidate than uniform sampling?\n\n\n* See my concerns with the limitations of your work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have mentioned two limitations of their work, which are interesting. The first which the authors have mentioned is that their upper bound on the cost increase of assigning a single point to a wrong center is not tight, whereas the second, concerns their analysis that it may include the cost of the same point multiple times. My main concern which was not addressed in the paper is that the theoretical guarantees involve expectation. My concern is, what is the worst-case analysis of your approximation that is obtained via \"explainability\" using either Algorithm 1 or its modified version? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "0H4KZmsX3wU", "reviewer": "Reviewer_fBhF", "summary": "The authors study the important problem of explainable clustering presenting new algorithms that improve substantially over the  state of the art results by shaving a k factor for k-medians and a klog^2 factor for k-means. The new results are polylog away from optimal. The algorithms are easy to implement and very efficient and the authors present also a lowerbound. \n\n", "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": "Nearly-Tight and Oblivious Algorithms for Explainable Clustering\n\nThe authors study the important problem of explainable clustering as defined by Moshkovitz et al. The authors present a new algorithm which improves substantially over the previous state of the art results by shaving a k factor for k-medians and a klog^2 factor for k-means. The new results are polylog away from optimal. \nThe algorithms presented are also easy to implement and very efficient. Remarkably the algorithm only needs to look at the output of a non-exaplainable clustering (i.e. O(dk) input space). \nThe authors also show an improved lowerbound. \n\nMore precisely technically the algorithm is based on running a simple procedure that samples uniformly cuts from the bounding box of the centers in input until a valid tree is formed.\n\nThe only drawback of the paper is the complete lack of an empirical evaluation. This is quite surprising for a paper that shows  a simple and efficient algorithm, as it would not be difficult at all to test it. This leaves the possibility that the algorithm, in practice, actually underperforms the state of the art methods.  This would not be completely surprising as the algorithm is based on oblivious randomized cuts so it may actually be not great (on average instances) while being close to optimal on worst-case instances. I personally think that an empirical evaluation is warranted and the lack of it is lowers the value of the paper. \n\nTechnically the algorithm is based on interesting observations on the problem, and obtaining a tighter upper bound on the optimal cost of reassignment. Similar techniques are used for k-means. Overall the technical material is good. \n\nAll in all the paper is quite strong and I would give a strong accept but for the lack of empirical evaluation. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review. \n\nThe main limitation is the lack of experimental evaluation.\n\nSuggestions:\n“Moreover, this algorithm is 115 oblivious to the data points, which avoids introducing biases.” -> I suggest to remove this as the bias can be in how the solution is used by the algorithm. The proof hinges on showing a relationship between the optimum cost and the number of points separated by random cuts as well as a bound of the increase of the cost for each separation. \n\nMinor comments:\n\n “52 As a consequence, the algorithm cannot overfit the data (any more than the reference clustering 53 possibly already does), and the same expected cost guarantees hold for any future data points not 54 known at the time of the clustering construction” Please explain why future data points have this guarantee as it Is not obvious here. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers provided sufficient positive feedback and support for this paper, valuing the new theoretical improvements upon the results of Dasgupta et al. for explainable clustering, under the k-medians and k-means objectives (with extensions to other norms as well, and with new nearly-tight upper and lower bounds). Therefore, I recommend accepting the paper. 

The main concern has to do with an overlap in results with a paper from ICML 2021 by Makarychev and Shen on the same topic. However, the prior paper did not appear publicly until well after the NeurIPS deadline, and therefore, the papers have been classified as independent work. In the next version of the paper, I strongly encourage the authors to update the related work discussing the 3-4 seemingly independent improvements to this problem, and in particular, pointing out any quantitative or qualitative similarities or differences between the works.
Decision: Accept (Poster)