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 $...
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 ...
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)
...
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)>\...
Top 50 recent answers are included
Related Tags
pr.probability × 231reference-request × 32
graph-theory × 27
ds.algorithms × 26
st.statistics × 23
co.combinatorics × 21
randomized-algorithms × 20
randomness × 18
it.information-theory × 16
chernoff-bound × 14
cc.complexity-theory × 13
markov-chains × 12
machine-learning × 10
random-walks × 10
lg.learning × 9
vc-dimension × 8
graph-algorithms × 6
random-graphs × 6
cr.crypto-security × 5
lower-bounds × 5
derandomization × 5
shannon-entropy × 5
sample-complexity × 5
stochastic-process × 5
linear-algebra × 4