On the limitations of embedding methods

Shahar Mendelson

doi:10.1007/11503415_24

On the limitations of embedding methods

Shahar Mendelson^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Citations (Scopus)

Abstract

We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz image of a subset of H, unless the Lipschitz constant is very large. We apply this result to the case when H consists of linear functionals of norm at most one on a Hilbert space, and thus show that "most" classification problems can not be represented as a reasonable Lipschitz loss of a kernel class.

Original language	English
Title of host publication	Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
Publisher	Springer Verlag
Pages	353-365
Number of pages	13
ISBN (Print)	3540265562, 9783540265566
DOIs	https://doi.org/10.1007/11503415_24
Publication status	Published - 2005
Event	18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy Duration: 27 Jun 2005 → 30 Jun 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3559 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory
Country/Territory	Italy
City	Bertinoro
Period	27/06/05 → 30/06/05

Access to Document

10.1007/11503415_24

Cite this

@inproceedings{f61eec8f68e646c0b45a3b3aa0f3106b,

title = "On the limitations of embedding methods",

abstract = "We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz image of a subset of H, unless the Lipschitz constant is very large. We apply this result to the case when H consists of linear functionals of norm at most one on a Hilbert space, and thus show that {"}most{"} classification problems can not be represented as a reasonable Lipschitz loss of a kernel class.",

author = "Shahar Mendelson",

year = "2005",

doi = "10.1007/11503415_24",

language = "English",

isbn = "3540265562",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "353--365",

booktitle = "Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings",

address = "Germany",

note = "18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory ; Conference date: 27-06-2005 Through 30-06-2005",

}

Mendelson, S 2005, On the limitations of embedding methods. in Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3559 LNAI, Springer Verlag, pp. 353-365, 18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory, Bertinoro, Italy, 27/06/05. https://doi.org/10.1007/11503415_24

On the limitations of embedding methods. / Mendelson, Shahar.
Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings. Springer Verlag, 2005. p. 353-365 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3559 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the limitations of embedding methods

AU - Mendelson, Shahar

PY - 2005

Y1 - 2005

N2 - We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz image of a subset of H, unless the Lipschitz constant is very large. We apply this result to the case when H consists of linear functionals of norm at most one on a Hilbert space, and thus show that "most" classification problems can not be represented as a reasonable Lipschitz loss of a kernel class.

AB - We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz image of a subset of H, unless the Lipschitz constant is very large. We apply this result to the case when H consists of linear functionals of norm at most one on a Hilbert space, and thus show that "most" classification problems can not be represented as a reasonable Lipschitz loss of a kernel class.

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

U2 - 10.1007/11503415_24

DO - 10.1007/11503415_24

M3 - Conference contribution

AN - SCOPUS:26944468649

SN - 3540265562

SN - 9783540265566

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 353

EP - 365

BT - Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings

PB - Springer Verlag

T2 - 18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory

Y2 - 27 June 2005 through 30 June 2005

ER -

On the limitations of embedding methods

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this