Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm

We thank the reviewer for the detailed comments and insightful questions.

W1: We have an example that shows an $\Omega(\log k)$ lower bound on the price of explainability for $k$‑medians under the $\ell_p$ norm for all $p \geq 1$. We will include it in the revised version of the paper. We will also expand the discussion of related lower bounds and hardness of approximation results, including the $\Omega(\log k)$ lower bound on the price of explainability for $k$‑medians under the $\ell_2$ norm due to Makarychev and Shan (2021) and the hardness results for explainable $k$‑medians under the $\ell_1$ norm by Gupta, Pittu, Svensson, and Yuan (2023).

Q1. I am curious about the explainable clustering problem in the setting where the centers are given as part of the input. Is it possible to construct a single clustering tree that performs well across all l_p norms, rather than building a separate explainable tree for each specific norm? Why or why not?

Thank you for the excellent question! There exists an instance with two centers such that no single threshold tree (even distribution over threshold trees) can achieve better than O(d^{1/4}) approximation for all $\ell_p$ norms simultaneously. We will include this example in the revised version.

The instance has two centers, one at the origin $c_1=(0,0,\dots,0)$, and the other at $c_2=(1 + d^{\frac{3}{4}},1,\dots,1)$, along with many data points co-located at each center and one special point $x = (1,1,\dots, 1)$. We show that any distribution $D$ over threshold trees (a single threshold cut in this case) yields an explainable clustering such that either the $\ell_1$ or the $\ell_2$ cost is in expectation $\Omega(d^{\frac{1}{4}})$ times the corresponding unconstrained clustering cost.

Case 1: If distribution $D$ assigns $x$ to $c_1$ with probability at least $1/2$, then the expected $\ell_1$ cost of the explainable clustering is at least $d/2$, while the optimal $\ell_1$ clustering cost is $d^{3/4}$ (by assigning $x$ to $c_2$).

Case 2: If distribution $D$ assigns $x$ to $c_2$ with probability at least $1/2$, the expected $\ell_2$ cost of the explainable clustering is at least $d^{3/4}/2$, while the optimal $\ell_2$ clustering cost is $\sqrt{d}$ (by assigning $x$ to $c_1$).

Q2. Additionally, regarding the dynamic clustering algorithm, normalization is applied to all centers. Will normalization also need to be applied to all nodes whenever new nodes are inserted? If so, how does this affect the efficiency of the algorithm?

As far as your second question is concerned, the assumption that all future centers lie in $[-1,1]^d$ is used mainly for the ease of exposition. There is an implementation of the algorithm that does not depend on this assumption. Specifically, if the centers after request $t$ lie in $[-R,R]^d$, the weighted distribution $\tilde{f}(x)$ that we use to sample a threshold in $(y_{j-1}, y]$ does not depend on $R$ (we can compute the threshold by sampling a uniform random variable $U \in ((y_{j-1} - m)^p, (y-m)^p)$ and return $U^{1/p}$). Moreover, if all timestamps are multiplied by the same positive number $\alpha$, the analysis is not affected. Thus, in line 1171, we can sample $z\sim \exp(\lambda)$ with $\lambda = (y-m)^p - (y_{j-1} - m)^p$ (that does not depend on R), without affecting the analysis. We will add this clarification in the revised version of the paper.

We thank the reviewer for constructive feedback.

1. As the reviewer correctly points out, our algorithm generalizes the one in Makarychev and Shan (2021), with the key difference being the modified distribution used to sample the threshold $\theta$. This change is essential for extending the guarantees to general $\ell_p$ norms. Beyond this algorithmic modification, our analysis introduces several new technical components. To achieve a tighter approximation ratio, we refine the analysis by partitioning cuts into three cases: (1) safe cut, (2) light cut, and (3) heavy and unsafe cut, while the previous work only considered light and heavy cuts. Additionally, the dynamic setting in this paper is entirely new. We will clarify these distinctions more explicitly in the revised version.

2. We thank the reviewer for the insightful comment and agree that the core algorithm for explainable clustering remains similar to prior work. The reviewer is also correct that the new ideas introduced for the dynamic setting can be extended to earlier algorithms for explainable k-medians under both the $\ell_1$ and $\ell_2$​ norms. While the high-level structure of the algorithm is preserved, the dynamic setting introduces several new technical challenges that require novel ideas:

(1) We use exponential clocks to assign timestamps to decision nodes, allowing us to identify the earliest cut that separates an inserted center and update the threshold tree. This avoids recomputing the entire tree from scratch. Specifically, the exponential timestamps allow us to update the current tree efficiently in time O(d polylog k). Note that even classifying a single data point $x$ naively might require traversing a root-to-leaf path in O(k) time. Although exponential clocks were previously used in the analysis of $\ell_1$-based clustering algorithms (e.g., Gupta et al. 2023; Makarychev and Shan 2023), this is the first time they are used algorithmically for maintaining the dynamic explainable clustering.

(2) Our static algorithm selects the anchor point as the coordinate-wise median of centers to control the number of centers separated by each cut. In the dynamic setting, the median of centers evolves as centers are inserted or deleted, which implicitly affects the threshold distribution. To address this, we keep track of the number of centers and rebuild the tree when necessary to maintain the anchor point as an approximate median of centers in each partition leaf call.

3. We thank the reviewer for the thoughtful question. Studying $\ell_p$ norm costs in clustering provides a flexible framework that interpolates between different clustering objectives, with practical and theoretical relevance. For instance, $\ell_1$ norm is known for its robustness to outliers, while $\ell_2$ norm is widely used due to its geometric interpretability and computational properties. Extending explainable clustering to general $\ell_p$​ norms allows practitioners to tailor the cost function to the needs of specific applications while preserving interpretability. Our goal is to understand how explainability impacts clustering quality across this broader family of objectives and to provide provable guarantees in this more general setting.

We thank the reviewer for the detailed comments and appreciate the recognition of our results in the offline setting.

We are not aware of any prior work on dynamic algorithms for explainable clustering. Dynamic algorithms have, however, been studied for unconstrained (non-explainable) $k$‑medians. While our dynamic algorithm is stated in terms of insertions and deletions of centers, it can be naturally combined with existing dynamic algorithms for unconstrained k-medians under $\ell_p$ norm to also handle dynamic updates to the data points themselves. Specifically, in settings where data points are inserted or deleted, we can maintain a good set of centers using a dynamic $k$-medians algorithm, and then use our algorithm to maintain the corresponding threshold tree for explainable clustering as these centers change. In particular, we can use a constant-factor approximation dynamic algorithm with small recourse that modifies only a small number of centers upon each insertion or deletion of a data point. We will include a clear discussion of this connection and state a formal corollary in the revised version.

We thank the reviewer for the detailed and constructive feedback.

1. The main intuition of extending the results from $p=1,2$ to general $p>=1$ is as follows. We build on the algorithmic framework of Makarychev and Shan (2021) for explainable k-medians under $\ell_2$ norm. The key modification lies in the sampling distribution for the threshold $\theta \in [0,R_t]$ in the Partition_Leaf function. Specifically, we sample theta according to the cumulative density function $x^p/(R_t)^p$, which corresponds to the density function $px^{p-1}/(R_t)^p$. This implies that for any $0<a<b<R_t$, the probability that the sampled threshold $\theta \in [a,b]$ is at most $p(b-a)b^p/(R_t)^p$, which is crucial for bounding the separation probability. Our analysis is more refined than that of Makarychev and Shan (2021); as a result, it applies to all finite $p$ and yields improved theoretical guarantees for the $\ell_2$ norm.

Note that these modifications are necessary to achieve a good approximation for $p \geq 1$. Specifically, for every value of $p$ we need to use a separate distribution. This is illustrated by the example we provide in our response to Reviewer tdu1 (see our answer to Q1 for Reviewer tdu1).

2. We have an example that shows an $\Omega(\log k)$ lower bound on the price of explainability for $k$‑medians under the $\ell_p$ norm for all $p \geq 1$. We will include it in the revised version of the paper. We will also expand the discussion of related lower bounds and hardness of approximation results, including the $\Omega(\log k)$ lower bound on the price of explainability for $k$‑medians under the $\ell_2$ norm due to Makarychev and Shan (2021) and the hardness results for explainable $k$‑medians under the $\ell_1$ norm by Gupta, Pittu, Svensson, and Yuan (2023).

We thank the reviewer for the detailed and insightful comments.