Mendelson, Shahar2015-12-070018-9448http://hdl.handle.net/1885/27137We 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 numbersKeywords: Approximation theory; Convergence of numerical methods; Estimation; Polynomials; Probability; Regression analysis; Set theory; Learning problems; Information theory Fat-shattering dimension; Glivenko-Cantelli classes; Kernel machines; Learning sample complexity; Uniform convexity200210.1109/TIT.2002.10131372015-12-07