Towards Tight Robust Coresets for $k$-Medians Clustering

For a point $x\in M$ and a radius $r>0$, let $B(x,r)=\{y\in M\mid \mathrm{dist}(x,y)\le r\}$ denote the ball centered at $x$ with radius $r$. The ball range space of $(M,\mathrm{dist})$ is the collection of all balls, denoted by $\mathrm{Balls}=\{B(x,r)\mid x\in M,r>0\}$. For a $k$-point set $C\in \left(\genfrac{}{}{0pt}{}{M}{k}\right)$, let $B(C,r)={\bigcup }_{c\in C}B(c,r)$. The $k$-$\mathrm{Balls}$ range space of $M$ is denoted by ${\mathrm{Balls}}_k=\{B(C,r)\mid C\in \left(\genfrac{}{}{0pt}{}{M}{k}\right),r>0\}$.

A finite set $X\subset M$ is said to be shattered by $\mathrm{Balls}$ if $|X\cap \mathrm{Balls}|=2^{|X|}$, where $X\cap \mathrm{Balls}=\{X\cap B(x,r)\mid B(x,r)\in \mathrm{Balls}\}$. The VC dimension of $(M,\mathrm{dist})$ is the maximum size of a subset of $M$ that can be shattered by $\mathrm{Balls}$, or $+\mathrm{\infty }$ if no such maximum exists.

We say that a metric space $(M,\mathrm{dist})$ has doubling dimension at most $t$, if for any ball $B(x,r)$, there exists a set $C\in \left(\genfrac{}{}{0pt}{}{M}{q}\right)$ with $q\le 2^t$ so that the ball $B(x,r)\subseteq B(C,\frac{r}{2})$, i.e., any ball can be covered by at most $2^t$ balls of half radius.

For a dataset $X\subset M$, the vanilla $(k,z)$-Clustering problem aims to compute a $k$-center set $C\in \left(\genfrac{}{}{0pt}{}{M}{k}\right)$ that minimizes

This problem captures several variants, including vanilla $k$-Medians ($z=1$) and vanilla $k$-Means ($z=2$). A well-known variant, called $(k,z)$-Clustering with $m$ outliers, or the robust$(k,z)$-Clustering problem, is to find $C\in \left(\genfrac{}{}{0pt}{}{M}{k}\right)$ that minimizes

Namely, ${\mathrm{cost}}^{(m)}(X,C)$ aggregates all but the largest $m$ distances to $C$. Similar to the vanilla case, we call the problem robust $k$-median when $z=1$ and robust $k$-means when $z=2$.

Let $(Y,w_Y)$ be a weighted set where each point $y\in Y$ has a weight $w_Y(y)\ge 0$. We use $w(y)$ to denote $w_Y(y)$ if the weighted set is clear in the context. Moreover, for a weighted set $Y$, we denote by ${\parallel Y\parallel }_0$ the number of points in $Y$ and by ${\parallel Y\parallel }_1$ the total weight of $Y$. The $k$-median objective on $Y$ is defined as

Let $(Y,w_Y)$ and $(Z,w_Z)$ be two weighted sets. We call $Z$ a valid $m$-weighted outlier of $Y$ if (i) $Z\subseteq Y$, (ii) $w_Z(z)\le w_Y(z)$ for all $z\in Z$, and (iii) $w_Z(Z)=m$. Also denote by $Y\setminus Z$ the weighted set $(Y,w_Y-w_Z)$.

For a weighted set $(Y,w_Y)$, we use $L_Y^{(m)}$ to denote the set of all valid $m$-weighted outliers of $Y$. The robust $(k,z)$-clustering objective on $Y$ is defined as

This robust coreset preserves the clustering cost for every outlier budget $t\le m$ (rather than only for $t=m$), which yields the following mergeability property.

Given a real number $a\in ℝ$, we define $a^{+}=\max \{a,0\}$. We shall repeatedly use a basic fact about the maximum of Gaussian variables.

We begin by reviewing the techniques of [27], which obtains the first polynomial-sized robust coresets. Given a dataset, the authors first find a constant-factor approximation $C^{\ast }$ for robust $k$-Medians and explicitly add the $m$ outliers from this solution to the coreset. Then they apply the ring-decomposition framework of [6], which builds upon [11], to reduce the remaining data points (called inliers) to $\tilde{O}(k^2{\epsilon }^{-1})$ rings, where points in each ring are approximately equidistant from the center. A robust coreset is then constructed for each ring using uniform sampling, and the mergeability of robust coresets (Fact 5) implies a robust coreset for the whole dataset. Given a ring $X$ of radius $r$, the analysis of uniform sampling relies on the following integral representation of the cost function:

Suppose that $D$ is a uniform sample (reweighted by $\frac{|X|}{|D|}$) from $X$, one immediately obtains

Now, if the sample size on each ring is $\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$, it follows from the classical VC theory that ${\Vert D\setminus B(C,u)\Vert }_1$ approximates $|X\cap B(C,u)|$ up to an additive error $\epsilon \cdot |X|$ for every $C$ and $u$, i.e., $D$ is an $\epsilon$-range space approximation of $X$. Since $X$ is a ring of diameter $O(r)$, the integrand of (2) vanishes outside an interval of length $O(r)$ and, consequently, $D$ is an $(\epsilon ,r,\epsilon |X|r)$-robust coreset of $X$. Applying this to $\tilde{O}(k^2{\epsilon }^{-1})$ rings results in a robust coreset of size $m+\tilde{O}(k^2{\epsilon }^{-1}\cdot k{d}_{\mathrm{VC}}{\epsilon }^{-2})=m+\tilde{O}(k^3{d}_{\mathrm{VC}}{\epsilon }^{-3})$, as concluded in [27]. A subsequent work [29] essentially reduces the number of “effective rings” to $\tilde{O}(k)$ by adaptively selecting the sample size for each ring, achieving a smaller coreset size of $m+\tilde{O}(k^2{d}_{\mathrm{VC}}{\epsilon }^{-2})$.

Our goal is to further reduce the coreset size to $m+Q(\epsilon )$, where $Q(\epsilon )$ denotes the size of a vanilla $\epsilon$-coreset. The state-of-the-art result is $Q(\epsilon )=\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$ [14], improving on [27] by a factor of $k$. This improvement is achieved by grouping the rings into $\mathrm{poly}\log (k/\epsilon )$ collections, each containing at most $k$ rings, and performing uniform sampling at the group level rather than for individual rings. A straightforward idea would be to apply the vanilla coreset construction directly to the union of all rings, i.e. the set of all inliers. However, this fails to guarantee a robust coreset, since points within the rings can become outliers with respect to center sets different from $C^{\ast }$. Therefore, new technical ideas are required.

A natural strategy is to leverage the core principle of vanilla coreset construction: perform uniform sampling across multiple rings and analyse the total error collectively, rather than summing the errors from individual rings. However, a key obstacle is that the error induced by outliers depends on the chosen center set and can vary by orders of magnitude across different rings, making it difficult to control the total error uniformly over the entire space of center sets. Addressing this motivates the key definition of an $(r,k)$-instance (see Definition 7), which is essentially a set of points that can be covered by $k$ balls of equal radius $r$ (i.e. contained in $B(A,r)$ for some $k$-point set $A$). The idea of grouping rings has been instrumental in recent advances towards constructing near-optimal vanilla coresets [18, 16, 15, 30, 14]. These approaches typically group rings of varying radii from different clusters, whereas in our $(r,k)$-instance, all rings must have a uniform radius $r$. While such uniformity is unnecessary for vanilla coreset constructions, it is crucial for robust coresets, as it ensures “comparable” outlier-induced errors across rings within the same group.

Now we provide a high-level overview of our algorithm, which decomposes the input dataset $X$ into a collection of $(r,k)$-instances (see Lemma 13 and Figure 5 for illustration). First, we add $m+{\epsilon }^{-1}$ points farthest from $C^{\ast }$ to the coreset. Adding these additional ${\epsilon }^{-1}$ points guarantees that all remaining points in $X$ are within a distance of $\epsilon \cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$ from $C^{\ast }$. Then we collect all points within distance $r_{\mathrm{in}}:=\frac{\epsilon }{mk}\cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$ from $C^{\ast }$, forming an $(r_{\mathrm{in}},k)$-instance. Now, all remaining points have distances to $C^{\ast }$ within the interval $[r_{\mathrm{in}},mk{r}_{\mathrm{in}}]$, allowing them to be decomposed into $\log (mk)$ layers of $(r,k)$-instances with geometrically increasing radii $r$. We then construct a robust coreset for each of these $(r,k)$-instances (with carefully chosen error guarantees) and merge them into a final robust coreset of $X$ using Fact 5. The main technical challenge is to construct robust coresets of size $\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$ for these $(r,k)$-instances, i.e., the layers and the inner instance; we illustrate the key ideas for each scenario below.

Consider a layer of $(r,k)$-instance $X=X_1\cup \mathrm{\cdots }\cup X_k\subset B(A,r)$, where each $X_i\subset B(a_i,r)$ for some $a_i\in A$. We develop Algorithm 1 to construct an $(\epsilon ,m,\epsilon |X|r)$-robust coreset for $X$; roughly speaking, we take $\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$ uniform samples from $X$ (Theorem 9). Without loss of generality, assume that all $X_i$ have equal cost $\mathrm{cost}(X_i,a_i)$. This type of instance is also referred to as an $(r,k)$-regular instance (Definition 4); we show in Lemma 10 how to remove this assumption and in Figure 2 for illustration.

A natural idea is to extend the single-ring analysis (shown in (2)) to an $(r,k)$-instance. With $\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$ points in $D$, we can still guarantee that $\left|{\Vert D\setminus B(C,u)\Vert }_1-|X\setminus B(C,u)|\right|\le \epsilon |X|$ for every $C$ and $u$. However, applying this bound directly would yield an additive error of $\epsilon k|X|r$ (arising from integrating over $k$ intervals of length $O(r)$, one for each of $k$ clusters), which is a $k$-factor larger than our target error of $\epsilon |X|r$. Hence, additional technical insights are needed for a tighter control of the error.

The first idea is to borrow insights from the vanilla coreset construction, where the chaining argument is central. An essential step there is bounding the net size by $\exp (\tilde{O}(k))$, which counts the number of distinct distance vectors ${\left(\mathrm{dist}(x,C)\right)}_{x\in D}$ for all possible choices of $C$, under a certain level of discretization. In the robust setting, however, a small perturbation to $C$ can drastically change the set of outliers and thus the distance vectors. A natural idea is to fix the set of outliers, which then requires taking a union bound over all $\left(\genfrac{}{}{0pt}{}{|X|}{m}\right)$ possible sets of $m$ outliers, causing an additional $\exp (m)$ factor in the net size. This results in a net size far exceeding the desired $\exp (\tilde{O}(k))$, which will blow up the error bound we aim to control.

To address this issue, we apply the chaining argument exclusively to those clusters whose points are all inliers with respect to $C$. Specifically, we partition both $X$ and $D$ into the same three collections of clusters with respect to $C$: $A_1$ (clusters of inliers), $A_2$ (clusters of outliers), and $A_3$ (clusters whose distances to $C$ lie within an interval of length $O(r)$). Such a decomposition is possible because every cluster in an $(r,k)$-instance has the same radius, and an additional realignment procedure (Lines 4–6 in Algorithm 1) ensures that each cluster $X_i$ has a total sample weight of $|X_i|$. Notably, the realignment procedure ensures that the sample set $D$ has the same partition as $X$, a property absent in vanilla coreset constructions. We then apply the chaining argument solely to $A_1$, obtaining an indexed-subset cost approximation that bounds the error introduced by $A_1$ . Since $A_1$ is a union of clusters and there are at most $2^k$ such unions, the net size only increases by a factor of $\exp (k)$, which remains manageable .

Since $A_2$ contains only outliers, we may safely ignore it. It remains to control the error contributed by $A_3$. Since the distances of all points in $A_3$ from $C$ lie within an interval of length $O(r)$, we anticipate extending the single-ring analysis in (2) to $A_3$ and obtaining an additive error of $O(\epsilon |X|r)$ . A key challenge is that $A_3$ varies with the choice of $C$, increasing the number of relevant ranges to consider. To mitigate this, we extend the notion of range space approximation to encompass all $2^k$ possible sets of $A_3$ . While this extension increases the number of ranges by a factor of $2^k$, we can safely ignore this factor because the original number of ranges is already on the order of $2^{k{d}_{\mathrm{VC}}}$. Consequently, the range space approximation guarantee of the sample set $D$ remains valid, meaning $D$ induces at most an $\epsilon |X|$ error for each of these ranges. Now, the integral in (2) is effectively over the distance interval for $A_3$, which has length $O(r)$, and the overall error for $A_3$ is thus within $\epsilon |X|\cdot O(r)$ .

Consider the inner $(r_{\mathrm{in}},k)$-instance $X=X_1\cup \mathrm{\cdots }\cup X_k$, where each $X_i\subseteq B(a_i,r_{\mathrm{in}})$. We shall construct an $(\epsilon ,m,mk{r}_{\mathrm{in}})$-robust coreset for $X$ , where the additive error is at most $mk{r}_{\mathrm{in}}\le \epsilon \cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$, which is acceptable.

We propose Algorithm 2 to achieve this goal. For each $X_i$, we first select an arbitrary subset $H_i\subseteq X_i$ of $m$ points and move these points to the center $a_i$. The coreset then consists of two components: a weighted point $(a_i,|H_i|)$ to represent the collection $H_i$, and a vanilla coreset of the remaining points $X\setminus \left({\bigcup }_{i\in [k]}{H}_i\right)$. See also Figure 3 for illustration. The algorithm’s correctness follows from the fact that the total moving distance between $X$ and $D$ is at most $mk{r}_{\mathrm{in}}$, which ensures the same level of additive error.

Interestingly, this robust coreset construction for the inner $(r_{\mathrm{in}},k)$-instance also leads to another coreset of size $O(km{\epsilon }^{-1})+\tilde{O}(k{d}_{\mathrm{VC}}{\epsilon }^{-2})$ for the full dataset (rather than just for the inner instance). The algorithm maintains this robust coreset $D$ along with all points outside the inner $(r_{\mathrm{in}},k)$-instance. Since each outside point $x$ satisfies $\mathrm{dist}(x,C^{\ast })\ge r_{\mathrm{in}}=\frac{\epsilon }{mk}\cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$, there can be at most $km{\epsilon }^{-1}$ such points, yielding the stated coreset size. We note that this matches the size obtained in a recent paper [33], although we use different reductions to the vanilla setting. Unlike our requirement that each ball in the inner $(r_{\mathrm{in}},k)$-instance has a small radius, their approach requires every ball to be dense, containing at least $m{\epsilon }^{-1}$ points.

This concludes our proof overview for the VC case. A structural diagram is shown in Figure 1.

The analysis for the doubling metric in Theorem 2 is almost identical to that for the VC case. We employ the same point set decomposition into $(r,k)$-instances (Lemma 13) and the same algorithms (Algorithms 1 and 2) for constructing robust coresets, with the only difference being the substitution of $d_D$ for $d_{\mathrm{VC}}$ in the coreset size. The key difference is that, in a doubling space, the VC dimension of the set of balls can be unbounded [26], preventing a direct application of the same range space argument used in the VC case. To overcome this, we adopt the technique from [26], which shows that by (randomly) distorting the distance function $\mathrm{dist}$ slightly , one can bound a “probabilistic” version of the VC dimension by $\tilde{O}(d_D)$ . This property enables a distorted variant of the range space argument , and we further show that the resulting error for $A_3$ under this distortion remains well-controlled (Lemma .

As discussed above, our algorithm for the inner $(r_{\mathrm{in}},k)$-instance (Algorithm 2) also produces a Euclidean coreset of size $O(km{\epsilon }^{-1})+Q(\epsilon )$, where $Q(\epsilon )$ now denotes the size of the vanilla $\epsilon$-coreset in Euclidean space. Note that the total number of moved points in Algorithm 2 is $mk$, while the number of outliers is only $m$, wasting a $k$ factor. This observation motivates Algorithm 3, which further reduces the Euclidean coreset size to $O(m{\epsilon }^{-1})+Q(\epsilon )$. The key idea is to increase the radius threshold $r_{\mathrm{in}}$ from $\frac{\epsilon }{mk}\cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$ to $\frac{\epsilon }{m}\cdot {\mathrm{cost}}^{(m)}(X,C^{\ast })$. See Figure 6 for illustration.

In the analysis of this algorithm, a major challenge arises when the inner $(r_{\mathrm{in}},k)$-instance contains points that are outliers with respect to some center set $C$. As noted earlier, a naïve adaptation of the vanilla chaining argument can blow up the net size by a factor of $\exp (m)$. To address this, we propose a novel decomposition of the robust clustering cost by strategically reassigning outliers across clusters, ensuring that only one cluster contains both inliers and outliers, while all other clusters contain exclusively inliers or exclusively outliers . This decomposition relies on the uniform radius assumption, which guarantees that moving each outlier introduces only a small additive error $O(r_{\mathrm{in}})$ to the overall clustering cost. Consequently, the net size in the chaining argument grows by at most a factor of $2^k$, which remains manageable as before.