Faster Approximation Algorithms for k-Center via Data Reduction

We thank the reviewer for insightful comments. We address the main concerns as follows.

As a alternative for deriving the bound, one could also first construct a spanner for high dimensional Euclidean spaces by Sariel Har-Peled, Piotr Indyk, Sidiropoulos (SODA'13) and then run an algorithm for k-center in sparse graphs by Thorup (SICOMP'04). Since these results were published earlier than the Eppstein, Har-Peled, Sidiropoulos paper, they should at least be mentioned.

Thanks for suggesting these references. We will add these in the next version.

The experiments could be better. The authors mainly compare between coreset-based approaches, but this leaves out other option. While the uniform sampling can serve as a sanity check for "is the data set trivial to cluster" and should be included, I am not sure what the point of the low-dimensional coreset construction is, which is designed for small approximation factors.

Although conceptually the low dimension baseline is not very relevant to our regime, we find the construction algorithm is in fact very similar to our high dimensional coreset. In particular, in an optimized variant/implementation of the low dimensional baseline, it is the same with our high-dimensional algorithm except that the random shift is skipped (and is replaced with a fixed grid). It is thus interesting to compare with such a baseline to demonstrate the usefulness of the random shift.

A more interesting comparison would have been for using a tree embedding ... which has $\mathrm{polylog}(n)$ approximation ...

First, we note that while tree embedding has $O(\log n)$ distortion, it has bounded distortion only in the expected sense, and this is too weak for $k$-center where we care about the max distance. Therefore, we think that tree embedding cannot yield a finite ratio for $k$-center, at least not $\mathrm{polylog}(n)$.

Nonetheless, we still try to add tree embedding as a new baseline, and we rerun the experiment on the Fashion-MNIST baseline. The initial result is listed here: Cost evaluation with new baselines -- Fashion-MNIST. Indeed, it shows that tree embedding performs poorly on this dataset.

One other question that immediately came to my mind is why the main result cannot be applied recursively. While the approximation will deteriorate, the dependency on $n$ could be reduced even more. I see no clear reason why that should not work and it would be nice if the authors either included it (with a discussion on how the parameters would change) or explained why it wouldn't work.

We thank the reviewer for the interesting suggestion. The short answer is that in some parameter regimes (and in particular in the $k = n^{1 - \epsilon}$ regime which we focus on), a recursive application will lead to an improved coreset size, and a respective improvement in the runtime for the $k$-center algorithm. The optimal number of recursion iterations depends on $k$. In what follows we provide a more detailed explanation.

Denote by $n_j$ the coreset size after $j$ applications of our algorithm. The first coreset is of size roughly $n_1\sim k n^{\alpha^{-2/3}}$, running it again will get us an $O(\alpha)$-coreset of size $n_{2}\sim k\cdot\left(kn^{\alpha^{-\frac{2}{3}}}\right)^{\alpha^{-\frac{2}{3}}}=k^{1+\alpha^{-\frac{2}{3}}}\cdot n^{\alpha^{-\frac{4}{3}}}$, and this is an improvement when $k\le n^{1-\alpha^{-\frac{2}{3}}}$. In general, for any fixed $j$, one can apply the algorithm recursively $j$ times and get an $O(j\cdot\alpha)$ coreset of asymptotic size $n_{j}\sim k^{\sum_{q=0}^{j-1}\left(\alpha^{-\frac{2}{3}}\right)^{q}}\cdot n^{\left(\alpha^{-\frac{2}{3}}\right)^{j}}=k^{\frac{1-(\alpha^{-2/3})^{j}}{1-\alpha^{-2/3}}}n^{(\alpha^{-2/3})^{j}}$. This is beneficial as long as $k\le n_j^{1-\alpha^{-\frac{2}{3}}}$. However, one should note that our notation hides polylogarithmic factors that will accumulate. Thus one should use the recursion only a constant number of times.

Applying [EHS20] on top of the resulting coreset after $j$ iterations will lead to an $O(j\cdot\alpha)$ approximation algorithm for $k$-center with running time bounded by $\tilde{O}\left(n+n_{j}^{1+\alpha^{-2}}\right)=\tilde{O}(n)+\tilde{O}\left(k^{\frac{1-(\alpha^{-2/3})^{j}}{1-\alpha^{-2/3}}}n^{(\alpha^{-2/3})^{j}}\right)^{1+\alpha^{-2}}\le\tilde{O}\left(n+k^{\frac{1+\alpha^{-2}}{1-\alpha^{-2/3}}}n^{\alpha^{-\frac{2j}{3}}\cdot(1+\alpha^{-2})}\right)$, for any fixed $j$.

We will do a more detailed calculation and add it to the next version.

We thank the reviewer for insightful comments. We address the main concerns as follows.

The algorithm achieves a constant factor approximation but not 2.

We agree that achieving a factor of $2$ in near-linear time when $k = n^{1 - \epsilon}$ is an ideal goal and is certainly an interesting open question. Although our work does not directly resolve it, we still offer relevant techniques for attacking the problem, which has potential to lead to small factor approximation (e.g., a ratio of $4$).

We thank the reviewer for insightful comments. We address the main concerns as follows.

In terms of methods, in coreset literature, people typically obtain centers from the coreset and then report the loss on full data using those centers and compare it with the cost on full data when the problem is directly solved for the full data. Are the same quantities shown in the graphs in Figure 1? It is not clear to me.

We do compare the cost in the full data. We will clarify this in the next version.

The authors could have used more sampling techniques as baselines for example they could have used coresets for other clustering problems like $k$-means, $k$-median and used them as baselines also along with uniform sampling.

We added $k$-median coreset as a baseline, based on the ring sampling method (see e.g. [1][2]) which is widely used in various recent works. We obtain an initial result for the cost evaluation on the Fashion-MNIST dataset, and our result can be found in the following: Cost evaluation with new baselines -- Fashion-MNIST. We will complete the experiment on the other datasets in the next version.

In short, this $k$-median coreset baseline performs similarly to the uniform sampling baseline, and is worse than our algorithm.

[1] Ke Chen. On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. SIAM Journal on Computing, 2009.

[2] Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn. A new coreset framework for clustering. STOC 2021.

The paper relies heavily on the idea of consistent hashing which is pretty recent. It would be good to give some more intuitive explanation of this ideas. For e.g. what $\Gamma$ and $\Lambda$ mean intuitively.

The consistent hashing is a space partition, where each part is a bucket. Ideally, we wish each part has a bounded diameter $\ell$ (which can be picked arbitrarily), and that any subset $S$ that has diameter $O(\ell)$ is completely contained in one bucket -- this ensures consistency in hashing subsets of $O(\ell)$ diameter.

Compared with the ideal case, what we actually obtain is relaxed in two aspects: a) the guarantee of consistency is relaxed to intersecting $\Lambda$ buckets instead of only one, and b) the subset $S$ needs to be small enough, whose diameter must at most $\ell / \Gamma$, instead of $O(\ell)$.

We will add this explanation in the next version.

If I understood correctly, in the definition of consistent hashing a smaller $\Lambda$ is better? Am I correct? If yes, how is the $\Lambda$ you obtain better than the existing one, since the parameter $c$ is less than 1.

Indeed, our $\Lambda$ is not better than the state of the art. However, the state of the art that achieves the best $\Lambda$ has a $2^d$ running time which is too costly. Instead, the focus of this paper is to find an efficient construction that runs in $\mathrm{poly}(d)$ time, at the cost of a worse yet still useful parameter.

How does your algorithm perform/ compare with others in case of small and moderate $k$ values?

We already provided a brief discussion of this in the introduction. Basically, for moderate $k = n^{1 - \epsilon}$ (where $0 < \epsilon <1$ is arbitrary), our algorithm can achieve $\mathrm{poly}(1 / \epsilon)$-approximation in $\tilde{O}(nd)$ time. This is better than the other works we mention, which either runs in $O(nk) = O(n^{2 - \epsilon})$ time, or in $n^{1 + \mathrm{poly}(\epsilon)}$ time, but not near-linear in $n$ as we do.

While I understand hiding the dependence on $\log n$ in the $\tilde O$ notation, I am not sure about the dependence on $d$. How will your algorithm perform compared with the Gonzalez and Eppstein algorithm in terms of $d$, especially as we may encounter problems where both $k$ and $d$ are large and using the JL Lemma will have impact on accuracy.

Indeed, we did not attempt to optimize the dependence of $d$ in Theorem 1. The dominating dependence of $d$ comes from Lemma 3.3 (which is a mathematical fact about Minkowski sum), and in other places our algorithm runs (nearly) linear in $d$. Therefore, the dependence of $d$ in the worst-case bound is worse than Gonzalez.

However, in practice one may not need to follow the worst-case upper bound of Lemma 3.3. In particular, in our implementation (in the experiments), for any given coreset size, our dependence of $d$ is near-linear.

We thank the reviewer for insightful comments. We address the main concerns as follows.

General Applicability of Coresets: ... The paper focuses on the Euclidean k-Center problem, so it’s unclear how easily these methods could extend to non-Euclidean metrics or more complex clustering structures.

Our techniques may extend to $\ell_p$ metrics, for example $\ell_1$. Indeed, the main Euclidean structure that we utilize is the consistent hashing, and such hashing with competitive bounds for $\ell_p$ spaces were known to exist, see e.g. [1] (albeit one may need to devise efficient constructions of the hashing, as in our paper).

[1] Arnold Filtser. Scattering and Sparse Partitions, and Their Applications. ACM Transactions on Algorithms, 2024.

Scalability to Extremely Large Datasets: ... However, it would be valuable to have further evidence on how the approach scales with extremely large datasets (e.g., millions of points and very high-dimensional spaces). Since real-world applications often deal with such data sizes, this would provide more insight into the practicality of the approach.

We expect that our algorithm would be competitive even in this extreme case.

On the one hand, the high dimensionality $d$ is a somewhat less important challenge in our case, since one may apply Johnson-Lindenstrauss Transform to make $d = O(\log n)$, so we do not expect super-high $d$ would have a significant impact to our algorithm.

On the other hand, for the case of $n$ being millions of points, we already demonstrated the performance of our algorithm in this case, in our kddcup dataset which has $n = 5M$, and $d = 38$.

Failure Probability: The paper mentions a failure probability for certain parts of the algorithm, but a more detailed discussion on how this failure probability affects the overall performance, particularly in practical settings, would be useful. ... Including error bounds or confidence intervals for the reported performance would help quantify the robustness of the approach. The statistical significance of the experimental results is not addressed. While the authors run multiple trials for their experiments, providing error bars or statistical tests would improve the reliability of the findings, especially when comparing performance across datasets or baselines.

First of all, we already take the failure probability into account in our experiments, and we report the cost etc. after we run the algorithms multiple times and take the average.

We also added new experiments to show the variance of the cost of our algorithm. Please check the following for the results of each dataset:

Census

Covertype

Fashion-MNIST

KDDCup

In short, the variance is very small compared with the magnitude of the cost.

how does the algorithm perform on datasets with extreme characteristics, such as sparse or imbalanced data? These scenarios are common in many real-world applications, and understanding how the algorithm handles them could further demonstrate its robustness. ... The paper doesn’t fully address how well the method handles noisy data or missing values, which are often present in practical datasets. Given that many real-world applications involve imperfect data, providing results for these scenarios would make the paper’s findings even more impactful.

We actually find imbalanced distribution/outliers in our KDDCup dataset. This also a way to explain why the uniform baseline performs so bad in this dataset (since it misses the extreme point which may affect the $k$-center objective significantly). Nonetheless, our algorithm performs consistently well even in this dataset.

The missing value seems to be an independent challenge, since it usually requires modeling the missing value to make the problem well-defined. Hence, this is indeed out of the scope of our current algorithm, but it is nonethelss interesting to explore how to model missing values for $k$-center.