Premium
Embedding with a Lipschitz function
Author(s) -
Mendelson Shahar
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20054
Subject(s) - embedding , struct , lipschitz continuity , extension (predicate logic) , mathematics , function space , converse , space (punctuation) , class (philosophy) , cube (algebra) , margin (machine learning) , function (biology) , discrete mathematics , set (abstract data type) , normed vector space , nonparametric statistics , pure mathematics , combinatorics , computer science , statistics , artificial intelligence , geometry , machine learning , evolutionary biology , biology , programming language , operating system
We 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005