I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation sketch of the input data. However, for the later case we know a characterization i.e. if a range space has finite VC dimension, then it can be approximated by a small (constant) size sample. On the other hand, for the case of $\epsilon$-coreset (similar to the concept of VC dimension) is there any characterization known over the problems which can or cannot be sketched by a small size sample?



2 Answers 2


The answer of Har-Peled is mainly regarding problems where you wish to cover points by shapes (e.g. balls). A strong relation to eps-nets and hitting sets can be found e.g. in his paper here

For the case of e.g. sum or sum of squared distances to a shape or set of shapes (as PCA, linear regression or k-means) there is a generic reduction from eps-net to coreset using importance sampling. I tried to summarize it here.


Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, taking an $\epsilon$-net sample of a set of points in the plane, computing its smallest enclosing disk, results in a disk $D$ that contains $(1-\epsilon)$ fraction of the whole point set (or $(1-\epsilon)$ of the measure).

Coresets on the other hand, provide geometric guarantees. For example, for a point set $P$ in the plane, an $\epsilon$-coreset for smallest enclosing disk is a subset $S$, such that any disk $D$ that contains $S$, if you slightly expand it (formally, scale it up by a factor of $(1+\epsilon)$, the it must contain all the points of $P$.

The beauty of samples is that you can generate them without a priori knowing what you are going to use them for. Coresets on the other hand are application dependent - you need different algorithms to compute them depending on the function you are trying to capture.

As for characterization - we have many positive results (see the survey here: http://sarielhp.org/p/04/survey/). We also have counter examples which are somewhat mysterious - http://sarielhp.org/p/02/2slab/ (no coreset no cry [after working for months on trying to compute a coreset for this problem, I definitely wanted to cry]). The rule of thumb is that you are not going to have a coreset if:

(A) The underlying function change dramatically if you can remove a single point, and there are many such points (say, closest pair, or k-center clustering, etc). Solving such problems in linear time requires different techniques.

(B) Or putting (A) differently - the underlying function is not very stable if you move points around.

It is unlikely to have a better characterization without assuming something significantly stronger on the underlying function that one is trying to compute.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.