A Close Look to Margin Complexity and Related Parameters

Concept classes can canonically be represented by sign-matrices, i.e., by matrices with entries $1$ and $-1$. The question whether a sign-matrix (concept class) $A$ can be learned by a machine that performs large margin classification is closely related to the “margin complexity” associated with $A$. We consider several variants of margin complexity, reveal how they are related to each other, and we reveal how they are related to other notions of learning-theoretic relevance like SQ-dimension, CSQ-dimension, and the Forster bound.