The Power of Uniform Sampling for Coresets
Abstract
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 .
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 .
Research Areas
