A Close Look to Margin Complexity and Related Parameters
Abstract
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.
Cite
Text
Kallweit and Simon. "A Close Look to Margin Complexity and Related Parameters." Proceedings of the 24th Annual Conference on Learning Theory, 2011.Markdown
[Kallweit and Simon. "A Close Look to Margin Complexity and Related Parameters." Proceedings of the 24th Annual Conference on Learning Theory, 2011.](https://mlanthology.org/colt/2011/kallweit2011colt-close/)BibTeX
@inproceedings{kallweit2011colt-close,
title = {{A Close Look to Margin Complexity and Related Parameters}},
author = {Kallweit, Michael and Simon, Hans Ulrich},
booktitle = {Proceedings of the 24th Annual Conference on Learning Theory},
year = {2011},
pages = {437-456},
volume = {19},
url = {https://mlanthology.org/colt/2011/kallweit2011colt-close/}
}