The Power of Uniform Sampling for Coresets

We develop a new coreset framework which has many advantages comparing with the well- studied Feldman-Langberg framework [FL11] and the recent new framework by [CASS21b]. An important feature of our framework is that it relates a uniform-version shattering dimension of the ambient metric space with the existence of small coresets. While in [FL11], a weighted version of such dimension is required. Reasonable upper bounds of such weighted shattering dimension are often hard to prove or even do not exist. Based on our new framework, we construct coresets for multiple important problems. First, We use our framework to construct improved coresets for Barycenter. Secondly, we construct improved coresets for 1-Median in low-dimensional Euclidean space. Specially, we construct coresets of size Õ(ϵ^−1.5 ) in R^2 and coresets of size Õ(ϵ^−1.6 ) in R^3 .

• Algorithms and Theory