<p>I discovered after this publication that there is older work by 
Dvoretzky-Kiefer-Wolfowitz in 1956 that looks specifically at this one-dimensional case for sampling.  There is also follow up by just Kiefer and Wolfowitz a year or two later that handles the (anchored) rectangle case.  </p>

<p>For these specific settings, there has been some much more refined work looking at the actual constants.  Here is a reference that might help: </p>

<ul>
<li>P. Massart, <a href="http://www.jstor.org/discover/10.2307/2244426?uid=3738016&amp;uid=2129&amp;uid=2&amp;uid=70&amp;uid=4&amp;sid=21101380033837" rel="nofollow">"The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality"</a>, 1990.</li>
</ul>

<p>I don't know off-hand any other work on the constants other than the 1-d or "anchored" rectangle cases</p>

<p>Jeff</p>

CC BY-SA 3.0
2012-11-01T02:27:52.267Z
Thank you for your answer Jeff. My understanding was that c should be a global constant, that is the same independently of the points and ranges. This I got from reading Theorem 14.4.4 from Alon and Spencer:"There is a constant c...". Now my reading of your answer suggests me that the 0.5 you find in your work was only the constant for the range space you defined in your work. Am I understanding this correctly?
Matteo
CC BY-SA 3.0
2012-11-01T03:59:44.557Z
Also I'm not sure I understand what you mean by "one-dimensional case for sampling".
Matteo
CC BY-SA 3.0
2012-11-09T07:32:22.673Z
Yes, there should be a universal constant c that holds independent of any range (as long as its VC-dimension is bounded) and any point set.  My experiments attempted to estimate this.  However, certain point sets will allow for a smaller constants (for instance points that lie approximately on a line, any convex range will look like intervals, and act like the VC-dimension is only 2).
Jeff Phillips
CC BY-SA 3.0
2012-11-09T07:35:03.947Z
By "one-dimensional case for sampling" I meant that this work referred to random sampling bounds.  There are other deterministic approaches.  In one dimension, sorting and taking $1/\epsilon$ evenly spaced points will yield an $\epsilon$-sample deterministically.  Here the constant is 1, and the dependence on $\epsilon$ is much better. More complicated results exist for other range spaces as well, but the constants are much less understood, and likely much worse.
Jeff Phillips
CC BY-SA 3.0
2012-11-01T00:26:01.837Z
2012-11-01T20:40:35.597Z
2012-11-01T20:40:35.597Z
Jeff Phillips
<p>Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\delta}\right)\right)$ points with replacement from $X$.</p>

<p>Löffler and Phillips [1] showed experimentally that the constant hidden in the Big-Oh notation is at most 0.5. 
I was wondering whether there is any known theoretical, rather than experimental, upper bound to this constant. </p>

<p>Thanks in advance for any reference</p>

<p>[1] Löffler, M and Phillips, J.M. "<a href="http://arxiv.org/abs/0812.2967" rel="nofollow">Shape fitting on point sets with probability distributions</a>". ESA'09</p>

<reference-request><cg.comp-geom><vc-dimension>
Hidden constant in eps-sample size computation
Matteo
# Hidden constant in eps-sample size computation

(Asked by: username_0 on 2012-10-31)

Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\delta}\right)\right)$ points with replacement from $X$.

Löffler and Phillips [1] showed experimentally that the constant hidden in the Big-Oh notation is at most 0.5.
I was wondering whether there is any known theoretical, rather than experimental, upper bound to this constant.

Thanks in advance for any reference

[1] Löffler, M and Phillips, J.M. "[Shape fitting on point sets with probability distributions](http://arxiv.org/abs/0812.2967)". ESA'09

**Tags:** reference-request, cg.comp-geom, vc-dimension


---

## 1 answers

### Answer by username_1 on 2012-11-01. Score: 7 | Accepted answer

I discovered after this publication that there is older work by
Dvoretzky-Kiefer-Wolfowitz in 1956 that looks specifically at this one-dimensional case for sampling. There is also follow up by just Kiefer and Wolfowitz a year or two later that handles the (anchored) rectangle case.

For these specific settings, there has been some much more refined work looking at the actual constants. Here is a reference that might help:

* P. Massart, ["The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality"](http://www.jstor.org/discover/10.2307/2244426?uid=3738016&uid=2129&uid=2&uid=70&uid=4&sid=21101380033837), 1990.

I don't know off-hand any other work on the constants other than the 1-d or "anchored" rectangle cases

Jeff

> **Comments:**
> **username_0**: Thank you for your answer Jeff. My understanding was that c should be a global constant, that is the same independently of the points and ranges. This I got from reading Theorem 14.4.4 from Alon and Spencer:"There is a constant c...". Now my reading of your answer suggests me that the 0.5 you find in your work was only the constant for the range space you defined in your work. Am I understanding this correctly?  
> **username_0**: Also I'm not sure I understand what you mean by "one-dimensional case for sampling".  
> **username_1**: Yes, there should be a universal constant c that holds independent of any range (as long as its VC-dimension is bounded) and any point set.  My experiments attempted to estimate this.  However, certain point sets will allow for a smaller constants (for instance points that lie approximately on a line, any convex range will look like intervals, and act like the VC-dimension is only 2).  
> **username_1**: By "one-dimensional case for sampling" I meant that this work referred to random sampling bounds.  There are other deterministic approaches.  In one dimension, sorting and taking $1/\epsilon$ evenly spaced points will yield an $\epsilon$-sample deterministically.  Here the constant is 1, and the dependence on $\epsilon$ is much better. More complicated results exist for other range spaces as well, but the constants are much less understood, and likely much worse.  

---

