2022 Developer Survey is open! Take survey.

New answers tagged

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 $...
user avatar
  • 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 ...
user avatar
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) ...
user avatar
  • 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)>\...
user avatar
  • 10k

Top 50 recent answers are included