On the Complexity of Binary Samples

Joel Ratsaby

Consider a class $\mH$ of binary functions $h:X\to \{-1,+1\}$ on a finite interval $X=[0, B]\subset \Real$. Define the {\em sample width} of $h$ on a finite subset (a sample) $S\s…