# Epsilon-approximations of set systems with finite VC-dimension

ECorollary 6.9 in A Guide to NIP theories by Pierre Simon proves the following

Theorem. For every positive integer $k$ and every positive real $\varepsilon$ there is an integer $n=n(k,\epsilon)$ such that any probability measure $\mu$ on a finite set system $(X,\Delta)$ with VC-dimension $\le k$ admits an $\varepsilon$-approximation of size $\le n$.

Recall that a finite set system is a pair $(X,\Delta)$ where $X$ is a finite set and $\Delta\subseteq{\mathcal P}(X)$. Given a probability measure $\mu$, an $\varepsilon$-approximation is a set $B\subseteq X$ such that

$$\left | \frac{|S \cap B|}{|B|} - \mu(S) \right | \leq \epsilon.$$

holds for every $S\in\Delta$.

Question I can prove the theorem if working with multi-sets (i.e. sets whose elements are counted with some finite multiplicity). As it is stated it may not be true. Suppose $X$ contains two points of mass $p_0<p_1$ with $\varepsilon<p_0$ and $2\varepsilon<p_1-p_0$ it seems there isn't any $\varepsilon$-approximations, no matter what size.

EDIT1: I just realize that the proof of the main theorem of Section 6 (the (q,q)-theorem) can be adapted to work with multi-sets. So it is not a major problem. Still, multi-sets make the proofs messier and I would like to know if they are really necessary.

EDIT2: I just realize that in an earlier version of A Guide to NIP theories Corollary 6.9 was stated with $\epsilon$-net for $\epsilon$-approximation. This version is correct. If one is not interest in good bounds, one can obtain an $\epsilon$-net from a multi-set just forgetting multiplicity. In the proof of the (q,q)-theorem only $\epsilon$-nets are used.

• You are right, but working with multisets is normally easier in these kinds of problems anyways. Many authors write "set" when they should have written "multiset". May 20 '15 at 1:52

The first one is finding S with measure greater than $1 - \epsilon$. Well, if the set $\{x_1,...,x_q\}$ is a multiset, then it's even easier to find a set which contains all these points.
The second one is in the end, finding the $S_1',...,S_N'$. Same thing: if there are repetitions, then it's even better.
I think that there's no way to avoid multisets in general (if $X$ is big enough and the measure is uniform enough, I think that with high probability you would get a set and not a multiset, but in general, that wouldn't be the case).
• Btw. in version 1 of Simon's article, Corollary 6.9 was stated for $\epsilon$-nets. This was correct and sufficient for the (q,q)-theorem. May 20 '15 at 11:03