Towards Optimal Coreset Construction for $(k,z)$-Clustering: Breaking the Quadratic Dependency on $k$

Constructing small-sized coresets for various clustering problems has attracted significant attention recently. We provide efficient coreset construction algorithms for $(k, z)$-Clustering with improved coreset sizes in several metric spaces. In particular, we provide an $\tilde{O}_z(k^{(2z+2)/(z+2)}\varepsilon^{-2})$-sized coreset for $(k, z)$-Clustering for all $z\geq 1$ in Euclidean space, improving upon the best known $\tilde{O}_z(k^2\varepsilon^{-2})$ size upper bound [Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC'22], breaking the quadratic dependency on $k$ for the first time (when $k\leq \varepsilon^{-1}$). For example, our coreset size for Euclidean $k$-Median is $\tilde{O}(k^{4/3} \varepsilon^{-2})$, improving the best known result $\tilde{O}(\min\left\{k^2\varepsilon^{-2}, k\varepsilon^{-3}\right\})$ by a factor $k^{2/3}$ when $k\leq \varepsilon^{-1}$; for Euclidean $k$-Means, our coreset size is $\tilde{O}(k^{3/2} \varepsilon^{-2})$, improving the best known result $\tilde{O}(\min\left\{k^2\varepsilon^{-2}, k\varepsilon^{-4}\right\})$ by a factor $k^{1/2}$ when $k\leq \varepsilon^{-2}$. We also obtain optimal or improved coreset sizes for general metric space, metric space with bounded doubling dimension, and shortest path metric when the underlying graph has bounded treewidth, for all $z\geq 1$. Our algorithm largely follows the framework developed by Cohen-Addad et al. with some minor but useful changes. Our technical contribution mainly lies in the analysis. An important improvement in our analysis is a new notion of $\alpha$-covering of distance vectors with a novel error metric, which allows us to provide a tighter variance bound. Another useful technical ingredient is terminal embedding with additive errors, for bounding the covering number in the Euclidean case.