Improving the sample complexity using global data

Shahar Mendelson

doi:10.1109/TIT.2002.1013137

Improving the sample complexity using global data

Shahar Mendelson^*

^*Corresponding author for this work

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

80 Citations (Scopus)

Abstract

We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L₂ spaces (e.g., log-covering numbers which are polynomial with exponent p < 2). We present several examples of relevant classes which have a "small" fat-shattering dimension, hence fit our setup, the most important of which are kernel machines.

Original language	English
Pages (from-to)	1977-1991
Number of pages	15
Journal	IEEE Transactions on Information Theory
Volume	48
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2002.1013137
Publication status	Published - Jul 2002

Access to Document

10.1109/TIT.2002.1013137

Cite this

@article{9040dbc598ad4457ae45520da884602c,

title = "Improving the sample complexity using global data",

abstract = "We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L2 spaces (e.g., log-covering numbers which are polynomial with exponent p < 2). We present several examples of relevant classes which have a {"}small{"} fat-shattering dimension, hence fit our setup, the most important of which are kernel machines.",

keywords = "Fat-shattering dimension, Glivenko-Cantelli classes, Kernel machines, Learning sample complexity, Uniform convexity",

author = "Shahar Mendelson",

year = "2002",

month = jul,

doi = "10.1109/TIT.2002.1013137",

language = "English",

volume = "48",

pages = "1977--1991",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Improving the sample complexity using global data

AU - Mendelson, Shahar

PY - 2002/7

Y1 - 2002/7

N2 - We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L2 spaces (e.g., log-covering numbers which are polynomial with exponent p < 2). We present several examples of relevant classes which have a "small" fat-shattering dimension, hence fit our setup, the most important of which are kernel machines.

AB - We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L2 spaces (e.g., log-covering numbers which are polynomial with exponent p < 2). We present several examples of relevant classes which have a "small" fat-shattering dimension, hence fit our setup, the most important of which are kernel machines.

KW - Fat-shattering dimension

KW - Glivenko-Cantelli classes

KW - Kernel machines

KW - Learning sample complexity

KW - Uniform convexity

UR - https://www.scopus.com/pages/publications/0036648803

U2 - 10.1109/TIT.2002.1013137

DO - 10.1109/TIT.2002.1013137

M3 - Article

SN - 0018-9448

VL - 48

SP - 1977

EP - 1991

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

ER -

Improving the sample complexity using global data

Abstract

Access to Document

Other files and links

Fingerprint

Cite this