The covering number in learning theory

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 Lm K 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 L K 1/2 may not be generated by a Mercer kernel.