Title :
Improving the sample complexity using global data
Author :
Mendelson, Shahar
Author_Institution :
Comput. Sci. Lab., Australian Nat. Univ., Canberra, ACT, Australia
fDate :
7/1/2002 12:00:00 AM
Abstract :
We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L2 spaces (e.g. log-covering numbers which are polynomial with exponent p<2). We present several examples of relevant classes which have a "small" fat-shattering dimension, and hence fit our setup, the most important of which are kernel machines
Keywords :
communication complexity; estimation theory; functions; information theory; learning (artificial intelligence); losses; polynomials; signal sampling; Glivenko-Cantelli classes; fat-shattering dimension; global data; improper learning problems; kernel machines; log-covering numbers; polynomial; proper learning problems; q-loss functions; sample complexity; small covering numbers; uniform convexity; Australia; Convergence; Extraterrestrial measurements; Kernel; Machine learning; Neural networks; Polynomials; Random variables; Statistics;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2002.1013137
