Size-sensitive Packing Number for the Hamming Cube and its Consequences

An abstract set system, or hypergraph, consists of a universe (here assumed finite), together with a subset of its power set. A set-system is $\delta$-separated if any pair of its constituent subsets have symmetric difference at least $\delta$. In 1992, Haussler proved an optimal upper bound on the packing number for $\delta$-separated set systems having bounded primal shatter dimension. A set system with bounded primal shatter dimension is said to have \emph{size-sensitive shattering constants} $d_1$ and $d_2$, if the number of distinct projections of the system on any subset of its universe having $m$ elements, is at most $O(m^{d_1}k^{d_2})$.

We prove a size-sensitive version of Haussler’s Packing lemma [Hau92] for set-systems with bounded primal shatter dimension, which have an additional size-sensitive property. This answers a question asked by Ezra [Ezr14]. As a consequence of this result we get an improvement on the discrepancy bounds for set systems with the above size sensitive property. Improved bound on the discrepancy for these special set systems also implies an improvement in the size of $(\nu, \alpha)$-samples (and relative $(\vareps,\delta)$-approximations) (joint work with Arijit Ghosh, Max-Planck-Institute, Saarbrücken).