<p>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 <a href="http://sarielhp.org/p/01/cluster/" rel="nofollow noreferrer">here</a> </p>

<p>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 <a href="https://arxiv.org/abs/1612.00889" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 3.0
2017-05-01T21:33:41.123Z
2017-05-01T21:33:41.123Z
Dan Feldman
<p>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).</p>

<p>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$.</p>

<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.</p>

<p>As for characterization - we have many positive results (see the survey here: <a href="http://sarielhp.org/p/04/survey/">http://sarielhp.org/p/04/survey/</a>). We also have counter examples which are somewhat mysterious - <a href="http://sarielhp.org/p/02/2slab/">http://sarielhp.org/p/02/2slab/</a> (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:</p>

<p>(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.</p>

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

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

CC BY-SA 3.0
2015-05-30T19:05:58.603Z
2015-05-30T19:05:58.603Z
Sariel Har-Peled
<p>I am trying to understand the notion of <a href="http://en.wikipedia.org/wiki/Coreset" rel="nofollow">$\epsilon$-coreset</a> 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?  </p>

<p>Thanks,</p>

<approximation-algorithms><computational-geometry><sample-complexity>
Coreset and VC dimension
Ram
# Coreset and VC dimension

(Asked by: username_0 on 2015-05-29)

I am trying to understand the notion of [$\epsilon$-coreset](http://en.wikipedia.org/wiki/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,

**Tags:** approximation-algorithms, computational-geometry, sample-complexity


---

## 2 answers

### Answer by username_1 on 2017-05-01. Score: 3 | Accepted answer

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](http://sarielhp.org/p/01/cluster/)

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](https://arxiv.org/abs/1612.00889).


---

### Answer by username_2 on 2015-05-30. Score: 6

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.


---

