A Tight VC-Dimension Analysis of Clustering Coresets with Applications
Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn · 2025
Read A Tight VC-Dimension Analysis of Clustering Coresets with Applications by Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-06588.txt.
Introduction
Vincent Cohen-Addad and four co-authors sharpen the math behind data summarization in a 2025 paper. A coreset is a small weighted sample that stands in for a huge point set in clustering tasks. It promises nearly the same cost for every possible choice of centers, so algorithms can run on the sample instead of the full data.
The authors give a tight analysis based on VC-dimension, a measure of a problem's complexity. Their bounds shrink coresets for k-median clustering in planar road-like networks by large factors over earlier work. They also improve bounds for clustering curves under the Fréchet distance. The results matter wherever clustering must scale to very large inputs.
Catalog record
| CREATOR | Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 115 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-06588
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Tight VC-Dimension Analysis of Clustering Coresets with Applications Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn Abstract We consider coresets for k k -clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the k k -median objective ∑ p min c ∈ C d i s t ( p , C ) \sum_{p}\min_{c\in C}dist(p,C) . Given a point set P P , a coreset Ω \Omega is a small weighted subset that approximates the cost of P P for all candidate solutions C C up to a ( 1 ± ε ) (1\pm\varepsilon) multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved k k -median coreset bounds for the following metrics: • Coresets of size O ~ ( k ε − 2 ) \tilde{O}\left(k\varepsilon^{-2}\right) for shortest path metrics in planar graphs, improving over the bounds O ~ ( k ε − 6 ) \tilde{O}\left(k\varepsilon^{-6}\right) by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC’21] and O ~ ( k 2 ε − 4 ) \tilde{O}\left(k^{2}\varepsilon^{-4}\right) by [Braverman, Jiang, Krauthgamer, Wu, SODA’21]. • Coresets of size O ~ ( k d ℓ ε − 2 log m ) \tilde{O}\left(kd\ell\varepsilon^{-2}\log m\right) for clustering d d -dimensional polygonal curves of length at most m m with curves of length at most ℓ \ell with respect to Frechet metrics, improving over the bounds O ~ ( k 3 d ℓ ε − 3 log m ) \tilde{O}\left(k^{3}d\ell\varepsilon^{-3}\log m\right) by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS’22] and O ~ ( k 2 d ℓ ε − 2 log m log | P | ) \tilde{O}\left(k^{2}d\ell\varepsilon^{-2}\log m\log|P|\right) by [Conradi, Kolbe, Psarros, Rohde, SoCG’24]. 1 Introduction Coresets are a staple of both learning theory and big data algorithms. Given a set of points P and a set of queries \mathcal{Q} along with an associated loss function f:P\times\mathcal{Q}\rightarrow\mathbb{R}_{\geq 0} , a coreset of P is a (typically weighted) subset \Omega of P with the property that f(\Omega,Q)\approx f(P,Q) for all Q\in\mathcal{Q} . Coresets have found numerous applications since their introduction in the early 2000s. One typical use case consists of clustering problems, such as k -median. Given a set P of n (possibly weighted) points in a metric space, the (k,z) -clustering objective asks to find a set \mathcal{S} of k center points so as to minimize the sum of the distances raised to the z th power from each point in P to its closest representative: f(P,\mathcal{S})=\textmd{{cost}}(P,\mathcal{S}):=\sum_{p\in P}w_{p}\cdot\min_{c\in\mathcal{S}}\textup{dist}^{z}(p,c), where w_{p} denotes a non-negative weight and dist denotes the distance function associated with the underlying metric. The for us most important example is the k -median objective, where z=1 . In this case, we aim to find a coreset \Omega such that for all candidate solutions S , i.e., set of k centers (1-\varepsilon)\cdot\textmd{{cost}}(P,\mathcal{S})\leq\textmd{{cost}}(\Omega,\mathcal{S})\leq(1+\varepsilon)\cdot\textmd{{cost}}(P,\mathcal{S}). For many important metric spaces, including Euclidean spaces, doubling metrics, and finite metrics, the question of obtaining optimal coreset sizes has been effectively settled. The state of the art coreset sizes are \tilde{O}(k\varepsilon^{-2}\cdot\min(\sqrt[3]{k},\varepsilon^{-1},d)) [ 5 , 20 , 39 ] for d -dimensional Euclidean spaces, \tilde{O}(kD\varepsilon^{-2}) [ 18 , 39 ] for doubling spaces with doubling constant D , and \tilde{O}(k\varepsilon^{-2}\log n) for finite n point metrics [ 18 , 21 ] , all of which are tight up to logarithmic factors in k or \varepsilon . 1 1 1 We use \tilde{O}(x) to suppress \text{polylog}(x) factors. In recent years, newfound insights from learning theory towards constructing good, unbiased estimators for these cost functions have fueled research on coresets. To prove that an unbiased estimator yields a coreset, the analysis has to (i) show that the variance of the estimator is small enough so as to allow to (ii) take a union bound over all solutions. The variance bounds for various estimators are independent of the underlying metric space and are at this stage of coreset research very well understood. Our ability to find small enumerators of the solution space, which are often referred to as nets is still an open problem for numerous metrics. One of the most important complexity measures for designing nets in learning theory is the VC dimension. For clustering, the VC dimension determines the maximum number of dichotomies that we can induce by placing a center c with some flexible radius r and labeling the points with distance at least r to c by 1 and the points with distance less than r to c by 0 . Specifically, the size d_{\textmd{{VC}}} of the largest set P\subseteq X for which we can generate all possible dichotomies is the VC dimension. The first sampling-based coreset results heavily relied on nets derived by way of the VC-dimension [ 15 , 40 , 28 , 30 , 36 ] . Indeed, to this day, there exist several metrics for which the VC dimension is the only known technique towards constructing coresets. Examples include shortest path metrics in minor free graphs [ 10 , 11 ] and Frechet and Hausdorff metrics [ 11 , 13 , 24 ] . Perhaps surprisingly due to its well studied nature in the field of coresets, our ability to construct coresets via the VC dimension is not fully understood. Most constructions reduce the problem to some variant of uniform sampling in cases where we only have bounds for the unweighted VC dimension (see for example [ 8 ] for shortest path metrics in planar graphs and [ 26 ] for Frechet metrics). Unfortunately, these reductions [ 15 , 8 ] always incur a loss in parameters because they require reducing the instance to a setting where uniform sampling becomes viable. Alternative methods for non-uniform sampling [ 44 , 30 ] likewise incur a loss in parameters. In particular, all constructions have at least a quadratic dependency in the, arguably most important, parameter k . This comes in addition to extra dependencies on other parameters, which vary based on the construction method used. 1.1 Our Results Motivated by the current state of the art, we aim towards obtaining a sharp VC-dimension-based analysis of sampling based coresets. Given a point set P in some metric space (X,\textup{dist}) , we let R(c,r):=\{p\in P\mid\textup{dist}(p,c)\geq r\} . Then we call \mathcal{R}=\cup_{c,r}R(c,r) the range space induced by metric balls. The VC dimension of \mathcal{R} is the size of the largest subset Y of X such that the power set of Y is contained in \mathcal{R} . Theorem 1.1 . Let P be a point set in some metric space (X,\textup{dist}) and let d_{\textmd{{VC}}} be the VC dimension of metric balls. Then there exists an \varepsilon -coreset for k -median of size \tilde{O}\left(k\cdot d_{\textmd{{VC}}}\cdot\varepsilon^{-2}\right). This achieves the first VC-dimension-based coreset bound with a k\cdot\text{polylog}(k) dependency, which is optimal up to polylog factors. We also note that the analysis is tight with respect to the other parameters, again up to polylog factors, in the sense that there exist metric spaces for which the stated bound cannot be improved by any coreset