On the Local Structure of Stable Clustering Instances

Introduction

Clustering is a fundamental, routinely-used approach to extract information from datasets. Given a dataset and the most important features of the data, a clustering is a partition of the data such that data elements in the same part have common features. The problem of computing a clustering has received a considerable amount of attention in both practice and theory.

The variety of contexts in which clustering problems arise makes the problem of computing a “good” clustering hard to define formally. From a theoretician’s perspective, clustering problems are often modeled by an objective function we wish to optimize (e.g., the famous $k$-median or $k$-means objective functions). This modeling step is both needed and crucial since it provides a framework to quantitatively compare algorithms. Unfortunately, the most popular objectives for clustering, like the $k$-median and $k$-means objectives, are hard to approximate, even when restricted to Euclidean spaces.

This view is generally not shared by practitioners. Indeed, clustering is often used as a preprocessing step to simplify and speed up subsequent analysis, even if this analysis admits polynomial time algorithms. If the clustering itself is of independent interest, there are many heuristics with good running times and results on real-world inputs.

This induces a gap between theory and practice. On the one hand, the algorithms that are efficient in practice cannot be proven to achieve good approximation to the $k$-median and $k$-means objectives in the worst-case. Since approximation ratios are one of the main methods to evaluate algorithms, theory predicts that determining a good clustering is a difficult task. On the other hand, the best theoretical algorithms turn out to be noncompetitive in applications because they are designed to handle “unrealistically” hard instances with little importance for practitioners. To bridge the gap between theory and practice, it is necessary to go beyond the worst-case analysis by, for example, characterizing and focusing on inputs that arise in practice.

Several approaches have been proposed to bridge the gap between theory and practice. For example, researchers have considered the average-case scenario (e.g., ) where the running time of an algorithm is analyzed with respect to some probability distribution over the set of all inputs. Smooth analysis (e.g., ) is another celebrated approach that analyzes the running time of an algorithm with respect to worst-case inputs subject to small random perturbations.

Another successful approach, the one we take in this paper, consists in focusing on structured inputs. In a seminal paper, Ostrovsky, Rabani, Schulman, and Swamy introduced the idea that inputs that come from practice induce a ground-truth or a meaningful clustering. They argued that an input $I$ contains a meaningful clustering into $k$ clusters if the optimal $k$-median cost of a clustering using $k$ centers, say $\text{OPT}_{k}(I)$, is much smaller than the optimal cost of a clustering using $k-1$ centers $\text{OPT}_{k-1}(I)$. This is also motivated by the elbow methodThe elbow-method consists in running an (approximation) algorithm for an incrementally increasing number of clusters until the cost drops significantly. (see Section 7 for more details) used by practitioners to define the number of clusters. More formally, an instance $I$ of $k$-median or $k$-means satisfies the $\alpha$-ORSS property if $\text{OPT}_{k}(I)/\text{OPT}_{k-1}(I)\leq\alpha$.

$\alpha$-ORSS inputs exhibit interesting properties. The popular $k$-means$++$ algorithm (also known as the $D^{2}$-sampling technique) achieves an $O(1)$-approximation for these inputs For worst-case inputs, the $k$-means$++$ achieves an $O(\log k)$-approximation ratio .. The condition is also robust with respect to noisy perturbations of the data set. ORSS-stability also implies several other conditions aiming to capture well-clusterable instances. Thus, the inputs satisfying the ORSS property arguably share some properties with the real-world inputs. In this paper, we also provide experimental results supporting this claim, see Appendix C.

These results have opened new research directions and raised several questions. For example:

Is it possible to obtain similar results for more general classes of inputs?

How does the parameter $\alpha$ impact the approximation guarantee and running time?

Is it possible to prove good performance guarantees for other popular heuristics?

How close to the “ground-truth” clustering are the approximate clusterings?

We now review the most relevant work in connection to the above open questions, see Sections 2 for other related work.

Awasthi, Blum and Sheffet have tackled the first two questions by introducing the notion of distribution stable instances. Distribution stable instances are a generalization of the ORSS instances (in other words, any instance satisfying the ORSS property is distribution stable). They also introduced a new algorithm tailored for distribution stable instances that achieves a $(1+\varepsilon)$-approximation for $\alpha$-ORSS inputs (and more generally $\alpha$-distribution stable instances) in time $n^{O(1/\varepsilon\alpha)}$. This was the first algorithm whose approximation guarantee was independent from the parameter $\alpha$ for $\alpha$-ORSS inputs.

Spectral Separability (Def. 6.1)

Kumar and Kannan tackled the first and third questions by introducing the proximity condition In this paper, we work with a slightly more general condition called spectral separability but the motivations behind the two conditions are similar.. This condition also generalizes the ORSS condition. It is motivated by the goal of learning a distribution mixture in a $d$-dimensional Euclidean space. Quoting , the message of their paper can loosely be stated as:

If the projection of any data point onto the line joining its cluster center to any other cluster center is $\gamma k$ times standard deviations closer to its own center than the other center, then we can cluster correctly in polynomial time.

In addition, they have made a significant step toward understanding the success of the classic $k$-means by showing that it achieves a $1+O(1/\gamma)$-approximation for instances that satisfy the proximity condition.

Perturbation Resilience (Def. 5.1)

In a seminal work, Bilu and Linial introduced a new condition to capture real-world instances. They argue that the optimal solution of a real-world instance is often much better than any other solution and so, a slight perturbation of the instance does not lead to a different optimal solution. Perturbation-resilient instances have been studied in various contexts (see e.g., ). For clustering problems, an instance is said to be $\alpha$-perturbation resilient if an adversary can change the distances between pairs of elements by a factor at most $\alpha$ and the optimal solution remains the same. Recently, Angelidakis, Makarychev, and Makarychev have given a polynomial-time algorithm for solving $2$-perturbation-resilient instancesWe note that it is NP-hard to recover the optimal clustering of a $<2$-perturbation-resilient instance . . Balcan and Liang have tackled the third question by showing that a classic algorithm for hierarchical clustering can solve $1+\sqrt{2}$-perturbation-resilient instances. This very interesting result leaves open the question as whether classic algorithms for (“flat”) clustering could also be proven to be efficient for perturbation-resilient instances.

Main Open Questions

Previous work has made important steps toward bridging the gap between theory and practice for clustering problems. However, we still do not have a complete understanding of the properties of “well-structured” inputs, nor do we know why the algorithms used in practice perform so well. Some of the most important open questions are the following:

Do the different definitions of well-structured input have common properties?

Do heuristics used in practice have strong approximation ratios for well-structured inputs?

Do heuristics used in practice recover the “ground-truth” clustering on well-structured inputs?

2 Our Results: A unified approach via Local Search

We make a significant step toward answering the above open questions. We show that the classic Local Search heuristic (see Algorithm 1), that has found widespread application in practice (see Section 2), achieves good approximation guarantees for distribution-stable, spectrally-separable, and perturbation-resilient instances (see Theorems 4.2, 5.2, 6.2).

More concretely, we show that Local Search is a polynomial-time approximation scheme (PTAS) for both distribution-stable and spectrally-separableAssuming a standard preprocessing step consisting of a projection onto a subspace of lower dimension. instances. In the case of distribution stability, we also answer the above open question by showing that most of the structure of the optimal underlying clustering is recovered by the algorithm. Furthermore, our results hold even when only a $\delta$ fraction (for any constant $\delta>0$) of the points of each optimal cluster satisfies the $\beta$-distribution-stability property.

For $\gamma$-perturbation-resilient instances, we show that if $\gamma>3$ then any solution is the optimal solution if it cannot be improved by adding or removing $2\gamma$ centers. We also show that the analysis is essentially tight.

These results show that well-structured inputs have the property that the local optima are close both qualitatively (in terms of structure) and quantitatively (in terms of objective value) to the global “ground-truth” optimum. These results make a significant step toward explaining the success of Local Search approaches for solving clustering problems in practice.

3 Organization of the Paper

Section 2 provides a more detailed review of previous work on worst-case approximation algorithms and Local Search. Further comments on stability conditions not covered in the introduction can be found in Section 7 at the end of the paper. Section 3 introduces preliminaries and notation. Section 4 is dedicated to distribution-stable instances, Section 5 to perturbation-resilient instances, and Section 6 to spectrally-separated instances. All the missing proofs can be found in the appendix.

Related Work

The problems we study are NP-hard: $k$-median and $k$-means are already NP-hard in the Euclidean plane (see Meggido and Supowit , Mahajan et al. , and Dasgupta and Freud ). In terms of hardness of approximation, both problems are APX-hard, even in the Euclidean setting when both $k$ and $d$ are part of the input (see Guha and Khuller , Jain et al. , Guruswami et al. , and Awasthi et al. ). On the positive side, constant factor approximations are known in metric space for both $k$-median and $k$-means (see ). For Euclidean spaces we have a PTAS for both problems, either assuming $d$ fixed and $k$ arbitrary , or assuming $k$ fixed and $d$ arbitrary .

Local Search

Local Search is an all-purpose heuristic that may be applied to any problem, see Aarts and Lenstra for a general introduction. For clustering, there exists a large body of bicriteria approximations for $k$-median and $k$-means . Arya et al. showed that Local Search with a neighborhood size of $1/\varepsilon$ gives a $3+2\varepsilon$ approximation to $k$-median, see also . Kanungo et al. proved an approximation ratio of $9+\varepsilon$ for $k$-means clustering by Local Search, which was until very recently the best known algorithm with a polynomial running time in metric and Euclidean spaces.They combined Local Search with techniques from Matousek for $k$-means clustering in Euclidean spaces. The running time of the algorithm as stated incurs an additional factor of $\varepsilon^{-d}$ due to the use of Matousek’s approximate centroid set. Using standard techniques (see e.g. Section B of this paper), a fully polynomial running time in $n$, $d$, and $k$ is also possible without sacrificing approximation guarantees. Recently, Local Search with an appropriate neighborhood size was shown to be a PTAS for $k$-means and $k$-median in certain restricted metrics including constant dimensional Euclidean space . Due to its simplicity, Local Search is also a popular subroutine for clustering tasks in various more specialized computational models . For more theoretical clustering papers using Local Search, we refer to .

Local Search is also often used for clustering in more applied areas of computer science (e.g., ). Indeed, the use of Local Search with a neighborhood of size $1$ for clustering was first proposed by Tüzün and Burke , see also Ghosh for a more efficient version of the same approach. Due the ease by which it may be implemented, Local Search has become one of the most commonly used heuristics for clustering and facility location, see Ardjmand . Nevertheless, high running times is one of the biggest drawbacks of Local Search compared to other approaches, though a number of papers have engineered it to become surprisingly competitive, see Frahling and Sohler , Kanungo et al. , and Sun .

Definitions and Notations

The problem we consider in this work is the following slightly more general version of the $k$-means and $k$-median problems.

The clustering of $A$ induced by $S$ is the partition of $A$ into subsets $C=\{C_{1},\ldots C_{k}\}$ such that $C_{i}=\{x\in A~{}|~{}c_{i}=\underset{c\in S}{\text{argmin }}\text{cost}(x,c)\}$ (breaking ties arbitrarily).

The well known $k$-median and $k$-means problems correspond to the special cases $\text{cost}(a,c)=\text{dist}(a,c)$ and $\text{cost}(a,c)=\text{dist}(a,c)^{2}$ respectively. Throughout the rest of this paper, let OPT denote the value of an optimal solution. To give slightly simpler proofs for $\beta$-distribution-stable and $\alpha$-perturbation-resilient instances, we will assume that $\text{cost}(a,b)=\text{dist}(a,b)$. If $\text{cost}(a,b)=\text{dist}(a,b)^{p}$, then $\alpha$ depends exponentially on the $p$ for perturbation resilience. For distribution stability, we still have a PTAS by introducing a dependency in $1/\varepsilon^{O(p)}$ in the neighborhood size of the algorithm. The analysis is unchanged save for various applications of the following lemma at different steps of the proof.

Let $p\geq 0$ and $1/2>\varepsilon>0$. For any $a,b,c\in A\cup F$, we have $\text{cost}(a,b)\leq(1+\varepsilon)^{p}\text{cost}(a,c)+\text{cost}(c,b)(1+1/\varepsilon)^{p}$.

Distribution Stability

We work with the notion of $\beta,\delta$-distribution stability which generalizes $\beta$-distribution stability. This extends our result to datasets that exhibit a slightly weaker structure than the $\beta$-distribution stability. Namely, the $\beta,\delta$-distribution stability only requires that for each cluster of the optimal solution, most of the points satisfy the $\beta$-distribution stability condition.

Let $(A,F,\text{cost},k)$ be an instance of $k$-clustering where $A\cup F$ lie in a metric space and let $S^{*}=\{c^{*}_{1},\ldots,c^{*}_{k}\}\subseteq F$ be a set of centers and $C^{*}=\{C^{*}_{1},\ldots,C^{*}_{k}\}$ be the clustering induced by $S^{*}$. Further, let $\beta>0$ and $0\leq\delta\leq 1$. Then the pair $(A,F,\text{cost},k),(C^{*},S^{*})$ is a $(\beta,\delta)$-distribution stable instance if, for any $i$, there exists a set $\Delta_{i}\subseteq C^{*}_{i}$ such that $|\Delta_{i}|\geq(1-\delta)|C^{*}_{i}|$ and for any $x\in\Delta_{i}$, for any $j\neq i$,

where $\text{cost}(x,c^{*}_{j})$ is the cost of assigning $x$ to $c^{*}_{j}$.

For any instance $(A,F,\text{cost},k)$ that is $(\beta,\delta)$-distribution stable, we refer to $(C^{*},S^{*})$ as a $(\beta,\delta)$-clustering of the instance. We show the following theorem for the $k$-median problem. For the $k$-clustering problem with parameter $p$, the constant $\eta$ becomes a function of $p$.

Let $p>0$, $\beta>0$, and $\varepsilon<\min(1-\delta,1/3)$. For a $(\beta,\delta)$-stable instance with $(\beta,\delta)$ clustering $(C^{*},S^{*})$ and an absolute constant $\eta$, the cost of the solution output by Local Search$(4\varepsilon^{-3}\beta^{-1}+O(\varepsilon^{-2}\beta^{-1}))$ (Algorithm 1) is at most $(1+\eta\varepsilon)\text{cost}(C^{*})$.

Moreover, let $L=\{L_{1},\ldots,L_{k}\}$ denote the clusters of the solution output by Local Search$(4\varepsilon^{-3}\beta^{-1}+O(\varepsilon^{-2}\beta^{-1}))$. If $\delta=0$ (i.e.: the instance is simply $\beta$-distribution-stable), there exists a bijection $\phi:L\mapsto C^{*}$ such that for at least $m=k-O(\varepsilon^{-3}\beta^{-1})$ clusters $L^{\prime}_{1},\ldots,L^{\prime}_{m}\subseteq L$, the following two statements hold.

At least a $(1-\varepsilon)$ fraction of $\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}$ are served by a unique center $\mathcal{L}(i)$ in solution $\mathcal{L}$.

The total number of clients $p\in\bigcup_{j\neq i}C^{*}_{j}$ served by $\mathcal{L}(i)$ in $\mathcal{L}$ is at most $\varepsilon|\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}|$.

We first give a high-level description of the analysis. Assume for simplicity that all the optimal clusters cost less than an $\varepsilon^{3}$ fraction of the total cost of the optimal solution. Combining this assumption with the $\beta$-distribution-stability property, one can show that the centers and points close to the center are far away from each other. Thus, guided by the objective function, the local search algorithm identifies most of these centers. In addition, we can show that for most of these good centers the corresponding cluster in the local solution is very similar to the optimal cluster (see Figure 1). In total, only very few clusters (a function of $\varepsilon$ and $\beta$) of the optimal solution are not present in the local solution. We conclude our proof by using local optimality. Our proof includes a few ingredients from such as the notion of inner-ring (we work with a slightly more general definition) and distinguishes between cheap and expensive clusters. Nevertheless our analysis is slightly stronger as we consider a significantly weaker stability condition and can not only analyze the cost of the solution of the algorithm, but also the structure of its clusters.

For any $\varepsilon_{0}$, we define the inner ring of cluster $i$, $\text{IR}^{\varepsilon_{0}}_{i}$, as the set of $x\in A\cup F$ such that $\text{dist}(x,c^{*}_{i})\leq\varepsilon_{0}\beta{\text{OPT}}/{|C^{*}_{i}|}$.

We say that cluster $i$ is cheap if $\sum_{x\in C^{*}_{i}}g_{x}\leq\varepsilon^{3}\beta\text{OPT}$, and expensive otherwise. We aim at proving the following structural lemma.

There exists a set of clusters $Z^{*}\subseteq C^{*}$ of size at most $2\varepsilon^{-3}\beta^{-1}+O(\varepsilon^{-2}\beta^{-1})$ such that for any cluster $C^{*}_{i}\in C^{*}-Z^{*}$, we have the following properties

At least a $(1-\varepsilon)$ fraction of $\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}$ are served by a unique center $\mathcal{L}(i)$ in solution $\mathcal{L}$.

The total number of clients $p\in\bigcup_{j\neq i}\Delta_{j}$ served by $\mathcal{L}(i)$ in $\mathcal{L}$ is at most $\varepsilon|\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}|$.

See Fig 1 for a typical cluster of $C^{*}-Z^{*}$. We start with the following lemma which generalizes Fact 4.1 in .

Let $C^{*}_{i}$ be a cheap cluster. For any $\varepsilon_{0}$, we have $|\text{IR}^{\varepsilon_{0}}_{i}\cap C_{i}^{*}|>(1-{\varepsilon^{3}}/{\varepsilon_{0}})|C^{*}_{i}|$.

We then prove that the inner rings of cheap clusters are disjoint for $\delta+\frac{\varepsilon^{3}}{\varepsilon_{0}}<1$ and $\varepsilon_{0}<\frac{1}{3}$.

Let $\delta+\frac{\varepsilon^{3}}{\varepsilon_{0}}<1$ and $\varepsilon_{0}<\frac{1}{3}$. If $C^{*}_{i}\neq C^{*}_{j}$ are cheap clusters, then $\text{IR}^{\varepsilon_{0}}_{i}\cap\text{IR}^{\varepsilon_{0}}_{j}=\emptyset$.

For each cheap cluster $C^{*}_{i}$, let $\mathcal{L}(i)$ denote a center of $\mathcal{L}$ that belongs to $\text{IR}^{\varepsilon}_{i}$ if there exists exactly such center and remain undefined otherwise. By Lemma 4.6, $\mathcal{L}(i)\neq\mathcal{L}(j)$ for $i\neq j$.

Let $\varepsilon<\frac{1}{3}$. Let $C^{*}-Z_{1}$ denote the set of clusters $C^{*}_{i}$ that are cheap, such that $\mathcal{L}(i)$ is defined and such that at least $(1-\varepsilon)|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|$ clients of $\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}$ are served in $\mathcal{L}$ by $\mathcal{L}(i)$. Then $|Z_{1}|\leq(2\varepsilon^{-3}+11.25\cdot\varepsilon^{-2}+22.5\cdot\varepsilon^{-1})\beta^{-1}$.

There are five different types of clusters in $C^{*}$:

$k_{2}$ cheap clusters with no center of $\mathcal{L}$ belonging to $\text{IR}^{\varepsilon}_{i}$

$k_{3}$ cheap clusters with at least two centers of $\mathcal{L}$ belonging to $\text{IR}^{\varepsilon}_{i}$

$k_{4}$ cheap clusters with $\mathcal{L}(i)$ being defined and less than $(1-\varepsilon)|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|$ clients of $\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}$ are served in $\mathcal{L}$ by $\mathcal{L}(i)$

$k_{5}$ cheap clusters with $\mathcal{L}(i)$ being defined and at least $(1-\varepsilon)|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|$ clients of $\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}$ are served in $\mathcal{L}$ by $\mathcal{L}(i)$

The definition of cheap clusters immediately yields $k_{1}\leq\varepsilon^{-3}\beta^{-1}$.

Since $\mathcal{L}$ and $C^{*}$ both have $k$ clusters and the inner rings of cheap clusters are disjoint (Lemma 4.6), we have $c_{1}k_{1}+c_{3}k_{3}+k_{4}+k_{5}=k_{1}+k_{2}+k_{3}+k_{4}+k_{5}=|Z_{1}|+k_{5}=k$ with $c_{1}\geq 0$ and $c_{3}\geq 2$ resulting in $k_{3}\leq(c_{3}-1)k_{3}=(1-c_{1})k_{1}+k_{2}\leq k_{1}+k_{2}$.

Before bounding $k_{2}$ and $k_{4}$, we discuss the impact of a cheap cluster $C^{*}_{i}$ with at least a $p$ fraction of the clients of $\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}$ being served in $\mathcal{L}$ by some centers that are not in $\text{IR}^{\varepsilon}_{i}$. By the triangular inequality, the cost for any client $x$ of this $p$ fraction is at least $(\varepsilon-\varepsilon^{2})\beta\text{cost}(C^{*})/|C^{*}_{i}|$. Then the total cost of all clients of this $p$ fraction in $\mathcal{L}$ is at least $p|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|(1-\varepsilon)\varepsilon\beta\text{cost}(C^{*})/|C^{*}_{i}|$. By Lemma 4.5, substituting $|\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}|$ yields for this total cost

To determine $k_{2}$, we must use $p=1$ while we have $p>\varepsilon$ for $k_{4}$. Therefore, the total costs of all clients of the $k_{2}$ and the $k_{4}$ clusters in $\mathcal{L}$ are at least $k_{2}(1-\varepsilon)^{2}\varepsilon\beta\text{cost}(C^{*})$ and $k_{4}(1-\varepsilon)^{2}\varepsilon^{2}\beta\text{cost}(C^{*})$, respectively.

Now, since $\text{cost}(\mathcal{L})\leq 5\text{OPT}\leq 5\text{cost}(C^{*})$, we have $(k_{2}+k_{4}\varepsilon)\varepsilon\beta\leq 5/(1-\varepsilon)^{2}\leq 45/4$.

Therefore, we have $|Z_{1}|=k_{1}+k_{2}+k_{3}+k_{4}\leq 2k_{1}+2k_{2}+k_{4}\leq(2\varepsilon^{-3}+11.25\cdot\varepsilon^{-2}+22.5\cdot\varepsilon^{-1})\beta^{-1}$. ∎

We continue with the following lemma, whose proof relies on similar arguments.

There exists a set $Z_{2}\subseteq C^{*}-Z_{1}$ of size at most $11.25\varepsilon^{-1}\beta^{-1}$ such that for any cluster $C^{*}_{j}\in C^{*}-Z_{2}$, the total number of clients $x\in\bigcup_{i\neq j}\Delta_{i}$, that are served by $\mathcal{L}(j)$ in $\mathcal{L}$ is at most $\varepsilon|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|$.

Therefore, the proof of Lemma 4.4 follows from combining Lemmas 4.7 and 4.8.

We now turn to the analysis of the cost of $\mathcal{L}$. Let $C(Z^{*})=\bigcup_{C^{*}_{i}\in Z^{*}}C^{*}_{i}$. For any cluster $C^{*}_{i}\in C^{*}-Z^{*}$, let $\mathcal{L}(i)$ be the unique center of $\mathcal{L}$ that serves at least $(1-\varepsilon)|\text{IR}^{\varepsilon^{2}}_{i}\cap C_{i}^{*}|>(1-\varepsilon)^{2}|C_{i}|$ clients of $\text{IR}^{\varepsilon^{2}}_{i}\cap C^{*}_{i}$, see Lemmas 4.4 and 4.5. Let $\widehat{\mathcal{L}}=\bigcup_{C^{*}_{i}\in C^{*}-Z^{*}}\mathcal{L}(i)$ and define $\widehat{A}$ to be the set of clients that are served in solution $\mathcal{L}$ by centers of $\widehat{\mathcal{L}}$. Finally, let $A(\mathcal{L}(i))$ be the set of clients that are served by $\mathcal{L}(i)$ in solution $\mathcal{L}$. Observe that the $A(\mathcal{L}(i))$ partition $\widehat{A}$.

Consider the following mixed solution $\mathcal{M}=\widehat{\mathcal{L}}\cup\{c_{i}^{*}~{}|~{}C_{i}^{*}\in Z^{*}\}$. We start by bounding the cost of $\mathcal{M}$. For any client $x\in\widehat{A}$, the center that serves it in $\mathcal{L}$ belongs to $\mathcal{M}$. Thus its cost in $\mathcal{M}$ is at most $l_{x}$. Now, for any client $x\in C(Z^{*})$, the center that serves it in $C^{*}$ is in $\mathcal{M}$, so its cost in $\mathcal{M}$ is at most $g_{x}$.

Finally, we evaluate the cost of the clients in $A-(\widehat{A}\cup C(Z^{*}))$. Consider such a client $x$ and let $C^{*}_{i}$ be the cluster it belongs to in solution $C^{*}$. Since $C^{*}_{i}\in C^{*}-Z^{*}$, $\mathcal{L}(i)$ is defined and we have $\mathcal{L}(i)\in\widehat{\mathcal{L}}\subseteq\mathcal{M}$. Hence, the cost of $x$ in $\mathcal{M}$ is at most $\text{cost}(x,\mathcal{L}(i))$. Observe that by the triangular inequality, $\text{cost}(x,\mathcal{L}(i))\leq\text{cost}(x,c^{*}_{i})+\text{cost}(c^{*}_{i},\mathcal{L}(i))=g_{x}+\text{cost}(c^{*}_{i},\mathcal{L}(i))$.

Now consider a client $x^{\prime}\in\text{IR}_{i}^{\varepsilon^{2}}\cap C^{*}_{i}\cap A(\mathcal{L}(i))$. By the triangular inequality, we have $\text{cost}(c^{*}_{i},\mathcal{L}(i))\leq\text{cost}(c^{*}_{i},x^{\prime})+\text{cost}(x^{\prime},\mathcal{L}(i))=g_{x^{\prime}}+l_{x^{\prime}}$. Hence,

It follows that assigning the clients of $C^{*}_{i}\cap(A-\widehat{A})$ to $\mathcal{L}(i)$ induces a cost of at most

Due to Lemma 4.4, we have $|\text{IR}_{i}^{\varepsilon^{2}}\cap C^{*}_{i}\cap A(\mathcal{L}(i))|\geq(1-\varepsilon)\cdot|\text{IR}_{i}^{\varepsilon^{2}}\cap C^{*}_{i}|$ and $|(\text{IR}_{i}^{\varepsilon^{2}}\cap C_{i}^{*})\cap(A-\widehat{A})|\leq\varepsilon\cdot|\text{IR}_{i}^{\varepsilon^{2}}\cap C_{i}^{*}|$. Further, $|(C_{i}^{*}-\text{IR}_{i}^{\varepsilon^{2}})\cap(A-\widehat{A})|\leq|(C_{i}^{*}-\text{IR}_{i}^{\varepsilon^{2}})|=|C^{*}_{i}|-|\text{IR}_{i}^{\varepsilon^{2}}\cap C^{*}_{i}|$. Combining these three bounds, we have

where the inequality in (1) follows from Lemma 4.5.

Summing over all clusters $C^{*}_{i}\in C^{*}-Z^{*}$, we obtain that the cost in $\mathcal{M}$ for the clients in $(A-\widehat{A})\cap C^{*}_{i}$ is less than

By Lemmas 4.7 and 4.8, we have $|\mathcal{M}-\mathcal{L}|+|\mathcal{L}-\mathcal{M}|=2\cdot|Z^{*}|\leq(4\varepsilon^{-3}+O(\varepsilon^{-2}))\beta^{-1}$. By selecting the neighborhood size of Local Search (Algorithm 1) to be greater than this value, we have $(1-\varepsilon/n)\cdot\text{cost}(\mathcal{L})\leq\text{cost}(\mathcal{M})$. Therefore, combining the above observations, we have

By simple transformations, we then obtain

We now turn to evaluate the cost for the clients that are in $\widehat{A}-C(Z^{*})$. For any cluster $C^{*}_{i}\in C^{*}-C(Z^{*})$ and for any $x\in C^{*}_{i}-A(\mathcal{L}(i))$ define $\text{Reassign}(x)$ to be the cost of $x$ with respect to the center in $\mathcal{L}(i)$. Note that there exists only one center of $\mathcal{L}$ in $IR^{\varepsilon}_{i}$ for any cluster $C^{*}_{i}\in C^{*}-C(Z^{*})$. Before going deeper in the analysis, we need the following lemma.

For any $C^{*}_{i}\in C^{*}-C(Z^{*})$, we have

We now partition the clients of cluster $C^{*}_{i}\in C^{*}-Z^{*}$. For any $i$, let $B_{i}$ be the set of clients of $C^{*}_{i}$ that are served in solution $\mathcal{L}$ by a center $\mathcal{L}(j)$ for some $j\neq i$ and $C^{*}_{j}\in C^{*}-Z^{*}$. Moreover, let $D_{i}=(A(\mathcal{L}(i))\cap(\bigcup_{j\neq i}B_{j}))$. Finally, define $E_{i}=(C^{*}_{i}\cap\widehat{A})-\bigcup_{j\neq i}D_{j}$.

Let $C^{*}_{i}$ be a cluster in $C^{*}-Z^{*}$. Define the solution $\mathcal{M}^{i}=\mathcal{L}-\{\mathcal{L}(i)\}\cup\{c^{*}_{i}\}$ and denote by $m^{i}_{x}$ the cost of client $x$ in solution $\mathcal{M}^{i}$. Then

We can thus prove the following lemma, which concludes the proof.

The proof of Theorem 4.2 follows from (1) summing the equations from Lemmas 4.9 and 4.12 and (2) Lemma 4.4. The comparison of the structure of the local solution to the structure of $C^{*}$ is an immediate corollary of Lemma 4.4.

Perturbation Resilience

We first give the definition of $\alpha$-perturbation-resilient instances.

Let $I=(A,F,\text{cost},k)$ be an instance for the $k$-clustering problem. For $\alpha\geq 1$, $I$ is $\alpha$-perturbation-resilient if there exists a unique optimal set of centers $C^{*}=\{c^{*}_{1},\ldots,c^{*}_{k}\}$ and for any instance $I^{\prime}=(A,F,\text{cost}^{\prime},k,p)$, such that

the unique optimal set of centers is $C^{*}=\{c^{*}_{1},\ldots,c^{*}_{k}\}$.

For ease of exposition, we assume that $\text{cost}(a,b)=\text{dist}(a,b)$ (i.e., we work with the $k$-median problem). Given solution $S_{0}$, we say that $S_{0}$ is $1/\varepsilon$-locally optimal if any solution $S_{1}$ such that $|S_{0}-S_{1}|+|S_{1}-S_{0}|\leq 2/\varepsilon$ has at least $\text{cost}(S_{0})$.

Let $\alpha>3$. For any instance of the $k$-median problem that is $\alpha$-perturbation-resilient, any $2(\alpha-3)^{-1}$-locally optimal solution is the optimal set of centers $\{c^{*}_{1},\ldots,c^{*}_{k}\}$.

Moreover, define $l_{c}$ to be the cost for client $c$ in solution $\mathcal{L}$ and $g_{c}$ to be its cost in the optimal solution $C^{*}$. Finally, for any sets of centers $S$ and $S_{0}\subset S$, define $N_{S}(S_{0})$ to be the set of clients served by a center of $S_{0}$ in solution $S$, i.e.: $N_{S}(S_{0})=\{x\mid\exists s\in S_{0},\text{dist}(x,s)=\min_{s^{\prime}\in S}\text{dist}(x,s^{\prime})\}$.

The proof of Theorem 5.2 relies on the following theorem of particular interest.

We first show how Theorem 5.3 allows us to prove Theorem 5.2.

On the other hand, the cost of $\mathcal{L}$ in $I^{\prime}$ is the same as in $I$. By Theorem 5.3

Thus the cost of $\mathcal{L}$ in $I^{\prime}$ is at most

Therefore, we have that the cost of $\mathcal{L}$ is at most the cost of $C^{*}$ in $I^{\prime}$ and so by definition of $\alpha$-perturbation-resilience, we have that the clustering $\{c^{*}_{1},\ldots,c^{*}_{k}\}$ is the unique optimal solution in $I^{\prime}$. Therefore $\mathcal{L}=C^{*}$ and the Theorem follows. ∎

For any client $c$, $\text{Reassign}_{c}\leq l_{c}+2g_{c}$.

The following lemma follows from the definition of the pairs.

Now, observe that the solution $M$ differs from $\mathcal{L}$ by at most $2/\varepsilon$ centers. Thus, by $1/\varepsilon$-local optimality we have $\text{cost}(\mathcal{L})\leq\text{cost}(M)$. Summing over all clients and simplifying, we obtain

The lemma follows by combining with Lemma 5.4. ∎

We now analyze the cost of the clients served by a center of $\mathcal{L}$ that has degree greater than $\varepsilon^{-1}$ in $\Gamma$. The argument is very similar.

Thus, summing over all clients $c$, we have by local optimality

By Lemma 5.4, combining Equations 5 and 3 and averaging over all centers of $\hat{L}$ we have

We now sum the equations of Lemmas 5.6 and 5.7 over all pairs and obtain

Additionally, we show that the analysis is tight (up to a $(1+\varepsilon)$ factor):

For any $\varepsilon>0$, there exists an infinite family of $3-\varepsilon$-perturbation-resilient instances such that for any constant $\varepsilon>0$, there exists a locally optimal solution that has cost at least $3\text{OPT}$.

What remains to be shown is that $L$ is locally optimal. Assume that we swap out $s$ centers. Due to symmetry, we can consider the solution $\{O_{i}|i\in[s]\}\cup\{L_{i}|i\in[k]-[s]\}$. Each of centers $\{O_{i}|i\in[s]\}$ serve $k$ clients with a cost of $k\cdot s\cdot(1+\varepsilon/3)$. The remaining clients are served by $\{L_{i}|i\in[k]-[s]\}$, as $5+2\varepsilon/3<7+\varepsilon/3$. The cost amounts to $s\cdot(k-s)\cdot 5+2\varepsilon/3$ for the clients that get reassigned and $(k-s)^{2}\cdot 3$ for the remaining clients. Combining these three figures gives us a cost of $k^{2}\cdot 3+ks\varepsilon-s^{2}\cdot(2+2\varepsilon/3)>k^{2}\cdot 3+ks\varepsilon+s^{2}\cdot 3$. For $k>\frac{3s}{\varepsilon}$, this is greater than $k^{2}3$, the cost of $L$. ∎

Spectral Separability

In this section we will study the spectral separability condition for the Euclidean $k$-means problem.

Nowadays, a standard preprocessing step in Euclidean $k$-means clustering is to project onto the subspace spanned by the rank $k$-approximation. Indeed, this is the first step of the algorithm by Kumar and Kannan (see Algorithm 2).

In general, projecting onto the best rank $k$ subspace and computing a constant approximation on the projection results in a constant approximation in the original space. Kumar and Kannan and later Awasthi and Sheffet gave tighter bounds if the spectral separation is large enough. Our algorithm omits steps 3 and 4. Instead, we project onto slightly more dimensions and subsequently use Local Search as the constant factor approximation in step 2. To utilize Local Search, we further require a candidate set of solutions, which is described in Section B. For pseudocode, we refer to Algorithm 3. Our main result is to show that, given spectral separability, this algorithm is PTAS for $k$-means (Theorem 6.2).

The best rank $k$ approximation $\underset{\text{rank}(X)=k}{\min}||A-X||_{F}$ is given via $A_{k}=U_{k}\Sigma V^{T}=U\Sigma_{k}V^{T}=U\Sigma V_{k}^{T}$, where $U_{k}$, $\Sigma_{k}$ and $V_{k}^{T}$ consist of the first $k$ columns of $U$, $\Sigma$ and $V^{T}$, respectively, and are zero otherwise. The best rank $k$ approximation also minimizes the spectral norm, that is $||A-A_{k}||_{2}=\sigma_{k+1}$ is minimal among all matrices of rank $k$. The following fact is well known throughout $k$-means literature and will be used frequently throughout this section.

Let $A$ be a set of points in Euclidean space and denote by $c(A)=\frac{1}{|A|}\sum_{x\in A}x$ the centroid of $A$. Then the $1$-means cost of any candidate center $c$ can be decomposed via

We first restate the separation condition.

Let $A$ be a set of points and let $\{C_{1},\ldots C_{k}\}$ be a clustering of $A$ with centers $\{c_{1},\ldots c_{k}\}$. Denote by $C$ an $n\times d$ matrix such that $C_{i}=\underset{j\in\{1,\ldots,k\}}{\text{argmin }}||A_{i}-c_{j}||^{2}$. Then $\{C_{1},\ldots C_{k}\}$ is $\gamma$ spectrally separated, if for any pair of centers $c_{i}$ and $c_{j}$ the following condition holds:

The following crucial lemma relates spectral separation and distribution stability.

For a point set $A$, let $C=\{C_{1},\ldots,C_{k}\}$ be an optimal clustering with centers $S=\{c_{1},\ldots,c_{k}\}$ associated clustering matrix $X$ that is at least $\gamma\cdot\sqrt{k}$ spectrally separated, where $\gamma>3$. For $\varepsilon>0$, let $A_{m}$ be the best rank $m=k/\varepsilon$ approximation of $A$. Then there exists a clustering $K=\{C_{1}^{\prime},\ldots C_{2}^{\prime}\}$ and a set of centers $S_{k}$, such that

the cost of clustering $A_{m}$ with centers $S_{k}$ via the assignment of $K$ is less than $||A_{m}-XX^{T}A_{m}||_{F}^{2}$ and

$(K,S_{k})$ is $\Omega((\gamma-3)^{2}\cdot\varepsilon)$-distribution stable.

We note that this lemma would also allow us to use the PTAS of Awasthi et al. . Before giving the proof, we outline how Lemma 6.5 helps us prove Theorem 6.2. We first notice that if the rank of $A$ is of order $k$, then elementary bounds on matrix norm show that spectral separability implies distribution stability. We aim to combine this observation with the following theorem due to Cohen et al. . Informally, it states that for every rank $k$ approximation, (an in particular for every constrained rank $k$ approximation such as $k$-means clustering), projecting to the best rank $k/\varepsilon$ subspace is cost-preserving.

The combination of the low rank case and this theorem is not trivial as points may be closer to a wrong center after projecting, see also Figure 2. Lemma 6.5 determines the existence of a clustering whose cost for the projected points $A_{m}$ is at most the cost of $C^{*}$. Moreover, this clustering has constant distribution stability as well which, combined with the results from Section B, allows us to use Local Search. Given that we can find a clustering with cost at most $(1+\varepsilon)\cdot||A_{m}-XX^{T}A_{m}||_{F}^{2}$, Theorem 6.6 implies that we will have a $(1+\varepsilon)^{2}$-approximation overall.

To prove the lemma, we will require the following steps:

A lower bound on the distance of the projected centers $||c_{i}V_{m}V_{m}^{T}-c_{j}V_{m}V_{m}^{T}||\approx||c_{i}-c_{j}||$.

Find a clustering $K$ with centers $S_{m}^{*}=\{c_{1}V_{m}V_{m}^{T},\ldots,c_{k}^{*}V_{m}V_{m}^{T}\}$ of $A_{m}$ with cost less than $||A_{m}-XX^{T}A_{m}||_{F}^{2}$.

Show that in a well-defined sense, $K$ and $C^{*}$ agree on a large fraction of points.

For any point $x\in K_{i}$, show that the distance of $x$ to any center not associated with $K_{i}$ is large.

For a point set $A$, let $C=\{C_{1},\ldots C_{k}\}$ be a clustering with associated clustering matrix $X$ and let $A^{\prime}$ and $A^{\prime\prime}$ be optimal low rank approximations where without loss of generality $k\leq\text{rank}(A^{\prime})<\text{rank}(A^{\prime\prime})$. Then for each cluster $C_{i}$

By Fact 6.3 $|C_{i}|\cdot||\frac{1}{|C_{i}|}\sum_{j\in C_{i}}(A_{i}^{\prime\prime}-A_{i}^{\prime})||_{2}^{2}$ is, for a set of point indexes $C_{i}$, the cost of moving the centroid of the cluster computed on $A^{\prime\prime}$ to the centroid of the cluster computed on $A^{\prime}$. For a clustering matrix $X$, $||XX^{T}A^{\prime}-XX^{T}A^{\prime}||_{F}^{2}$ is the sum of squared distances of moving the centroids computed on the point set $A^{\prime\prime}$ to the centroids computed on $A^{\prime}$. We then have

For any point $p$ associated with some row of $A$, let $p^{m}=pV_{m}V_{m}^{T}$ be the corresponding row in $A_{m}$. Similarly, for some cluster $C_{i}$, denote the center in $A$ by $c_{i}$ and the center in $A_{m}$ by $c_{i}^{m}$. Extend these notion analogously for projections $p^{k}$ and $c_{i}^{k}$ to the span of the best rank $k$ approximation $A_{k}$.

where the second inequality follows from Lemma 6.7.

In the following, let $\Delta_{i}=\frac{\sqrt{k}}{\sqrt{|C_{i}|}}||A-XX^{T}A||_{2}$. We will now construct our target clustering $K$. Note that we require this clustering (and its properties) only for the analysis. We distinguish between the following three cases.

These points remain assigned to $c_{i}^{m}$. The distance between $p_{m}$ and a different center $c_{j}^{m}$ is at least $\frac{1}{2}||c_{i}^{m}-c_{j}^{m}||\geq\frac{\gamma-1}{2}\varepsilon(\Delta_{i}+\Delta_{j})$ due to Equation 5.

These points will get reassigned to their closest center.

The distance between $p_{m}$ and a different center $c_{j}^{m}$ is at least $\frac{1}{2}||c_{i}^{m}-c_{j}^{m}||\geq\frac{\gamma-1}{2}\varepsilon(\Delta_{i}+\Delta_{j})$ due to Equation 5.

We assign $p^{m}$ to $c^{m}_{i}$ at the cost of a slightly weaker movement bound on the distance between $p^{m}$ and $c^{m}_{j}$. Due to orthogonality of $V$, we have for $m>k$, $(V_{m}-V_{k})^{T}V_{k}=V_{k}^{T}(V_{m}-V_{k})=0$. Hence $V_{m}V_{m}^{T}V_{k}=V_{m}V_{k}^{T}V_{k}+V_{m}(V_{m}-V_{k})^{T}V_{k}=V_{k}V_{k}^{T}V_{k}+(V_{m}-V_{k})V_{k}^{T}V_{k}=V_{k}V_{k}^{T}V_{k}=V_{k}$. Then $p^{k}=pV_{k}V_{k}^{T}=pV_{m}V_{m}^{T}V_{k}V_{k}^{T}=p_{m}V_{k}V_{k}^{T}$.

Further, $||p^{k}-c_{j}^{k}||\geq\frac{1}{2}||c_{j}^{k}-c_{i}^{k}||\geq\frac{\gamma-1}{2}(\Delta_{i}+\Delta_{j})$ due to Equation 5. Then the distance between $p_{m}$ and a different center $c_{j}^{m}$

where the equality follows from orthogonality and the second to last inequality follows from Lemma 6.7.

Now, given the centers $\{c_{1}^{m},\ldots c_{k}^{m}\}$, we obtain a center matrix $M_{K}$ where the $i$th row of $M_{K}$ is the center according to the assignment of above. Since both clusterings use the same centers but $K$ improves locally on the assignments, we have $||A_{m}-M_{K}||_{F}^{2}\leq||A_{m}-XX^{T}A_{m}||_{F}^{2}$, which proves the first statement of the lemma. Additionally, due to the fact that $A_{m}-XX^{T}A_{m}$ has rank $m=k/\varepsilon$, we have

To ensure stability, we will show that for each element of $K$ there exists an element of $C$, such that both clusters agree on a large fraction of points. This can be proven by using techniques from Awasthi and Sheffet (Theorem 3.1) and Kumar and Kannan (Theorem 5.4), which we repeat for completeness.

Let $K=\{C_{1}^{\prime},\ldots C_{k}^{\prime}\}$ and $C=\{C_{1},\ldots C_{k}\}$ be defined as above. Then there exists a bijection $b:C\rightarrow K$ such that for any $i\in\{i,\ldots,k\}$

Denote by $T_{i\rightarrow j}$ the set of points from $C_{i}$ such that $||c^{k}_{i}-p^{k}||>||c^{k}_{j}-p^{k}||$. We first note that $||A_{k}-XX^{T}A||_{F}^{2}\leq 2k\cdot||A_{k}-XX^{T}A||_{2}^{2}\leq 2k\cdot\left(||A-A_{k}||_{2}+||A-XX^{T}A||_{2}\right)^{2}\leq 8k\cdot||A-XX^{T}A||_{2}^{2}\leq 8\cdot|C_{i}|\cdot\Delta_{i}^{2}$ for any $i\in\{1,\ldots,k\}$. The distance $||p^{k}-c_{i}^{k}||\geq\frac{1}{2}||c^{k}_{i}-c_{j}^{k}||\geq\frac{\gamma-1}{2}\cdot\left(\frac{1}{\sqrt{C_{i}}}+\frac{1}{\sqrt{|C_{j}|}}\right)\sqrt{k}||A-XX^{T}A||_{2}^{2}$. Assigning these points to $c^{k}_{i}$, we can bound the total number of points added to and subtracted from cluster $C_{j}$ by observing

Therefore, the cluster sizes are up to some multiplicative factor of $\left(1\pm\frac{32}{(\gamma-1)^{2}}\right)$ identical. ∎

We now have for each point $p^{m}\in C_{i}^{\prime}$ a minimum cost of

where the first inequality holds due to Case 3, the second inequality holds due to Lemma 6.8 and the last inequality follows from $\gamma>3$ and Equation 6. This ensures that the distribution stability condition is satisfied. ∎

Any $(1+\varepsilon)$-approximation will not in general agree with a target clustering. To see this consider two clusters: (1) with mean on the origin and (2) with mean $\delta$ on the the first axis and on all other coordinates. We generate points via a multivariate Gaussian distribution with an identity covariance matrix centered on the mean of each cluster. If we generate enough points, the instance will have constant spectral separability. However, if $\delta$ is small and the dimension large enough, an optimal $1$-clustering will approximate the $k$-means objective.

A Brief Survey on Stability Conditions

There are two general aims that shape the definitions of stability conditions. First, we want the objective function to be appropriate. For instance, if the data is generated by mixture of Gaussians, the $k$-means objective will be more appropriate than the $k$-median objective. Secondly, we assume that there exists some ground truth, i.e. a correct assignment of points into clusters. Our objective is to recover this ground truth as well as possible. These aims are not mutually exclusive. For instance, an ideal objective function will allow us to recover the ground truth. We refer to Figure 3 for a visual overview of stability conditions and their relationships.

Given that an algorithm optimized with respect to some objective function, it is natural to define a stability condition as a property the optimum clustering is required to have.

Assume that we want to cluster a data set with respect to the $k$-means objective, but have not decided on the number of clusters. A simple way of determining the ”correct” value of $k$ is to run a $k$-means algorithm for $k\{1,2,\ldots m\}$ until the objective value decreases only marginally (using $m$ centers). At this point, we set $k=m-1$. The reasoning behind this method, commonly known as the elbow-method is that we do not gain much information by using $m$ instead of $m-1$ clusters, so we should favor the simpler model. Contrariwise, this implies that we did gain information going from $m-2$ to $m-1$ and, in particular, that the $m-2$-means cost was considerably larger than the $m-1$-means cost.

Ostrovsky et al. considered whether such discrepancies in the cost also allow us to solve the $k$-means problem more efficiently, see also Schulman for an earlier condition for two clusters and the irreducibility condition by Kumar et al. . Specifically, they assumed that the optimal $k$-means clustering has only an $\varepsilon^{2}$-fraction of the cost of the optimal $(k-1)$-means clustering. For such cost separated instances, the popular $D^{2}$-sampling technique has an improved performance compared to the worst-case $O(\log k)$-approximation ratio . Awasthi et al. showed that if an instance is cost-stable, it also admits a PTAS. In fact, they also showed that the weaker condition $\beta$-stability is sufficient. $\beta$-stability states that the cost of assigning a point of cluster $C_{i}$ to another cluster $C_{j}$ costs at least $\beta$ times the total cost divided by the size of cluster $C_{i}$. Despite its focus on the properties of the optimum, $\beta$-stability has many connections to target-clustering (see below). Nowadays, the cost-stable property is one of the strongest stability conditions, implying both distribution stability and spectral separability (see below). It is nevertheless the arguably most intuitive stability condition.