<p>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) ?</p>

<p>Thanks</p>

CC BY-SA 3.0
2013-11-09T05:30:29.493Z
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?
Sariel Har-Peled
CC BY-SA 3.0
2013-11-09T19:22:40.547Z
@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?
Matteo
<co.combinatorics><cg.comp-geom><machine-learning><lg.learning><vc-dimension>
Different estimators for uniform convergence of means/averages to expectations
Matteo
# Different estimators for uniform convergence of means/averages to expectations

(Asked by: username_0 on 2013-11-08)

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) ?

Thanks

**Tags:** co.combinatorics, cg.comp-geom, machine-learning, lg.learning, vc-dimension

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  

---

## 0 answers

