- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper explores improvements to the K-Means clustering algorithm. Building upon the NLR matrix factorization method previously proposed by others, this approach incorporates engineering techniques to achieve a more memory-efficient implementation.
Critical strengths
-
Some of the engineering techniques presented in the paper are useful, such as normalization and matrix product computation.
-
The method proposed in the paper offers storage advantages when dealing with large-scale data.
Critical weaknesses
-
The paper’s level of innovation is extremely limited. It appears to lack any theoretical novelty, offering only optimizations to the engineering implementation strategies that are both commonplace and intuitively obvious (e.g., data normalization, reducing the storage of intermediate variables). Consequently, I do not believe the paper possesses the level of innovation or the core contributions required for publication at ICLR.
-
The proposed method appears to be merely an engineering refinement of the NLR approach [Zhuang et al. 2024]. Theoretically, it should yield the same level of accuracy as NLR; however, the paper fails to provide a direct numerical comparison against it. Furthermore, any performance advantages over other methods should be attributed to the underlying NLR framework rather than the proposed method.
-
The runtime of the proposed method is significantly longer than that of existing approaches. As shown in Section 5.2.2, the proposed method requires 38 minutes, compared to just 39 seconds and 20 seconds for the baseline methods, which makes it roughly 58 times slower. Therefore, the proposed method has poor practicality.
-
The paper lacks ablation studies to validate the individual contribution of each component of the proposed method.
Questions for authors
Why not compare the NLR [Zhuang et al. 2024]?
2 comments
Thanks for the clarifications and extensive additional experiments. The authors' response has addressed some of my concerns regarding the experimental comparisons. However, I still believe that the paper's main contribution lies in engineering optimizations for computational efficiency, rather than a novel clustering algorithm or improved clustering accuracy. Therefore, I maintain my negative assessment of the paper.
Response to Reviewer b1rz
We thank the reviewer for suggesting a direct comparison with unfused NLR. We performed the suggested experiment and report the results in Global Response and Additional Experiments I. On the same H200, unfused PyTorch NLR took 1.9 to 3.9 times as long per iteration as GEM across four synthetic settings. Both implementations achieved a mean ARI of 1.0000 to four decimal places.
We address the four concerns in the order raised:
The memory saving requires resolving a dependency between the projection and the stopping rule. The projection's scale factor becomes available only after a reduction over the entire tentative update. By then, a straightforward in-place implementation has overwritten the previous factor needed to compute iterate movement. GEM accumulates the squared norms of both factors and their inner product while the old and tentative entries are still available. Once the scale factor is known, those three scalars give the squared movement in exact arithmetic.
We compute these statistics in the matrix-multiplication epilogue and avoid materializing the gradient. Together, these changes eliminate two full-size FP32 buffers. Unfused GPU NLR in Global Response and Additional Experiments I quantifies the memory savings through buffer estimates and reports measured peak allocations for the PyTorch baseline. Furthermore, spectral normalization makes step-size selection less sensitive to the scale of the dataset. With the rescaled constraint residual, the fixed-dual smoothness bound in Proposition 1 has no explicit dependence on the sample size, which helps explain why we can use the same step size across datasets of very different sizes.
We indeed attribute the recovery gains over Lloyd to the original NLR formulation. GEM's contribution is to reduce the cost of solving it. With the same normalized objective, initial factor, solver parameters, and stopping rule, the fused and unfused implementations follow the same iterates in exact arithmetic. We used the same datasets for both implementations and generated their initial factors independently. For these experiments, we used an updated version of GEM with BF16 inputs to the matrix multiplications. The PyTorch baseline used FP32 with TF32 disabled.
Gaia is a scalability test. GEM solved the real world data problem on 118 million observations using a single GPU. In the separate 200-million-point benchmark, GEM finished faster than Flash-KMeans, which was forced to use CPU-GPU streaming due to memory constraint.
The extra computation is most useful when a poor partition could affect downstream conclusions and reference labels are unavailable. Figure 3 of Zhuang et al. (2024) illustrates this risk through variable Lloyd recovery on CyTOF and high-error runs on CIFAR-10. Without reference labels, a user may accept a poor partition simply because the solver met its stopping criterion.
Our new results in Global Response and Additional Experiments II show that the recovery gap persisted after ten Lloyd restarts per dataset. Across the two settings with 100 clusters, none of the individual Lloyd starts reached an ARI of 0.99, while GEM’s mean ARI rounded to 1.0000 in both settings. GEM also reduced mean excess misclustering error from 0.247 to 0.162 under cluster imbalance and achieved a mean ARI of 1.000 versus 0.934 for Lloyd under anisotropic noise. These demonstrate the robustness of GEM/NLR.
The experiments discussed above cover the unfused NLR comparison, Lloyd restarts, and robustness to departures from the mixture assumptions. To isolate the effect of label recovery, we also compared readouts on the same fitted factors. Direct K-means and SVD followed by K-means both achieved near-perfect recovery on the balanced isotropic and anisotropic mixtures. Under strong imbalance, adding SVD increased mean ARI from 0.871 to 0.886. See Label recovery in Global Response and Additional Experiments II.