Abstract
Coresets are a powerful tool for scaling clustering algorithms by summarizing large datasets into small, weighted subsets that preserve the cost of clustering within a $(1 \pm \epsilon)$ factor. Despite decades of research into dimension-independent coreset bounds, the optimal size for low-dimensional Euclidean spaces remained an open question. This paper provides the first tight characterization of coreset sizes for $k$-Median clustering in small dimensions. The authors demonstrate a significant "strong separation" in one dimension: while $k=1$ requires only $\tilde{O}(\epsilon^{-1/2})$ points, $k \ge 2$ necessitates $\Omega(\epsilon^{-1})$ points. Furthermore, they establish improved bounds for small $d > 1$, bridging the gap between low-dimensional and high-dimensional regimes.
Introduction
In the era of big data, coresets serve as a "cheat code" for computational efficiency. By reducing a massive dataset to a tiny, weighted version, researchers can run complex algorithms like $k$-Median clustering on a few thousand points instead of billions, while maintaining mathematical guarantees. While high-dimensional coreset bounds have been extensively studied, the tightest possible sizes for small dimensions—even for 1D data—were surprisingly unknown until now.
The Complexity of Low Dimensions
Existing literature has largely focused on dimension-independent bounds, which are robust but often overkill for real-world spatial data (e.g., GPS coordinates or spectral embeddings) that reside in very low dimensions ($d=1, 2, \text{ or } 3$). Prior to this work, even the simplest 1D case exhibited a massive gap between known upper and lower bounds. The goal of an $\epsilon$-coreset for $k$-Median clustering is to find a small set of points $S$ such that for any possible set of $k$ centers, the clustering cost calculated on $S$ is within a $(1 \pm \epsilon)$ factor of the cost calculated on the original full dataset $P$.
Methodological Innovations
The authors employ three primary strategies to close these theoretical gaps:
- Adaptive Bucket Partitioning: For 1D data, they refined the bucket-partitioning framework by using an adaptive approach that allocates error budgets based on a block's contribution to the total clustering cost. This allows the algorithm to focus points where the cost function is most sensitive.
- Discrepancy Theory: For dimensions $d > 1$, they utilized discrepancy-based methods to select points that "balance out" approximation errors across different geometric shapes, such as Euclidean balls.
- Quadratic Approximation: To establish lower bounds, the authors proved that for $k \ge 2$, the cost function behaves like a piecewise quadratic function. Using Taylor expansion arguments, they showed that a minimum number of "pieces" (points) is mathematically required to approximate this curvature linearly with low error.
Key Results and the $k=1$ vs. $k=2$ Separation
The most striking discovery is the "strong separation" in 1D. For a single cluster ($k=1$), the cost function is relatively simple and convex, allowing for a very small coreset of size $\tilde{O}(\epsilon^{-1/2})$. However, as soon as a second center is added ($k=2$), the cost function gains curvature, forcing the coreset size up to $\Omega(\epsilon^{-1})$. This marks the first time such a separation has been proven in any dimension.
As shown in the table above, the authors' results settle several long-standing questions. Notably, for small $d$, the coreset size scales with $\sqrt{d}/\epsilon$, which is significantly more efficient than the standard $1/\epsilon^2$ bounds used in high dimensions, until $d$ increases toward $1/\epsilon^2$.
Conclusion
This work provides a definitive answer for 1D coreset sizes and significantly narrows the gaps for low-dimensional Euclidean spaces. While the 1D case is resolved, challenges remain for $d \ge 2$, where the gap between the $\tilde{O}(\sqrt{d}/\epsilon)$ upper bound and the $\Omega(1/\sqrt{\epsilon})$ lower bound persists. Future research may also extend these insights to $(k, z)$-clustering, such as $k$-Means, where higher-order polynomial cost functions present additional complexity.
Summary updated