Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [epsilon-nets]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
1 vote
150 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
152 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
248 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
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
346 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
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