Summary
The paper studies the optimal upper bound of explainable k-median and shows a tight analysis for the random coordinate cut algorithm. The explainable k-clustering model was first introduced by Dasgupta et al. [ICML’20] and was followed by a flurry of work to understand the optimal approximation factor to achieve explainability. For the k-median task, previous work has shown that an $\Omega(\log k)$ factor is necessary, and algorithms that follow a random coordinate cut scheme can achieve $O(\log k \cdot \log\log k)$-approximation. This paper shows that by picking appropriate distributions, the random coordinate cut can achieve the asymptotically tight approximation of $O(\log k)$.
At the heart of the analysis of the paper is a newly-defined *set elimination game* (SEG), where elements are split into multiple (potentially overlapping) sets, and the referee takes an element $e$ at random and eliminates all the sets that contain $e$ unless every remaining set contain $e$. The final value of the game is defined as the measure of the final surviving set. The paper establishes the upper bound for explainable k-median clustering by: 1). showing a ‘’reduction’’ from the cost of explainable k-median of a single point $x$ to the value of the SEG, 2). proving the expected value of the game as $O(\log k)\cdot \mu(S^*)$, where $S^*$ is the set with the smallest measure.
In my opinion, the paper is generally well-written, and it settles an important question in explainable k-median clustering. The proof idea is novel, and it is presented in a clean manner (minus some minor exposition issues, see the weakness for details). Therefore, I believe the merits of the paper are sufficient for acceptance.
Strengths
Explainable clustering has been a popular topic in the recent few years, and the paper settles an open problem in the area. The idea of set elimination games is novel and interesting, and the paper is well-written. The organization helps the reader a lot in understanding the paper.
Weaknesses
I do not see any major technical weaknesses in the paper. On the exposition part, I have some minor comments:
- The paper is written in relatively advanced technical languages, and they might not be readily accessible to the broader NeurIPS audiences. To make the readers’ task easier, I think it makes sense to add some more intuitions on why using the set elimination game, why the value should be small, and the high-level intuitions for the analysis.
- Conversely, the paper spent little effort discussing why explainability in k-clustering is important and why shaving off the exponentially-small $\log\log k$ factor is significant. I would recommend adding some discussion on this front for later versions.
- Some notation problems. In the proof of Theorem 2.2, there is a slight overload of notation in the construction of $\Omega$, and $S$: $S$ was used as a *variable* for the sets in the definition of the SEG, but in the proof it becomes the *realization*, i.e., fixed sets. I would recommend using a different notation instead. Also, $x_j$ (which I guess means the j-th coordinate of the point $x$) is used before it is defined.
Questions
- You never mentioned the initialization of the reference sets, but judging from the proof of Theorem 2.2, you’re assuming the optimal k-median centers as the reference centers, right? Something like this should be mentioned and discussed.
- You never mentioned the *distribution* of the random coordinate cut in the paper; from the requirement of Theorem 2.1, it seems uniform at random works. Is this right? You should explicitly define the distribution, either way (‘’pick at random’’ $\neq$ ‘’pick uniformly at random’’ – the former only means picking something from *a* distribution).
- What is the intuition for the 'surprising sets'? I can read that the name 'surprising' may come from the fact that for $h(S_1) \cdot \mu(S_i) \geq \log k$, either $S_1$ should be hit very late or $S_i$ should have a high volume, which means it should have been hit/eliminated way earlier. If this is true, please also add a discussion about it, as it'll help readers understand your proof.
- Do you see any other applications for the Set Elimination Game?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The work is of theoretical nature, so the (non-technical) limitations are on the model side, e.g., the explainable clustering model might not provide easy-to-understand explanations in real life. However, I do not think this affects the significance of the contribution.