On Optimal Coreset Construction for Euclidean (k, z)-Clustering

Constructing small-sized coresets for various clustering problems in different metric spaces has attracted significant attention for the past decade. A central problem in the coreset literature is to understand what is the best possible coreset size for (k,z)-clustering in Euclidean space. While there has been significant progress in the problem, there is still a gap between the state-of-the-art upper and lower bounds. For instance, the best known upper bound for k-means (z=2) is minO(k3/2 ε−2),O(k ε−4) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22], while the best known lower bound is Ω(kε−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22]. In this paper, we make significant progress on both upper and lower bounds. For a large range of parameters (i.e., ε, k), we have a complete understanding of the optimal coreset size. In particular, we obtain the following results: (1) We present a new coreset lower bound Ω(k ε−z−2) for Euclidean (k,z)-clustering when ε ≥ Ω(k−1/(z+2)). In view of the prior upper bound Õz(k ε−z−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22], the bound is optimal. The new lower bound is surprising since Ω(kε−2) [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] is “conjectured” to be the correct bound in some recent works (see e.g., [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22; Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22]). Our new lower bound instance is a delicate construction with multiple clusters of points, which is a significant departure from the previous construction in [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] that contains a single cluster of points. The new lower bound also implies improved lower bounds for (k,z)-clustering in doubling metrics. (2) For the upper bound, we provide efficient coreset construction algorithms for (k,z)-clustering with improved or optimal coreset sizes in several metric spaces. In particular, we provide an Õz(k2z+2/z+2 ε−2)-sized coreset, with a unfied analysis, for (k,z)-clustering for all z≥ 1 in Euclidean space. This upper bound improves upon the Õz(k2ε−2) upper bound by [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC’22] (when k≤ ε−1), and matches the recent independent results [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS’22] for k-median and k-means (z=1,2) and extends them to all z≥ 1.