Size sensitive packing number for Hamming cube and its consequences

Abstract

We prove a size-sensitive version of Haussler's Packing lemma~Haussler92spherepacking for set-systems with bounded primal shatter dimension, which have an additional size-sensitive property. This answers a question asked by Ezra~Ezra-sizesendisc-soda-14. We also partially address another point raised by Ezra regarding overcounting of sets in her chaining procedure. As a consequence of these improvements, we get an improvement on the size-sensitive discrepancy bounds for set systems with the above property. Improved bounds on the discrepancy for these special set systems also imply an improvement in the sizes of relative (, )-approximations and (, )-samples.

Tasks

Reproductions