acceptodds
Under review as a conference paper at ICLR 2027

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

Abstract

Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for -means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Clustering, GPU acceleration, Pareto frontier, memory efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_b1rzOpenReview ↗
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
AuthorsOpenReview ↗

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:

  1. 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.

  2. 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.

  3. 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-KKMeans, 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.990.99, while GEM’s mean ARI rounded to 1.00001.0000 in both settings. GEM also reduced mean excess misclustering error from 0.2470.247 to 0.1620.162 under cluster imbalance and achieved a mean ARI of 1.0001.000 versus 0.9340.934 for Lloyd under anisotropic noise. These demonstrate the robustness of GEM/NLR.

  4. 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 KK-means and SVD followed by KK-means both achieved near-perfect recovery on the balanced isotropic and anisotropic mixtures. Under strong imbalance, adding SVD increased mean ARI from 0.8710.871 to 0.8860.886. See Label recovery in Global Response and Additional Experiments II.

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.

Reviewer_AYV1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces GEM-KMeans, a memory-efficient GPU implementation of non-negative low-rank (NLR) matrix factorization designed for large-scale K-means clustering. The method incorporates spectral normalization and integrates gradient updates, non-negative projections, and sufficient-statistics accumulation directly into GPU matrix-multiplication kernels. While preserving NLR's original mathematical formulation, this approach reduces the number of required buffer matrices—each matching the size of the factor matrices—from three to one. The authors establish the smoothness and descent properties of the "fixed dual projection gradient update" and evaluate the method using synthetic Gaussian mixture data, CyTOF data, and the Gaia DR3 dataset, which contains 118 million samples. Experimental results show that, compared with various GPU-based K-means baselines, this method achieves higher clustering accuracy, though it incurs a notable runtime increase under certain configurations.

Critical strengths

Significant contributions have been made toward improving memory efficiency. With a fused GPU implementation, the memory requirements—which typically scale with the number of factors—have been drastically reduced, without sub-sampling or altering the underlying NLR objective function. This is a major advancement, as it enables existing, statistically grounded clustering methods to operate on sample sizes that were previously intractable.

The approach has been robustly validated for large-scale applications. Experiments involving up to hundreds of millions of samples consistently demonstrate superior clustering quality across a variety of settings. This confirms that these engineering-level innovations extend well beyond theory, proving highly practical and effective in real-world scenarios.

Critical weaknesses

The methodological and theoretical innovations are limited. The clustering formulation and core motivation—rooted in the concept of "statistical recovery"—both derive from prior research on NLR/SDP. The paper's convergence analysis focuses on the descent process under fixed dual variables, rather than establishing convergence or statistical recovery guarantees for the full primal-dual algorithm as implemented. Consequently, the paper’s primary contribution is confined to implementation-level optimizations, making its significance in the broader field of machine learning modest.

The trade-off between clustering accuracy and runtime is poor. Improving clustering accuracy comes at an exorbitant computational cost. For instance, on the Gaia DR3 dataset, the reported gain in average Normalized Mutual Information (NMI) is only about 0.01, while the median runtime surges from 20–39 seconds (for the baseline methods) to approximately 38 minutes for GEM-KMeans. Unless a specific application scenario strictly demands such marginal gains in clustering consistency, this method's practical value is significantly diminished. To establish its utility in real-world applications, a more systematic, comprehensive comparative analysis—conducted under comparable runtime or computational-budget conditions—is required.

Questions for authors
  1. Does the theoretical analysis provide guarantees for convergence or exact recovery for the full primal-dual algorithm (including the dual update step)? Or do these guarantees apply only to the projected gradient iterations with fixed dual variables (i.e., guaranteeing only descent)? Please explicitly state which specific conclusions apply to "Algorithm 1."

  2. In what primary application scenarios is the reported improvement in accuracy sufficient to justify the significant increase in runtime? Could the results be analyzed using a fixed wall-clock time or a set computational resource budget, rather than solely comparing final clustering scores?

  3. To what extent can the observed gains in clustering accuracy be attributed to the original NLR objective function, versus the GPU fusion and normalization operations proposed in the paper? Specifically, under identical optimization settings, do the implementations with and without these fusion operations yield comparable solutions and convergence behavior?

1 comment
AuthorsOpenReview ↗

Response to Reviewer AYV1

We thank the reviewer for the detailed review. We discuss the trade-off in practice and use the new unfused comparison to clarify what fusion contributes.

  1. We highlight that GEM inherits NLR's statistical recovery guarantee at the level of the optimization problem, in that GEM and NLR have equivalent mathematical formulations for the nonconvex relaxation of KK-means SDP clustering. Our primary contribution for GEM is computational and its memory efficiency for scaling. The only algorithmic difference is GEM's spectral normalization, which makes the optimization scale-independent. This is because gradient descent is the forward Euler scheme that implicitly requires a first-order discretization of the objective function. With growing gradient (in problem size nn), the objective function becomes less smooth, and step size needs to be carefully annealed with nn to reduce the approximation error. The actual implementation of GEM avoids this tuning by spectrally normalizing the data and therefore reparametrizing the dual variable.

    Beyond this rescaling for computational robustness, Zhuang et al. (2024, Theorem 1 and Proposition 2) in fact established local convergence of the projected-gradient primal solve and of dual ascent under exact primal solves, as well as full primal-dual iteration convergence (a consequence of Proposition 2 + Theorem 1 in their paper). For a fixed initialization, parameters, and update rules, fusion preserves the iterates in exact arithmetic as NLR. Therefore, up to the spectral normalization, the analysis of NLR can be carried over to handle a localized dual neighborhood (instead of a fixed dual variable). We will revise the introduction to connect with the conditional guarantees for NLR from the empirical recovery observed with GEM.

  2. The extra computation is most useful when a poor partition could affect downstream conclusions and reference labels are unavailable, as in exploratory cell-population analysis. In the right panel of Figure 2, Flash-KKMeans missed the recovery threshold in 47 of 50 trials. Zhuang et al. (2024, Figure 3) likewise report variable Lloyd recovery on CyTOF and high-error runs on CIFAR-10. Without reference labels, a user may accept a poor partition because the solver has met its stopping criterion.

    In Global Response and Additional Experiments II, the recovery gap persisted after ten restarts per dataset, with selection by lowest within-cluster sum of squares. Across the two synthetic settings with 100 clusters, none of the individual Lloyd starts reached an ARI of 0.990.99, while GEM’s mean ARI of 1.00001.0000 in both settings.

    With that being said, we agree that Lloyd is preferable on Gaia when runtime is the priority. Gaia primarily tests whether GEM can solve the full-data NLR problem on 118 million observations using one GPU. We have also since optimized GEM and plan to compare GEM with early stopping against Lloyd with restarts under the same wall-clock budget.

  3. The recovery gains over Lloyd come primarily from the original NLR formulation. GEM uses spectral normalization to make the projected-gradient updates less sensitive to data scale, and GPU fusion to reduce memory usage and improve efficiency. As reported in Global Response and Additional Experiments I, both fused and unfused implementations achieved a mean ARI of 1.00001.0000 to four decimal places on all four synthetic settings, while unfused NLR took 1.91.9 to 3.93.9 times as long per iteration. On CyTOF, GEM also had a lower iteration cost, while unfused NLR achieved a slightly higher mean ARI.

    For the same normalized objective, initial factor, solver parameters, and stopping rule, the fused and unfused implementations compute identical updates in exact arithmetic. They follow the same sequence of iterates and terminate at the same factor.

Reviewer_oxRoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents GEM-KMeans, a memory-efficient GPU implementation of the nonnegative low-rank (NLR) formulation for K-Means. The main idea is to fuse the gradient update, nonnegative projection, and accumulation of normalization and convergence statistics into a matrix-multiplication epilogue. This reduces factor-sized storage from three arrays to one without subsampling the data.

Experiments on synthetic datasets generated from Gaussian mixture models, CyTOF cell profiles, and Gaia stellar observations demonstrate clustering on up to 200200 million samples using a single H200 GPU. Compared with the tested GPU implementations of Lloyd’s algorithm, GEM-KMeans generally achieves better clustering accuracy, although this often comes with substantially longer runtime.

Critical strengths

S1. The main contribution of this paper is the memory saving. This makes the existing NLR approach practical at a much larger scale.

S2. The experiments include both large synthetic datasets and real datasets. GEM generally achieves better clustering accuracy than the tested Lloyd implementations, suggesting that it can be useful for applications where clustering quality is a priority.

Critical weaknesses

W1. Some theoretical and experimental details need clarification. The scope of GEM’s claimed statistical guarantee is unclear, particularly how its initialization relates to the conditions of the cited NLR theory (see Q1). Several experimental settings are missing (see Q3), and a comparison with an unfused NLR implementation would be helpful to assess the benefit of fusion (see Q2). These issues make the claimed guarantees and practical gains harder to assess and the experiments harder to reproduce.

Questions for authors

Q1. Section 1.1 states that GEM scales to hundreds of millions of points with “guaranteed statistical accuracy in the exact recovery regime.” Could you clarify what guarantee is being claimed here and what ensures exact recovery? If this refers to the NLR guarantees in Zhuang et al. (2024), Theorem 1 requires the initial matrix to be sufficiently close to an optimal solution. Is GEM’s initialization guaranteed to satisfy this condition? If so, could you explain why?

Q2. Could you compare GEM with an unfused implementation of the same NLR method on the same GPU, using the same initialization and numerical settings? A comparison of time per iteration, peak GPU memory usage, and clustering accuracy would be helpful to show the practical benefit of fusion.

Q3. Could you provide the step sizes, penalty parameters, dual ascent tolerance, convergence tolerance and minimum iteration counts used for GEM in the experiments? Please also give the ranks used for CyTOF and Gaia, and the iteration limits used in Figures 1, 3 and 4. How were these settings chosen? Providing these details would help readers better understand and reproduce the experiments.

Q4. Figure 2 reports GEM’s iteration loop time and Flash-KMeans’ wall time. Does the latter include preprocessing and initialization? Could you also report the time from input data to final cluster labels for both methods, including the preprocessing, initialization and label recovery required by each method?

Q5. Could you add a brief overview of the complete clustering procedure to the main text, including initialization and how the final cluster labels are obtained? These steps are currently described only in Appendix D. Including a short description would make the main text more self-contained and the method easier to follow.

Q6. How is the Cholesky QR initialization implemented when r>dr>d, as in the configurations (d,r)=(200,300)(d,r)=(200,300) and (d,r)=(50,60)(d,r)=(50,60) in Table 2? Since V=XX⊤ZV=XX^\top Z has rank at most d<rd<r, V⊤VV^\top V is singular and the stated formula involving R−1R^{-1} does not apply. Appendix D notes the full-rank requirement, but does not specify how these configurations are handled. Could you provide the initialization procedure actually used in these experiments?

Q7. On Gaia, GEM achieves a mean NMI of 0.3150.315, compared with 0.3040.304 for Flash-KMeans and 0.3050.305 for Fast-PyTorch-KMeans. However, its median runtime is approximately 3838 minutes, compared with 3939 seconds and 2020 seconds, respectively. These results show absolute NMI improvements of 0.0110.011 and 0.0100.010, while the runtime is approximately 5858 and 114114 times that of the respective baselines. Is this improvement in NMI worth the substantial increase in runtime?

Could you compare GEM with the Lloyd baselines using K-Means++ or a comparable data-informed initialization, and with multiple restarts within the same total running time as GEM? This would help assess whether GEM's accuracy advantage persists when the baselines use stronger initialization or spend a comparable amount of time improving their solutions.

3 comments
AuthorsOpenReview ↗

Response to Reviewer oxRo, Part 1

We thank the reviewer for the detailed questions. We clarify the scope of the recovery guarantee, report the solver settings, and explain the initialization, timing, and label recovery procedures below.

  1. GEM inherits NLR's statistical recovery guarantee at the level of the optimization problem. Centering and rescaling preserve the minimizers of the nonconvex relaxation of KK-means, so under the exact-recovery assumptions of Zhuang et al. (2024), reaching a global minimizer recovers the true partition. Our contribution is to make this solver more memory-efficient at scale. Spectral normalization controls the scale of the data term, so that the fixed-dual smoothness bound in Proposition 1 has no explicit dependence on sample size.

    Theorem 1 of Zhuang et al. establishes local convergence of the projected-gradient primal solve when the initial factor is sufficiently close to an optimal solution. Proposition 2 analyzes dual ascent under exact primal solves. We have not established that GEM's data-informed initializer satisfies the proximity condition. For GEM, we proved descent at a fixed dual variable and evaluate recovery of the full algorithm empirically. We will revise the introduction to make the scope of these guarantees explicit.

  2. In Global Response and Additional Experiments I, we report that unfused PyTorch NLR took 1.91.9 to 3.93.9 times as long per iteration as GEM on the same H200 across four synthetic settings. Both solvers achieved a mean ARI of 1.00001.0000 to four decimal places. The comparison used matched datasets and independently generated initial factors. GEM used an updated BF16 matrix-product inputs, and PyTorch used FP32 with TF32 disabled. The same section reports measured PyTorch peak allocations and estimates for both implementations. On setting B2, for example, the measured PyTorch peak averaged 85.8685.86 GiB, and the GEM solver-buffer estimate was 15.3015.30 GiB.

  3. We will add the following hyperparameter summary to the appendix. We did not tune the parameters aggressively. After scaling the data, we tried a small set of nearby step sizes and penalties in preliminary runs. We generally started with rr between 1.5 and 2 times the cluster count and increased it when convergence was unsatisfactory.

    Figure / settingFactor widthStep sizePenaltyDual ascent toleranceConvergence tolerance
    Fig. 1 / A1, A2300.005200.00010.001
    Fig. 1 / A3300.005300.00010.001
    Fig. 1 / A4600.005300.00010.001
    Fig. 1 / B1, B23000.005200.00010.001
    Fig. 2 / all panels400.00550.0010.001
    Fig. 3 / CyTOF220.0120.0010.0001
    Fig. 4 / Gaia DR3420.01500.00010.001

    GEM used a max cap of 50000 iterations in Figures 1, 3, and 4. Figure 2 used caps of 100,300,1,000,3,000,10000100, 300, 1,000, 3,000, 10000, and 3000030000, with early stopping enabled. We will also list the minimum iteration counts in the revised appendix.

  4. The wall-clock time in Fig. 2 includes random initialization. In our additional experiments at γ=1\gamma=1 (Global Response and Additional Experiments II), initialization took about 3.93.9ms on A1 and 1.41.4ms on A2, accounting for about 1.61.6\\% and 0.070.07\\% of the respective Flash-KKMeans solver times. Including random initialization therefore had little effect on the reported times in these two settings.

    Over the same setting with 10 reruns, GEM took, on average, 11.4511.45s on A1 and 125.86125.86s on A2, including input handling, preprocessing, initialization, optimization, and label recovery. These GEM reruns used KK-means directly on the final factor and achieved mean ARI of 1.00001.0000 to four decimal places on both settings. We will clarify the timing boundaries in the revision.

  5. We will add a brief overview to the main text. GEM centers the data and scales it by its spectral norm, uses a randomized range finder on the data Gram matrix to initialize the factor, and optimizes the NLR objective. In the included experiments, we extract labels by applying KK-means to the rows of the top left singular vectors of the fitted factor, retaining one singular vector per requested cluster. Our new experiments shows that, SVD followed by KK-means and direct KK-means both achieved near-perfect recovery on the balanced isotropic and anisotropic synthetic mixtures. Under imbalance, adding SVD raised mean ARI from 0.871 to 0.886. We will specify the readout used for each result.

AuthorsOpenReview ↗

Response to Reviewer oxRo, Part 2

  1. When the rank rr exceeds the feature dimension dd, the sketch Gram matrix is singular as noted. For the configurations in question, GEM actually just skips Cholesky QR and projects the original sketch directly onto the feasible set: V=XX⊤Z,U0=ΠΩ(V).V=XX^{\top}Z,\qquad U_0=\Pi_{\Omega}(V). The fallback retains all factor columns and avoids a triangular solve with a singular factor. GEM uses the same fallback when the Gram matrix is ill-conditioned. We will document it in Appendix D.

  2. We agree that Lloyd is preferable on Gaia when runtime is the priority. We included Gaia primarily as a scalability test, showing that GEM can run the full-data NLR solver on 118118 million observations on a single GPU. The extra computation is more readily justified when the partition informs downstream decisions and no reference labels are available. In that setting, a user may accept a poor partition simply because the solver met its stopping criterion. Figure 3 of Zhuang et al. (2024) illustrates this risk through variable misclustering errors on CyTOF and high-error Lloyd runs on CIFAR-10.

    The submitted Gaia experiment ran GEM to its prescribed stopping criterion. We have since optimized the implementation and plan to compare GEM with early stopping against Lloyd with restarts under matched wall-clock budgets. This will show how much clustering quality GEM can retain at shorter runtimes.

  • In Global Response and Additional Experiments II, we report the results of ten restarts per dataset for each Lloyd baseline, using KK-means++ for Fast-PyTorch-KKMeans and random initialization for Flash-KKMeans. We selected the partition with the lowest within-cluster sum of squares and included all ten starts in the runtime. Both baselines were faster on the synthetic settings, but none of the restarts across the two settings reached an ARI of 0.990.99.

Thank you for the clarifications and additional experiments. These address some of my concerns. However, GEM and the unfused baseline use different precision settings, making it difficult to determine how much of the reported speedup comes from fusion itself. I also remain concerned about the tradeoff between quality and runtime on Gaia. I will keep my original score.

Reviewer_ePYHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper builds a GPU implementation of the nonnegative low-rank (NLR) K-means method. It essentially makes two adaptations, a spectral normalization and computes XX'U in a GEMM, which removes the gradient buffer and the copy of the previous iterate.

Critical strengths
  1. They study a well-motivated problem. SDP-based K-means has strong exact-recovery guarantees but is rarely used at scale. Getting the NLR relaxation to 10^8 points on a single GPU is a useful demonstration.
  2. The epilogue computes the movement statistics before overwriting U, which removes both nxr buffers while keeping the stopping rule exact.
  3. Normalization fixes a real scaling problem. The local Lipschitz refinement gives a constant near feasibility, with no dependence on n. This justifies an n-independent step size.
  4. Strong recovery on synthetic data. Figure 2 shows NLR reaches the statistical floor on every seed, while Flash-KMeans rarely does. This comparison is informative.
  5. The paper is honest about runtime costs and the need for a global reduction.
  6. Implementation details (Appendix B–C) are thorough.
Critical weaknesses
  1. No ablation of the main contribution. The headline claim is memory and IO efficiency, but there is no unfused GPU NLR baseline (for example, the same algorithm in PyTorch or plain cuBLAS). There are also no measured peak-memory or runtime numbers for fused vs unfused. Without this, we cannot tell how much of the scaling comes from the kernel and how much would come from any GPU port. Per-iteration throughput (achieved TFLOPS or bandwidth vs roofline) is also missing.
  2. Theory is thin and does not cover the algorithm as run. Proposition 1 and Corollary 1 are textbook projected-gradient results for a fixed dual. There is no analysis of the full primal–dual scheme with the gated dual update, the new data-informed initialization, the TF32 arithmetic, or the SVD + K-means rounding. The paper itself notes that normalization can change the iterate path. Yet the contribution list says GEM is "the first K-means solver that scales to hundreds of millions of points with guaranteed statistical accuracy in the exact recovery regime." I believe that is an overclaim: the guarantee belongs to the NLR optimum and the original local-convergence analysis, not to this implementation.
  3. Weak baselines. Every Lloyd baseline uses a single random initialization. There is no k-means++, no multiple restarts with best-objective selection, and no spectral initialization. Meanwhile GEM uses a randomized range-finder initialization plus SVD + K-means rounding. The stopping tolerances also differ across methods (the paper admits they are "not directly equivalent"). Lloyd with k-means++ and a few restarts, or Lloyd started from the same spectral initialization, could close much of the GMM gap at a fraction of GEM's cost.
  4. Key hyperparameters are missing. The values used in experiments are never stated (unless I missed them?).
  5. Narrow synthetic regime. All GMMs are balanced, isotropic, and right at the CNR threshold). There are no unbalanced clusters, anisotropic noise, or misspecified K. The real-data label recovery (SVD of U, then K-means) is a further step whose effect is not studied.
Questions for authors

See Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer ePYH

We thank the reviewer for the detailed feedback. We added a direct comparison with unfused GPU NLR, strengthened the Lloyd baselines, and tested GEM's sensitivity to initialization, mixture assumptions, and label recovery.

  1. In Global Response and Additional Experiments I, we report a direct comparison with unfused PyTorch NLR on the same H200. Across four synthetic settings, unfused NLR took 1.91.9 to 3.93.9 times as long per iteration as GEM, and both solvers achieved a mean ARI of 1.00001.0000 to four decimal places. The same section reports measured PyTorch memory peaks, buffer estimates, and effective throughput.

  2. We highlight that GEM and NLR have equivalent mathematical formulations for the nonconvex relaxation of KK-means SDP clustering. Our primary contribution for GEM is computational and its memory efficiency for scaling. The only algorithmic difference is GEM's spectral normalization, which makes the optimization scale-independent. This is because gradient descent is the forward Euler scheme that implicitly requires a first-order discretization of the objective function. With growing gradient (in problem size nn), the objective function becomes less smooth, and step size needs to be carefully annealed with nn to reduce the approximation error. The actual implementation of GEM avoids this tuning by spectrally normalizing the data and therefore reparametrizing the dual variable.

    Beyond this rescaling for computational robustness, Zhuang et al. (2024, Theorem 1 and Proposition 2) in fact established local convergence of the projected-gradient primal solve and of dual ascent under exact primal solves, as well as full primal-dual iteration convergence (a consequence of Proposition 2 + Theorem 1 in their paper). For a fixed initialization, parameters, and update rules, fusion preserves the iterates in exact arithmetic as NLR. Therefore, up to the spectral normalization, the analysis of NLR can be carried over to handle a localized dual neighborhood (instead of a fixed dual variable). We will revise the introduction to connect with the conditional guarantees for NLR from the empirical recovery observed with GEM.

    For finite-precision behavior, Global Response and Additional Experiments I reports that BF16 GEM and FP32 unfused NLR both achieved a mean ARI of 1.0000 to four decimal places across the four synthetic settings. To assess the TF32 arithmetic used in the submission, we plan to compare TF32, BF16, and FP32 with the initial factor and solver settings held fixed.

    The SVD followed by KK-means label recovery procedure is inherited from the original NLR implementation. In Global Response and Additional Experiments II, we compare four procedures on the same fitted factors. All four achieved near-perfect recovery on the balanced isotropic and anisotropic mixtures. Under strong imbalance, SVD before K-means increased mean ARI slightly from 0.871 to 0.886.

  3. In Global Response and Additional Experiments II, we report the results of ten restarts per dataset for each Lloyd baseline, using KK-means++ for Fast-PyTorch-KKMeans and random initialization for Flash-KKMeans.We selected the partition with the lowest WCSS and included all ten restarts in the runtime. Both baselines remained faster than GEM on the synthetic settings, but none of the 200 individual starts across the two settings with 100 clusters reached an ARI of 0.99.

  4. We indeed omitted some of the hyperparameters used in the experiments. We summarize them in the table below, and will add it to the revision. Here rr is the factor width, α\alpha is the step size, β\beta is the penalty, ϵd\epsilon_d is the dual-update tolerance, and ϵc\epsilon_c is the convergence tolerance. | Figure / setting | rr | α\alpha | β\beta | ϵd\epsilon_d | ϵc\epsilon_c | |---|---:|---:|---:|---:|---:| | Fig. 1 / A1, A2 | 30 | 0.005 | 20 | 10−410^{-4} | 10−310^{-3} | | Fig. 1 / A3 | 30 | 0.005 | 30 | 10−410^{-4} | 10−310^{-3} | | Fig. 1 / A4 | 60 | 0.005 | 30 | 10−410^{-4} | 10−310^{-3} | | Fig. 1 / B1, B2 | 300 | 0.005 | 20 | 10−410^{-4} | 10−310^{-3} | | Fig. 2 / all panels | 40 | 0.005 | 5 | 10−310^{-3} | 10−310^{-3} | | Fig. 3 / CyTOF | 22 | 0.01 | 2 | 10−310^{-3} | 10−410^{-4} | | Fig. 4 / Gaia DR3 | 42 | 0.01 | 50 | 10−410^{-4} | 10−310^{-3} |

  5. We conducted additional experiments as suggested, varying cluster balance, noise covariance, and the number of clusters specified. In Global Response and Additional Experiments II, these experiments shows that GEM outperformed KK-means++ Lloyd under imbalance and anisotropy. With 25 true clusters, GEM performed better when fitting 30, and Lloyd when fitting 20.

    The effect of label recovery methods is also reported in the same response. Both KK-means readouts achieved near-perfect recovery on the same fitted factors for balanced isotropic and anisotropic mixtures. Under imbalance, adding SVD raised mean ARI from 0.8710.871 to 0.8860.886.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Global Response and Additional Experiments I

We thank the reviewers for their constructive feedback. Several reviews asked how much GEM improves the efficiency of unfused NLR, whether stronger Lloyd baselines close the recovery gap, and how sensitive recovery is to initialization, departures from the synthetic GMM, and label extraction. We summarize the additional experiments addressing these questions below.

Benchmark settings

For ease of reference, we use labels A1-A4 and B1-B2 for the six main synthetic settings, with nn samples, dd features, KK clusters, and rank rr.

SettingnnddKKrr
A11,000,000502030
A210,000,000502030
A3100,000,000502030
A4200,000,000502060
B11,000,000200100300
B210,000,000200100300

Unfused NLR ablation

We implemented unfused NLR in PyTorch, and compared it with GEM on an H200. Both solvers used the normalized formulation and matched dataset seeds, with independently generated data-informed initial factors. GEM used an updated BF16 matrix-product inputs, and PyTorch used FP32 with TF32 disabled. The following table reports the mean ARI and mean time per iteration across paired runs:

SettingPairsGEM ARIUnfused ARIGEM ms/iter.Unfused ms/iter.Unfused/GEM
A1101.00001.00000.7681.4331.87
A2101.00001.00006.76812.7411.88
B151.00001.00005.00819.5743.91
B251.00001.000048.735158.6383.26
CyTOF100.72660.75120.2020.2251.11

Unfused NLR took 1.91.9 to 3.9×3.9\times as long per iteration on the four tested synthetic settings, where both solvers achieved mean ARI of 1.00001.0000 to four decimal places. On CyTOF, GEM also took less time per iteration, although unfused NLR achieved a slightly higher mean ARI. The mean iteration times correspond to 7.817.81 to 49.2549.25 effective TFLOP/s for GEM and 4.194.19 to 15.1315.13 for unfused NLR across the synthetic settings, counting approximately 4ndr4ndr FLOPs for the two main matrix products over the full iteration time. We plan a controlled TF32, BF16, and FP32 comparison with the initial factor and solver settings held fixed.

As detailed in Section 4 of the paper, fusion removes two n×rn\times r FP32 buffers for the gradient and previous factor, saving 8nr8nr bytes in that buffer accounting. The following table reports GPU memory usage in GiB. Measured values are averages of PyTorch’s peak allocations across runs. We estimate GPU memory use by summing the sizes of the solver buffers held simultaneously at peak, using each buffer’s dimensions and data type. The estimates exclude the CUDA context, library workspaces, and allocator overhead:

SettingUnfused measured peakUnfused buffer estimateGEM BF16 buffer estimate
A11.020.980.24
A29.879.832.42
A3—98.3524.23
A4—353.1669.33
B18.618.581.58
B285.8685.8315.30
CyTOF0.110.070.02

For A4, the FP32 input and three factor-sized buffers alone require 171.4171.4 GiB, above the H200's 139.8139.8 GiB usable capacity. Our accounting therefore predicts an out-of-memory failure for the unfused implementation at A4. GEM completed all five A4 runs.

AuthorsOpenReview ↗

Global Response and Additional Experiments II

Lloyd initialization

We ran Fast-PyTorch-KKMeans with its built-in KK-means++ initializer and FlashKMeans with random initialization. Each method used ten starts per dataset and returned the partition with the lowest within-cluster sum of squares (WCSS). The next two tables report mean clustering scores, with sample standard deviations, and mean runtimes in seconds. The Lloyd runtimes include all ten starts and the time to evaluate WCSS and select the best partition. GEM runtimes include label recovery.

SettingSeedsMetricGEMFast-PyTorchFlashKMeans
A110ARI1.00000.9492 ± 0.02670.9371 ± 0.0288
A210ARI1.00000.9619 ± 0.03280.9556 ± 0.0307
B15ARI1.00000.8777 ± 0.01810.8987 ± 0.0170
B25ARI1.00000.8429 ± 0.02690.8640 ± 0.0150
CyTOF10NMI0.8298 ± 0.02070.7955 ± 0.00680.8017 ± 0.0097
SettingGEM (s)Fast-PyTorch, 10 starts (s)FlashKMeans, 10 starts (s)
A111.453.173.38
A2125.8628.3341.77
B1163.4022.5815.03
B21,610.36804.35258.62
CyTOF4.960.2443.26

The recovery gap persisted on all four synthetic settings. Across B1 and B2, none of the 200 individual Lloyd starts reached an ARI of 0.990.99. Both Lloyd baselines remained faster on the synthetic settings, and Fast-PyTorch-KMeans also remained faster on CyTOF.

Robustness beyond balanced isotropic GMMs

We generated mixtures with n=106n=10^6, d=50d=50, and K0=25K_0=25 true clusters, varying one condition at a time. We compared GEM using SVD + KK-means for label recovery with Fast-PyTorch-KKMeans using its built-in KK-means++ initializer. Results are averages over three matched seeds. For correctly specified cases, excess error is the misclustering rate minus the Bayes oracle's error:

SettingGEM ARILloyd ARIGEM excess errorLloyd excess error
Balanced, isotropic1.0000.7880.0000.220
Unbalanced, 20:1 weight ratio0.8440.8090.1620.247
Anisotropic, condition number 1001.0000.9340.0000.080
Fit K=20K=200.3880.712——
Fit K=30K=300.9800.885——

GEM reduced excess misclustering error under imbalance even though Lloyd found a partition with lower WCSS. Under anisotropic noise, GEM matched the Bayes oracle's error to the reported precision on all three seeds. With misspecified KK, GEM recovered better when fitting 30 clusters, while Lloyd recovered better when fitting 20. We plan to repeat these comparisons at larger sample sizes.

Label recovery from the fitted factor

We fit GEM once per dataset and applied four label extraction procedures to the same fitted factor UU. We compared the submitted procedure, which applies KK-means to the top-KK left singular vectors of UU, with KK-means on the rows of UU, row-wise argmax, and argmax with the columns grouped into KK clusters by cosine similarity. For each of the two KK-means readout procedures, we used ten starts with KK-means++ and selected by lowest WCSS in the corresponding embedding. The table reports mean ARI over five matched seeds on synthetic mixtures with n=106n=10^6, d=50d=50, and K=25K=25.

SettingSVD + KK-meansKK-means on UUArgmaxArgmax + merge
Balanced, isotropic1.0001.0001.0001.000
Anisotropic1.0001.0000.99991.000
Unbalanced0.8860.8710.8530.846

All four procedures achieved near-perfect recovery in the balanced isotropic and anisotropic settings. Under strong imbalance, SVD + KK-means improved mean ARI by 0.0150.015 over direct KK-means. Both KK-means procedures returned 25 clusters in every run, while row-wise argmax returned 34–50 in the unbalanced setting.

Dear Reviewers,

Would you please followup on the authors responses? Your input is very helpful for the decision!

Regards,

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.