Covering numbers for real-valued function classes

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

Research output: Contribution to journalArticle

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

Original languageEnglish (US)
Pages (from-to)1721-1724
Number of pages4
JournalIEEE Transactions on Information Theory
Volume43
Issue number5
DOIs
StatePublished - Dec 1 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

Cite this