Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

Question

An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., for any $S \in \mathcal{S}$,

$$ \left| \frac{|S\cap X|}{|X|} - \frac{|S \cap P|}{|P|} \right| < \epsilon $$

The (combinatorial) discrepancy $\mathsf{disc}(\mathcal{S})$ of $\mathcal{S}$ on the other hand is the minimum of

$$ \max_{S \in \mathcal{S}} \left|\sum_{e \in S}{\chi(e)} \right| $$

over all colorings $\chi:X \rightarrow \{\pm 1\}$. You can think of this as coloring $X$ with blue and red so that each set is as balanced as possible; the discrepancy is the imbalance of the most imbalanced set in the most balanced coloring.

Finally, an $\epsilon$-net is a set $P \subseteq X$ such that every set $S$ of size $|S| \geq \epsilon |X|$ has non-empty intersection with $P$.

There is a close relationship between combinatorial discrepancy and $\epsilon$-samples. More precisely, if $\mathsf{disc}(\mathcal{S})<\frac\epsilon2 |X|$, taking either the red or the blue colored points, whichever set is smaller, gives an $\epsilon$-sample of size at most $|X|/2$. This construction can be repeated recursively. Thus upper bounds on discrepancy imply better size vs. error tradeoffs for $\epsilon$-samples.

The question is if small discrepancy also implies better size vs error tradeoffs for $\epsilon$-nets.

For example for set systems with finite VC-dimention we have discrepancy bound $O(\sqrt{|X|\log |X|})$. We can construct an $\epsilon$-net of size $O(\frac1\epsilon\log\frac1\epsilon)$. How much smaller $\epsilon$-nets can we get from better bounds for discrepancy?

Answer 1

First, and more obviously, an $\epsilon$-sample is an $\epsilon$-net.

Of course, the above observation gives usually very loose bounds for $\epsilon$-nets. The bound you mention at the end of our post relies not just on small discrepancy but also on VC-dimension itself, so the relationship is not so clear. Let me elaborate.

Let $s(\epsilon)$ be the size of the minimum $\epsilon$-sample for your system. As you mention this can be bounded in terms of discrepancy.

We call a restriction of $\mathcal{S}$ to $Y$ the set system $\mathcal{S}|_Y = \{S \cap Y: S \in \mathcal{S}\}$. Finally, the shatter function $\pi(s)$ is equal to the maximum number of distinct sets in any restriction $\mathcal{S}|_Y$ to a set $Y$ of size at most $|Y| \leq s$.

We can show that there exist $\epsilon$-nets of size at most $O(\frac{1}{\epsilon} \log \pi(s(\epsilon/2)))$. This goes as follows.

1. any set system of $m$ sets has an $\epsilon$-net of size $O(\frac{1}{\epsilon} \log m)$;

2. an $\epsilon/2$ net of an $\epsilon/2$-sample for $\mathcal{S}$ is an $\epsilon$-net for $\mathcal{S}$;

Let us instantiate this for $\mathcal{S}$ of constant VC-dimension. For such $\mathcal{S}$, $s(\epsilon) \leq \epsilon^{-2}\log \epsilon^{-1}$. Also, by the Sauer-Shelah lemma, for constant VC dimension $\mathcal{S}$, $\pi(s) = s^{O(1)}$. Plugging this into the bound we got above gives $O(\frac{1}{\epsilon}\log \frac{1}{\epsilon})$ for the size of an $\epsilon$-net.

As you see, the bound on the size of $\epsilon$-nets depends on $\pi$ and not just on the discrepancy. I am not sure if there are any tighter connections. There is a bound on $\pi$ in terms of discrepancy, but the bound is exponential in the discrepancy, so it's not terribly useful.

---

Finally a note: for $\mathcal{S}$ with VC-dimension $d$ we can show there exist $\epsilon$-samples of size $O(\epsilon^{-\frac{2d}{d+1}})$. This is because the discrepancy of such set system is bounded by $n^{\frac12 - \frac1{2d}}$. The reason why most older references state the loose bound of $\sqrt{n\log n}$ is that until the very recent work of Nikhil Bansal, there were no known polynomial time algorithms for constructing such low discrepancy colorings. Even now, the algorithm giving the loose bound is just a random coloring, so it's very simple and very efficient, and the loose bound makes practically no difference if your end goal is an $\epsilon$-net.