Embedding with a Lipschitz function

Shahar Mendelson*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    4 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)25-45
    Number of pages21
    JournalRandom Structures and Algorithms
    Issue number1
    Publication statusPublished - Aug 2005


    Dive into the research topics of 'Embedding with a Lipschitz function'. Together they form a unique fingerprint.

    Cite this