The covering number in learning theory

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

203 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)739-767
Journal / PublicationJournal of Complexity
Volume18
Issue number3
Publication statusPublished - Sep 2002

Abstract

The covering number of a ball of a reproducing kernel Hilbert space as a subset of the continuous function space plays an important role in Learning Theory. We give estimates for this covering number by means of the regularity of the Mercer kernel K. For convolution type kernels K(x,t) = k(x - t) on [0, 1]n, we provide estimates depending on the decay of k, the Fourier transform of k. In particular, when k̂ decays exponentially, our estimate for this covering number is better than all the previous results and covers many important Mercer kernels. A counter example is presented to show that the eigenfunctions of the Hilbert-Schmidt operator LK associated with a Mercer kernel K may not be uniformly bounded. Hence some previous methods used for estimating the covering number in Learning Theory are not valid. We also provide an example of a Mercer kernel to show that L1/2K may not be generated by a Mercer kernel. © 2002 Elsevier Science (USA).

Research Area(s)

  • Covering number, Learning theory, Mercer kernel, Reproducing kernel Hilbert space

Citation Format(s)

The covering number in learning theory. / Zhou, Ding-Xuan.

In: Journal of Complexity, Vol. 18, No. 3, 09.2002, p. 739-767.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review