×

A note on different covering numbers in learning theory. (English) Zbl 1057.68044

Summary: The covering number of a set \(\mathcal F\) in the space of continuous functions on a compact set \(X\) plays an important role in learning theory. In this paper, we study the relation between this covering number and its discrete version, obtained by replacing \(X\) with a finite subset. We formally show that when \(\mathcal F\) is made of smooth functions, the discrete covering number is close to its continuous counterpart. In particular, we illustrate this result in the case that \(\mathcal F\) is a ball in a reproducing kernel Hilbert space.

MSC:

68Q32 Computational learning theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Ben-David, S.; Cesa-Bianchi, N.; Haussler, D., Scale-sensitive dimensions, uniform convergence, and learnability, J. Assoc. Comput. Mach., 44, 4, 615-631 (1997) · Zbl 0891.68086
[2] Aronszajn, N., Theory of reproducing kernels, Trans. Amer. Math. Soc., 686, 337-404 (1950) · Zbl 0037.20701
[3] Cucker, F.; Smale, S., On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39, 1, 1-49 (2002) · Zbl 0983.68162
[4] Devroye, L.; Lugosi, G., Combinatorial Methods in Density Estimation (2001), Springer: Springer Berlin · Zbl 0964.62025
[5] Evgeniou, T.; Pontil, M.; Poggio, T., Regularization networks and support vector machines, Adv. Comput. Math., 13, 1-50 (2000) · Zbl 0939.68098
[6] Hoeffding, W., Probability inequality for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[7] Kolmogorov, A.; Fomin, S., Introductory Real Analysis (1975), Dover: Dover New York
[8] Smale, S.; Zhou, D. X., Estimating the approximation error in learning theory, Anal. Appl., 1, 1-25 (2003)
[9] Vapnik, V. N., Estimation of Dependencies based on Empirical Data (1982), Springer: Springer Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.