Size sensitive packing number for Hamming cube and its consequences

الأصل · EN

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.