Coreset and VC dimension

Question

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?

Thanks,

Answer 1

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.

Answer 2

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.