arthur_k-means_2007

1 Introduction↩︎

Clustering problems are ubiquitous, and arise in a variety of application domains including data mining, machine learning, computer vision, computational geometry, bioinformatics, and supply-chain logistics. Typically, in a \(k\)-clustering problem, we are given a metric space \((\mathcal{C}, d)\) and must choose a set \(S\) of \(k\) centers to open. Each client \(j\in \mathcal{C}\) incurs a connection or assignment cost, namely the distance between \(j\) and center in \(S\) that it has been assigned to (which is often the closest center in \(S\)). In many such problems, the goal is to choose \(k\)-centers so as to minimize some function of the induced assignment-cost vector. Classical problems of this form, which have been extensively studied, include the \(k\)-median, \(k\)-means, and \(k\)-center problems, wherein the function (to be minimized) is the sum, sum of squares, and maximum, of the assignment-cost vector entries respectively.

In this paper, we study the minimum-norm \(k\)-clustering problem, which is a far-reaching generalization of the \(k\)-median and \(k\)-center problems (and also essentially captures the \(k\)-means problem). In this problem, we are given an arbitrary monotone, symmetric norm \(f:\mathbb{R}^n\mapsto\mathbb{R}_+\), where \(n=|\mathcal{C}|\), and we wish to minimize \(f(\text{assignment-cost vector})\). Monotone, symmetric norms capture a very wide range of objective functions; we list two relevant examples here, and refer the reader to [1] and the references therein for further examples.

• \(\ell_p\)-norms: These are probably the most well-known example of monotone, symmetric norms, where \(\ell_p(v) := (\sum_{j=1}^n |v_j|^p)^{1/p}\), for \(p\geq 1\). When \(p = 1, \infty\), we obtain the \(k\)-median and \(k\)-center problems respectively, and \(p=2\) essentially captures the \(k\)-means problem (the \(k\)-means objective is \(\ell_2^2\)).

• \(\text{Top}_{\ell}\) and ordered norms: The \(\text{Top}_{\ell}\)-norm of a vector \(v\in\mathbb{R}^n\) is the sum of the \(\ell\) largest entries of \((|v_j|)_{j\in[n]}\). Letting \(v^\downarrow\) denote the vector \(v\) with its entries sorted in non-increasing order, for \(v\geq 0\), we have \(\text{Top}_{\ell}(v) = \sum_{j = 1}^\ell v^\downarrow_j\). An ordered norm is a nonnegative linear combination of \(\text{Top}_{\ell}\) norms; equivalently, we can describe this by a non-increasing weight vector \(w \ge 0\), which defines the ordered norm \(f(v):=\sum_{j=1}^n w_j v^\downarrow_j\) for \(v\geq 0\). The problems of minimizing the \(\text{Top}_{\ell}\)-norm and ordered-norm of the induced cost vector are referred to as the \(\ell\)-centrum and ordered \(k\)-median problems respectively in the clustering literature [1]–[5].

Furthermore, the class of monotone symmetric norms is closed under nonnegative linear combinations, and taking the maximum (over a finite collection of monotone symmetric norms). Also, for any monotone norm \(g\), \(f = g(v^\downarrow)\) and \(f = \mathbb{E}_\pi[g(\{v_{\pi(i)}\}_{i \in [n]})]\) (where \(\pi\) is a random permutation) are monotone symmetric norms. Thus, minimum-norm \(k\)-clustering is indeed a very versatile problem that can be used to model a wide range of applications.

An elegant algorithmic idea that has been applied to some \(k\)-clustering problems is adaptive sampling [6], [7] (see also [8]). In adaptive sampling, we randomly choose the location of the next center to open with probability proportional to the objective-function contribution of the point under the currently chosen set. The power of adaptive sampling lies in its simplicity; unlike other more complicated (and often linear-programming-based) algorithms, adaptive sampling is fast, and uses pairwise-distance information in a conservative manner. This makes adaptive-sampling-based algorithms well-suited for computing a preliminary set of centers in data-sparsification procedures (e.g. coreset construction [9], [10]), as well as other situations where pairwise-distance queries are expensive (e.g. [11]–[13]).

It is known that adaptive sampling can be used to obtain a bicriteria constant-factor approximation for the \(k\)-median and \(k\)-means clustering problems [7]; by this we mean, a solution that opens at most \(\alphak\) centers and has cost at most \(\beta\) times the optimum—denoted an \((\alpha,\beta)\)-approximate solution—where \(\alpha,\beta=O(1)\). For both these problems, as noted earlier, the objective is a min-sum objective, where we sum up the costs incurred by the individual clients. Consequently, sampling the next center to open with probability proportional to its current cost does indeed yield good solutions (with constant probability). While adaptive sampling, which is also called \(D^2\)-sampling in the context of the \(k\)-means objective, has been leveraged in various settings—e.g., for other objectives [7], [14], [15], constrained \(k\)-means problems [16]–[18], streaming settings [19], [20], models where other clustering information is available [21]—to our knowledge, with the exception of the very recent work [12], [13], all these applications of adaptive sampling have involved \(k\)-clustering with min-sum objectives, a milieu naturally suited for adaptive sampling.

Recently, [12], [13] extended the adaptive-sampling approach to obtain a bicriteria constant-factor approximation for the \(\ell\)-centrum problem (i.e., where the norm is a \(\text{Top}_{\ell}\) norm). A notable aspect of this result is that, unlike a min-sum objective, the \(\text{Top}_{\ell}\)-norm objective is not separable, i.e., we cannot quite isolate the contribution of a client to the objective, and consequently, it is not clear how to utilize the adaptive-sampling template here. Nevertheless, [12], [13] observed that one can sidestep this issue by moving to the min-sum (hence, separable) proxy function introduced by [1], which well-estimates the \(\text{Top}_{\ell}\)-norm. In this sense, \(\text{Top}_{\ell}\)-norms are only mildly non-separable, and by using adaptive sampling on this separable proxy function (i.e., sampling a client with probability proportional to its proxy-cost contribution), one can obtain an \(\bigl(O(1),O(1)\bigr)\)-approximate solution for \(\text{Top}_{\ell}\) norms [12], [13].

1.1 Our contributions↩︎

We design an adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm \(k\)-clustering. Given the generality of minimum-norm \(k\)-clustering, we thus obtain a fast, simple algorithm that is versatile and can be applied to a very wide range of \(k\)-clustering problems. The simplicity and efficiency of adaptive sampling also opens up the possibility of leveraging our ideas to handle minimum-norm \(k\)-clustering in the streaming setting (as has been done for \(k\)-means).

The only other polynomial-time guarantee known for minimum-norm \(k\)-clustering is a constant-factor approximation algorithm due to Chakrabarty and Swamy [1]. They obtain a “true” approximation, i.e., the solution returned opens (at most) \(k\) centers, but their algorithm is much more involved: it is based on solving a suitable LP-relaxation of the problem, which makes it less efficient than our adaptive-sampling algorithm. It is worth noting that by using our algorithm to sparsify the data, and then running the algorithm in [1], we can obtain a (true) \(O(1)\)-approximation algorithm with better running time that succeeds with constant probability; see Section 4.3.

We also show that for \(\text{Top}_{\ell}\) norms, which form a building block of monotone symmetric norms, adaptive sampling yields a (true) \(O(\log k)\)-approximation. Previously, such guarantees were known only for min-sum objectives when the underlying distance function \(d\) (determining the client assignment costs) satisfies the approximate triangle inequality \(d(p,q)\leq\rho\bigl(d(p,r)+d(r,q)\bigr)\) for all points \(p,q,r\), for some parameter \(\rho\) [6], [14], [15]. Notably, the proxy function that renders \(\text{Top}_{\ell}\)-norm as a min-sum objective does not satisfy this approximate triangle inequality for any finite \(\rho\), so we need to supplement the analysis in [6] with new ideas.

Technical overview.

Technically, the highly non-separable nature of general monotone, symmetric norms (for instance, the norm could be the maximum of any collection of monotone, symmetric norms) presents a significant challenge, and makes it much more challenging to deal with this general class of objectives as compared to \(\text{Top}_{\ell}\) norms. In particular, unlike the case of \(\text{Top}_{\ell}\)-norms, there is no simple proxy-cost function that one can switch to, that renders the minimum-norm problem separable. As mentioned above, having such a separable proxy function was key towards extending adaptive sampling to make it work for \(\text{Top}_{\ell}\)-norms in [12], [13]. However, without access to such a separable function for a general monotone, symmetric norm, we need to come up with new ideas. Indeed, this highly non-separable nature of general monotone, symmetric norms, which manifests itself in terms of the lack of a convenient separable proxy cost function, often presents an obstacle in extending results obtained for \(\text{Top}_{\ell}\)-norms to general monotone, symmetric norms, and for a variety of combinatorial-optimization problems (e.g., \(k\)-clustering, shortest path, matching), we have much less of an understanding of the minimum-norm variant of the problem compared to the \(\text{Top}_{\ell}\)-norm variant of the problem.¹

The way forward is to utilize majorization theory [23], which tells us that we can control the norm \(f(v)\) by controlling all \(\text{Top}_{\ell}\)-norms of \(v\). More precisely (see Theorem [thm:majorization]), to ensure that \(f(v)\leq O(1)\cdot f(o^*)\), where \(o^*\) is the cost-vector induced by an optimal solution, it suffices to ensure that \(\text{Top}_{\ell}(v)\leq O(1)\cdot\text{Top}_{\ell}(o^*)\) for all \(\ell\), or, in fact, (roughly speaking) geometrically increasing values of \(\ell\). Since we have an adaptive-sampling algorithm for \(\text{Top}_{\ell}\) norms [12], [13], this seems promising; however, the execution of this algorithm, in particular, the sampling process, (naturally) depends on the index \(\ell\), whereas we need to control the \(\text{Top}_{\ell}\)-norms for multiple values of \(\ell\) simultaneously. Also, note that simply running the \(\text{Top}_{\ell}\)-norm algorithm multiple times will not work, since we will end up opening far too many centers, \(O(k\log n)\).

Nonetheless, we are able to devise an adaptive-sampling algorithm (Algorithm [adsample-alg]) for this problem by exploiting some key insights from the analysis of the adaptive-sampling algorithm for \(\text{Top}_{\ell}\) norms in [12], [13]. The analysis therein (see Section 3.1) shows that the algorithm makes progress when it chooses a center in the “core” of a cluster induced by an optimal solution that is currently costly (Claim [coreisgood]), and that this event happens with constant probability as long as the current \(\text{Top}_{\ell}\)-cost is large (Lemma [choosecore]). While these cores differ for different values of \(\ell\), for any fixed cluster, they form a nested family: the cores get smaller as \(\ell\) increases (Claim [corenested]). This yields the following extremely-fruitful insight, which drives our algorithm: if at each step, we concentrate on the largest index \(\ell\) for which the current \(\text{Top}_{\ell}\)-cost is large, then with constant probability, the new center that we open will simultaneously make progress with respect to all costly \(\text{Top}_{\ell}\)-norms. Hence, using a standard martingale argument, we can show that after \(O(k)\) centers are opened, the \(\text{Top}_{\ell}\)-cost of our solution is bounded for all indices \(\ell\) (with constant probability), and this implies that we have an \(\bigl(O(1),O(1)\bigr)\)-approximate solution (Theorem [adsample-thm]).

1.2 Related literature↩︎

The \(\ell\)-centrum and its generalization, the ordered \(k\)-median problem, have been extensively studied in the Operations Research literature (see, e.g., [3], [24], [25] and the references within). The first \(O(\log n)\)-approximation algorithms for \(\ell\)-centrum and the ordered \(k\)-median problems were given by Tamir [2] and Aouad and Segev [3] respectively. Subsequently, Byrka et al. [4], and Chakrabarty and Swamy [5] gave the first constant-factor approximations for these two problems. Chakrabarty and Swamy [1] introduced the much-more general minimum-norm \(k\)-clustering problem, and used LP techniques to devise a \((408+\varepsilon)\)-approximation algorithm for the problem that opens exactly \(k\) centers. To the best of our knowledge, this the only polytime approximation result known for monotone symmetric norms. But there has been some work on parameterized approximation algorithms for even-more general norm-clustering problems [26].

In this paper, we study adaptive sampling algorithms for the minimum-norm \(k\)-clustering problem. Adaptive sampling (initially coined as \(D^2\) sampling in the context of the \(k\)-means problem), was introduced and studied by Arthur and Vassilvitskii [6]. Their adaptive sampling-based algorithm, k-means++, yields a solution of expected cost \(O(\log k) \cdot \mathit{OPT}\); this bound was later proved to be tight, even in two dimensions [27]. With some modifications to the original k-means++ algorithm, it is possible to obtain improved runtime and approximation guarantees. In particular, Bachem et al. [28] showed that one can obtain an \(O(\log k)\)-approx in sublinear time by replacing the exact \(D^2\)-sampling step with a (faster) approximation based on Markov Chain Monte Carlo sampling. Aggarwal, Deshpande, and Kannan [7] later proved that using the \(D^2\)-sampling protocol to open \(O(k)\) centers (instead of exactly \(k\) centers) yields a constant factor bicriteria approximation for \(k\)-means. Adaptive sampling has been used to give approximation algorithms for other variants of the \(k\)-means problem as well, including under the streaming model [19], [20], clustering with outliers [18], [29], other constrained \(k\)-means problems [16], [17], as also other objectives such as minimizing the sum of the \(p\)th-powers of distances [7], Bregman divergences [14], truncated costs [15], and \(\text{Top}_{\ell}\)-norms [12], [13]. As noted earlier, except for [12], [13], all these works consider min-sum, and hence, separable objectives, and [12], [13] also move to a min-sum proxy function that well-estimates the \(\text{Top}_{\ell}\) norm.

2 Preliminaries↩︎

Monotone, symmetric norms.

Recall that a function \(f : \mathbb{R}^n \to \mathbb{R}_+\) is a norm if it satisfies (i) \(f(x) = 0\) iff \(x = 0\); (ii) \(f(x + y) \leq f(x) + f(y)\) for all \(x, y \in \mathbb{R}^n\) (triangle inequality); and (iii) \(f(\lambda x) = |\lambda| f(x)\) for all \(x \in \mathbb{R}^n\), \(\lambda \in \mathbb{R}\) (homogeneity). If \(f\) is monotone, then \(f(x) \le f(y)\) for all \(0 \le x \le y\), and \(f\) is symmetric if permuting the coordinates of \(v\) does not change the value of \(f(v)\).

We collect here various properties of monotone, symmetric norms from prior work that we will utilize. For a vector \(v\in\mathbb{R}^n_+\), we use \(v^\downarrow\) to denote \(v\) with its coordinates sorted in non-increasing order. A special class of monotone symmetric norms which will be particularly useful are \(\text{Top}_{\ell}\) norms.

\(\text{Top}_{\ell}\)-norms can be difficult to work with because they are non-separable, i.e., it is unclear how to isolate the contribution from a single coordinate \(v_i\) towards \(f(v)\). But this difficulty can be somewhat mitigated by working with a separable proxy function—the expression on the RHS of Claim [csproxy] (a)—introduced by [1]. (This proxy function does not however satisfy the triangle inequality, which does cause other complications.) For \(z\in\mathbb{R}\), define \(z^+:=\max\{z, 0\}\).

An important property of \(\text{Top}_{\ell}\)-norms is that they serve as a handle for reasoning about arbitrary monotone symmetric norms. Indeed, a key insight that is useful when dealing with monotone symmetric norms, and leveraged by our algorithm as well, is that for any monotone symmetric norm \(f\), in order to control \(f(v)\), it suffices to control \(\text{Top}_{\ell}(v)\) for all \(\ell \in [n]\). In fact, it suffices to control only logarithmically-many \(\text{Top}_{\ell}\) norms (incurring a small loss in approximation quality).

We are using the definition of \(\mathsf{POS}_{n,\delta}\) in [30], which is slightly different from the definition in [1], as we will utilize certain results from [30]; but this difference is not crucial.

We will need to estimate \(\text{Top}_{\ell}(u)\) for \(\ell\in\mathsf{POS}_{n,\delta}\), given estimates of \(u^\downarrow_\ell\) for all \(\ell\in\mathsf{POS}_{n,\delta}\). We utilize the following result from [30], which we have slightly paraphrased. We say that a vector \(v\in\mathbb{R}_+^\mathsf{POS}\) is non-increasing if \(v_\ell\geq v_{\ell'}\) for indices \(\ell,\ell'\in\mathsf{POS}, \ell<\ell'\).

Complementing the above, we utilize the following result, which shows how we can find a suitable set \(\mathcal{T}\) containing good estimates of \(u^\downarrow_\ell\) for all \(\ell\in\mathsf{POS}_{n,\delta}\).

Minimum-norm \(k\)-clustering.

In \(k\)-clustering problems, we are given a set of centers \(\mathcal{F}\), \(n\) clients, \(\mathcal{C}\), a distance function \(d : (\mathcal{F}\cup \mathcal{C})^2 \to \mathbb{R}_{\ge 0}\), and must choose a set of \(k\) centers from \(\mathcal{F}\) to open. The assignment cost incurred by client \(j \in \mathcal{C}\) for a given set \(S \subseteq \mathcal{F}\), denoted \(d(j, S)\), is their distance to the closest center in \(S\). Thus, a set of open centers \(S\) induces a cost vector, denoted \(d(\mathcal{C}, S)\), where \(d(\mathcal{C}, S)_j = d(j, S)\) is the assignment cost incurred by client \(j\) under \(S\). We mostly consider the setting where \(\mathcal{F}= \mathcal{C}\), but in Section 4.2, we discuss how the general setting can be handled.In the minimum-norm \(k\) clustering problem, we seek to minimize \(f\bigl(d(\mathcal{C}, S)\bigr)\), where \(f\) is a given monotone, symmetric norm. A useful special case of this is when \(f\) is a \(\text{Top}_{\ell}\)-norm. Observe that this special case, which is sometimes called the \(\ell\)-centrum problem, captures both the \(k\)-center (\(\ell= 1\)) and \(k\)-median (\(\ell = n\)) problems.

Recall that, for \(k\)-median, the following adaptive-sampling process yields a constant-factor bicriteria approximation: pick a random point \(j\in\mathcal{C}\) to add to the current center-set \(S\) with probability proportional to \(d(j,S)\), and repeat this for \(O(k)\) iterations. It is worth pointing out that this algorithm, as stated, can fail badly even for \(k\)-center (i.e., \(1\)-centrum).

3 Adaptive sampling↩︎

We now present our adaptive-sampling algorithm for minimum-norm \(k\)-clustering. As suggested by Theorem [thm:majorization], our approach for controlling a general monotone, symmetric norm is by controlling all \(\text{Top}_{\ell}\) norms. So we first discuss adaptive sampling for \(\text{Top}_{\ell}\)-norms in Section 3.1. We then exploit insights gained from the analysis of adaptive sampling for \(\text{Top}_{\ell}\) norms to devise our adaptive-sampling algorithm for monotone, symmetric norms (Section 3.2).

3.1 \(\text{Top}_{\ell}\)-norms↩︎

We give an overview of the key ideas of the adaptive-sampling algorithm of [12] for \(\text{Top}_{\ell}\)-norms, which we build upon in Section 3.2. As noted previously, the \(\text{Top}_{\ell}\)-objective can be difficult to work with directly, due to its non-separable nature. Instead, [12] observed that, for suitably chosen parameters \(\beta, t_\ell\), one can work with the proxy function \(\sum_{j\in\mathcal{C}}(d(j,S)-\beta t_\ell)^+\) suggested by Claim [csproxy] (where \(S\) is the center-set), which is separable. We can now treat \((d(j, S) - \beta t_\ell)^+\) as the individual contribution of client \(j\) to the current cost of the solution, and so the next center to open is sampled with probability proportional to this proxy cost.

So the adaptive-sampling algorithm in [12] for \(\text{Top}_{\ell}\)-norms is simply the following: choose the first center uniformly at random from \(\mathcal{C}\), choose every subsequent center as discussed above, and continue this for \(O(k)\) centers. They showed that if \(t_\ell\) is good estimate of the \(\ell\)-th largest cost incurred by an optimal solution, then (for a suitably chosen \(\beta\)) this returns an \(O(1)\)-approximation with constant probability.

Analysis.

We include some components of the analysis in [13], which we need to modify slightly for our purposes. Throughout, \(S\) denotes the current (random) center-set. Fix an optimal solution \(O^*=\{o^*_1,\ldots,o^*_k\}\) for the \(\text{Top}_{\ell}\) \(k\)-clustering problem, and let \(C^*_1, \ldots,C^*_k\) denote the clusters induced by this solution, which we will often call the optimal clusters; that is, \(C^*_q\) is the set of clients assigned to center \(o^*_q\), for all \(q\in[k]\). Let \(\mathit{OPT}_\ell=\text{Top}_{\ell}\bigl(d(\mathcal{C},O^*)\bigr)\) denote the optimal \(\text{Top}_{\ell}\)-cost. Let \(\tau=35\), \(\rho=35\). It will be convenient to state the analysis in terms of certain parameters \(\alpha,\beta,\gamma\), whose values are chosen to satisfy the following:² \[\beta = \gamma= \alpha +1, \quad \rho\geq 2(\alpha+2\beta+3)+\gamma, \quad \Bigl(1-\tfrac{\gamma}{\rho}\Bigr)\cdot\tfrac{\alpha-1}{2\alpha(\alpha+\beta+3)}\geq\frac{1}{\tau}. \label{abkchoices}\tag{1}\] For instance, one can take \(\alpha=2\), \(\gamma=\beta=3\). At a given iteration of the algorithm, we classify an optimal cluster \(C^*_q\in\bigl\{C^*_1,\ldots,C^*_k\bigr\}\) as “good” or “bad”, depending on whether the clients in \(C^*_q\) incur a large proxy cost compared to what they incur under \(O^*\).

If all clusters are good, then the \(\text{Top}_{\ell}\)-cost of the current solution is \(O(\mathit{OPT}_\ell)\), assuming that \(t_\ell\) is a good estimate of \(t^*_\ell = d(\mathcal{C}, O^*)^\downarrow_\ell\).

On the other hand, if the \(\text{Top}_{\ell}\)-cost of our solution is large, then one can show that the next center added to the solution \(S\) lies in the “core” of some bad cluster \(C^*_q\), with some constant probability \(p\). Moreover, when a center is opened from the core of \(C^*_q\), that cluster becomes good (Claim [coreisgood]) and hence, remains good in all subsequent iterations. Definition 4 gives the precise definition of core, but informally, the core of a cluster \(C^*_q\) consists of points that are sufficiently close to its center \(o^*_q\).

Thus, in every iteration, we make progress towards obtaining a low-cost solution by reducing the number of bad clusters with probability \(p\). Hence, the expected number of bad clusters decreases with each iteration, and one can then use standard martingale arguments to show that after \((k+\sqrt{k})/p\) iterations, with some constant probability, we obtain a solution with no bad clusters, and therefore a near-optimal solution. We now discuss some details.

Define the radius of a cluster \(C^*_q\) to be \(r_\ell(C^*_q) := \frac{\sum_{j \in C^*_q} (d(j, o^*_q)-t_\ell)^+}{|C^*_q|}\).

By slightly reworking the arguments in [12] (to account for our definition of core), we have the following.

Lemma [choosecore] is the main result proved in [13], which underlies their proof that adaptive sampling works for \(\text{Top}_{\ell}\)-norms. This will also be key to extending adaptive sampling to monotone, symmetric norms in Section 3.2.

3.2 Arbitrary monotone symmetric norms↩︎

We now describe the adaptive-sampling algorithm for minimum-norm \(k\)-clustering. Recall that in this problem, we seek to minimize \(f\bigl(d(\mathcal{C}, S)\bigr)\), where \(d(\mathcal{C}, S)\) is the cost vector induced by opening \(S\), and \(f:\mathbb{R}^n\mapsto\mathbb{R}_+\) is an arbitrary monotone, symmetric norm. We will typically refer to \(f(d(\mathcal{C}, S))\) as the \(f\)-cost induced by \(S\). Let \(\mathsf{POS}=\mathsf{POS}_{n,\delta}\) (Definition 2).

Again, the objective function is non-separable in that we cannot isolate the contribution of a specific client to the \(f\)-cost in any convenient way. Furthermore, in contrast with \(\text{Top}_{\ell}\)-norms, we do not have a proxy-cost function that renders the problem separable. We therefore resort to Theorem [thm:controllAllL], which shows that in order to control the \(f\)-cost induced by our solution, it suffices to control the \(\text{Top}_{\ell}\)-cost of our solution with respect to all \(\ell \in \mathsf{POS}\).

A naive way of utilizing this observation is to simply run the adaptive-sampling algorithm for \(\text{Top}_{\ell}\)-norms from Section 3.1 for each \(\ell \in \mathsf{POS}\), and return the union of these solutions. However, this would open \(O(k|\mathsf{POS}|)=O(k\log n)\) centers, instead of the \(O(k)\) centers we seek in a \(\bigl(O(1),O(1)\bigr)\)-approximate solution. Also, this naive algorithm would achieve much more than what is required in that the resulting solution \(S\) would satisfy \(\text{Top}_{\ell}\bigl(d(\mathcal{C}, S)\bigr) \leq \rho (1 + \varepsilon) \mathit{OPT}_\ell\) for every \(\ell \in \mathsf{POS}\),³ where recall that \(\mathit{OPT}_\ell\) is the optimal \(\text{Top}_{\ell}\)-cost, which implies that it is a \(\rho(1+\varepsilon)\)-approximate solution for every monotone, symmetric norm \(h\) (by Theorem [thm:majorization]); this kind of universal approximation is a much stronger guarantee than we seek, and for such a strong guarantee one must end up opening \(O(k\log n)\) centers [31].

Since we only want the \(f\)-cost \(f\bigl(d(\mathcal{C},S)\bigr)\) of our solution to be \(O(1)\cdot\mathit{OPT}\), where \(\mathit{OPT}\) is the optimal \(f\)-cost, we only need that, for every \(\ell\in\mathsf{POS}\), \(\text{Top}_{\ell}\bigl(d(\mathcal{C},S)\bigr)\) is within a constant-factor of the \(\text{Top}_{\ell}\)-cost of a fixed solution, namely the optimal solution \(O^*\) to the minimum-norm problem. We design a sampling process that allows us to do so by capitalizing on some insights from the analysis of the adaptive-sampling algorithm for \(\text{Top}_{\ell}\)-norms presented in Section 3.1. From the analysis therein, we can infer that to ensure that \(\text{Top}_{\ell}\bigl(d(\mathcal{C},S)\bigr)=O(1)\cdot\text{Top}_{\ell}\bigl(d(\mathcal{C},O^*)\bigr)\) for all \(\ell\in\mathsf{POS}\), it suffices for \(S\) to hit the \(\ell\)-core of every cluster \(C^*_q\) induced by \(O^*\), for all \(\ell\in\mathsf{POS}\). Here, one extremely useful property comes in handy: for any fixed cluster \(C^*_q\), the \(\ell\)-cores for different indices \(\ell\) are nested (Claim [corenested]); this is precisely, why we define \(\mathop{\mathrm{core}}_{\ell}(C^*_q)\) slightly differently as compared to [13]. This implies that if we open a center from \(\mathop{\mathrm{core}}_{\ell}(C^*_q)\), then we have also hit \(\mathop{\mathrm{core}}_{\ell'}(C^*_q)\) for all indices \(\ell'\leq\ell\); so we have simultaneously turned \(C^*_q\) into an \(\ell'\)-good cluster (see Definition 3) for all \(\ell'\leq\ell\), and thereby made progress by bounding the proxy-cost of \(C^*_q\) for all these indices.

We can now finish things up with one additional observation: we only need to consider indices \(\ell\in\mathsf{POS}\) for which the current \(\text{Top}_{\ell}\)-cost is large. Formally, call an index \(\ell\) costly if \(\text{Top}_{\ell}\bigl(d(\mathcal{C},S)\bigr)>\rho(1+\varepsilon)\text{Top}_{\ell}\bigl(d(\mathcal{C},O^*)\bigr)\). (In the actual algorithm, we work with a suitable estimate of \(\text{Top}_{\ell}\bigl(d(\mathcal{C},O^*)\bigr)\).) Let \(\ell_{\max}\) be the largest costly index. Now suppose we run an iteration of the adaptive-sampling algorithm from Section 3.1 for index \(\ell_{\max}\), i.e., we open the next center at \(j\in\mathcal{C}\) with probability proportional to \((d(j,S)-3t_{\ell_{\max}})^+\). By Lemma [choosecore], we know that we will hit \(\mathop{\mathrm{core}}_{{\ell_{\max}}}(C^*_q)\) for some \(\ell_{\max}\)-bad cluster \(C^*_q\) with constant probability, which will imply that \(C^*_q\) becomes an \(\ell\)-good cluster for every costly index \(\ell\in\mathsf{POS}\). The upshot is that we have now “taken care of \(C^*_q\)” in the sense that for every index \(\ell\in\mathsf{POS}\), we know that the \(\text{Top}_{\ell}\)-proxy cost of clients in \(C^*_q\) is small, or the \(\text{Top}_{\ell}\)-cost of the entire solution is small. Therefore, by Lemma [choosecore], we obtain that with some constant probability \(p\), we “take care of” some cluster in each iteration, and one can utilize the same martingale argument to show that with constant probability, after \(O(k)\) iterations, there is no costly index; hence, \(f\bigl(d(\mathcal{C},S)\bigr)=O(1)\cdot\mathit{OPT}\) (assuming we have the right \(t_\ell\) values).

Analysis.

It will be convenient to assume via scaling that \(f(1,0,\ldots,0)=1\). For \(\ell\in[n]\), let \(t^*_\ell=d(\mathcal{C},O^*)^\downarrow_\ell\) be the \(\ell\)-th largest assignment cost incurred under the optimal solution \(O^*\). Our main result is as follows. We have not attempted to optimize constants here, but instead chosen simplicity of exposition (and some calculations).

Complementing this, Lemma [polyset] shows that one can compute in polytime a set \(\mathcal{T}\) containing a vector \(\vec{t}\) satisfying the conditions of Theorem [adsample-thm]. So if we run Algorithm [adsample-alg] for each vector in \(\mathcal{T}\) and return the best solution obtained, then this will be an \(\bigl(O(1),O(1)\bigr)\)-bicriteria solution for minimum-norm \(k\)-clustering with constant probability.

In Algorithm [adsample-alg], we use \(B_\ell:=\sum_{r=1}^\ell t_{\mathop{\mathrm{prev}}(r)}\) as an estimate of \(\text{Top}_{\ell}\bigl(d(\mathcal{C},O^*)\bigr)\). We begin by showing that this estimate is fairly accurate if \(\vec{t}\) satisfies the conditions of Theorem [adsample-thm].

Next, we show that the \(\ell\)-cores of a cluster are nested.

We conclude by showing that we can efficiently obtain a vector \(\vec{t}\) satisfying the conditions of Theorem 3.

4 Refinements and extensions↩︎

4.1 An \(O(\log k)\)-approximation for \(\text{Top}_{\ell}\) norms using \(k\) centers↩︎

We show that, for \(\text{Top}_{\ell}\) norms, if we stop the adaptive-sampling process after \(k\) iterations, then we obtain an (true) \(O(\log k)\)-approximation. Recall that such a guarantee was obtained by Arthur and Vassilvistskii ArthurV07? for \(k\)-means and \(k\)-median, where the latter is the special case of \(\text{Top}_{\ell}\) norm when \(\ell=n\). We consider the setting \(\mathcal{F}=\mathcal{C}\), but one can show that this guarantee also holds for the extension of adaptive sampling to the \(\mathcal{F}\neq\mathcal{C}\) setting discussed in Section 4.2.

We borrow heavily from the exposition in [33], which simplified somewhat the analysis in ArthurV07?. However, we encounter some significant difficulties due to the fact that the proxy cost function \(\sum_{j\in\mathcal{C}}\bigl(d(j,S)-\beta t_\ell\bigr)^+\) does not satisfy the traingle inequality, even in the approximate sense considered by [15].⁴

Recall that \(O^*=\{o^*_1,\ldots,o^*_k\}\) denotes some fixed optimal solution for the \(\text{Top}_{\ell}\) \(k\)-clustering problem, and \(C^*_1,\ldots,C^*_k\) are the corresponding optimal clusters, where \(C^*_q\) is the set of clients assigned to center \(o^*_q\), for all \(q\in[k]\). As in [33], ArthurV07?, we divide the optimal clusters \(C^*_1,\ldots,C^*_k\) into two categories, those that are hit by the current center-set \(S\) (i.e., \(S\cap C^*_q\neq\varnothing\)), and the un-hit clusters. The analysis for \(k\)-means comprises at a high level two main ingredients: (1) showing that the expected cost of the clusters that are hit is \(O(1)\) times the optimum, and (2) charging the expected cost of the un-hit clusters to the expected cost of the hit clusters. For \(\text{Top}_{\ell}\) norms, the second portion of the analysis (using the proxy cost) proceeds similarly, but the first part of the analysis becomes more involved, and we need to proceed differently to take into account the lack of triangle inequality.

Recall that adaptive sampling for \(\text{Top}_{\ell}\)-norms proceeds as follows. Let \(t_\ell\) be an estimate of \(t^*_\ell=d(\mathcal{C},O^*)^\downarrow_\ell\), the \(\ell\)-th largest cost incurred by an optimal solution. We add centers iteratively: let \(S_0:=\varnothing\), and \(S_i\) denote the center-set after \(i\) iterations. In the first iteration, we pick a point uniformly at random from \(\mathcal{C}\) to form \(S_1\); in each subsequent iteration \(i\), we sample \(s_i\in\mathcal{C}\) with probability proportional to \(\bigl(d(s_i,S_{i-1})-3t_\ell\bigr)^+\) and set \(S_i\leftarrowS_{i-1}\cup \{s_{i-1}\}\). We continue this for \(k\) iterations. We prove the following.

Analysis.

For sets \(C,S\subseteq\mathcal{C}\), and \(\theta\in\mathbb{R}_+\), define \(\mathit{cost}(C,S;\theta):=\sum_{j\in C}\bigl(d(j,S)-\theta\bigr)^+\); with \(\theta=\beta t_\ell\), this measures the total proxy cost of clients in \(C\) with respect to center-set \(S\). We abbreviate \(\mathit{cost}(\{j\},S;\theta)\) to \(\mathit{cost}(j,S;\theta)\), and \(\mathit{cost}(C,\{j\};\theta)\) to \(\mathit{cost}(C,j;\theta)\).

As in Section 3.1, it will be convenient to perform the analysis in terms of parameters \(\alpha,\beta,\kappa,\tau\), where \[\alpha=2, \quad\;\;\beta=3\geq\alpha+1, \quad \;\;\kappa=2\alpha+4, \quad\;\; \tau=\max\bigl\{\alpha+\kappa+2,\,2\bigl(1+\tfrac{\alpha(2\alpha+5)}{\alpha-1}\bigr)\bigr\}. \label{toplchoices}\tag{2}\]

Recall that the radius of a cluster \(C^*_q\) is \(r_\ell(C^*_q) := \frac{\mathit{cost}(C^*_q,o^*_q;t_\ell)}{|C^*_q|}\), and the \(\ell\)-core of \(C^*_q\) is \(\mathop{\mathrm{core}}_{\ell}(C^*_q):=\{j\in C^*_q: d(j, o^*_q) \leq \alpha(t_\ell + r_\ell(C^*_q))\}\). Define \(\mathsf{num}_q:=|C^*_q-\mathop{\mathrm{core}}_{\ell}(C^*_q)|\). Say that \(C^*_q\) is \(\ell\)-close with respect to the current center-set \(S\) if \(d(o^*_q,S)\leq\kappa\max\bigl\{r_\ell(C^*_q),t_\ell\bigr\}\); otherwise \(C^*_q\) is \(\ell\)-far.

For \(i=0,1,\ldots,k\), let \(H_i:=\{q\in[k]: S_i\cap C^*_q\neq\varnothing\}\), \(U_i:=[k]-H_i\), and \(W_i:=i-|H_i|\). While \(H_i\) and \(U_i\) track the clusters that are hit and not hit respectively in the first \(i\) iterations, \(W_i\) counts the “lost” or “wasted” iterations among the first \(i\) iterations, where the algorithm “lost out” on hitting a new cluster. Define \(\Lambda_i:=\sum_{q\in H_i}\mathit{cost}(C^*_q,S_i;\beta t_\ell)\), and \(\Psi_i:=W_i\cdot\frac{\sum_{q\in U_i}\mathit{cost}(C^*_q,S_i;\beta t_\ell)}{|U_i|}\). Note that all of the above quantities are random variables. Observe that \(\Lambda_0=0\) (since \(H_0=\varnothing\)) and \(\Psi_0=\Psi_1=0\) (since \(W_0=W_1=0\)), and \(\Lambda_k+\Psi_k=\mathit{cost}(\mathcal{C},S_k;\beta t_\ell)\), since \(W_k=|U_k|\).

We will prove that \({\textstyle{\mathop{\mathrm{\mathbb{E}}}}_{{}}}\bigl[\Lambda_i\bigr]\leq O(1)\cdot\bigl(\mathit{cost}(\mathcal{C},O^*;t_\ell)+\ell t_\ell\bigr)\) for all \(i\in[k]\) if \(t_\ell\geq t^*_\ell\) (Lemma 5), and \({\textstyle{\mathop{\mathrm{\mathbb{E}}}}_{{}}}\bigl[\Psi_{i}-\Psi_{i-1}\bigr]\leq\frac{{\textstyle{\mathop{\mathrm{\mathbb{E}}}}_{{}}}\bigl[\Lambda_{i-1}\bigr]}{k-i+1}\) for all \(i\in[k]\) (Lemma 6). It follows that \({\textstyle{\mathop{\mathrm{\mathbb{E}}}}_{{}}}\bigl[\Lambda_k+\Psi_k\bigr]\leq O(\log k)\cdot\bigl(\mathit{cost}(\mathcal{C},O^*;t_\ell)+\ell t_\ell\bigr)\). So if \(t_\ell\) is a good estimate of \(t^*_\ell\), we obtain that the expected cost of the solution returned is \(O(\log k)\cdot\mathit{OPT}\), proving Theorem [finbnd].

For the first iteration, the following claim will be useful.

The bound on \({\textstyle{\mathop{\mathrm{\mathbb{E}}}}_{{}}}\bigl[\Lambda_i\bigr]\) will follow from the following result.

The proof of Lemma [newhit] is somewhat technical and long, so we defer this to the end of the section to avoid detracting the reader.

Finally, we prove Lemma [newhit]. We restate the lemma for convenience.

4.2 The setting \(\mathcal{F}\ne \mathcal{C}\)↩︎

First, note that the adaptive-sampling algorithm and its analysis extend to the setting \(\mathcal{F}\supseteq\mathcal{C}\): we still sample a client in step [sample], and open a center at this client in step [fopen]. Given this, we can proceed in two ways. One standard idea that works for many \(k\)-clustering problems is to simply “move” each client to the center in \(\mathcal{F}\) closest to it. We then obtain an instance where the clients are located at some subset of \(\mathcal{F}\) (with possibly multiple co-located clients), so we can use the adaptive-sampling algorithm from Section [adsample]. This works because the loss in \(f\)-cost due to moving clients can be bounded in terms of \(\mathit{OPT}\).

For \(S\subseteq\mathcal{F}\), let \(d'(j,S)\) denote the assignment-cost of \(j\) under \(S\) for the new instance, i.e., when \(j\) has been moved from its original location to the center in \(\mathcal{F}\) closest to it. So we have \(|d'(j,S)-d(j,S)|\leq d(j,\mathcal{F})\). So if \(\mathit{OPT}'\) is the optimal \(f\)-cost for the new instance, we have \(\mathit{OPT}'\leq 2\cdot\mathit{OPT}\): if \(O^*\) is an optimum solution for the original problem, then we have \(d'(j,O^*)\leq d(j,O^*)+d(j,\mathcal{F})\) for every client \(j\), so \(f\bigl(d'(\mathcal{C},O^*)\bigr)\leq\mathit{OPT}+f\bigl(d(\mathcal{C},\mathcal{F})\bigr)\) and \(f\bigl(d(\mathcal{C},F)\bigr)\leq\mathit{OPT}\). Therefore, if \(S\subseteq\mathcal{F}\) is a \(\rho\)-approximate solution for the new instance, then we have \(d(j,S)\leq d(j,\mathcal{F})+d'(j,S)\), so we have \(f\bigl(d(\mathcal{C},S)\bigr)\leq f\bigl(d(\mathcal{C},\mathcal{F})\bigr)+\rho\cdot\mathit{OPT}'\leq(2\rho+1)\mathit{OPT}\).

A cleaner approach, which avoids a factor-\(2\) loss in approximation, is to directly modify adaptive sampling in the following simple fashion. In step [sample], we still sample a client \(s_i\in\mathcal{C}\) with probability proportional to \(\bigl(d(s_i,S_{i-1})-\beta t_{\ell_{\max}}\bigr)^+\) (for a suitable \(\beta\) value); but in step [fopen], we now add to \(S_i\) the center in \(\mathcal{F}\) closest to \(s_i\). This modification was made for \(\text{Top}_{\ell}\)-norms in [13], and, exactly as with the case \(\mathcal{F}=\mathcal{C}\), we can rely on their analysis to extend things to general monotone, symmetric norms. Suppose that \(\alpha,\beta,\gamma,\rho,\tau\) satisfy \[\beta = \gamma= 2\alpha +1, \quad \rho\geq 2(\alpha+2\beta+3)+\gamma, \quad \Bigl(1-\tfrac{\gamma}{\rho}\Bigr)\cdot\tfrac{\alpha-1}{2\alpha(\alpha+\beta+3)}\geq\frac{1}{\tau}. \label{genchoices}\tag{8}\] In particular, we can take \(\alpha=2\), \(\beta=\gamma=5\), \(\tau=\rho=45\). These inequalities imply the inequalities (5) in [13] (by taking \(\kappa=\alpha+\beta+3\)), which are used in [13] to analyze adaptive sampling for \(\text{Top}_{\ell}\)-norms when \(\mathcal{F}\neq\mathcal{C}\). With this choice of parameters, [13] show that almost the entire analysis of adaptive sampling for \(\text{Top}_{\ell}\)-norms in the setting \(\mathcal{F}=\mathcal{C}\) continues to hold. In particular, with the same definitions for \(\ell\)-good, \(\ell\)-bad clusters, and \(\ell\)-core (and \(\ell\)-supercore) of a cluster, Claim [allgood] and Lemma [choosecore] continue to hold. The only portion of the analysis that we need to modify is Claim [coreisgood] showing that if we sample a client from the \(\ell\)-core of a cluster then that cluster becomes \(\ell\)-good.

Given the above claim, we obtain the following guarantee for the \(\mathcal{F}\neq\mathcal{C}\) setting by the exact same arguments as in Section 3.2.

Complementing this with Lemma [polyset], we again obtain an \(\bigl(O(1),O(1)\bigr)\)-bicriteria algorithm for minimum-norm \(k\)-clustering when \(\mathcal{F}\neq\mathcal{C}\), by running the adaptive-sampling algorithm for each vector \(\vec{t}\) in the set \(\mathcal{T}\) output by Lemma [polyset], and returning the best solution found.

4.3 Faster \(O(1)\)-approximation by sparsifying data↩︎

We show that by using our algorithm in conjunction with the (true) \(O(1)\)-approximation algorithm for minimum-norm \(k\)-clustering in [1], referred to as \(\mathsf{CSAlg}\) from now on, we can obtain a faster \(O(1)\)-approximation algorithm. We note that this way of obtaining running-time savings was also outlined by [7] for the \(k\)-means problem.

We consider the \(\mathcal{F}=\mathcal{C}\) setting for simplicity (which is the setting also considered in [1]). Let \(\mathsf{POS}=\mathsf{POS}_{n,1}\), i.e., \(\mathsf{POS}\) consists of all powers of \(2\) up to \(n\) (possibly including \(n\)). Algorithm \(\mathsf{CSAlg}\) also requires knowing the right threshold vector \(\vec{t}\) satisfying the conditions in Theorem [adsample-thm]. As shown earlier, we can find a set \(\mathcal{T}\) containing such a vector (Lemma [polyset]). For an instance with \(n\) clients and a fixed \(\vec{t}\in\mathcal{T}\), \(\mathsf{CSAlg}\) solves an LP, which is the standard \(k\)-median LP (with \(O(n^2)\) variables and constraints) augmented with \(O(n)\) additional constraints,⁵ and rounds its optimal solution. To elaborate, \(\mathsf{CSAlg}\) considers the setting wherein the norm \(f\) is the maximum of a collection of ordered norms specifed in the input, and their LP has constraints bounding the (proxy) cost under each ordered norm in this collection. Given Theorem [thm:majorization], one can approximate \(f\) by specifying \(\text{Top}_{\ell}\)-norm budgets for all \(\ell\in\mathsf{POS}\) (obtained from a threshold vector \(\vec{t}\in\mathbb{R}_{\geq 0}^{\mathsf{POS}}\)), so this results in \(O(\log n)\) such constraints. In the sequel, we refer to this LP as the augmented \(k\)-median LP, which has \(O(n^2)\) variables and \(O(n^2)\) constraints. For a given \(\vec{t}\), the running time of \(\mathsf{CSAlg}\) is dominated by the time needed to solve this augmented \(k\)-median LP.⁶ Thus, the overall running time of \(\mathsf{CSAlg}\), is \(O\bigl(|\mathcal{T}|\cdot\mathsf{LPsolve}(n)\bigr)\), where \(\mathsf{LPsolve}\) is the time needed to solve their augmented \(k\)-median LP on an instance with \(n\) clients.

For the faster algorithm, we first use Algorithm [adsample-alg] to obtain an \((\alpha,\rho)\)-approximate solution \(S\), where \(\alpha,\rho=O(1)\), with constant probability. This involves running Algorithm [adsample-alg] for each \(\vec{t}\) in the set \(\mathcal{T}\), and returning the best solution found. A simple implementation of Algorithm [adsample-alg] takes \(O(nk)\) time, so we can find \(S\) in \(O(|\mathcal{T}|nk)\) time. Now, we consider the instance where we move each client to its closest center in \(S\), and are allowed to open centers only at locations in \(S\). We run \(\mathsf{CSAlg}\) on the resulting instance, which we call the sparsified instance where, by design, there are at most \(|S|\leq\alphak\) distinct client locations and we may have co-located clients. (While the algorithm in [1] is stated for the setting \(\mathcal{F}=\mathcal{C}\), it works as is for the setting \(\mathcal{F}\supseteq\mathcal{C}\) and opens centers at a subset of \(\mathcal{F}\).) Lemma [spapprox] shows that moving to the sparsified instance incurs only an \(O(1)\)-factor loss in approximation. Since \(|S|\leq\alphak\), running \(\mathsf{CSAlg}\) on the sparsified instance takes time \(O\bigl(|\mathcal{T}'|\cdot\mathsf{LPsolve}(\alphak)\bigr)\), where \(\mathcal{T}'\) is a set containing a suitable threshold vector for the sparsified instance (which still has \(n\) clients). So the total running time is \(O\bigl(|\mathcal{T}|nk+|\mathcal{T}'|\cdot\mathsf{LPsolve}(\alphak)\bigr)\). This is better than the earlier running time, since solving LPs takes super-quadratic time [34]), but note also that the time required to solve LPs now only affects the dependence of the runtime on \(k\).

Furthermore, we show in Lemma 8 that one can refine Lemma [polyset] so that, for an instance with \(n\) clients, one can identify a set of size \(O(n\log n)\) that contains a threshold vector \(\vec{t}\) such that: (a) running a slightly modified version of Algorithm [adsample-alg] with \(\vec{t}\) yields an \(\bigl(O(1),O(1)\bigr)\)-approximation; and (b) running \(\mathsf{CSAlg}\) with \(\vec{t}\) yields an \(O(1)\)-approximate solution. Thus, \(|\mathcal{T}|\) and \(|\mathcal{T}'|\) can be bounded by \(O(n\log n)\), so Lemmas 8 and [spapprox] show that this sparsify-and-solve approach yields an \(O(1)\)-approximation (with constant probability) in \(O\bigl(n\log n\cdot(nk+\mathsf{LPsolve}(O(k)))\bigr)\) time. In particular, for constant \(k\), the overall runtime is now roughly quadratic in \(n\). In contrast, even assuming (very generously) that we have a linear-time algorithm for (approximately) solving LPs, we would obtain \(\mathsf{LPsolve}(n)=O(n^2)\) (since the LP has \(n^2\) variables), and so running \(\mathsf{CSAlg}\) on the original instance would require \(\Omega(n^3\log n)\) time.

References↩︎