In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the estimator used on the sample is the sample average. Is it possible to use a different estimator? Is it required that the estimator has some specific properties (I assume at least unbiasedness) ?


  • $\begingroup$ At least in computational geometry, a lot of the VC dimension stuff is used to compute a sample, find a consistent hypothesis with the sample, and claim how far it is from the real shape as far as the Hamming distance (integrated over the distribution). So your language does not quite describe this settings. No? $\endgroup$ – Sariel Har-Peled Nov 9 '13 at 5:30
  • $\begingroup$ @SarielHar-Peled, IMHO the core idea is that it is just a uniform law of large numbers. If you have an $\varepsilon$-approximation, then the proportion of points in the sample that belong to a range is close to the proportion in the original set, for all ranges. But what you're estimating is just a proportion, so I'm asking whether you could use other estimators than the sample average. This can be extended to pseudodimension for averages of real functions. Can I use a different estimator than $\frac{1}{n}\sum_{i=1}^n f(X_i)$, where $X_1,\dots,X_n$ are my sampled points? $\endgroup$ – Matteo Nov 9 '13 at 19:22

Your Answer

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

Browse other questions tagged or ask your own question.