Summary
This paper studies the standard $k$-means problem. Given a $k$-means instance $(P,k)$, the goal is to find a set $C$ of centers with size at most $k$ such that the sum of the squared distances from $P$ to $C$ is minimized. For the $k$-means problem, Lattanzi and Sohler (ICML 2019) proposed an elegant combination of the local search and the $k$-means++ seeding methods. Instead of enumerating all the swap pairs constructed between the data points and the current centers, they showed that $k$-means++ sampling can be used for sampling a data point to serve as the candidate center for swapping in such that a $509$-approximation can be achieved in expectation in time $O(ndk^2loglogk)$. This paper extends the single-swap strategy to multi-swap strategy. In a single local search step, this paper shows that using $k$-means++ to sample $t$ data points induces a good $t$-swap for the local search process such that the clustering cost can be reduced significantly by at least a $\Omega(1-1/k)$ fraction with certain probability. After $O(k^{t-1})$ local search steps, an improved approximation can be achieved related to the swap size $t$, where the total running time can be bounded by $\tilde{O}(ndk^{2t})$. When $t$ is large enough, the approximation could be smaller than 10.48. By combining the techniques from Cohen Addad et al. (NeurIPS 2021), the papers shows that by using more local search steps (with exponential dependence on $\epsilon$), the approximation guarantee can nearly match the lower bound of the $9+\epsilon$ of the standard multi-swap local search method.
Strengths
The strengths of this paper can be summarized as follows:
1. This paper proposes a fast multi-swap local search method for solving the standard $k$-means problem, which runs in linear time in the data size. The approximation ratio significantly improves the previous one with linear running time in the data size (i.e., 509-approximation)
2. This paper gives another multi-swap local search method which better approximates the optimal clustering centers during the local search swaps using a subroutine called APX-CENTERS, where an improved approximation guarantee, i.e., $9+\epsilon$, can be obtained with running time exponentially dependent on $poly(\epsilon^{-1})$. The approximation ratio matches the approximation lower bound of local search methods for the $k$-means problem and significantly improves the running time of previous work based on direct enumeration of swap pairs constructed between the whole dataset and the current centers opened.
3. In experiments, this paper proposes a heuristic method which avoids the exhaustive searching process for determining which subset of the sampled set of data points should be swapped in. The experiments show that the multi-swap local search method achieves better performance on clustering quality with fixed local search iterations compared with single-swap local search methods.
Weaknesses
1. Although the authors show that sampling-based multi-swap local search can improve the approximation to a very small constant and even matches the lower bound of local search methods, the core idea behind is to use the successive $k$-means++ sampling strategy to construct candidate set of centers for swapping in, which is an extension of the sampling-based local search method (denoted as LS++ method )proposed by Lattanzi and Sohler. The claimed improvement in ratio seems to be minor as LS++ already guarantees constant approximation (in [1] the authors claimed that they did not attempt to optimize the constants and this paper verifies that LS++ can yield approximation ratio smaller than 26.4). The key idea behind the analysis for multi-swap local search method is as follows: (1) the authors further divide the optimal clusters into different groups according to their current clustering cost (i.e., $cost(P_h^*,C) \ge \delta ALG/k$ or $cost(P_h^*,C) < \delta ALG/k$) (2) the authors give weights for swap pairs such that each current center can be used for at most $(1+1/t)$ times when performing a summation of all bad swap pairs. The analysis for probability lower bound that induces a good swap is similar to that of LS++ method.
2. Some theoretical details is unclear to me. During the construction of ideal weighted multi-swaps, this paper partitions the optimal clustering centers and current clustering centers based on $\tilde{O}=${
$o_i \ | \ cost(O_i^*,C) \ge \delta ALG/k$} and $\tilde{C}=$ $C\backslash$ {$C[o_i] \ | \ o_i \in O^* \backslash \tilde{O}$}. Then, in the construction of ideal multi-swaps, each swap is consist of $In$ and $Out$ such that $In \subseteq \tilde{O}$ and $Out \subseteq \tilde{C}$. If my understanding is not wrong, some of the optimal centers in $\tilde{O}$ is not used for construction of ideal multi-swaps. If not all optimal centers is used at least once for constructing ideal multi-swaps, then the bound for summation of clustering cost for all "bad'" optimal clusters may not hold in Lemma 11. The ideal multi-swaps construction considers the two caes: (1) for each center $c_i \in \tilde{C}$ that is neither busy nor lonely, form $In$ with the optimal centers captured by $c_i$ (multi-swap) and borrow $|In|-1$ lonely centers from $L$ (2) for each center in $\tilde{C}$ that is busy, form single swap using each of optimal centers captured by $c_i$ and the lonely centers in $L$. However, there may exist some case that for some optimal clusering center $o_i^* \in \tilde{O}$, the current center $c_j$ that captures $o_i^*$ is not in $\tilde{C}$ and hence $o_i^*$ will no longer be used for constructing ideal multi-swaps. Here is an example where $o_i^*, o_2^*, o_3^*$ is the optimal clustering centers, and $c_1$, $c_2$, $c_3$ is the current centers with swap size $p=2$. In this instances, it holds that $c_1$ captures $o_1^*$ and $o_2^*$, $c_3$ captures $o_3^*$, $cost(O_1^*,C) \ge \delta ALG/k$, $cost(O_2^*,C)<\delta ALG/k$ and $cost(O_3^*,C) \ge \delta ALG/k$. Hence, we have $\tilde{O}=${$o_1^*,o_3^*$} and $\tilde{C} =${$c_2,c_3$}. During the construction of ideal multi-swaps, since $c_1$ is not in $\tilde{C}$, $o_1^*$ will never be used during the construction.
3. Another main weakness of this paper is the experiments. (1) As a local search algorithm, it’s important to validate the performance of the proposed algorithm within a certain time limitation, which is not presented in the experimental results. This paper mainly compares the experimental performances with fixed local search steps. It is unfair since multi-swap local search method takes more time than single-swap local search methods (i.e., the LS++ method). (2) In experiments, the maximum local search step is set to be 50, which is much smaller than the theoretical bounds (100000kloglogk) for obtaining good performance for LS++ algorithm. For this setting, even single-swap local search method may not converge to a good local optimal solution. The authors should present more evaluation for larger local search steps (i.e., several hundreds or thousands of local search steps) and fixed running time that is large enough for each algorithm to reach the convergence. (3) The size of the tested datasets is rather small (i.e., no larger than 500,000). However, in the recent results for clustering algorithms, instances of size over 1 million [1] or even 100 million [2] have been considered. Since multi-swap local search is much slower than the single-swap local search method (even with heuristic acceleration by avoiding the enumeration of all subsets of data points for swapping in), it is unclear that whether the proposed algorithm can scale well on large-scale datasets compared with single-swap local search method.
[1] Ren J, Hua K, Cao Y. Global Optimal K-Medoids Clustering of One Million Samples[J]. Advances in Neural Information Processing Systems, 2022, 35: 982-994.
[2] Matsui Y, Ogaki K, Yamasaki T, et al. Pqk-means: Billion-scale clustering for product-quantized codes[C]//Proceedings of the 25th ACM international conference on Multimedia. 2017: 1725-1733.
Questions
1. During the construction of ideal multi-swaps, can the construction process described in the paper guarantee that all the optimal centers in $\tilde{O}$ is used at least once for constructing ideal multi-swaps (see the example of weakness 2). If some of the optimal clustering centers are not used for constructing ideal multi-swaps, will the bound for summation of clustering cost for all "bad'" optimal clusters in Lemma 11 still hold?
2. In Lemma 2, this paper shows that if the current clustering cost for some optimal cluster $O_i^*$ is larger than $(2+3\delta)$ times its optimal clustering cost, the clustering cost of data points close to $o_i^*$ should take a large fraction (related to $\delta$) of the whole clustering cost induced by $O_i^*$. Hence, in each local search step, the success probability for performing a good swap should be related to parameter $\delta$, for example $\Omega(1/\delta)$. However, the running time of the proposed multi-swap local search algorithm is independent of $\delta$. I think there should be at least an $\frac{1}{\delta}$ term in the running time, or does it mean that $\delta$ is a constant given as the input, please explain.
3. In previous multi-swap local search approximation schemes, the approximation ratio is given as a function related to the swap size $t$ (i.e., in [1], the approximation is given as $(3+2/t)^2$). However, in this paper, the approximation ratio is determined by an inequality related to $\eta$ and $t$. Can the author provide the approximation ratio in the form similar to that of [1] such that one could figure out how large that swap size is enough for obtaining an approximation guarantee of 10.48.
4. Why are all the instances in the experimental setting small? In the recent results for clustering algorithms, instances of size over 1 million [2] or even 100 million [3] have been considered. How does the proposed multi-swap local search method scale on large datasets?
5. What are the performances of different local search algorithms within a certain time limitation (large enough for reaching the convergence)?
[1] Kanungo T, Mount D M, Netanyahu N S, et al. A local search approximation algorithm for k-means clustering[C]//Proceedings of the eighteenth annual symposium on Computational geometry. 2002: 10-18.
[2] Ren J, Hua K, Cao Y. Global Optimal K-Medoids Clustering of One Million Samples[J]. Advances in Neural Information Processing Systems, 2022, 35: 982-994.
[3] Matsui Y, Ogaki K, Yamasaki T, et al. Pqk-means: Billion-scale clustering for product-quantized codes[C]//Proceedings of the 25th ACM international conference on Multimedia. 2017: 1725-1733.
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed 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
Since this is a theoretical paper, I don't think there is potential negative societal impact of this work.