6
$\begingroup$

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". ESA'09

Improve this question
$\endgroup$
7
$\begingroup$

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:

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

Jeff

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – Matteo
    Nov 1 '12 at 2:27
  • $\begingroup$ Also I'm not sure I understand what you mean by "one-dimensional case for sampling". $\endgroup$
    – Matteo
    Nov 1 '12 at 3:59
  • 1
    $\begingroup$ 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). $\endgroup$
    – Jeff Phillips
    Nov 9 '12 at 7:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeff Phillips
    Nov 9 '12 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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