Discrepancy and $\epsilon$-Approximations for Bounded VC-Dimensions 


Emo Welzl (joint work with Jiri Matousek, Lorenz Wernisch)
Freie Universität Berlin
Institut für Informatik
Email: welzl@inf.fu-berlin.de
Report B 91-06
April 1991 

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-91-06.ps.gz
Let $(X,\RR)$ be a set system on an $n$-point set $X$. We investigate colorings $\chi:X\to\{-1,+1\}$, such that the sum of colors in each set $R \in \RR$ does not deviate too much from $0$. The largest value $| \sum_{x \in R} \chi(x)|$ over all $R \in \RR$ is the {\em discrepancy} of $\chi$ on ${\cal R}$. We also consider {$\eps$-ap\-prox\-i\-ma\-tions}: For $0 < \eps < 1$, a subset $A$ of $X$ is an {\em $\eps$-ap\-prox\-i\-ma\-tion} for $(X,\RR)$, if $|\, |A \cap R| / |A| - |R| / n \,| < \eps $ for all $R \in \RR$. Let $d$ be a fixed integer such that for any $Y\subseteq X$, the number of distinct sets of the form $R\cap Y$, $R\in\RR$ is bounded by $O(|Y|^d)$ (i.e., $(X,\RR)$ is an $n$-point range space with the {\em primal shatter function} $\pi_{\cal R}(m)$ bounded by $O(m^d)$). Then we prove that there is always a coloring with discrepancy bounded by $O(\pdiscub)$. We show that this implies that, for any $r$, there exists a {\em $(1/r)$-ap\-prox\-i\-ma\-tion} for $(X,{\cal R})$ of size $O(\paproub)$. This improves on a previous bound of $O(r^2\log r)$ due to Vapnik and Chervonenkis. If any subcollection of $m$ sets of $\RR$ partitions the points into at most $O(m^d)$ classes (i.e., the {\em dual shatter function} is bounded by $O(m^d)$), then we get a bound of $O(\ddiscub)$ for discrepancy and of $O(\daproub)$ for $(1/r)$-ap\-prox\-i\-ma\-tions. These bounds via the dual shatter function can be realized by deterministic polynomial time algorithms. All the bounds are tight upto polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.