A Tight VC-Dimension Analysis of Clustering Coresets with Applications

We consider coresets for k-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the k-median objective p minc∈C dist(p, C). Given a point set P , a coreset Ω is a small weighted subset that approximates the cost of P for all candidate solutions C up to a (1 ± ε) multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved k-median coreset bounds for the following metrics:

• Coresets of size Õ kε -2 for shortest path metrics in planar graphs, improving over the bounds Õ kε -6 by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and Õ k 2 ε -4 by [Braverman, Jiang, Krauthgamer, Wu, SODA'21].

• Coresets of size Õ kdℓε -2 log m for clustering d-dimensional polygonal curves of length at most m with curves of length at most ℓ with respect to Frechet metrics, improving over the bounds Õ k 3 dℓε -3 log m by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and

We note that unlike for k-median, these bounds are not known to be tight for specific metrics. For example, finite n-point metrics admit coresets of size Õ(k • log n • ε -2 ) for k-means, which is optimal [18,21], whereas the VC-dimension derived bound only yields a coreset of size Õ(k • log n • ε -3 ). Nevertheless, for the aforementioned clustering objectives such as shortest path metrics in planar graphs and the Frechet distance, this still yields improvements over the state of the art. In an earlier version of this paper, we claimed an improved bound of Õ k • d VC • (ε -2 + ε -z ) , which turned out to be false. We believe that the bounds in Theorem 1.2 are optimal in the sense that there exist metrics and ranges of ε and k for which the stated bound cannot be improved by any coreset construction. A discussion is given at the end of this paper.

Coresets via Uniform Sampling. We give explicit bounds of various papers studying coresets with bounded VC dimension in Table 1.

Reference Size (Number of Points) Feldman, Langberg (STOC'11) [28] Õ(k 3 • d VC,w • ε -2 ) Munteanu, Schwiegelshohn, Sohler, and Woodruff (NeurIPS'18) [44] O