Covering numbers for real-valued function classes

P. L. Bartlett; S. R. Kulkarni; S. E. Posner

doi:10.1109/18.623181

Covering numbers for real-valued function classes

P. L. Bartlett, S. R. Kulkarni, S. E. Posner

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

39 Scopus citations

Abstract

We find tight upper and lower bounds on the growth rate for the covering numbers of functions of bounded variation in the ₁ metric in terms of all the relevant constants. We also find upper and lower bounds on covering numbers for general function classes over the family of ₁(dP) metrics in terms of a scale-sensitive combinatorial dimension of the function class.

Original language	English (US)
Pages (from-to)	1721-1724
Number of pages	4
Journal	IEEE Transactions on Information Theory
Volume	43
Issue number	5
DOIs	https://doi.org/10.1109/18.623181
State	Published - 1997

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Bounded variation
Covering numbers
Fat-shattering dimension
Metric entropy
Scale-sensitive dimension
VC dimension

Access to Document

10.1109/18.623181

Cite this

@article{8bdbd0b41dcf4ce88e3dadeceb9ca0f0,

title = "Covering numbers for real-valued function classes",

abstract = "We find tight upper and lower bounds on the growth rate for the covering numbers of functions of bounded variation in the 1 metric in terms of all the relevant constants. We also find upper and lower bounds on covering numbers for general function classes over the family of 1(dP) metrics in terms of a scale-sensitive combinatorial dimension of the function class.",

keywords = "Bounded variation, Covering numbers, Fat-shattering dimension, Metric entropy, Scale-sensitive dimension, VC dimension",

author = "Bartlett, {P. L.} and Kulkarni, {S. R.} and Posner, {S. E.}",

year = "1997",

doi = "10.1109/18.623181",

language = "English (US)",

volume = "43",

pages = "1721--1724",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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

number = "5",

}

TY - JOUR

T1 - Covering numbers for real-valued function classes

AU - Bartlett, P. L.

AU - Kulkarni, S. R.

AU - Posner, S. E.

PY - 1997

Y1 - 1997

N2 - We find tight upper and lower bounds on the growth rate for the covering numbers of functions of bounded variation in the 1 metric in terms of all the relevant constants. We also find upper and lower bounds on covering numbers for general function classes over the family of 1(dP) metrics in terms of a scale-sensitive combinatorial dimension of the function class.

AB - We find tight upper and lower bounds on the growth rate for the covering numbers of functions of bounded variation in the 1 metric in terms of all the relevant constants. We also find upper and lower bounds on covering numbers for general function classes over the family of 1(dP) metrics in terms of a scale-sensitive combinatorial dimension of the function class.

KW - Bounded variation

KW - Covering numbers

KW - Fat-shattering dimension

KW - Metric entropy

KW - Scale-sensitive dimension

KW - VC dimension

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

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

U2 - 10.1109/18.623181

DO - 10.1109/18.623181

M3 - Article

AN - SCOPUS:0031235711

SN - 0018-9448

VL - 43

SP - 1721

EP - 1724

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -

Covering numbers for real-valued function classes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this