Questions tagged [epsilon-nets]
The epsilon-nets tag has no usage guidance.
4 questions with no upvoted or accepted answers
4
votes
0
answers
266
views
Open problems on epsilon nets
What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?
- 41
1
vote
0
answers
266
views
Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices
I found an algorithm for constructing an $\epsilon$-net for a positive semidefine matrix $A\in[-1,1]^{n\times n}$ which has $rank(A)=d$, described in the paper
The approximate rank of a matrix and ...
- 161
1
vote
0
answers
149
views
Hitting sets for sets of VC dimension d
Let $S$ be a collection of sets of binary vectors (in $\{0,1\}^m$) $S_1, S_2, \dotsc, S_t$ (say $t = O(m^d)$) each of VC dimension $d$. What can be said about the size of a hitting set $S_\text{hit}$ ...
- 11
0
votes
0
answers
19
views
Is there any relation between the size of optimal $\epsilon$-nets and the sample complexity for getting one through IID samples?
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$-...
- 716