Summary
This paper studies the concept of replicability in clustering. This topic is important because replicability is what allows for other researchers to reproduce the results of a study to verify their correctness. This is a big problem these days, 50% of scientists saying that there is a replicability crisis. In the interest of improving the scientific verification process, designing replicable algorithms (i.e., algorithms that function the same when executed twice with the same random seed). This differs from the related notion of clustering stability in that its success is more dependent on the algorithmic design than structures in the data.
In their setting, points are sampled from a random distribution over the d-dimensional unit ball according to some given metric. It models many norms, including \ell_p norms. They use Impagliazzo et al.’s notion of rho-replicability: The probability (over every two sampled sets of points and a single random seed) that the algorithm on each set but with the same random seed yields the same output is at least rho. Outputs to these clustering problems are functions that, given a point, assigns it to a cluster (with no explicit center, just an identifier).
The main results are new algorithms for statistical k-means and k-medians, with extended improvements when using the Euclidean metric. Their approximation factors both near the approximation factor of a given black-box vanilla algorithm, and their sample complexity on general metrics has an exponential dependence on the dimension (it is sub-exponential in the Euclidean version). They also show an approximation algorithm for the replicable statistical k-centers algorithm. Given an approximation of the form a*OPT+b for k-centers, they give an approximation of the form c*OPT+d, where c and d are linear in both a and b. The query complexity is exponential in the dimensionality.
Their algorithm uses a quadtree decomposition, which creates a tree structure over all points. The leaves (which correspond to points) are then mapped to cluster centers. So when you receive a query for a point, you traverse the tree to find the leaf which contains it (as it is a partition of the space), and you map it to the corresponding cluster. However, in order to adequately depict the distribution of the space with their decomposition (which they are not given), they require access to an exponential number of queries in d. In the Euclidean case, they can first reduce the dimensionality via Johnson-Lindenstrauss, and map an epsilon-net from the original space to the low-dimensional space. There still is the difficulty of mapping the clustering between these two spaces, but it seems most of those details are in the appendix.
For replicability, they form a grid, sample points in the space, and map them to the centers of cells to estimate probability mass of each cell. On high-mass cells according to a random threshold, and then they apply a vanilla algorithm.
Finally, they compare k-means++ and k-means++ run on the core produced for their replicability results. It is pretty clear that their approach leads to much greater replicability.
Strengths
This paper is written extremely clearly. I really appreciate how slow and careful the introduction and preliminaries are, which I believe could be followed by someone unfamiliar with the field. For instance, while many of us take for granted that a replicable clustering algorithm optimizes for some utility notion, they take the time to explain this and how it is distinct from their replicability goal (which is a bigger focus of their preliminary section). They also take the time to point out to the reader that their metric function and the ell_p parameter p are different, and give an in-depth but understandable explanation of the intuition behind ell_p for different values of p. The informal presentation at the beginning of results in section 3 is also very nice.
The results are nice and interesting, but I wouldn’t say they are groundbreaking. The techniques have clear foundations in previous methods, but it also seems unique how they combined them together. I wasn’t sure by reading the paper how their replicability results compare to previous literature.
Weaknesses
I found it very odd that the main focus of the paper introduction and title was replicable k-centers, but they spend most of their time on (nonreplicable) k-centers. It seems like if the highlight of the paper was replicability, they should have focused on the methods used to achieve this. I feel the details of this algorithm were insufficient for a reader invested in replicable k-centers. Additionally, I wasn’t sure how their results compared to any baseline results that exist, so it is difficult to judge the novelty.
Questions
1. I was a bit confused by the sentence “We emphasize that even though we only observe a sample from P we aim to solve the problem on the whole support of the distribution.” Can you clarify exactly what this means? Is it that the algorithm works on an actual given dataset P but needs to be able to work on all possible datasets? I would think that would be assumed.
2. How do your algorithms compare to existing algorithms? Is there any baseline implied by any other work?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
There was no limitations section, though it did not seem needed (but would be preferred).