2014/12/12 by Dutta, Kunal, Ghosh, Arijit
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1412.3922
We prove a size-sensitive version of Haussler's Packing lemma~\citeHaussler92spherepacking for set-systems with bounded primal shatter dimension, which have an additional \em size-sensitive property. This answers a question asked by Ezra~\citeEzra-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 \em relative (ε, δ)-approximations and (ν, α)-samples.