Questions tagged [epsilon-nets]
The epsilon-nets tag has no usage guidance.
10 questions
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
1
vote
2
answers
191
views
How to find the size of an ϵ-net of a vector space?
Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
- 113
2
votes
1
answer
170
views
Empirical Rademacher averages versus Hoeffdings bound
Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.
An upper-bound for ...
- 123
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
9
votes
1
answer
347
views
How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d?
An $\varepsilon$-net for a range space $(X,\mathcal{R})$ is a subset $N$ of $X$ such that $N\cap R$ is nonempty for all $R\in \mathcal{R}$ such that $|X\cap R| \ge \varepsilon |X|$.
Given a range ...
- 613
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
11
votes
1
answer
1k
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 9,910
7
votes
2
answers
275
views
Counting Metrics
Say that I have a set of $n$ points $N$, and am interested in metrics $d:N\times N \rightarrow \mathbb{R}$ over $N$. Let $M$ denote the set of all metrics over $N$.
Now let me define the distance ...
- 9,910
10
votes
2
answers
500
views
Consequences of lower bounds for $\epsilon$-nets on approximation
Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
- 2,633