New answers tagged pr.probability
0
votes
Accepted
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
From the DKW inequality, it follows one can learn an arbitrary distribution over $\mathbb{R}$ (and in particular over $\{1,2,\dots,n\}$ to Kolmogorov distance* $\varepsilon$ with probability at least $...
- 4,331
3
votes
Accepted
How to find the size of an ϵ-net of a vector space?
Note that $\mathcal{W}_{\epsilon}$ is an epsilon-net in the parametrization space, which is just $p$-dimensional Euclidean space. (So there is no need to think about covering numbers in e.g. spaces of ...
- 46
0
votes
How to find the size of an ϵ-net of a vector space?
See, for example,
Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer:
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. IEEE Trans. Inf. Theory 63(8): 4838-4849 (2017)
...
- 10k
2
votes
Accepted
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Let us suppose that $H$ shatters some $k$ points $(x_i,y_i)$, $i\in[k]$.
That means that for all $b\in\{0,1\}^k$, there is an $f=f_b\in F$ such that $y_if(x_i)\le\gamma$ if $b_i=1$ and
$y_if(x_i)>\...
- 10k
Top 50 recent answers are included