Embedding with a Lipschitz function

Shahar Mendelson

doi:10.1002/rsa.20054

Embedding with a Lipschitz function

Shahar Mendelson^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We investigate a new notion of embedding of subsets of {-1, 1}ⁿ 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}ⁿ, 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 language	English
Pages (from-to)	25-45
Number of pages	21
Journal	Random Structures and Algorithms
Volume	27
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20054
Publication status	Published - Aug 2005

Access to Document

10.1002/rsa.20054

Cite this

@article{2b7d6f4a5be249eebe12034e379bc002,

title = "Embedding with a Lipschitz function",

abstract = "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.",

keywords = "Embedding with a Lipschitz Function, Local Theory of Normed Spaces, Margin, Random Sets",

author = "Shahar Mendelson",

year = "2005",

month = aug,

doi = "10.1002/rsa.20054",

language = "English",

volume = "27",

pages = "25--45",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley & Sons Ltd.",

number = "1",

}

TY - JOUR

T1 - Embedding with a Lipschitz function

AU - Mendelson, Shahar

PY - 2005/8

Y1 - 2005/8

N2 - 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.

AB - 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.

KW - Embedding with a Lipschitz Function

KW - Local Theory of Normed Spaces

KW - Margin

KW - Random Sets

UR - http://www.scopus.com/inward/record.url?scp=24144477489&partnerID=8YFLogxK

U2 - 10.1002/rsa.20054

DO - 10.1002/rsa.20054

M3 - Article

SN - 1042-9832

VL - 27

SP - 25

EP - 45

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Embedding with a Lipschitz function

Abstract

Access to Document

Other files and links

Fingerprint

Cite this