Mendelson, Shahar2015-12-131042-9832http://hdl.handle.net/1885/79787We investigate a new notion of embedding of subsets of {-1, 1}n in a given normed space, in a way which preserves the structure of the given set as a class of functions on {1, ..., n}. This notion is an extension of the margin parameter often used in Nonparametric Statistics. Our main result is that even when considering "small" subsets of {-1, 1}n, the vast majority of such sets do not embed in a better way than the entire cube in any normed space that satisfies a minor structural assumption.Keywords: Embedding with a Lipschitz Function; Local Theory of Normed Spaces; Margin; Random Sets200510.1002/rsa.200542015-12-11