acceptodds
Under review as a conference paper at ICLR 2027

Priority-Aware Explainable Clustering

Abstract

Explainable clustering aims to represent a given clustering using an interpretable model, such as a decision tree, while approximately preserving the original assignment cost. For -medians clustering under the norm, prior work has shown that threshold decision trees achieve a competitive ratio of , and that this bound is tight. In this paper, we introduce priority-aware clustering, a refinement of explainable clustering in which different centers have different priorities. We start with the setting in which all centers are split into two groups: a small number of high-priority centers and remaining centers. Our randomized algorithm outputs a threshold decision tree with leaves that yields an improved competitive ratio of for high-priority centers, while preserving an guarantee overall. We further extend our results to settings with multiple priority classes or in which every center has its own priority. In the latter case, the competitive ratio for a center ranked is . Our results provide a more flexible framework for explainable clustering, enabling interpretable models that offer stronger fidelity guarantees for high-priority clusters while maintaining worst-case guarantees.

Primary area:
interpretability and explainable AI
Keywords:
interpretability, explainability, clustering

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_3RHqOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces the problem of priority-aware explainable clustering, where clusters in a reference clustering may have different priorities. The goal is to construct a decision tree that provides strong approximation guarantees for the kk-medians objective. The setting differs from the traditional one, studied in many papers, because it aims to achieve better guarantees for points assigned to high-priority clusters.

Let c1,…,ckc_1,\ldots,c_k be a set of reference centers partitioned into ss sets P1,…,PsP_1,\ldots,P_s, where PiP_i is the set of centers with the iith highest priority. The authors assume that the set of higher-priority centers has fewer centers than the set with smaller priority,

There are two main theoretical results:

  • it is possible to build a randomized decision tree TT (Theorem 1.1) with at most sksk leaves such that the distance between a point xx, whose closest center is ci∈Pc_i \in P, and its center T(x)T(x) is (in expectation) $ O( \log |P| \log s) |x-c_i|_1$. The assumption that ∣P1∣≤…≤∣Ps∣|P_1| \le \ldots \le |P_s| implies that points whose closest center has high priority have better theoretical guarantees.

  • a result with the same flavor as the above one, but with different bounds (Theorem 1.2), for the setting in which all centers may have different priorities ( s=ks=k). The competitive ratio for the point with the iith highest priority is O(log⁡i(log⁡log⁡log⁡i)1+ϵ)O (\log i (\log \log \log i)^{1+ \epsilon}) and the number of leaves is O(k(log⁡log⁡k)1+ϵ)O(k (\log \log k )^{1+\epsilon}), for every ϵ>0\epsilon >0.

To obtain the results, they employ and adapt the machinery developed for obtaining optimal bounds for explainable clustering via decision trees

Critical strengths
  • The motivation of the proposed problem is reasonable: minimizing the price of explainability for some clusters of higher priority. This is an interesting addition to the literature that studies explainable clustering from a theoretical standpoint.

  • The paper gives a good theoretical characterization for the problem, providing meaningful upper bounds on the competitive ratio and on the number of leaves required by the proposed decision trees (Theorems 1.1 and 1.2. They also show that additional leaves are necessary to improve the competitive ratio, even for a single high-priority center. The presentation is also good, at least for someone acquainted with the field.

Critical weaknesses

When a decision tree has exactly kk leaves, each cluster can be explained by a single rule (a conjunction of conditions). When more than kk leaves are allowed, however, interpretability may be substantially reduced, since some clusters (potentially including high-priority ones) may require a disjunction of many rules to be described. The guarantees established in the paper allow sksk leaves (Theorem 1.1) and O(k(log⁡log⁡k)1+ϵ)O(k(\log\log k)^{1+\epsilon}) leaves (Theorem 1.2).

These guarantees alone do not establish that the resulting trees remain interpretable. An experimental evaluation would help assess their practical usefulness, particularly the number and complexity of rules needed to describe individual clusters. While the absence of experiments may be acceptable in a primarily theoretical conference, I believe solid empirical evidence is important to establish the significance of these results for ICLR community.

This concern is the main reason why I consider the paper borderline.

Questions for authors

No question that would affect my assessment

2 comments

We thank the reviewer for the thoughtful feedback and for recognizing the theoretical contribution of the paper. We would like to briefly address the concern regarding interpretability when more than kk leaves are allowed.

We distinguish between the explanation of an individual assignment and the complexity of describing the entire region assigned to a cluster. In the standard kk-leaf setting, these two notions coincide: each cluster corresponds to a single leaf, while every individual assignment is explained by the conjunction of threshold conditions along the corresponding root-to-leaf path.

Our bi-criteria setting preserves the latter property. Even when a center labels multiple leaves, every individual point is still explained by a single root-to-leaf path consisting of simple threshold conditions on individual features. Thus, allowing additional leaves does not turn the explanation of an individual assignment into a disjunction of many rules. Specifically, the height of the PrioriTree output is at most k-s-2, so the size of an explanation of a clustering assignment is still comparable to the number of clusters kk and independent of the dimension dd, as in the standard explainable clustering model. Therefore, in a medical application, for example, a doctor can still verify a classification of a patient to the cluster of high risk patients by only checking a concise explanation of the form "age >= 65, blood pressure >= 140" and so on.

The reviewer correctly points out that there is additional complexity if one wants to describe the entire region assigned to a center: this region may be a union of several leaf regions. We can quantify this fragmentation for PrioriTree. If LcL_c denotes the number of final leaves labeled by c∈Pic\in P_i, then

∑c∈PiLc=k.\sum_{c\in P_i}L_c=k.

Thus, centers in PiP_i are represented by k/∣Pi∣k/|P_i| leaves on average, while a particular center may appear in at most kk leaves.

We will add this discussion to the final version. We will also include experiments reporting the empirical competitive ratio, number of leaves, tree depth, runtime, and the observed fragmentation of individual clusters. This will allow us to evaluate directly the interpretability--accuracy tradeoff introduced by allowing additional leaves.

Thank you for the discussion!

I think it is a good idea to add this discussion to the final version.

However, this does not change my assessment much. I am keeping my score, as I still consider the paper borderline for the reasons explained in my review.

Reviewer_DWTnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates priority-aware interpretable clustering. Within the framework of fixed reference centers and threshold trees, the objective is to ensure stronger competitive ratio guarantees for higher-priority centers. The authors propose PRIORITREE, which extends the kk-leaf tree, constructed via RandomCuts, by incorporating representative centers for each priority class into every leaf and subsequently applying RandomCuts again. This approach yields an sksk-leaf tree with class-specific guarantees of O(log⁡slog⁡∣Pi∣)O(\log s \log |P_i|). For scenarios involving a total ordering of centers, the authors introduce a partitioning strategy and a recursive algorithm, RANKEDPRIORITREE, which achieves rank-based guarantees of approximately Oϵ(log⁡i(log⁡log⁡log⁡i)1+ϵ)O_\epsilon(\log i (\log\log\log i)^{1+\epsilon}) with Oϵ(k(log⁡log⁡k)1+ϵ)O_\epsilon(k(\log\log k)^{1+\epsilon}) leaves. The analysis employs a multi-winner "Set Elimination Game" to derive bounds on the expected cost.

Critical strengths
  1. The problem formulation is meaningful; it advances the study of interpretable clustering from a uniform competitive ratio to a framework that provides differentiated guarantees based on priority levels, a clear and well-motivated approach.

  2. The theoretical contributions are comprehensive, covering multiple priority levels, full-ordering scenarios, and an analysis based on the "Set Elimination Game," with a well-defined technical trajectory.

  3. The discussion regarding lower bounds, arguing that the additional number of leaves is not merely an artifact of the algorithm, offers valuable insight into the complexity of priority-aware interpretable clustering.

Critical weaknesses
  1. There is a significant mismatch between the lower and upper bounds; in particular, the iterated logarithmic factor and the tree-size expansion in Theorem 1.2 are not supported by the lower bounds, which weakens the tightness of the core theoretical results.

  2. The results for total ordering involve an ϵ\epsilon parameter and hidden constants. Given the actual range of kk, the number of leaves, the depth, and the constants resulting from the recursive partitioning and tree construction may be practically unacceptable; however, the paper provides no empirical or numerical evaluation.

  3. Theorem 1.1 (for multiple priority levels) requires ∣P1∣≤⋯≤∣Ps∣|P_1| \le \dots \le |P_s| and a tree with sks^k leaves, leading to severe tree-size expansion when ss is large. While the total-ordering approach offers an improvement, the overall contribution appears to be more of an incremental extension. Furthermore, the paper lacks sufficient discussion regarding practical constraints—such as the requirement that priority classes be known in advance or that reference centers remain fixed.

Questions for authors
  1. Is it possible to provide lower bounds that match—or nearly match—the rank-specific guarantees in Theorem 1.2? Specifically, are the terms (logloglogi)1+ϵ(logloglog i)^{1+\epsilon} and the tree-size-dependent term (loglogk)1+ϵ(loglogk)^{1+\epsilon} necessary?

  2. Can the assumption ∣P1∣≤⋯≤∣Ps∣|P_1| \le \dots \le |P_s| in Theorem 1.1 be removed? If the sizes of the priority classes do not satisfy this condition, how do the guarantees change?

  3. Could you provide numerical experiments—using either synthetic or real-world data—that report the actual competitive ratio, number of leaves, tree depth, and runtime, in order to demonstrate the practical applicability of the theoretical results?

  4. Lower bound D.1 focuses specifically on the center with the highest priority and the average competitive ratio; can this be extended to scenarios involving multiple high-priority centers or to guarantees for each individual rank?

  5. Are the priority-aware guarantees stable when xx is near the boundary of the centers for multiple priority classes, or when the reference center contains noise?

3 comments

We thank the reviewer for the thoughtful feedback. Before answering the questions, we clarify two points raised as critical weaknesses.

Critical Weaknesses 2 and 3. The number of leaves of PrioriTree is sksk, not sks^k. Hence the tree size is linear in both the number of classes and the number of centers. Moreover, PrioriTree has exactly sksk leaves with probability 11, so there are no hidden constants in this leaf count.

We also emphasize that the total-ordering results are built directly on PrioriTree. The simpler Theorem 4.1 partitions the ordered centers into only O(log⁡log⁡k)O(\log\log k) classes (P1={c1}P_1=\{c_1\} and, for i≥2i\ge2, PiP_i contains the next 22i−12^{2^{i-1}} centers) and applies PrioriTree once. This yields O(klog⁡log⁡k)O(k\log\log k) leaves and O(log⁡ilog⁡log⁡log⁡k)O(\log i \log\log\log k) approximation for rank ii. RankedPrioriTree refines this construction so that the approximation depends only on the rank and not additionally on kk. Thus, if hidden constants in the recursive construction are a practical concern, Theorem 4.1 provides a simpler alternative. We will also include experiments reporting empirical approximation, leaves, depth, and runtime.

Questions 1 and 4. We can strengthen our lower bounds in two complementary directions. For every set SS of mm centers,

leaves⁡(T)≥k+∑ct∈S[ln⁡k50−5αt]+.\operatorname{leaves}(T)\ge k+\sum_{c_t\in S}\left[\frac{\ln k}{50}-5\alpha_t\right]_+.

Hence obtaining o(log⁡k)o(\log k) approximation for all mm centers requires Ω(mlog⁡k)\Omega(m\log k) extra leaves; for a total ordering, applying this to the first ii centers gives Ω(ilog⁡k)\Omega(i\log k).

We also prove a target-dependent bound: for every A≥2A\ge2, there is an instance with mm designated high-priority centers such that approximation at most AA for all of them requires

k+A3⌊k−m5000eA(A+1)2ln⁡(A+2)⌋k+\frac{A}{3}\left\lfloor\frac{k-m}{5000e^A(A+1)^2\ln(A+2)}\right\rfloor

leaves. In particular, when k−m≥10000eA(A+1)2ln⁡(A+2)k-m\ge10000e^A(A+1)^2\ln(A+2), the number of extra leaves is

Ω ⁣(k−meA(A+1)ln⁡(A+2)).\Omega\!\left(\frac{k-m}{e^A(A+1)\ln(A+2)}\right).

These bounds are not tight enough to determine whether the iterated-logarithmic factors in Theorem 1.2 are necessary, but they substantially strengthen Appendix D and show that many extra leaves can be unavoidable.

Question 2. The ordering ∣P1∣≤⋯≤∣Ps∣|P_1|\le\cdots\le|P_s| is not needed by the analysis. For arbitrary non-empty groups, the same proof gives O(log⁡s(1+log⁡∣Pi∣))O(\log s(1+\log|P_i|)) for PiP_i, so the groups can always be indexed by non-decreasing size. The ordered case is particularly interesting when this indexing agrees with priority, because then higher-priority classes receive guarantees at least as strong as lower-priority classes. Our lower bound also shows why it is not possible to recover our results for arbitrary sizes of the priority classes: if a high-priority class has m=Θ(k)m=\Theta(k) centers, obtaining o(log⁡k)o(\log k) for all of them requires Ω(klog⁡k)\Omega(k\log k) extra leaves.

Question 3. As noted above, we will add experiments measuring empirical competitive ratio, tree size, depth, and runtime.

Question 5. The guarantees hold for every x∈Rdx\in\mathbb{R}^d and set of reference centers, so they remain valid even arbitrarily close to a cluster boundary. Also note that the reference centers need not be optimal: if they give a β\beta-approximation and αmax⁡\alpha_{\max} is the largest applicable center-wise ratio, then

E[cost⁡(X,T)]≤αmax⁡βOPT.\mathbb E[\operatorname{cost}(X,T)]\le \alpha_{\max}\beta\mathrm{OPT}.

Reviewer_DWTnOpenReview ↗

review

Thank you for your response. Some of my concerns, such as weakness 2,3, have been clarified; however, I would like to see some experimental results and validation. For example, a paper published at ICLR '26 [1] provides both theoretical foundations and experimental validation. Additionally, could you provide the revised version of the paper?

[1] Fleissner M, Chennuru Vankadara L, Ghoshdastidar D. Explaining kernel clustering via decision trees[C]//International Conference on Learning Representations. 2024, 2024: 3408-3430.

We thank the reviewer for their suggestions. We followed the reviewers advice and included both an experimental section and the revised version of the paper.

Please, see the updated paper and our comment under our paper for details.

Reviewer_uvGDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies priority-aware explainable clustering for kk-medians, where different clustering centers have different priorities. The authors propose PrioriTree, a randomized algorithm that constructs threshold decision trees with improved guarantees for high-priority centers. For two priority classes, the algorithm achieves an O(log⁡m)O(\log m) approximation for high-priority centers while maintaining an O(log⁡k)O(\log k) guarantee overall, using 2k2k leaves. The results are further extended to multiple priority classes and fully ordered centers, with approximation guarantees depending on the priority class sizes or center rankings. The paper also establishes lower bounds on tree size and approximation ratios.

Critical strengths
  1. The paper studies an interesting extension of explainable clustering. By considering different priorities among clustering centers, it addresses the need to provide stronger approximation guarantees for important clusters while preserving the quality of the overall clustering.

  2. The proposed algorithms provide strong theoretical guarantees. In particular, for two priority classes, PrioriTree achieves an O(log⁡m)O(\log m) approximation ratio for high-priority centers while maintaining an O(log⁡k)O(\log k) guarantee for all centers, using only 2k2k leaves. The paper further extends the results to multiple priority classes and fully ordered centers.

Critical weaknesses
  1. The tightness of Theorem 1.2 remains unclear. Specifically, Theorem 1.2 achieves an approximation ratio of Oε(log⁡i(log⁡log⁡log⁡i)1+ε)O_\varepsilon(\log i(\log\log\log i)^{1+\varepsilon}) for the center ranked ii, using Oε(k(log⁡log⁡k)1+ε)O_\varepsilon(k(\log\log k)^{1+\varepsilon}) leaves. Appendix D shows that improving the approximation ratio for even one center requires additional leaves, and establishes an Ω(log⁡k)\Omega(\log k) lower bound on the average competitive ratio for trees with o(klog⁡k)o(k\log k) leaves. However, the standard RandomCuts algorithm uses only kk leaves and achieves αi=O(log⁡k)\alpha_i=O(\log k) for every center i∈[k]i\in[k] (Gupta et al., 2023). Thus, its average competitive ratio is 1k∑i=1kαi=O(log⁡k)\frac{1}{k}\sum_{i=1}^k\alpha_i=O(\log k), matching the lower bound in Appendix D up to constant factors. These lower bounds do not establish whether the additional iterated-logarithmic factors in Theorem 1.2 are necessary, or whether similar guarantees can be achieved with fewer leaves.

  2. The complexity of explaining individual clusters is not fully addressed. In Algorithm 2, when m=1m=1, the final tree contains kk leaves labeled by the same high-priority center. Consequently, the region assigned to this center may be split across multiple leaves, requiring several sets of threshold conditions to describe the entire cluster. For m>1m>1, how does this affect the explanation complexity of individual high-priority clusters?

  3. The multi-priority guarantees do not always improve upon standard RandomCuts. Theorem 1.1 achieves an approximation ratio of O(log⁡slog⁡∣Pi∣)O(\log s\log |P_i|) for priority class PiP_i, using sksk leaves. However, this bound may be weaker than the existing O(log⁡k)O(\log k) guarantee of RandomCuts (Gupta et al., 2023). For example, when s=ks=\sqrt{k} and ∣Pi∣=k|P_i|=\sqrt{k} for all ii, Theorem 1.1 gives an O(log⁡2k)O(\log^2 k) bound with k3/2k^{3/2} leaves, whereas RandomCuts achieves O(log⁡k)O(\log k) with only kk leaves. Thus, the proposed algorithm does not always provide a stronger approximation guarantee when the number of priority classes is large, despite using more leaves.

Questions for authors

See Weaknesses.

2 comments

We thank the reviewer for the thoughtful feedback. Below, we address each of the reviewer's concerns.

  1. Tightness of Theorem 1.2 and strengthened lower bounds.

    We can strengthen the lower bounds of Appendix D in two complementary directions. First, the analysis of the lower bound instance of Appendix D implies a more general result than Theorem D.1: for every set SS of mm centers,

    leaves⁡(T)≥k+∑ct∈S[ln⁡k50−5αt]+.\operatorname{leaves}(T)\geq k+\sum_{c_t\in S}\left[\frac{\ln k}{50}-5\alpha_t\right]_+.

    Consequently, obtaining o(log⁡k)o(\log k) competitive ratio simultaneously for mm designated centers requires Ω(mlog⁡k)\Omega(m\log k) additional leaves. In the fully ordered setting, applying this result to the prefix S={c1,…,ci}S=\{c_1,\ldots,c_i\} gives an Ω(ilog⁡k)\Omega(i\log k) lower bound for simultaneously obtaining o(log⁡k)o(\log k) approximation for the first ii centers.

    Second, for every A≥2A\geq2 and k>mk>m, there exists an instance with mm designated high-priority centers such that achieving competitive ratio at most AA for all of them requires

    k+A3⌊k−m5000eA(A+1)2ln⁡(A+2)⌋k+\frac{A}{3}\left\lfloor\frac{k-m}{5000e^A(A+1)^2\ln(A+2)}\right\rfloor

    leaves. In particular, whenever k−m≥10000eA(A+1)2ln⁡(A+2)k-m\geq10000e^A(A+1)^2\ln(A+2), the number of additional leaves is

    Ω(k−meA(A+1)ln⁡(A+2)).\Omega\left(\frac{k-m}{e^A(A+1)\ln(A+2)}\right).

    Thus, up to polynomial and logarithmic factors in AA, roughly (k−m)e−A(k-m)e^{-A} additional leaves can be necessary. These bounds do not completely close the gap to Theorem 1.2, and we do not claim that the iterated-logarithmic factors are necessary. However, they substantially strengthen Appendix D and show that a significant number of additional leaves is unavoidable for strong priority-aware guarantees.

  2. Explanation complexity of individual clusters.

    We believe it is useful to distinguish between two different notions of explanation complexity. The notion used in this paper, consistent with the standard threshold-tree formulation of explainable clustering, is the explanation of an individual assignment: a point is explained by the conjunction of the threshold conditions along its root-to-leaf path.

    Under this notion, allowing a center to label several leaves does not make the explanation of an individual point more complicated by a multiplicative factor equal to the number of such leaves. A point still follows only one root-to-leaf path. For Algorithm 2, the initial RandomCuts tree has depth at most k−1k-1, and the final subtree attached to any leaf has ss leaves and hence depth at most s−1s-1. Thus, an individual assignment is described by at most k+s−2k+s-2 threshold conditions, independently of the ambient dimension dd.

    If one instead asks for a single logical description of the entire region assigned to a particular center, that region may be a union of multiple leaf regions. This is a different, more global notion of explanation complexity from the pointwise/path-based notion used throughout the explainable-clustering literature and in our paper.

    We can quantify this fragmentation for PrioriTree. For each of the kk leaves of the initial RandomCuts tree, the final subtree contains exactly one representative from every priority class PiP_i. Therefore, if LcL_c denotes the number of final leaves labeled by a center c∈Pic\in P_i, then

    ∑c∈PiLc=k.\sum_{c\in P_i} L_c=k.

    Thus, centers in PiP_i are represented by k/∣Pi∣k/|P_i| leaves on average, while a particular center may be represented by as many as kk leaves in the worst case. When ∣Pi∣=1|P_i|=1, the unique center in that class indeed labels exactly kk leaves.

    We will have this discussion in the final version of the paper.

  3. The regime with many priority classes.

    Theorem 1.1 is most useful when the important classes are relatively small and the number of priority levels is moderate. When there are many fine-grained priority classes, our ranked construction is more appropriate. In the reviewer's example, s=ks=\sqrt{k} and ∣Pi∣=k|P_i|=\sqrt{k}. Ordering the centers consistently with the priority classes gives every center in PiP_i rank at most iki\sqrt{k}. Theorem 4.1 therefore gives

    O(log⁡(ik)log⁡log⁡log⁡k)=O~(log⁡k)O\bigl(\log(i\sqrt{k})\log\log\log k\bigr)=\widetilde O(\log k)

    approximation with only O(klog⁡log⁡k)O(k\log\log k) leaves, instead of k3/2k^{3/2} leaves.

    Moreover, our strengthened lower bound shows that obtaining o(log⁡k)o(\log k) approximation simultaneously for all k\sqrt{k} centers of one such class can require Ω(klog⁡k)\Omega(\sqrt{k}\log k) additional leaves. These lower bounds are not tight, but show that a substantial number of extra leaves are required to beat Random Cuts. We will include closing the gap between upper and lower bounds as an interesting question for future work in the conclusion section, which we will add to the final version of the paper.

Thank you for your answers. The rebuttal addresses Weaknesses 1 and 2, while Weakness 3 is partially addressed. I suggest discussing the limitations for many priority classes in the Conclusion section. I will maintain my original rating.

Reviewer_KqPWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces and studies priority-aware explainable clustering for the k-medians problem under the l_1-norm, where reference cluster centers are assigned different priority levels and the decision tree is required to provide stronger competitive ratio guarantees for higher-priority centers. The authors design randomized algorithms ) that augment a standard tree by sampling priority-class representatives from the deepest ancestor nodes along each root-to-leaf path, achieving a log competitive ratio with sk leaves across s priority classes and an log log log competitive ratio with k(\log \log k)^1+eps leaves in the fully ranked setting.

Critical strengths

The paper moves beyond uniform worst-case guarantees by introducing center-specific priority hierarchies. This addresses high-stakes applications where misclassifying critical clusters is much more costly than others.

it introduces an algorithms (called PRIORITREE) and its recursive extension, utilizing an ancestor-sampling leaf-expansion mechanism to avoid tree-size blowups and low-priority distortion. This is paired with sophisticated probabilistic analysis of the Set Elimination Game via dyadic phase decompositions.

The paper establishes that randomized threshold trees require extra leaves (specifically, k+log k for single-center improvements and klogk for average competitive ratios), successfully demonstrating the near-optimality of the proposed bi-criteria trade-offs.

overall, the paper successfully bridges practical, high-stakes clustering requirements with elegant algorithmic design and tight theoretical bounds, providing both efficient mechanisms and mathematical proof of their optimality.

Critical weaknesses

Seems that there are inconsistencies regarding Theorem 1.1 and Lemma 5.2. While their formal statements restrict target centers and assume a specific cardinality ordering, the actual proofs and downstream applications (such as Theorem 4.1 and Appendix C) do not enforce or rely on some of these restrictions.

Seems that some logarithmic terms across multiple theorems and lemmas can evaluate to zero when parameters equal 11 (e.g., singleton priority classes or top-ranked centers). These should be adjusted.

The main body concludes abruptly right after the proof of Lemma 5.2 on page 9. Adding a dedicated conclusion section discussing key findings and open questions would significantly improve the paper's overall polish and flow.

The paper contains also smaller technical oversights that need clarification; e.g., Clarifying the left- versus right-limit convention during phase stopping times in the continuous-time Set Elimination Game.

Questions for authors

Address weakness points above;

The other issue is relevance to the scope of ICLR

1 comment

We thank the reviewer for their feedback. We proceed to address each of the weakness points mentioned by the reviewer.

  • We would like to clarify that the cardinality constraint

    ∣P1∣≤∣P2∣≤⋯≤∣Ps∣|P_1|\leq |P_2|\leq \cdots \leq |P_s|

    is not required by the analysis of PrioriTree. More generally, for any partition of the centers into ss non-empty groups, the same argument gives an approximation ratio

    O(log⁡s (1+log⁡∣Pi∣))O\bigl(\log s\,(1+\log |P_i|)\bigr)

    for every center in PiP_i, with the singleton case handled trivially. Thus, as far as the mathematical guarantee is concerned, the groups can always be indexed in non-decreasing order of cardinality. Our result is particularly interesting when this ordering is also consistent with the priority ordering: then higher-priority classes receive guarantees that are at least as strong as those of lower-priority classes. This is the reason we state Theorem 1.1 under the cardinality-ordering assumption.

    There is also no inconsistency in the use of Lemma 5.2. The set HH in the lemma can be any designated subset of centers. To analyze PiP_i, we apply it with H=PiH=P_i and L=C∖PiL=C\setminus P_i, exactly as in the proof of Theorem 1.1. We will make this point clearer in the revision.

  • The issue that expressions such as log⁡∣Pi∣\log |P_i| or log⁡i\log i can evaluate to zero when the corresponding parameter equals 11 is purely notational. We will replace them by, for example, 1+log⁡∣Pi∣1+\log |P_i| and 1+log⁡i1+\log i, or handle singleton cases separately. This is a trivial correction and does not affect any proof or asymptotic result.

  • We agree with the reviewer that a conclusion section would benefit the exposition. We will add a short conclusion summarizing the main results and several natural open questions.

  • The left/right-limit issue in the continuous-time Set Elimination Game is likewise a minor notational point. Our current definition makes R(t)R(t) the state immediately before an arrival at time tt. We will state this convention explicitly and use the corresponding post-arrival state whenever needed. No change to the stochastic process or to the analysis is required.

  • Finally, we believe that the work is well aligned with ICLR. Explainability is a central consideration in machine learning, and prior work shows that standard kk-leaf explainable kk-medians necessarily incurs an Ω(log⁡k)\Omega(\log k) worst-case loss. Our work asks whether this loss can be distributed non-uniformly when some clusters are substantially more important than others. By allowing a modest number of additional leaves, we obtain substantially stronger guarantees for selected high-priority centers while retaining logarithmic guarantees overall. We therefore believe that this priority-aware viewpoint is both theoretically interesting and relevant to interpretable machine learning.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised Paper and Experimental Results Overview

We thank the reviewers for their responses and helpful suggestions. We updated the paper to address the concerns of the reviewers.

We also include experimental results that support our claims.

Experimental Results:

We test the performance of a practical variant of PrioriTree that is very close to the theoretical algorithm, but makes two optimizations that are particularly useful in practice. We test the algorithm for 2 priority classes and in the ranked setting. Our experiments show that PrioriTree performs well in practice and, importantly, that by greedily trimming the additional leaves produced by PrioriTree when expanding the initial RandomCuts tree, we can obtain significantly smaller trees without hurting the clustering performance.

Specifically, recall that, for two priority classes, the theoretical PrioriTree algorithm first constructs a tree using RandomCuts and then expands every leaf of this tree using RandomCuts again. Our practical variant differs in two ways. First, only when expanding a leaf of the initial RandomCuts tree containing 2 centers (the single center in the leaf and a copied representative), instead of sampling the additional cut randomly, we greedily choose the best separating cut according to the training cost. The important characteristics of the algorithm, which are the selection of representatives and the initial RandomCuts tree remain unchanged. Second, we trim the resulting tree by retaining the extra splits that provide the largest improvement in training cost and discarding those with smaller gains. Our experiments indicate that most of the benefit of PrioriTree can be retained with substantially fewer additional leaves (sometimes 25% of the extra leaves used by the theoretical algorithm). We use the analogous ideas in the ranked setting, where small representative subtrees are fitted only inside the selected expansions.

We encourage the reviewers to read the experimental section, for more details, especially the graphs at the end of the paper. We will include additional experiments at the final version of the paper.

Addressing other concerns:

We also corrected notational inaccuracies mentioned by reviewer KqPW, included our stronger lower bounds and a conclusion section, where we discuss our results and future questions. We also expanded the discussion on why our bi-criteria algorithms are still explainable.

These changes will be further polished in the final version of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.