PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Wenlong Lyu, Xujie Xiao, Yuheng Jia

arXiv:2610.06182v1cs.LG

TL;DR

Lloyd’s algorithm and D-local optimization provide limited local-optimality guarantees, while exhaustive two-point certification is costly. The paper introduces BPS-2PLS, using exact search and safe screening to reach a two-point local optimum. Under stated sampling and occupancy conditions, candidate counts are logarithmically bounded, and experiments report substantial pruning.

  • Problem

    One-point local optimality does not rule out improvements from simultaneous reassignments, while direct two-point certification requires costly sample-pair and destination enumeration.

    Source: §1 · p. 1

  • Method

    BPS-2PLS alternates one-point descent with exact two-point search over safely screened samples, using connected-move structure to limit the search.

    Source: §1 · p. 2

  • Results

    Mean pruning rates exceed 97% at the largest tested sizes, and m = O_P(log n) under the stated sampling and occupancy conditions.

    Source: §1 · p. 2

  • Takeaways & Limitations

    BPS-2PLS terminates at a two-point local optimum, and experiments show it can improve existing heuristics when used as a refinement.

    Source: §1 · p. 2, §9 · p. 10

    Screening can retain all samples, and the theorem bounds neither one-point descent time nor the number of search rounds.

    Source: §9 · p. 10

Abstract

from arXiv · show

Lloyd's algorithm and the discrete local (D-local) optimization method (Li et al., 2025) for $k$-means provide only weak local-optimality guarantees, and their solution quality remains sensitive to initialization. In this paper, we introduce $r$-point local optimality, under which no reassignment of at most $r$ samples decreases the objective function, and focus on $r=2$. The main computational obstacle is the $\mathcal{O}(n^2(k^2+d))$ cost of exhaustive two-point certification for $n$ samples in $d$ dimensions and $k$ 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 $k,d$ and nonvanishing cluster occupancy, the number $m$ of retained candidates satisfies $m=\mathcal{O}_{\mathbb{P}}(\log n)$ 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 0.10% to 2.81% of samples on average at the largest tested sizes. The code is available at https://github.com/lwl-learning/BPS-2PLS.

1 INTRODUCTION

The paper extends k-means local optimality beyond single-sample moves and develops a screened search that certifies two-point local optima. Its analysis bounds the retained candidate set under stated sampling and occupancy conditions, while experiments report substantial pruning.

1 INTRODUCTION

  • The paper introduces an r-point local-optimality hierarchy from D-locality at r = 1 to global optimality at r = n, focusing on r = 2.Two individually non-improving reassignments can jointly improve WCSS because their centroid updates interact through shared clusters.Source: §1 · pp. 1–2
  • Direct certification appears expensive because it enumerates sample pairs and destination clusters.The paper motivates screening and structural reductions to address this computational obstacle.Source: §1 · pp. 1–2
  • At a D-local optimum, every improving two-point move must involve a cluster shared by both reassignments, reducing possible moves to six directed configurations.Screening discards a sample only when an upper bound on gains of connected two-point moves involving it is non-positive.Source: §1 · pp. 1–2
  • Mean pruning rates exceed 97% at the largest tested sizes, while retained candidate counts satisfy m = O_P(log n) under the stated conditions.The subsampling experiment covers six datasets; the bound assumes fixed k and d, nonvanishing cluster occupancy, and bounded-support sampling with bounded density or Gaussian-mixture sampling.Source: §1 · p. 2
  • BPS-2PLS combines exact two-point search with safe sample screening and terminates at a two-point local optimum.After initial Lloyd convergence, it alternates Min-D-LO one-point descent with exact search over retained samples.Source: §1 · p. 2

2 RELATED WORK

The paper distinguishes its sample-cardinality neighborhoods and WCSS objective from earlier relocation and center-based methods. It combines safe screening with search over the complete two-point neighborhood.

2 RELATED WORK

  • Unlike Tarsitano (2003), the paper studies two-sample reassignments under standard WCSS through a point-cardinality hierarchy and exact search with safe screening.Tarsitano (2003) scans sample pairs and destination clusters under the Friedman–Rubin determinant criterion.Source: §2 · p. 2
  • Center-based neighborhoods can change many labels, whereas this paper defines neighborhoods by the number of reassigned samples.Examples include centroid relocation, merge-and-split repartitioning, and center swaps.Source: §2 · p. 2
  • BPS-2PLS uses safe screening to preserve every improving two-point move while certifying two-point local optimality at termination.This contrasts with exact Lloyd accelerations that reduce computation without changing a prescribed algorithm’s output.Source: §2 · p. 2

3 PROBLEM SETUP AND PRELIMINARIES

The section sets up k-means as a clustering objective over feasible nonempty clusters and distinguishes Lloyd fixed points from D-local optima. D-locality evaluates one-point moves after recomputing affected centroids.

3 PROBLEM SETUP AND PRELIMINARIES

  • The clustering uses a label vector over k clusters, with feasible partitions requiring every cluster to remain nonempty after reassignment.WCSS is the k-means objective, and a move is improving when the objective decrease is positive.Source: §3 · pp. 2–3
  • Lloyd’s algorithm alternates nearest-centroid assignments with centroid recomputation, but its fixed-point condition does not ensure partition local optimality.The assignments and centroids are each optimal with the other fixed, yet this partial optimality does not account for centroid changes caused by reassignment.Source: §3 · p. 3
  • A one-point move’s exact gain compares the WCSS reduction from removing a sample with the increase from inserting it into another cluster.Both affected centroids are recomputed; D-local optimality requires every feasible one-point move to have nonpositive gain.Source: §3 · p. 3

4 r-POINT LOCAL OPTIMALITY

The section defines local optimality by the number of simultaneously reassigned samples and represents their interactions with a cluster-transfer graph. Connected moves characterize local optimality and sharply constrain improving two-point moves at D-local states.

4 r-POINT LOCAL OPTIMALITY

  • A simultaneous q-point reassignment changes q distinct sample labels while leaving other labels unchanged, then recomputes affected centroids subject to feasibility.The move gain is the original objective minus the objective after reassignment.Source: §4 · p. 3
  • The r-point hierarchy ranges from one-point local optimality, equivalent to D-locality, to n-point local optimality, equivalent to global optimality.For 1 ≤ s < r ≤ n, every r-point local optimum is also s-point locally optimal.Source: §4 · p. 3
  • The cluster-transfer graph represents each sample reassignment as a directed edge from its source cluster to its destination cluster.Its vertices are the affected clusters.Source: §4 · p. 4
  • A clustering is r-point locally optimal exactly when every feasible weakly connected move of at most r samples is non-improving.If it is already (r − 1)-point locally optimal, every improving exact-r move must have a weakly connected transfer graph.Source: §4 · p. 4
  • At a D-local state, every improving two-point move affects at most three clusters and belongs to one of six configurations.Destination search costs O(n^2k) per pass given D and the required p_ij, without requiring cluster balance.Source: §4 · p. 4

5 EXACT TWO-POINT LOCAL SEARCH

At a D-local state, every improving two-point move is connected, reducing partner search to six configurations. Exact gains enable alternating one-point descent and two-point search, with destination optimization and maintained statistics reducing search work.

5 EXACT TWO-POINT LOCAL SEARCH

  • Every improving pair at a D-local state is connected: the two reassignments share at least one cluster.Fixing one reassignment as the anchor reduces the partner configurations to six.Source: §5 · p. 4
  • An anchored pair’s exact WCSS gain is assembled from removal gains, insertion costs, and transfer terms for affected clusters.For a forward chain, the gain is Rs(i) + Ta(j, i) − Ab(j).Source: §5 · p. 4
  • With unbalanced cluster sizes, exhaustive anchored search can still have Θ(n^2k^2) candidates despite constant-time gain evaluation.Only same-source, different-destination and forward-chain configurations require optimizing a second destination.Source: §5 · p. 4
  • PD-2PLS alternates best-improvement one-point descent with exact search over all sample pairs, while reusing maintained cluster statistics and distances.A Top-3 all-cluster list supports constant-time feasible destination queries and O(n^2k) anchor–partner evaluations per pass.Source: §5 · pp. 4–5

6 SAFE BOUNDARY-POINT SCREENING

Boundary-Point Screening bounds the gain of every connected two-point move involving each sample, discarding samples whose bound is non-positive. Exact search over the retained set preserves the best positive move and, with strict descent, terminates at a two-point local optimum.

6 SAFE BOUNDARY-POINT SCREENING

  • At a D-local state, BPS bounds every feasible connected two-point gain involving sample i and discards i when its bound is non-positive.A retained sample has a positive certificate Ui.Source: §6 · pp. 5–6
  • Anchors with the same envelope key reuse one envelope, and total envelope construction and certificate evaluation take O(nk log n) time.There are at most 6(k−1)n partner lines in total.Source: §6 · pp. 5–6
  • The certificate is built by upper-bounding partner gains with affine lines in a pivot-centered query radius, then maximizing over a shared partner superset.The bound for each configuration is Uτ(u) = Cτ(u) + ηeρe(i)^2 + He(ρe(i)), with He the line envelope.Source: §6 · p. 5
  • Because every improving pair’s samples have positive certificates, ExactPairSearch on B preserves the maximum positive gain; strict descent then ends at a two-point local optimum.BPS-2PLS uses O(m^2(d + k)) pair-search time and does not require evaluating any pij.Source: §6 · p. 6

7 CANDIDATE-SET SIZE GUARANTEES

The retained samples localize near empirical cluster boundaries, where squared distances to the nearest and second-nearest centers are close. Under stated sampling models and nonvanishing occupancy, the candidate set has a logarithmic size bound; the resulting cost claim is conditional on D-local outputs meeting that occupancy condition.

7 CANDIDATE-SET SIZE GUARANTEES

  • Retained samples lie in a boundary region formed by portions of slabs around pairwise equal-distance hyperplanes.The region is defined using the two smallest squared distances from a point to the empirical centers.Source: §7 · p. 7
  • The logarithmic candidate-set bound applies under either bounded-support sampling with bounded density or Gaussian-mixture sampling, with fixed k and d and nonvanishing occupancy.The mixture result allows unequal weights and anisotropic covariances without requiring separated component means.Source: §7 · p. 7
  • Localization alone is insufficient for a small candidate set: bounded, balanced two-cluster instances can have m = n.The sublinear bound requires control of boundary-region probability mass and squared sample diameter.Source: §7 · p. 7
  • For fixed d and k, qualifying D-local outputs have m/n → 0 in probability and post-descent screening-and-search cost O_P(n log n).The theorem does not guarantee occupancy attainment or bound the numbers of Lloyd iterations, one-point scans, or two-point rounds.Source: §7 · p. 7

8 EXPERIMENTS

Across twelve datasets, BPS-2PLS achieves the lowest available mean WCSS on ten, and two-point updates can enable further descent beyond one-point local optima. The experiments also examine heuristic refinement and candidate-set scaling as sample size grows.

8.1 COMPARISON OF SAMPLE-REASSIGNMENT-BASED METHODS

  • BPS-2PLS attains the lowest available mean WCSS on ten of twelve datasets, including ties.Hartigan yields lower WCSS on MNIST-2000 and Sensorless.Source: Table 3 · p. 8, §8.1 · p. 8
  • BPS-2PLS reduces mean WCSS versus Lloyd by 4.30% on Yale and 7.28% on ORL, while reductions are below 0.06% on five of the six largest datasets.The CIFAR-10 result is a tie; Sensorless has a 1.11% reduction.Source: §8.1 · p. 8
  • BPS-2PLS takes 1.08–2.57× as long as D-LO on eight datasets and less time on the other four.Hartigan takes 11.09× and 242.76× as long as BPS-2PLS on MNIST-2000 and Sensorless, respectively.Source: §8.1 · p. 8
  • On four displayed datasets, two-point moves are followed by further one-point improvements; the displayed MNIST-2000 run stops at its first D-local state.On COIL20, WCSS falls from 99.87% of initial Lloyd WCSS at the first D-local solution to 95.62% at the final solution, mostly through subsequent one-point moves.Source: §8.1 · p. 8, Figure 2 · p. 8

8.2 ENHANCING HEURISTIC METHODS

  • Post refinement lowers mean WCSS in all eighteen available heuristic comparisons, while Inner lowers it versus Baseline in twelve of thirteen comparisons but does not consistently beat Post.Post includes centroid recomputation and one-point descent absent from the LocalSearch baseline; Inner uses 37.6% and 40.2% of J-Means baseline runtime on Yale and ORL, while Post achieves lower mean WCSS.Source: §8.2 · p. 9, Table 4 · p. 9

8.3 CANDIDATE-SET SIZE VERSUS SAMPLE SIZE

  • At the largest tested sizes, mean retained fractions range from 0.10% to 2.81%, with pruning above 97% in all six datasets.Candidate counts show no sustained increase across the evaluated range; 20News and CIFAR-100 rise at smaller sizes before leveling off or decreasing.Source: §8.3 · p. 9, Figure 3 · p. 9

9 CONCLUSION

The conclusion presents BPS-2PLS as a two-point local-search method with logarithmic candidate-size and screening-and-search bounds under stated sampling and occupancy conditions. The accompanying appendices characterize connected moves, describe the search and update procedures, and establish exactness and termination.

9 CONCLUSION

  • Under the stated sampling and occupancy conditions, geometric localization gives m = O_P(log n) and O_P(n log n) screening-and-search time after one-point descent for fixed d and k.Experiments show further descent beyond one-point local optima and potential improvement of existing heuristics; screening can retain all samples, and the theorem does not bound one-point descent time or the number of rounds.Source: §9 · pp. 9–10

A.2 COMPONENTWISE ADDITIVITY AND CONNECTED MOVES

  • The gain of a feasible reassignment decomposes across weakly connected components of its transfer graph, and r-point optimality can therefore be checked using connected moves of at most r samples.If an improving exact-r move exists from an (r−1)-point optimum, it must be connected.Source: §A.2 · pp. 12–13

B COUNTING CONNECTED EXACT-r MOVES

  • For fixed r, a cluster of size Θ(n) can yield Θ_r(n^r k^r) connected moves; the bound for a β-balanced partition is O_r(β^r n^r k^r) for each source-diversity value.The stated equal-size balanced case is tight when k ≥ r + 1 and n/k ≥ 2.Source: B COUNTING CONNECTED EXACT-r MOVES · pp. 13–14

C.1 ALGORITHMS AND SHARED SEARCH ROUTINE

  • Both procedures alternate best-improvement one-point descent with exact two-point search; BPS-2PLS restricts the moved sample indices to its screened set.The shared search still uses full-clustering statistics and destination domains, while only the two moved indices are restricted.Source: §C.1 · pp. 14–15

C.2 CLUSTER-UPDATE PRIMITIVES AND FEASIBILITY

  • The six connected two-point configurations have distinct joint feasibility conditions, and their gains are computed from updates to affected cluster statistics.A same-source configuration requires source size above two; distinct-source moves require the relevant unreplenished sources to remain nonempty.Source: §C.2 · p. 16

C.3 EXACT TOP-3 DESTINATION QUERIES; C.4 EQUIVALENT SAMPLE-PAIR ORDERING

  • Top-3 insertion-score lists support constant-time destination queries except common-destination cases, which scan O(k) labels; destination optimization costs O(k) per sample pair.Computing the pair distance once adds O(d), and this ordering returns the same maximum positive gain as anchored enumeration.Source: §C.3 · p. 16, §C.4 · p. 17

C.5 EXACTNESS AND TERMINATION

  • At a D-local state, every improving exact two-point move is connected, and exhaustive pair search returns zero exactly when no improving two-point move exists.Accepted one- or two-point moves strictly decrease WCSS; screening preserves every improving pair, so both procedures terminate.Source: §C.5 · p. 17

C.6 DISTANCE EVALUATION, TIME, AND MEMORY

The appendix compares full caching with lazy block evaluation and gives the resulting runtime and memory bounds. It also details the gain envelopes and pivot radii used by screening, then outlines the candidate-size proof.

C.6 DISTANCE EVALUATION, TIME, AND MEMORY

  • Full caching costs O(n^2d) preprocessing and O(n^2) storage, while lazy evaluation computes retained-pair distances in blocks without quadratic preprocessing.Full-cache lookups are constant-time; lazy evaluation can recompute distances in later rounds.Source: §C.6 · pp. 17–18, Table 5 · p. 18
  • The runtime accounting separates Lloyd iterations, one-point scans, and screening-and-search rounds, with local state updates charged when moves are accepted.For a uniform worst-case bound, the candidate count is the maximum over rounds, not its average.Source: §C.6 · p. 18
  • Under Theorem 7.2, screening and search after one-point descent, including an accepted-pair update, remain O_P(n log n) for fixed d and k.The bound uses the maximum retained count across rounds; the iteration and scan counts include unsuccessful termination checks, but no convergence-rate bound is asserted for them.Source: §C.6 · p. 18

D.1 CONFIGURATION COEFFICIENTS

  • Table 6’s gain coefficients follow from the exact gains in Table 1 after optimizing any free partner destination.The envelope key uses different source and destination components for the listed configurations.Source: §D.1 · p. 18, Table 6 · p. 19

D.2 ENVELOPE CONSTRUCTION AND QUERIES

  • Line upper envelopes are built by sorting slopes and maintaining active lines; queries use breakpoint search or a monotone scan for sorted radii.The aggregate construction and query cost is O(nk log n).Source: §D.2 · pp. 18–19

D.3 CACHED PIVOT RADII

  • Cached sample-centroid and centroid-centroid distances provide the pivot radii used to construct and query the envelopes.The squared radius for a sample and a center-pair midpoint is expressed using the two sample-centroid distances and the squared centroid separation.Source: §D.3 · p. 19

E PROOFS FOR CANDIDATE-SET SIZE GUARANTEES

  • Appendix E first proves deterministic localization of retained samples, then bounds their count with slab covering for the two stated distribution classes.The proof section describes this route to the candidate-set size guarantees.Source: E PROOFS FOR CANDIDATE-SET SIZE… · p. 19

E.1 DETERMINISTIC LOCALIZATION OF RETAINED SAMPLES

The deterministic analysis confines retained samples to a narrow near-boundary region, but a constructed sequence shows that screening can retain every sample. Under uniform slab-counting control, the paper then establishes logarithmic candidate growth for the specified sampling distributions.

E.1 DETERMINISTIC LOCALIZATION OF RETAINED SAMPLES

  • With n_min ≥ 4, a retained sample must have a small assignment margin: its squared-distance gap to another center is below 25p_max/n_min.Samples outside the localized region cannot be retained, while being inside it is only a necessary—not sufficient—condition for retention.Source: §E.1 · pp. 19, 21

E.2 A WORST-CASE CONSTRUCTION

  • The bounded, balanced construction has m = n because every sample participates in an improving swap, ruling out a distribution-free sublinear bound.Its support locations vary with n, so it does not contradict the fixed-distribution theorem.Source: §E.2 · p. 21

E.3 UNIFORM SLAB COUNTING AND AUTOMATIC CENTER SEPARATION

  • Uniform slab counts and bounded projection densities yield automatic separation between distinct empirical centers in qualifying D-local states.The counting bound is uniform over slab locations, directions, and widths, including slabs chosen from the observations.Source: §E.3 · pp. 22–23

E.4 THE TWO DISTRIBUTION CLASSES

  • For fixed k, d, and nonvanishing occupancy, m = O_P(log n) under bounded-support sampling with bounded density or fixed Gaussian-mixture sampling.The Gaussian-mixture argument needs neither separated component means nor recovery of component labels by empirical clustering.Source: §E.4 · pp. 23–24

F EXPERIMENTAL SETUP

The experiments compare clustering quality and cost across benchmark datasets using shared representations and controlled initializations. The accompanying analyses discuss a possible explanation for smaller gains in larger clusters, distinguish terminal from internal heuristic refinement, and caution against reading finite subsampling results as an asymptotic rate.

F EXPERIMENTAL SETUP

  • The clustering-quality comparison uses twelve datasets, with k set to the reference-class count and shared feature representations across methods.CIFAR datasets use pre-extracted DINOv2 features, while other datasets use the specified pixel, TF–IDF, or measurement representations.Source: F EXPERIMENTAL SETUP · p. 24
  • Quality comparisons use ten shared kmeans++ initializations and report best, mean, and standard deviation; runtime averages are measured separately from quality.The reported runtime includes algorithmic work such as screening but excludes data loading and quality evaluation.Source: F EXPERIMENTAL SETUP · p. 26

G.1 WCSS IMPROVEMENTS IN LARGER CLUSTERS

  • A proposed explanation for smaller one- and two-point gains in larger clusters is that individual moves have diminishing influence relative to total WCSS.The authors note that larger coordinated rearrangements may still improve the objective.Source: §G.1 · p. 26

G.2 HEURISTIC REFINEMENT INSERTION POINTS

  • Post variants apply BPS-2PLS to a heuristic’s final clustering, whereas Inner variants refine intermediate states and can change the later search trajectory.Terminal refinement cannot increase WCSS for a given baseline output; internal refinement need not outperform the baseline on every initialization.Source: §G.2 · pp. 26–27

G.3 CANDIDATE-SET SCALING PROTOCOL AND INTERPRETATION

  • The subsampling study averages retained counts across five subsets and three initializations at each tested size, but cannot establish an asymptotic candidate-growth rate.A constant-size behavior for algorithmic outputs remains a conjecture, not a conclusion from these finite-dataset averages.Source: §G.3 · p. 27

G.4 ADDITIONAL CLUSTERING QUALITY FOR SAMPLE-REASSIGNMENT METHODS

The supplementary results compare clustering agreement with WCSS refinement and break down BPS-2PLS runtime. Agreement changes vary across datasets and metrics, while descent is usually the largest measured runtime phase.

G.4 ADDITIONAL CLUSTERING QUALITY FOR SAMPLE-REASSIGNMENT METHODS

  • BPS-2PLS improves mean ACC and NMI over Lloyd on seven datasets and has the highest available means of both on Yale, ORL, COIL20, and COIL100.Source: §G.4 · pp. 27–28
  • On USPS-1000, Hartigan has higher ACC and NMI than BPS-2PLS despite BPS-2PLS having lower WCSS; on six larger datasets, mean ACC and NMI changes versus D-LO are below 0.01 percentage points.Source: §G.4 · p. 28

G.5 ADDITIONAL CLUSTERING QUALITY FOR HEURISTIC ENHANCEMENT

  • Post improves mean ACC in 16 of 18 available comparisons and mean NMI in all 18; ACC changes range from −0.03 to 10.27 points and NMI increases from 0.04 to 13.55 points.Source: §G.5 · p. 29
  • Inner improves mean ACC and NMI in 11 of 13 comparisons each, but its relative performance against Post depends on dataset and metric.On ORL, MergeSplit–Inner has the lowest mean WCSS but lower mean ACC than both baseline and Post; the tables are descriptive and do not establish statistical significance.Source: §G.5 · p. 29

G.6 RUNTIME BY ALGORITHMIC PHASE

  • Descent is the largest runtime phase on 11 of 12 datasets, accounting for 52.2%–96.7%; ORL is the exception, where screening takes 60.7% versus descent’s 33.3%.Source: §G.6 · p. 30, Table 13 · p. 30
  • Exact pair search accounts for at most 13.5% on Yale and no more than 4.8% elsewhere; screening-enabled timing measures runtime composition, not screening’s net speedup.Source: §G.6 · p. 30
Loading 2610.06182v1…