acceptodds
Under review as a conference paper at ICLR 2027

Two-Point Local Optimality in -Means via Boundary-Point Screening

Abstract

Lloyd's algorithm and the discrete local (D-local) optimization method (Li et al., 2025a) for -means provide only weak local-optimality guarantees, and their solution quality remains sensitive to initialization. In this paper, we introduce **-point local optimality**, under which no reassignment of at most samples decreases the objective function, and focus on . The main computational obstacle is the cost of exhaustive two-point certification for samples in dimensions and clusters. To address this challenge, we prove that (i) every improving two-point move of a D-local optimum must involve a cluster shared by both reassignments, and (ii) only certificate-defined boundary points can participate in an improving pair. Exploiting this structure, we propose *Boundary-Point-Screened Two-Point Local Search* (BPS-2PLS), which terminates at a two-point local optimum. For fixed and nonvanishing cluster occupancy, the number of retained candidates satisfies under i.i.d. sampling from a bounded-support distribution with bounded density or from a Gaussian mixture. Across twelve benchmarks, BPS-2PLS attains the lowest available mean WCSS on ten. In a subsampling study, screening retains - of samples on average at the largest tested sizes. The code is available at https://anonymous.4open.science/r/BPS-2PLS.

Primary area:
optimization
Keywords:
k-Means, two-point local optimality, safe screening

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_9QjcOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the classic k-means clustering problem. A classic heuristic is Lloyd's heuristic that unfortunately can get stuck in less good local optimals. To overcome this, the paper considers the possiblity to additionally reassign a point/sample to a different cluster center to decrease the cost and then continue with Lloyd's. Actually optimality with respect to a single point was done in a recent paper by Li et al in 2025.

The main contribution of the current paper is to propose local optimality with respect to multiple point/sample reassignments, and, with a focus on 2-optimality, they show structural properties that allow them to speed up the search for improving swaps in certain situations.

The paper presents experiments showing that this leads to better results than e.g. 1 optimality without increasing the comptuational cost too much.

Critical strengths

The paper addresses an important problem and makes a clean heuristic work better and identifies structural properties which allow them to speed up the search.

Critical weaknesses

Going from 1-optimality to 2- and more generally any swap optimality is not an original contribution or interesting. This is standard in local search.

The structural properties are nice but not striking by themselves.

The computational experiments are not very concluding. Why is it not used together with, e.g., k-means++ initialization or k-means++ greedy initialization that is implemented in scipy?

Questions for authors
7 comments

W1: Going from 1-optimality to 2- and more generally any swap optimality is not an original contribution or interesting. This is standard in local search.

We thank the reviewer for this comment. We agree that extending a local-search neighborhood from one-point moves to multi-point exchanges is a common idea in combinatorial optimization. We do not claim the abstract concept of rr-point local optimality itself as an independent contribution. Rather, our contribution is an exact characterization of the complete improving two-point neighborhood for the standard k-means WCSS objective, together with efficient search and optimality-certification mechanisms built on this characterization.

The key difficulty is that simultaneously reassigning two samples requires recomputing the centroids of their shared clusters, which introduces interactions between the two moves. Consequently, two one-point moves that are individually non-improving may jointly reduce WCSS. Direct enumeration over all sample pairs and destination clusters would require O(n2k2)O(n^2k^2) search.

Our technical contributions address this difficulty in three ways:

  1. Structural characterization. We prove that, at a D-local state, every improving two-point move must have a weakly connected cluster-transfer graph. This restricts the complete improving two-point neighborhood to six feasible configurations, each involving at most three clusters (Theorem 4.4 and Table 1).
  2. Exact search. Using closed-form WCSS gain expressions and Top-3 insertion-score lists, we optimize destination selection without enumerating all destination-label combinations. Given the required sample-pair distances, this reduces the search complexity to O(n2k)O(n^2k).
  3. Safe screening. We construct an upper-bound certificate for each sample that bounds the gains of all feasible connected two-point moves involving that sample. A sample with a non-positive certificate can therefore be safely excluded without missing any improving two-point move. Under the stated distributional and occupancy assumptions, we further prove that the number of retained samples satisfies m=OP(log⁡n)m=O_P(\log n), yielding OP(nlog⁡n)O_P(n\log n) screening-and-search complexity per round for fixed k,dk,d.

We also acknowledge prior work on two-sample reassignments, including Tarsitano (2003), which studies a different clustering criterion. Our contribution is the exact structural characterization, safe optimality certification, and candidate-set size guarantee for the standard WCSS objective.

Changes in the paper: In the Introduction, we revised the first contribution statement to avoid presenting the general local-optimality hierarchy as the main novelty. It now reads: “We characterize the complete improving two-point neighborhood at a D-local state through weakly connected cluster-transfer graphs. For r=2r=2, this characterization yields six configurations and enables exact destination optimization.”

W2: The structural properties are nice but not striking by themselves.

A2: We agree that the connectedness property of the cluster-transfer graph, viewed in isolation, is not the main contribution of this work. Its significance lies in how it enables an exact characterization of the complete two-point search neighborhood and, in turn, the design of exact search and safe screening algorithms.

Specifically, we use the cluster-wise decomposition of the k-means WCSS objective to show that gains associated with distinct weakly connected components are additive. Therefore, at a D-local state, a two-point move consisting of disconnected components cannot improve WCSS. It follows that every improving two-point move must have a weakly connected cluster-transfer graph.

For r=2r=2, this property has a direct algorithmic consequence: a connected transfer graph formed by two moves involves at most three clusters, allowing us to enumerate the complete improving neighborhood exactly through six configurations (Theorem 4.4 and Table 1). We then use closed-form WCSS gain expressions and Top-3 insertion-score lists to replace exhaustive destination optimization with efficient queries. Given the sample-pair distances, this reduces the destination-search complexity from O(n2k2)O(n^2k^2) to O(n2k)O(n^2k).

More importantly, the same structural characterization underpins our safe screening mechanism. We construct reusable upper-envelope certificates for the six configurations, providing an upper bound on the gains of all relevant connected two-point moves involving each sample. Samples with non-positive certificates can therefore be safely discarded without missing any improving move. Furthermore, Theorem 7.2 establishes that, under the stated distributional assumptions and nonvanishing occupancy condition, the retained candidate count satisfies m=OP(log⁡n)m=O_P(\log n), giving OP(nlog⁡n)O_P(n\log n) screening-and-search complexity per round for fixed k,dk,d.

We also clarify that connectedness alone does not reduce the worst-case search complexity for general rr. As shown in Appendix B, the number of connected moves can still be as large as Θr(nrkr)\Theta_r(n^r k^r) in the worst case. Accordingly, our main algorithmic contributions focus on the special structure for r=2r=2 and the exact search and safe screening mechanisms it enables.

Changes in the paper: We added an explanatory paragraph after Theorem 4.4 to clarify the theorem's role in reducing the complete two-point neighborhood and supporting the algorithms in Sections 5 and 6.

W3: The computational experiments are not very concluding. Why is it not used together with, e.g., k-means++ initialization or k-means++ greedy initialization that is implemented in scipy?

We first clarify that the original experiments already use standard k-means++ initialization. Specifically, for each dataset, we independently generate ten k-means++ initial center sets and share each set across all comparison methods to ensure a fair comparison. This protocol is described in the Initialization paragraph of Appendix F. We recognized that it was not sufficiently clear in the main text and made it explicit in the revised Section 8.1.

Following the reviewer's suggestion, we also evaluated the methods with greedy k-means++ initialization. We conducted additional experiments on seven datasets, generating ten independent greedy k-means++ initial center sets per dataset and sharing each set across all comparison methods. The results are reported in Table 19 of Appendix G.9.

With greedy k-means++ initialization, BPS-2PLS achieves the lowest mean WCSS on five of the seven datasets. On the other two datasets, its results remain close to the best: its mean WCSS is approximately 0.029% higher than Hartigan on MNIST-2000 and 0.001% higher than D-LO on 20News. BPS-2PLS also achieves lower mean WCSS than Min-D-LO on all seven datasets.

These results show that, on the seven evaluated datasets, BPS-2PLS retains its WCSS advantage over Min-D-LO under both standard and greedy k-means++ initialization.

Changes in the paper: Section 8.1 and the Initialization paragraph in Appendix F now explicitly describe the shared standard k-means++ initialization protocol. Appendix G.9 and Table 19 report the additional results with greedy k-means++ initialization.

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

This paper develops a method for certifying two-point local optimality in kk-means: no simultaneous reassignment of at most two samples, followed by centroid recomputation, can reduce WCSS. At a one-point local optimum, the authors show that every improving two-point move must connect through a shared cluster, yielding six configurations. They then construct safe upper bounds that screen samples unable to participate in improving pairs.

Under the stated distributional assumptions, fixed k,dk,d, and a nonvanishing minimum cluster occupancy, the retained candidate count satisfies $ m=O_P(\log n). $ Compared with the preceding work on continuous and discrete local optimality, the principal advance is a larger neighborhood together with an efficient certification mechanism.

Critical strengths
  1. The authors sucessfully combine connected-move structure, reusable upper envelopes, and safe screening to make a stronger local-optimality certificate computationally accessible.

  2. Uniform slab counting controls data-dependent clustering states without assuming that empirical centers are independent of the observations.

  3. The evaluation includes twelve datasets, shared initializations, heuristic refinement, and candidate-set scaling, which is reasonably broad

Critical weaknesses
  1. The paper does not provide paired comparisons between PD-2PLS and BPS-2PLS using identical starting states, move-selection rules, and implementations. Appendix Table 13 reports only screening-enabled phase timings, which cannot establish the net speedup attributable to screening.

  2. The practical quality gains are often small. Although improvements over Lloyd are meaningful on some smaller datasets, they are below 0.06%0.06\% on five of the six largest datasets. Incremental gains over Min-D-LO are generally smaller still. Equal-time comparisons against additional initializations or alternative refinement strategies would better establish practical value.

  3. Some enhancement experiments do not isolate the contribution of two-point moves. For example, postprocessing LocalSearch adds centroid recomputation and one-point descent as well as two-point search. The resulting improvement cannot be attributed entirely to the proposed neighborhood. A “baseline + Min-D-LO” intermediate comparison is needed.

Questions for authors
  1. With screening enabled and disabled, are the best accepted moves and final solutions identical? What are the corresponding total runtimes and distance-evaluation counts?

  2. How frequently does the minimum-occupancy condition hold throughout all search rounds on the evaluated datasets?

  3. Under equal computational budgets, does BPS-2PLS retain an advantage over multiple Min-D-LO initializations?

8 comments

W1 & Q1: The paper does not provide paired comparisons between PD-2PLS and BPS-2PLS using identical starting states, move-selection rules, and implementations. Appendix Table 13 reports only screening-enabled phase timings, which cannot establish the net speedup attributable to screening. With screening enabled and disabled, are the best accepted moves and final solutions identical? What are the corresponding total runtimes and distance-evaluation counts?

We added paired experiments comparing PD-2PLS (without screening) and BPS-2PLS (with screening), and provide a theoretical explanation for why screening preserves the search result.

Theoretical guarantee. At any D-local state zz, Theorem 4.4 establishes that every improving two-point move must have a weakly connected cluster-transfer graph. Moreover, the safe screening certificate constructed in Section 6 satisfies, for any feasible connected two-point move MM involving samples ii and jj, Ui≥G(M;z),Uj≥G(M;z).U_i\geq G(M;z),\qquad U_j\geq G(M;z). Thus, if MM is improving, i.e., G(M;z)>0G(M;z)>0, then Ui>0U_i>0 and Uj>0U_j>0. Both samples must therefore belong to the retained candidate set B=i∈[n]:Ui>0.B=\\{i\in[n]:U_i>0\\}. Consequently, screening cannot discard any sample participating in an improving two-point move.

It follows that PD-2PLS and BPS-2PLS identify the same maximum positive gain at every D-local state. Under exact arithmetic and a common deterministic tie-breaking rule, they select the same move and follow the same search trajectory to the same final clustering.

Empirical validation. We conducted paired experiments on five datasets using the same ten initial center sets for both methods, with five timing repetitions per initialization. For BPS-2PLS, we reused the corresponding per-initialization runtimes from Table 3. The final sample labels were identical, sample by sample, in all 50 dataset–initialization pairs.

The table reports the mean number of sample-pair distance evaluations and the end-to-end runtime.

DatasetPD distance evaluationsBPS distance evaluationsPD time (s)BPS time (s)PD/BPS
Yale9.0×1049.0\times10^41.7×1041.7\times10^40.3020.3270.92×
ORL8.1×1058.1\times10^58.2×1048.2\times10^43.1752.4031.32×
USPS-10002.1×1062.1\times10^61.1×1041.1\times10^48.4101.2806.57×
COIL203.5×1063.5\times10^62.0×1032.0\times10^314.7561.25311.78×
MNIST-20006.5×1066.5\times10^65.7×1035.7\times10^325.8922.52110.27×

Screening reduces sample-pair distance evaluations by 81.1%–99.94%. In terms of end-to-end runtime, BPS-2PLS is faster on four datasets, with a maximum PD/BPS runtime ratio of 11.78×. On the smaller Yale dataset, screening reduces distance evaluations by 81.1%, but its overhead slightly exceeds the saved search time, increasing total runtime by approximately 8.3%.

In summary, the theoretical analysis shows that safe screening preserves all improving two-point moves, and the experiments confirm identical final labels. Screening substantially reduces sample-pair distance evaluations and provides significant end-to-end speedups on the medium- and large-scale datasets.

Changes in the paper: Appendix C.5 adds the exactness and trajectory-equivalence argument. Appendix F describes the paired experimental protocol. Appendix G.7 and Tables 16–17 report end-to-end runtimes, distance-evaluation counts, and output consistency.

W2 & Q3: The practical quality gains are often small. Although improvements over Lloyd are meaningful on some smaller datasets, they are below on five of the six largest datasets. Incremental gains over Min-D-LO are generally smaller still. Equal-time comparisons against additional initializations or alternative refinement strategies would better establish practical value. Under equal computational budgets, does BPS-2PLS retain an advantage over multiple Min-D-LO initializations?

We added a fixed-time-budget multiple-restart experiment on eleven datasets. We used ten paired k-means++ start sequences per dataset and compared the best WCSS obtained by Lloyd, Min-D-LO, and BPS-2PLS under budgets of TT, 2T2T, and 5T5T. For each dataset, TT is the largest median runtime among the three methods. The budget includes initialization and the complete optimization process; unfinished restarts are not included when selecting the best WCSS.

Results. The table reports the number of trials in which each method completed at least one restart, together with the paired win/tie/loss counts for BPS-2PLS against the two baselines. Under the shorter TT budget, some methods do not complete a restart in every trial. The win/tie/loss counts therefore include only paired trials in which both methods have at least one completed run.

BudgetTrials with a completed run (BPS / Min / Lloyd)BPS vs. Min-D-LOBPS vs. Lloyd
TT71 / 81 / 10942 / 16 / 4 (62)46 / 0 / 25 (71)
2T2T107 / 107 / 11074 / 19 / 12 (105)66 / 0 / 41 (107)
5T5T110 / 110 / 11076 / 21 / 13 (110)67 / 0 / 43 (110)

Under the 5T5T budget, BPS-2PLS records 76 wins, 21 ties, and 13 losses against Min-D-LO, and 67 wins and 43 losses against Lloyd. At the dataset level, BPS-2PLS has more wins than losses against Min-D-LO on ten of the eleven datasets. The advantage is also reflected in the magnitude of the WCSS improvements on some datasets (Appendix G.10, Table 22). For example, the median paired relative WCSS reductions over Min-D-LO are 0.3605% on Yale, 0.2993% on ORL, and 0.1610% on COIL100. These results show that, on some datasets, additional Min-D-LO restarts do not fully compensate for its more restricted search neighborhood.

Overall, BPS-2PLS retains a relatively consistent WCSS advantage over multiple Min-D-LO restarts, whereas its advantage over multiple Lloyd restarts depends on the dataset.

Changes in the paper: Appendix F describes the time-budget construction and restart protocol. Appendix G.10 and Tables 20–21 report pilot runtimes, completion counts under each budget, and paired win/tie/loss results. Table 22 reports the per-dataset paired outcomes and median relative WCSS reductions under 5T5T, together with the median number of completed restarts.

W3: Some enhancement experiments do not isolate the contribution of two-point moves. For example, postprocessing LocalSearch adds centroid recomputation and one-point descent as well as two-point search. The resulting improvement cannot be attributed entirely to the proposed neighborhood. A “baseline + Min-D-LO” intermediate comparison is needed.

We thank the reviewer for pointing this out. We added Min-D-LO control experiments at both the Post and Inner insertion positions. The new results are incorporated into Table 4, alongside the original WCSS and runtime results.

Post refinement. BPS-2PLS achieves lower mean WCSS than Min-D-LO in all 18 available method–dataset comparisons. This shows that two-point search provides additional WCSS reductions after controlling for centroid recomputation and one-point descent.

Inner refinement. BPS-2PLS improves mean WCSS over Min-D-LO in 9 of the 13 available method–dataset comparisons, while the remaining four show no improvement and, in some cases, a degradation. Unlike Post refinement, Inner refinement changes the subsequent trajectory of the outer heuristic, so its final result need not improve monotonically.

Changes in the paper: Section 8.2 and Table 4 now compare the absolute WCSS and runtime of Post-1/Post-2 and Inner-1/Inner-2. Appendix F and G.2 describe the paired experimental protocol and the refinement insertion points.

Reviewer_aXfzOpenReview ↗
Rating
3
Confidence
4(+2)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes BPS-2PLS, a k-means variant that handles reassignment with 2 samples at a time instead of conventional single-point reassignments. To overcome the expensive and exhaustive 2-point certification, 2 main algorithmic innovations are used. First, connected-move characterization reduces the search space and yielding six configurations. The method further uses safe boundary-point screening to remove ineffective samples from moving. Experiments demonstrate that the design translates to a direct gain in WCSS.

Critical strengths
  1. This is a solid technical paper. Connected-move characterization is particularly useful for efficient two-point local optimization and is a meaningful theoretical contribution.

  2. The BPS-2PLS algorithm itself also seems novel. The screening mechanism is integrated well and is a big improvement on top of heuristic methods.

  3. I also found the theory and algorithm integration good, making the proposed method principled.

  4. The experimental coverage is also broad, across 12 datasets and notable variants of k-means. The results are also consistent.

Critical weaknesses
  1. There seems to be a discrepancy between BPS-2PLS on small and large datasets. For example, on image dataset, WCSS reduction over one-point k-means variant seems to be very small. This may imapct the practical importance of stronger local optimality.

  2. The method uses connected-move characterization and safe screening to accelerate the exhaustive version of BPS-2PLS, but the naive version of BPS-2PLS is not tested, so the actual gain is never characterized.

  3. Improvement in WCSS is limited and may not translate to better NMI or clustering accuracy. The evidence on downstream clustering improvements is also limited.

Questions for authors
  1. Different k-means variants have different quality (WCSS or NMI) andd efficiency tradeoffs. It would be nice if the authors could consider a Pareto graph to clearly visualize this tradeoff. If BPS-2PLS shows good performance there, it will make the paper much more convincing.

  2. See my weakness #2.

8 comments

W1: There seems to be a discrepancy between BPS-2PLS on small and large datasets. For example, on image dataset, WCSS reduction over one-point k-means variant seems to be very small. This may imapct the practical importance of stronger local optimality.

We thank the reviewer for raising this concern. We agree that the relative WCSS reductions achieved by BPS-2PLS are small on some large datasets. We therefore analyzed this phenomenon from both theoretical and empirical perspectives.

Theoretical analysis. By Eq. (36), at a D-local state, the gain of any improving two-point move satisfies

\leq g_i^{\max}+\frac{22p_{\max}}{n_{\min}} \leq \frac{22p_{\max}}{n_{\min}},$$ where $p_{\max}$ is the squared sample diameter and $n_{\min}$ is the minimum cluster size. If the sample diameter is bounded and cluster occupancy is nonvanishing, i.e., there exist constants $C_{\mathrm{diam}}>0$ and $\alpha>0$ such that $p_{\max}\leq C_{\mathrm{diam}}$ and $n_{\min}\geq\alpha n$, then the absolute gain of a single two-point move is bounded by $$G(M;z)\leq \frac{22C_{\mathrm{diam}}}{\alpha n} =O(n^{-1}).$$ If, in addition, the WCSS is bounded below by a positive constant times $n$, then the relative gain of a single two-point move is $O(n^{-2})$. This explains why the relative contribution of an individual two-point move can diminish rapidly as the dataset grows. Thus, a small WCSS reduction alone does not necessarily imply that the search has found few additional improvement opportunities. **Additional search-behavior analysis.** The bound above concerns a single two-point move and does not directly bound the cumulative WCSS reduction over the entire BPS-2PLS trajectory. To examine the additional improvement opportunities found after the first D-local state, we replayed the ten shared initializations used in Table 3 for each dataset. Starting from the first D-local state reached by the initial Min-D-LO descent within BPS-2PLS, we counted all subsequent accepted one-point and two-point moves and measured the cumulative relative WCSS reduction from that state. The results are reported in Table 9 of Appendix G.1. For example, BPS-2PLS accepts an average of 147.9 additional moves on COIL100 and 97.1 on CIFAR-100. **Additional large-scale experiments.** To examine whether the observed behavior is determined by sample size alone, we also evaluated two large image datasets: | Dataset | $n$ | $k$ | Mean relative WCSS reduction | Mean additional moves | | ----------------- | ------: | ----: | ---------------------------: | --------------------: | | ALOI | 108,000 | 1,000 | $1.9\times10^{-3}$ | 2,357.2 | | Tiny ImageNet-200 | 110,000 | 200 | $4.1\times10^{-5}$ | 446.9 | Although the two datasets have similar sample sizes, BPS-2PLS accepts an average of 2,357.2 additional moves on ALOI, with a relative WCSS reduction of $1.9\times10^{-3}$, compared with 446.9 additional moves on Tiny ImageNet-200. These results indicate that the cumulative benefit depends strongly on the dataset and cannot be explained by sample size alone. Overall, the practical benefit of stronger local optimality depends on the structure of the dataset, rather than on its size alone. **Changes in the paper:** Section 8.1 now discusses the small relative WCSS reductions observed on large datasets. Appendix G.1 provides the single-move gain bound and analyzes the additional moves and cumulative WCSS reductions after the first D-local state. Tables 9–10 report the results on the twelve benchmark datasets and the two additional large-scale datasets.

W2 & Q2: The method uses connected-move characterization and safe screening to accelerate the exhaustive version of BPS-2PLS, but the naive version of BPS-2PLS is not tested, so the actual gain is never characterized.

We thank the reviewer for pointing out the absence of a naive exhaustive baseline. To evaluate the computational contributions of connected-move characterization and safe screening separately, we compared three exact two-point local-search methods on five datasets:

  1. Exhaustive-2PLS: Enumerates all unordered sample pairs and all feasible destination-label combinations. For efficiency, it caches feasible configurations and gain coefficients by source-cluster pair and evaluates batches using MATLAB matrix operations.
  2. PD-2PLS: Uses Theorem 4.4 to restrict improving two-point moves to six connected configurations. Optimizing the destination labels reduces the search cost per sample pair from O(k2)O(k^2) to O(k)O(k).
  3. BPS-2PLS: Adds safe screening to PD-2PLS, excluding samples that cannot participate in any improving two-point move and thereby further reducing the exact search space.

All three methods perform exact two-point local search. By Theorem 4.4 and the screening guarantee in Section 6, they identify the same maximum positive gain at any D-local state. Therefore, under exact arithmetic and the same deterministic tie-breaking rule, they select the same optimal move at each D-local state and follow the same search trajectory to the same final solution.

Paired experiments. For each dataset, we used the same ten k-means++ initial center sets for all three methods and timed each initialization five times. The BPS-2PLS timings were reused from the corresponding initializations in Table 3. The final sample labels were identical, sample by sample, for all 50 dataset–initialization pairs. The table reports end-to-end mean runtimes and runtime ratios.

DatasetExhaustive (s)PD (s)BPS (s)Exhaustive / PDExhaustive / BPS
Yale0.6430.3020.3272.13×1.97×
ORL35.3333.1752.40311.13×14.70×
USPS-10002.8908.4101.2800.34×2.26×
COIL2014.02914.7561.2530.95×11.20×
MNIST-20007.41525.8922.5210.29×2.94×

Results. Connected-move search is 2.13× and 11.13× faster than vectorized exhaustive enumeration on Yale and ORL, respectively. However, PD-2PLS is slower on USPS-1000, COIL20, and MNIST-2000. This is mainly due to implementation differences: the exhaustive implementation caches source-cluster-pair coefficients and evaluates destination combinations in batches, whereas the current PD-2PLS implementation checks move configurations and scans feasible destinations pair by pair. Thus, a reduction in theoretical search complexity does not necessarily translate into lower wall-clock time on finite instances; implementation efficiency also matters.

With safe screening enabled, BPS-2PLS is faster than vectorized exhaustive search on all five datasets, with end-to-end speedups of 1.97×–14.70×. Compared with PD-2PLS, BPS-2PLS is faster on four datasets, with the largest speedup being 11.78×. On Yale, screening introduces a small net overhead because its cost exceeds the time saved by reducing pair search.

In summary, connected-move characterization reduces the complexity of searching the complete two-point neighborhood, while safe screening further reduces the number of sample pairs requiring exact evaluation. Although the practical benefit of connected-move search alone depends on implementation efficiency, combining it with screening yields end-to-end speedups over exhaustive search on all five datasets while preserving identical final results.

Changes in the paper: Appendix F now describes the implementations and paired experimental protocol. Appendix G.7 adds the runtime comparison of Exhaustive-2PLS, PD-2PLS, and BPS-2PLS (Table 16), as well as the comparison of sample-pair distance evaluations (Table 17). Section 8.1 briefly points readers to this analysis.

W3: Improvement in WCSS is limited and may not translate to better NMI or clustering accuracy. The evidence on downstream clustering improvements is also limited.

We agree that lower WCSS does not necessarily lead to higher ACC or NMI. WCSS measures within-cluster compactness, whereas ACC and NMI measure agreement with reference labels. Our theoretical guarantees concern local optimality with respect to WCSS and do not directly imply improvements in these external clustering metrics.

The revised manuscript reports ACC and NMI results on twelve datasets in Appendix G.4. Compared with Lloyd, BPS-2PLS improves both mean ACC and mean NMI on seven datasets. On ORL, the improvements are 6.03 and 4.37 percentage points, respectively; on Yale, they are 2.97 and 3.50 percentage points. BPS-2PLS also achieves the highest available mean ACC and NMI on Yale, ORL, COIL20, and COIL100.

At the same time, the improvements over the stronger one-point local-search baseline Min-D-LO are small on some datasets, particularly the larger ones. Further WCSS reductions do not necessarily lead to appreciable gains in ACC or NMI. For example, on USPS-1000, Hartigan achieves higher ACC and NMI than BPS-2PLS despite having higher WCSS. This illustrates that WCSS optimization and agreement with reference labels are not monotonically related.

The heuristic-refinement experiments in Appendix G.5 provide additional evidence. Across the 18 available comparisons for the four heuristic methods, Post refinement improves mean ACC in 16 cases and mean NMI in all 18 cases.

Changes in the paper: Appendix G.4 adds ACC and NMI results and analyses for the twelve datasets (Tables 11–12). Appendix G.5 adds ACC and NMI comparisons for heuristic refinement (Tables 13–14). Section 8.1 now points readers to these results.

Comments on the paper

1 comment

We thank all reviewers for their constructive feedback and recognition of our contributions. Reviewer aXfz highlighted the technical soundness, novelty, and integration of theory and algorithms. Reviewer JA2z appreciated the connected-move characterization, reusable upper-envelope certificates, and rigorous candidate-size analysis. Reviewer 9Qjc recognized the importance of the problem and the algorithmic value of the structural properties.

In response to their concerns, we have substantially strengthened the manuscript through the following revisions:

Reviewer aXfz mainly concerns practical value and computational efficiency. We provided a theoretical explanation for the small WCSS improvements on large datasets, supplemented by additional search-behavior analyses and two large-scale experiments. We also introduced an exhaustive-search baseline, showing that BPS-2PLS achieves 1.97–14.70× speedups while preserving identical final solutions. Additional ACC/NMI results and Pareto analyses clarify the quality–runtime trade-offs.

Reviewer JA2z mainly concerns algorithmic effectiveness and experimental controls. We added paired screening ablations, confirming 81.1%–99.94% fewer sample-pair distance evaluations without changing the final solutions. We further introduced Min-D-LO refinement controls, examined the minimum-occupancy condition across 517 D-local states, and conducted equal-time multiple-restart experiments. Under the 5T5T budget, BPS-2PLS achieved 76 wins, 21 ties, and 13 losses against Min-D-LO across 110 paired trials.

Reviewer 9Qjc mainly concerns novelty and initialization. We clarified that our contribution lies in the exact characterization and efficient certification of the complete improving two-point neighborhood, rather than the general concept of multi-point local search. We also clarified the shared k-means++ initialization protocol and added greedy k-means++ experiments, where BPS-2PLS achieved the lowest mean WCSS on five of seven datasets.

Overall, these revisions strengthen the theoretical and empirical support for BPS-2PLS while clarifying its limitations. Although improvements in external clustering metrics and runtime are dataset-dependent, our results demonstrate that stronger WCSS local optimality can be certified efficiently through exact search and safe screening.

We thank the reviewers again for helping us improve the clarity and rigor of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.