PaperlayerView exact revision on arXiv

Source-linked AI summary

Relax, no need to round: integrality of clustering formulations

Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward

arXiv:1408.4045v5stat.MLcs.DScs.LGmath.STstat.TH

TL;DR

The paper asks when convex relaxations can recover a planted clustering directly, rather than merely approximate an objective. It develops dual-certificate conditions for k-median and k-means relaxations and analyzes their recovery under random point-cloud models. The k-median LP recovers above separation 2 + ε, while the k-means LP requires separation at least 4 for integrality; the SDP guarantee is not tight.

  • Problem

    The paper asks when convex relaxations can recover the ground-truth clustering directly, since prior work largely studied their approximation of objective values.

    Source: §1 · pp. 1–2

  • Method

    The authors establish deterministic integrality conditions using dual certificates, then use concentration arguments to show those conditions hold with high probability for random inputs.

    Source: §2 · pp. 6–7

  • Results

    The k-median LP recovers planted clusters above separation 2 + ε for sufficiently large n, whereas the k-means LP is integral only at separation at least 4.

    Source: §7 · p. 14

  • Takeaways & Limitations

    Exact recovery provides a way to bypass rounding and compare convex relaxations by whether their optima recover the underlying discrete solution.

    Source: §1 · p. 2

    The k-means SDP separation guarantee is not tight; the authors conjecture recovery above 2 + ε.

    Source: §1.3 · p. 4

Abstract

from arXiv · show

We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: $k$-means and $k$-median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and (b) they are generic tools which are relatively parameter-free, not tailored to specific assumptions over the input. More precisely, we consider the distributional setting where there are $k$ clusters in $\mathbb{R}^m$ and data from each cluster consists of $n$ points sampled from a symmetric distribution within a ball of unit radius. We ask: what is the minimal separation distance between cluster centers needed for convex relaxations to exactly recover these $k$ clusters as the optimal integral solution? For the $k$-median linear programming relaxation we show a tight bound: exact recovery is obtained given arbitrarily small pairwise separation $\epsilon > 0$ between the balls. In other words, the pairwise center separation is $\Delta > 2+\epsilon$. Under the same distributional model, the $k$-means LP relaxation fails to recover such clusters at separation as large as $\Delta = 4$. Yet, if we enforce PSD constraints on the $k$-means LP, we get exact cluster recovery at center separation $\Delta > 2\sqrt2(1+\sqrt{1/m})$. In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the $k$-means algorithm) can fail to recover clusters in this setting; even with arbitrarily large cluster separation, k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. To complement the theoretical analysis, we provide an experimental study of the recovery guarantees for these various methods, and discuss several open problems which these experiments suggest.

1. INTRODUCTION

The introduction asks when convex relaxations can recover planted point-cloud clusters directly, without rounding. It compares k-median and k-means relaxations, gives separation guarantees, and contrasts their recovery with common heuristics and stochastic block models.

1. INTRODUCTION

  • The study shifts focus from approximation factors to whether a convex relaxation’s optimum directly recovers the ground-truth clustering, a phenomenon called exact recovery or integrality.The introduction notes that this can bypass rounding.Source: §1 · pp. 1–2

1.1. Geometric clustering.

  • Geometric clustering maps data into a metric space and partitions the points into k disjoint clusters; k-median uses representative data points, while k-means minimizes squared distances to cluster averages.The k-median objective sums distances to representative points; the k-means objective averages squared Euclidean distances within each cluster.Source: §1.1 · p. 2, Figure 1 · p. 3

1.2. Prior work.

  • Prior work studied approximation and k-median LP recovery at larger separations; this paper reports recovery at 2 + ε for sufficiently large samples.Earlier work cited in the introduction showed recovery at separation at least 3.75.Source: §1.2 · p. 3

1.3. Our contribution.

  • For unit-radius balls, the k-median LP recovers planted clusters above separation 2 + ε, while the k-means LP fails below 4; the k-means SDP guarantee is not tight.The k-median and k-means LP separation bounds are stated as tight; the authors conjecture the SDP guarantee holds above 2 + ε.Source: §1.3 · p. 4
  • PAM and Lloyd’s algorithm can fail with high probability, and k-means++ with constant-factor overseeding can fail even at arbitrarily large separation.The paper also reports failure for these heuristics well inside the regime where its relaxation guarantees apply.Source: §1.3 · p. 4, §1.4 · p. 5
  • The analysis uses dual certificates and concentration results to establish deterministic sufficient conditions, then shows those conditions hold with high probability for random inputs.For the k-means LP, complementary slackness shows exact recovery is possible with high probability if and only if separation is at least 4.Source: §1.3 · p. 5

1.4. Why Study Convex Relaxations?

  • Convex relaxations provide certificates of optimality and are not tied to a particular data distribution, unlike algorithms tailored to specific input assumptions.The relaxations studied depend only on k, the number of clusters.Source: §1.4 · p. 5

1.5. Comparison with stochastic block models.

  • Unlike the graph-based stochastic block model, this work clusters Euclidean point clouds; its random model samples vertices, creating dependent distances and heterogeneous point profiles.The paper notes that its conditions could potentially apply to other, including deterministic, point clouds.Source: §1.5 · pp. 5–6

2. INTEGRALITY FOR THE k-MEDIAN LP RELAXATION

The section gives sufficient conditions under which the k-median LP has an integral optimum matching the planted clusters. For large samples from suitable rotationally symmetric distributions, the LP recovers clusters with center separation greater than 2.

2. INTEGRALITY FOR THE k-MEDIAN LP RELAXATION

  • A dual certificate proves integrality by matching the intended clustering's primal cost with a feasible dual solution.The proof restricts dual distance-threshold variables to be constant within each cluster.Source: §2 · p. 6
  • The sufficient condition improves on the condition in [46] by allowing cluster separation as small as 2 + ε.The stated improvement applies to the k-median LP condition discussed in this section.Source: §2 · p. 7
  • Separation and center dominance suffice for the k-median LP to have an integral optimum equal to the partition into the specified clusters.Center dominance requires the contribution function's maximum to occur near each ball's center for a range of dual distance thresholds.Source: §2 · pp. 7–8
  • For k unit balls with centers separated by more than 2, sufficiently many independent samples from a continuous rotationally symmetric distribution yield an integral k-median LP with probability approaching 1.The distribution must be supported in the unit ball, and every neighborhood of its center must have positive measure.Source: §2 · p. 8

3. AN INTEGRALITY GAP FOR THE k-MEANS LP RELAXATION

The natural k-means LP requires a strong separation condition for the planted clustering to be integral. Under the section's distributional model, separation 4 is the recovery threshold.

3. AN INTEGRALITY GAP FOR THE k-MEANS LP RELAXATION

  • The section contrasts the k-means LP's threshold with the k-median LP, which can recover clusters at separation just above 2.For Δ < 4, the planted clustering is not the LP solution with high probability when enough points are provided.Source: §3 · pp. 8–9
  • An integral solution matching the proposed clusters requires every within-cluster point pair to be closer than every cross-cluster pair.This condition follows from complementary slackness for the natural k-means LP.Source: §3 · p. 9
  • For sufficiently many points from rotationally symmetric distributions in unit balls, the k-means LP fails to recover planted clusters when Δ < 4 and recovers them when Δ > 4.The threshold is tight under the stated distributional model.Source: §3 · p. 9

4. INTEGRALITY FOR THE k-MEANS SDP RELAXATION

Adding positive semidefinite constraints strengthens the k-means relaxation and enables an integrality analysis based on a dual certificate. A deterministic average-separation condition guarantees a unique integral optimum matching the k-means clustering.

4. INTEGRALITY FOR THE k-MEANS SDP RELAXATION

  • The SDP proof constructs a dual certificate and derives deterministic recovery conditions by requiring positive semidefiniteness and nonnegative dual variables.The derived average-separation condition compares within- and between-cluster distances and averages.Source: §4 · pp. 10–12
  • The intended primal solution is block-diagonal, with entries 1/n within each cluster block and zero elsewhere.A feasible dual solution with matching objective certifies optimality; the rank condition certifies uniqueness.Source: §4 · p. 11
  • If a squared-distance clustering instance satisfies average separation, the k-means SDP has a unique integral optimum equal to the k-means optimal clustering.The proof constructs a feasible dual certificate and uses a rank condition to establish uniqueness.Source: §4 · pp. 11–12

5. WHERE CONVEX RELAXATIONS SUCCEED, LLOYD’S METHOD CAN FAIL

The section shows that Lloyd's method and k-means++ can fail to recover separated clusters even where convex relaxations recover them. The failures arise from initialization patterns that leave some groups without suitable centers.

5. WHERE CONVEX RELAXATIONS SUCCEED, LLOYD’S METHOD CAN FAIL

  • With overwhelming probability, Lloyd's initialization either leaves a group of three clusters without three initial centers or puts two centers in its distant cluster and one across its two nearby clusters.In either configuration, the algorithm will not recover the true clustering.Source: §5 · p. 13
  • For any constant overseeding factor c > 1 and minimum separation Δ > 2, inputs exist on which k-means++ with ck initial centers fails with high probability to recover clusters exactly.The construction extends to arbitrarily large separation.Source: §5 · p. 13

6. SIMULATIONS

Across the simulations, k-median LP and k-means SDP recover planted clusters at lower separation thresholds than k-means LP. Integrality alone is not always planted-cluster recovery: k-median LP can return a different clustering, while k-means LP and SDP failures can be fractional.

SIMULATIONS

  • Each experiment sampled n points per cluster from k disjoint unit-radius balls in R^m and counted success only when the relaxation was integral and recovered those clusters.Each (Δ, n) setting was repeated 10 times; Figure 4 used 3 clusters in R3, with 6≤N≤42 and 2≤Δ≤3.5.Source: §6 · p. 13, Figure 4 · p. 14
  • For 2 clusters in R3, k-median LP and k-means SDP outperform k-means LP at lower separation; their performance is comparable, but k-median LP is much faster.The k-means LP is rarely integral for Δ<3.Source: §6 · p. 13, Figure 3 · p. 14
  • Across the simulations, k-median LP always produced integral solutions, though some did not match the planted clusters.When N is small, another clustering can make sense as more optimal than the planted distribution.Source: §6 · p. 14
  • For k-means LP and SDP, every integral solution matched the expected clustering, while failures in Figures 3 and 4 were non-clustering matrices.These matrices contain ground-truth cliques plus extra inter-cluster edges.Source: §6 · p. 14

7. CONCLUSIONS AND FUTURE WORK

The conclusions compare exact-recovery guarantees across clustering relaxations and identify settings and questions for future work. The paper also points to broader integrality questions beyond the equal-radius, equal-size disjoint-ball model.

CONCLUSIONS AND FUTURE WORK

  • The k-means LP is integral only for Δ≥4, where simple thresholding can also distinguish clusters; k-median LP is much better at recovering optimal solutions.This comparison is supported by both theoretical and empirical results.Source: §7 · p. 14
  • For any k, k-median LP recovers the planted clusters with high probability at separation 2+ε when n is large enough, but the required n remains unquantified in terms of other parameters.The paper states that quantifying this sample-size requirement remains open.Source: §7 · p. 14
  • Failed k-means LP or SDP solutions can retain planted-cluster cliques while adding edges between clusters, rather than representing a clustering.The figure contrasts these matrices with solutions representing k complete connected components.Source: Figure 5 · p. 15
  • The authors conjecture that the k-means SDP recovers clusters with high probability for separation Δ>2+ε.The cited passage states this as a conjecture, not a proved guarantee.Source: §7 · p. 15
  • The analysis studies iid points in disjoint equal-radius balls; relaxing equal radii or equal cluster sizes, and considering overlap or Gaussian mixtures, are proposed directions.The authors note that these latter settings lack a clear ground-truth clustering to recover.Source: §7 · p. 15
  • Future directions include studying near-optimal rather than integral solutions and proving exact-recovery guarantees for approximation algorithms beyond the k-median primal-dual algorithm.The paper gives a sufficient condition for exact recovery by the k-median primal-dual algorithm.Source: §7 · p. 15
  • The same integrality questions could be studied in other domains, including graphical-model inference and graph partitioning.Source: §7 · p. 15

APPENDIX A. PROOF OF THEOREM 6

Theorem 6 establishes that separation and center dominance yield an integral k-median LP solution corresponding to the given clusters. The proof uses these properties to construct dual variables satisfying the required inequalities.

APPENDIX A. PROOF OF THEOREM 6

  • Separation and center dominance imply an integral k-median LP solution that separates the union of the sets into A1,…,Ak.Source: Appendix A · p. 17
  • Center dominance makes the maximum right-hand side within cluster Aj occur near its center, while separation prevents other clusters from contributing to the left-hand side there.The proof uses this to establish the inequality for points near each center.Source: Appendix A · p. 17
  • The proof equalizes n_jα_j−OPT_j across clusters so the right-hand side of equation (5) is consistent when maximizing over clusters.Source: Appendix A · p. 18
  • Because the points and sets are given, the resulting constraints form a linear system with one degree of freedom.Source: Appendix A · p. 18

APPENDIX B. PROOF OF THEOREM 7

Theorem 7 proves that the k-median LP recovers the intended clustering with probability at least any fixed γ<1 once each cluster contains sufficiently many sampled points. Its proof establishes center dominance first in expectation, then transfers that property to the sampled data.

Theorem 7

  • For every γ<1, the k-median LP is integral with probability at least γ when n is sufficiently large under Theorem 7’s distributional assumptions.The clusters are translations of a continuous, rotationally symmetric measure supported in the unit ball, with positive measure in every neighborhood of the center and pairwise center distances greater than 2.Source: Appendix B · p. 18

Proof strategy

  • The weak law of large numbers and concentration inequalities transfer expected center dominance to sampled points, with probability approaching one as n grows.The argument also uses positive probability of sampling near each center to ensure a sampled point lies in the region where the objective is maximized.Source: Appendix B · p. 19
  • A separation-based construction chooses α>1 so the expected objective is maximized at each cluster center, using rotational symmetry in the proof.The construction copies intersections of an expanded ball inside other cluster balls without overlap; the proof notes that rotational symmetry is not strictly necessary if the center-maximization property holds.Source: Appendix B · pp. 18–19
  • Continuity preserves center-maximization when the parameters α1,…,αk remain sufficiently close to the common α.Lemma 14 establishes a neighborhood of parameter values for which the expected objective still attains its maximum at each center.Source: Appendix B · pp. 19–20

APPENDIX C. EXACT RECOVERY USING THE k-MEANS SDP

The appendix proves uniqueness of the intended k-means SDP solution by constructing a dual certificate. It reduces positive semidefiniteness to conditions on the data and derives a sufficient geometric criterion for integrality.

Dual certificate

  • A dual certificate with Q ⪰ 0 and nullspace dimension k proves that the intended cluster solution is the unique k-means SDP solution.The certificate also requires each block Q(a,b) to annihilate the all-ones vector.Source: Appendix C · p. 23
  • The certificate’s PSD requirement reduces to a quadratic-form inequality on vectors perpendicular to the cluster-indicator subspace.The appendix decomposes the squared-distance matrix to simplify that inequality.Source: Appendix C · p. 24

Sufficient condition

  • Lemma 17 gives a sufficient condition, imposed across every pair of clusters and point indices, for the SDP’s unique solution to equal the intended clustering.The condition is expressed through the constructed certificate’s parameters.Source: Appendix C · pp. 22, 24

Geometric criterion

  • A parallelogram-identity reformulation expresses the sufficient condition geometrically, and the appendix asks what cluster separation ensures it holds.The reformulated condition still guarantees a unique intended SDP solution.Source: Appendix C · p. 24

APPENDIX D. THE k-MEANS SDP DISTINGUISHES CLUSTERS

For equal-size clusters sampled from a common continuous, rotationally symmetric distribution within unit balls, the appendix derives a sufficient separation condition for k-means SDP recovery. Under that condition, the SDP has a unique integral solution matching the intended clustering with high probability.

Model and assumptions

  • The probabilistic model assumes equal cluster sizes, unit-radius supports, and a common continuous, rotationally symmetric distribution translated to each center.The appendix represents the data as centered random points plus a matrix encoding center shifts.Source: Appendix D · p. 25

Separation analysis

  • A deterministic proposition bounds the worst-case left-hand side of the SDP’s geometric condition for two clusters with disjoint ball supports and means at their centers.Its minimizing configurations differ according to whether Δ is at most 4 or greater than 4.Source: Appendix D · p. 25

Probabilistic bound

  • Concentration bounds on the centered data yield a sufficient condition for the geometric integrality inequality to hold with high probability.The argument applies a union bound across clusters before stating the condition.Source: Appendix D · pp. 25–26

Recovery guarantee

  • Under the theorem’s separation condition, the k-means SDP has a unique integral solution matching the intended clustering with probability exceeding the stated bound.The theorem’s probability bound is stated as exceeding 1 − 2mk exp(…).Source: Appendix D · p. 26

APPENDIX E. WHERE CONVEX RELAXATIONS SUCCEED, LLOYD’S METHOD CAN FAIL

The appendix constructs separated three-cluster groups on which Lloyd’s method can remain trapped in a nonoptimal clustering. It extends the construction to show high failure probability for k-means++ with overseeding and pruning.

Lloyd’s method

  • If Lloyd’s initialization puts two centers in C and one in A ∪ B, subsequent assignments and centroid updates preserve that allocation, leaving the clustering nonoptimal.The third cluster is far from the first two, so points in A and B continue sharing the same center while points in C split between the other two.Source: Appendix E · p. 26
  • Repeating the three-cluster construction across sufficiently separated groups can make Lloyd’s success probability exponentially small as the number of groups increases.Failure occurs if a group receives fewer than three initial centers or is initialized with the trapping configuration.Source: Appendix E · pp. 26–27

k-means++

  • If overseeding leaves only one center among A_i ∪ B_i for any group, the resulting algorithm deterministically fails to recover the clusters.This condition underlies the appendix’s failure construction for overseeding followed by pruning.Source: Appendix E · p. 27
  • For any overseeding factor c>1, the appendix constructs K=3k centers with pairwise separation Δ>2 such that overseeding and pruning fail with probability at least any specified γ<1.The construction places close A and B clusters beside a distant C cluster in each group.Source: Appendix E · p. 27

APPENDIX F. RECOVERY GUARANTEES THROUGH PRIMAL-DUAL ALGORITHM

Under separation and center-dominance conditions, the primal-dual algorithm recovers the exact clustering when run with the specified LP-derived parameter. The appendix explains how clusterwise dual variables support this recovery and when the algorithm’s conflict-removal step is unnecessary.

APPENDIX F. RECOVERY GUARANTEES THROUGH PRIMAL-DUAL ALGORITHM

  • The k-median LP result also implies that Jain and Vazirani’s Primal-Dual algorithm [36] converges to the exact solution when separation and center dominance hold.Source: Appendix F · p. 28
  • The algorithm removes medians whose contributors overlap; this makes it an approximation algorithm, and its output is exact when no point contributes to two medians.The appendix also explains the algorithm’s dual variables as point payments and the cost of opening a median.Source: Appendix F · p. 28

F.1. Exact recovery via the Primal-Dual algorithm.

  • The LP dual solution has variables constant within each cluster, suggesting that choosing z from the primal and dual solutions freezes each cluster at once.This is the proposed link between the LP integrality result and the algorithm’s behavior.Source: §F.1 · p. 28
  • With z = nαA − OPTA = nαB − OPTB, Proposition 20 states that the algorithm assigns points in A to mA and points in B to mB under separation and center dominance.The proposition gives the exact-recovery result for two sets A and B.Source: §F.1 · p. 29

Related papers

Loading 1408.4045v5…