0
$\begingroup$

A combinatorial $\epsilon$-net is defined as follows:

Let $(X, \mathcal{R})$ be a range space, and let $A \subseteq X$ be a finite subset of $X$. A set $N \subseteq A$ is a combinatorial $\varepsilon$-net for $A$ if $N$ has a nonempty intersection with every set $R \in \mathcal{R}$ such that $|R \cap A| \geq \varepsilon |A|$.

$$N \cap R \neq \emptyset \quad \text{for all} \quad R \in \mathcal{R} \quad \text{with} \quad |R \cap A| \geq \varepsilon |A|$$

A probabilistic $\epsilon$-net generalizes the combinatorial $\epsilon$-net by assuming a distribution on $X$.

Let $(X, \mathcal{R})$ be a range space, and let $D$ be a probability distribution on $X$. A set $N \subseteq X$ is an $\varepsilon$-net for $X$ with respect to $D$ if for any set $R \in \mathcal{R}$ such that $\Pr_D(R) \geq \varepsilon$, the set $R$ contains at least one point from $N$, i.e., $$ \forall R \in \mathcal{R}, \Pr_D(R) \geq \varepsilon \Rightarrow R \cap N \neq \emptyset. $$

Question: If there exist a combinatorial $\epsilon$-net for $(X, \mathcal{R})$ of size $N_{comb}$, then can I say something about the number of IID samples i need to get a probabilistic $\epsilon$-net for $(X, \mathcal{R})$?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.