A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
Esther E. Ezra · SIAM Journal on Computing · 2016
Let $(X,\EuScript{S})$ be a set system on an $n$-point set $X$. The discrepancy of $\EuScript{S}$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in \EuScript{S}$ and two-colorings $\chi$ on $X$. We consider the scenario where, for any subset $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$, the number of restrictions of the sets of $\EuScript{S}$ to $X'$ of size at most $k$ is only $O(m^{d_1} k^{d-d_1})$ for fixed integers $d > 0$ and $1 \le d_1 \le d$ (this generalizes the standard notion of bounded primal shatter dimension when $d_1 = d$). In this case we show that there exists a coloring $\chi$ with discrepancy bound $O^{*}(|S|^{1/2 - d_1/(2d)} n^{(d_1 - 1)/(2d)})$, for each $S \in \EuScript{S}$, where $O^{*}(\cdot)$ hides a polylogarithmic factor in $n$. This bound is tight up to a polylogarithmic factor [J. Matoušek, Discrete Comput. Geom., 13 (1995), pp. 593--601, Geometric Discrepancy, Algorithms Combin. 18, Springer-Verlag, Heidelberg, 1999], and the corresponding coloring $\chi$ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka [Proceedings of the 53 rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 61--67] for constructive discrepancy minimization. Our bound improves and generalizes the bounds obtained from the machinery of Har-Peled and Sharir [Discrete Comput. Geom, 45 (2011), pp. 462--496] (and the follow-up work in [M. Sharir and S. Zaban, Output-Sensitive Tools for Range Searching in Higher Dimensions, unpublished manuscript, 2011; available online from www.cs.tau.ac.il/thesis/thesis/zaban.pdf]) for points and halfspaces in $d$-space for $d \ge 3$. Last but not least, we show that our bound yields improved bounds for the size of relative $(\varepsilon, \delta)$-approximations for set systems of the above kind.