Improving the sample complexity using global data
Shahar Mendelson · IEEE Transactions on Information Theory · 2002
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 L/sub 2/ 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.