Let $A$ and $B$ be sets of real-valued functions on $X$. Are there any reasonably tight bounds on the VC-dimension of $A\cap B$ in terms of the VC-dimensions of $A$ and $B$?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ There are Van Der Vaart results on the set of sets constructed as intersection of the members of A&B but that's different. I expect that one cannot do better than the min of their VC dimensions. $\endgroup$– ABIMCommented Aug 8 at 13:37
-
$\begingroup$ If $A \subseteq B$, then the VC-dim is the min. $\endgroup$– mathworker21Commented Aug 8 at 18:04
-
$\begingroup$ What does that mean? You mean if $X\subset A\cap B$ then $VC(X)\le \min\{VC(A),VC(B)\}$ no? $\endgroup$– ABIMCommented Aug 8 at 21:14
-
1$\begingroup$ If they're linearly ordered by inclusion, then a tight upper bound is 2, do you need a proof for this? $\endgroup$– SaginusCommented Sep 25 at 11:12
Add a comment
|